Frank-Wolfe算法进阶题

题目描述
考虑非线性规划问题：
minimize f(x) = (x₁ - 3)² + (x₂ - 4)²
subject to x₁ + x₂ ≤ 5, x₁ ≥ 0, x₂ ≥ 0
初始点 x⁽⁰⁾ = (0, 0)。要求使用Frank-Wolfe算法（条件梯度法）求解，并分析其收敛性。

解题过程
Frank-Wolfe算法适用于线性约束的凸优化问题，通过将目标函数线性化，在可行域上求解线性子问题来生成搜索方向。以下是详细步骤：

1. 算法原理

   • 问题需满足：f(x) 为凸函数，约束为线性（构成凸多面体可行域）。
   • 每步迭代：
     a. 在当前点 xᵏ 处线性化 f(x)，得到梯度 ∇f(xᵏ)。
     b. 求解线性规划子问题：minimize ∇f(xᵏ)ᵀ d，满足约束条件，得到方向点 sᵏ。
     c. 更新 xᵏ⁺¹ = xᵏ + αᵏ(sᵏ - xᵏ)，其中 αᵏ ∈ [0,1] 为步长（常取闭式解或线搜索）。

2. 初始化

   • 给定初始点 x⁽⁰⁾ = (0, 0)，设定容忍误差 ε = 10⁻⁶。
   • 目标函数梯度 ∇f(x) = [2(x₁ - 3), 2(x₂ - 4)]。

3. 第一次迭代 (k=0)

   • 计算梯度：∇f(x⁽⁰⁾) = [-6, -8]。
   • 线性子问题：minimize -6d₁ - 8d₂，约束为 d₁ + d₂ ≤ 5, d₁ ≥ 0, d₂ ≥ 0。
     • 梯度方向 (-6, -8) 使目标减小需最大化 d₁ 和 d₂。观察约束 d₁ + d₂ ≤ 5，最优解为 d* = (5, 0) 或 (0, 5)? 代入验证：
       • 若 d = (5,0)：目标值 = -30
       • 若 d = (0,5)：目标值 = -40（更小，更优）
       • 进一步检查边界：d = (5,0) 和 (0,5) 均为顶点，但 (0,5) 使目标更小。因此 s⁽⁰⁾ = (0, 5)。
   • 计算方向向量：s⁽⁰⁾ - x⁽⁰⁾ = (0, 5)。
   • 更新步长 α⁽⁰⁾：
     沿方向最小化 f(x⁽⁰⁾ + α(0, 5)) = (0 - 3)² + (5α - 4)² = 9 + (5α - 4)²。
     对 α 求导：10(5α - 4) = 0 → α = 0.8。由于 α ∈ [0,1]，取 α⁽⁰⁾ = 0.8。
   • 新点 x⁽¹⁾ = (0, 0) + 0.8 × (0, 5) = (0, 4)。

4. 第二次迭代 (k=1)

   • 梯度：∇f(x⁽¹⁾) = [2(0-3), 2(4-4)] = [-6, 0]。
   • 线性子问题：minimize -6d₁ + 0·d₂，约束同前。
     • 梯度分量为负时需增大 d₁，约束下最大 d₁ = 5（d₂ = 0），故 s⁽¹⁾ = (5, 0)。
   • 方向：s⁽¹⁾ - x⁽¹⁾ = (5, -4)。
   • 线搜索：最小化 f((0,4) + α(5, -4)) = (5α - 3)² + (4 - 4α - 4)² = (5α - 3)² + (-4α)²。
     化简为 25α² - 30α + 9 + 16α² = 41α² - 30α + 9。
     求导：82α - 30 = 0 → α = 30/82 ≈ 0.366。
   • 新点 x⁽²⁾ = (0, 4) + 0.366 × (5, -4) ≈ (1.83, 2.54)。

5. 收敛判断

   • Frank-Wolfe收敛条件：当 ∇f(xᵏ)ᵀ(xᵏ - sᵏ) ≤ ε 时停止（表示当前点与子问题最优解无显著改进）。
   • 在 x⁽²⁾ 处计算梯度 ∇f ≈ [-2.34, -2.92]，子问题目标为 min ∇fᵀd。
     需验证后续迭代是否满足条件，本题最优解为 x* = (3, 2)（满足 x₁ + x₂ = 5），初始点选择影响路径，但算法会收敛至最优。

关键点

• Frank-Wolfe适合线性约束问题，每步求解线性规划，避免投影操作。
• 步长可精确计算因目标函数为二次凸函数。
• 收敛速度通常为线性，依赖可行域几何性质。