非线性规划中的Frank-Wolfe条件梯度法基础题 题目描述 考虑有约束非线性规划问题： minimize f(x) = (x₁ - 3)² + (x₂ - 4)² subject to x₁ + x₂ ≤ 5, x₁ ≥ 0, x₂ ≥ 0 其中目标函数f(x)是凸二次函数，约束为线性不等式。要求使用Frank-Wolfe条件梯度法求解该问题，从初始点x⁽⁰⁾ = (0, 0)开始，进行两次迭代，并分析每次迭代的搜索方向、步长选择和收敛性。 解题过程 Frank-Wolfe法适用于线性约束的凸优化问题。其核心思想是：在每次迭代中，将目标函数在当前点处线性化，通过求解线性规划子问题确定搜索方向，再沿该方向进行一维搜索。 1. 算法原理回顾 步骤1 ：在当前点x⁽ᵏ⁾计算梯度∇f(x⁽ᵏ⁾) 步骤2 ：求解线性规划子问题得到可行点s⁽ᵏ⁾： minimize ⟨∇f(x⁽ᵏ⁾), s⟩ subject to s ∈ 可行域 步骤3 ：计算搜索方向d⁽ᵏ⁾ = s⁽ᵏ⁾ - x⁽ᵏ⁾ 步骤4 ：通过一维搜索确定步长αₖ ∈ [ 0,1 ]： minimize f(x⁽ᵏ⁾ + αd⁽ᵏ⁾) 步骤5 ：更新迭代点x⁽ᵏ⁺¹⁾ = x⁽ᵏ⁾ + αₖd⁽ᵏ⁾ 2. 第一次迭代（k=0） 初始点 ：x⁽⁰⁾ = (0, 0) 梯度计算 ： ∇f(x) = [ 2(x₁ - 3), 2(x₂ - 4) ] ∇f(x⁽⁰⁾) = [ -6, -8 ] 线性规划子问题 ： 目标：minimize -6s₁ - 8s₂ 约束：s₁ + s₂ ≤ 5, s₁ ≥ 0, s₂ ≥ 0 分析梯度方向：由于梯度分量为负，目标函数值在s₁和s₂增大时减小。但需满足s₁ + s₂ ≤ 5。通过枚举顶点： 顶点(0,0)：目标值=0 顶点(5,0)：目标值=-30 顶点(0,5)：目标值=-40 最优解s⁽⁰⁾ = (0, 5)（目标值最小） 搜索方向 ：d⁽⁰⁾ = s⁽⁰⁾ - x⁽⁰⁾ = (0, 5) - (0, 0) = (0, 5) 一维搜索 ： 令φ(α) = f(x⁽⁰⁾ + αd⁽⁰⁾) = f(0, 5α) = (0 - 3)² + (5α - 4)² = 9 + (5α - 4)² 求导φ'(α) = 2(5α - 4)×5 = 50α - 40 令导数为0得α₀ = 0.8（在[ 0,1 ]范围内） 更新点 ：x⁽¹⁾ = (0, 0) + 0.8×(0, 5) = (0, 4) 此时目标函数值f(x⁽¹⁾) = (0-3)² + (4-4)² = 9 3. 第二次迭代（k=1） 当前点 ：x⁽¹⁾ = (0, 4) 梯度计算 ：∇f(x⁽¹⁾) = [ 2(0-3), 2(4-4)] = [ -6, 0 ] 线性规划子问题 ： 目标：minimize -6s₁ + 0·s₂ 约束：s₁ + s₂ ≤ 5, s₁ ≥ 0, s₂ ≥ 0 分析：目标函数仅与s₁有关，且系数为负。为使目标最小化，应取s₁尽可能大。 考虑约束s₁ + s₂ ≤ 5，最大s₁=5（此时s₂=0） 最优解s⁽¹⁾ = (5, 0) 搜索方向 ：d⁽¹⁾ = (5, 0) - (0, 4) = (5, -4) 一维搜索 ： 令φ(α) = f(x⁽¹⁾ + αd⁽¹⁾) = f(5α, 4 - 4α) = (5α - 3)² + (4 - 4α - 4)² = (5α - 3)² + (-4α)² = 25α² - 30α + 9 + 16α² = 41α² - 30α + 9 求导φ'(α) = 82α - 30，令其为0得α₁ = 30/82 ≈ 0.3659 更新点 ：x⁽²⁾ = (0, 4) + 0.3659×(5, -4) ≈ (1.829, 2.536) 目标函数值f(x⁽²⁾) ≈ (1.829-3)² + (2.536-4)² ≈ 4.92 4. 收敛性分析 问题的最优解为x* = (3, 2)（无约束最优解(3,4)投影到可行域），f(x* ) = 0。 经过两次迭代，点x⁽²⁾从(0,0)移动到(1.829,2.536)，目标值从25降至4.92，说明算法向最优解靠近。 Frank-Wolfe法的收敛速度通常为线性，因为搜索方向可能趋近正交于梯度（"锯齿现象"）。本例中第二次迭代的方向(5,-4)与梯度(-6,0)不完全对齐，体现了这一特性。