非线性规划中的Frank-Wolfe算法基础题
字数 2540 2025-11-08 10:02:38

非线性规划中的Frank-Wolfe算法基础题

题目描述
考虑一个非线性规划问题，其中目标函数是光滑凸函数，约束条件为线性不等式。具体问题如下：
最小化 \(f(x) = (x_1 - 3)^2 + (x_2 - 4)^2\)
约束条件为：

\[\begin{aligned} x_1 + x_2 &\leq 5, \\ 2x_1 - x_2 &\leq 6, \\ x_1, x_2 &\geq 0. \end{aligned} \]

要求使用Frank-Wolfe算法（也称条件梯度法）求解该问题，从初始点 \(x^{(0)} = (0, 0)\) 开始，进行两次迭代。

解题过程
Frank-Wolfe算法适用于目标函数凸、约束集为凸且紧（有界闭集）的优化问题。其核心思想是在每步迭代中，将目标函数线性化，在可行域上求解线性规划子问题，得到下降方向，再沿该方向进行一维搜索。

步骤1: 初始化

  • 初始点 \(x^{(0)} = (0, 0)\)，迭代计数器 \(k = 0\)。
  • 设定收敛容忍度（本例中仅演示两次迭代，暂不涉及收敛判断）。

步骤2: 第一次迭代（k=0）

  1. 计算梯度：目标函数梯度 \(\nabla f(x) = [2(x_1 - 3), 2(x_2 - 4)]\)。在 \(x^{(0)} = (0, 0)\) 处，梯度为 \(\nabla f(x^{(0)}) = (-6, -8)\)。
  2. 求解线性规划子问题：在可行域上最小化线性函数 \(\nabla f(x^{(0)})^T s = -6s_1 - 8s_2\)。该线性规划问题为：

\[ \begin{aligned} \min_{s} &\quad -6s_1 - 8s_2 \\ \text{s.t.} &\quad s_1 + s_2 \leq 5, \\ &\quad 2s_1 - s_2 \leq 6, \\ &\quad s_1, s_2 \geq 0. \end{aligned} \]

由于目标函数系数全为负，最大值出现在可行域极点。通过枚举极点（如 (0,0)、(5,0)、(3,0)、(11/3, 4/3) 等），代入目标函数比较，得最优解 \(s^{(0)} = (5, 0)\)（对应目标值 -30，最小）。
3. 确定下降方向：方向 \(d^{(0)} = s^{(0)} - x^{(0)} = (5, 0) - (0, 0) = (5, 0)\)。
4. 一维搜索：沿射线 \(x^{(0)} + \alpha d^{(0)} = (5\alpha, 0)\)（\(\alpha \in [0, 1]\)）最小化 \(f(x)\)。代入目标函数：

\[ f(5\alpha, 0) = (5\alpha - 3)^2 + (0 - 4)^2 = 25\alpha^2 - 30\alpha + 25. \]

这是关于 \(\alpha\) 的二次函数，导数 \(50\alpha - 30 = 0\) 得 \(\alpha = 0.6\)。由于 \(\alpha \in [0,1]\)，取步长 \(\alpha_0 = 0.6\)。
5. 更新迭代点：\(x^{(1)} = x^{(0)} + \alpha_0 d^{(0)} = (0, 0) + 0.6 \times (5, 0) = (3, 0)\)。

步骤3: 第二次迭代（k=1）

  1. 计算梯度：在 \(x^{(1)} = (3, 0)\) 处，梯度 \(\nabla f(x^{(1)}) = (2(3-3), 2(0-4)) = (0, -8)\)。
  2. 求解线性规划子问题：最小化 \(\nabla f(x^{(1)})^T s = 0 \cdot s_1 - 8s_2\)。等价于最小化 \(-8s_2\)，即最大化 \(s_2\)。在约束下，当 \(s_1 = 0, s_2 = 5\) 时（满足 \(s_1 + s_2 \leq 5\)，其他约束自动满足），\(s_2\) 最大。故 \(s^{(1)} = (0, 5)\)。
  3. 确定下降方向：\(d^{(1)} = s^{(1)} - x^{(1)} = (0, 5) - (3, 0) = (-3, 5)\)。
  4. 一维搜索：沿 \(x^{(1)} + \alpha d^{(1)} = (3 - 3\alpha, 5\alpha)\) 最小化 \(f(x)\)：

\[ f(3-3\alpha, 5\alpha) = ((3-3\alpha) - 3)^2 + (5\alpha - 4)^2 = 9\alpha^2 + (5\alpha - 4)^2 = 34\alpha^2 - 40\alpha + 16. \]

对 \(\alpha\) 求导：\(68\alpha - 40 = 0\)，得 \(\alpha = 40/68 \approx 0.5882\)。检查可行性：代入约束，例如 \((3-3\alpha) + 5\alpha = 3 + 2\alpha \leq 5\) 要求 \(\alpha \leq 1\)，成立。故步长 \(\alpha_1 \approx 0.5882\)。
5. 更新迭代点：\(x^{(2)} = (3, 0) + 0.5882 \times (-3, 5) \approx (1.2354, 2.9410)\).

步骤4: 结果分析
两次迭代后，解从 (0,0) 经 (3,0) 更新至约 (1.235, 2.941)。目标函数值从 \(f(0,0)=25\) 降至 \(f(3,0)=16\)，再降至约 10.88。继续迭代将逼近理论最优解（本例中为约束交点 (1,4)，f=4）。Frank-Wolfe算法通过线性子问题生成可行方向，适合线性约束的凸优化。

非线性规划中的Frank-Wolfe算法基础题 题目描述 考虑一个非线性规划问题，其中目标函数是光滑凸函数，约束条件为线性不等式。具体问题如下： 最小化 \( f(x) = (x_ 1 - 3)^2 + (x_ 2 - 4)^2 \) 约束条件为： \[ \begin{aligned} x_ 1 + x_ 2 &\leq 5, \\ 2x_ 1 - x_ 2 &\leq 6, \\ x_ 1, x_ 2 &\geq 0. \end{aligned} \] 要求使用Frank-Wolfe算法（也称条件梯度法）求解该问题，从初始点 \( x^{(0)} = (0, 0) \) 开始，进行两次迭代。 解题过程 Frank-Wolfe算法适用于目标函数凸、约束集为凸且紧（有界闭集）的优化问题。其核心思想是在每步迭代中，将目标函数线性化，在可行域上求解线性规划子问题，得到下降方向，再沿该方向进行一维搜索。 步骤1: 初始化 初始点 \( x^{(0)} = (0, 0) \)，迭代计数器 \( k = 0 \)。 设定收敛容忍度（本例中仅演示两次迭代，暂不涉及收敛判断）。 步骤2: 第一次迭代（k=0） 计算梯度 ：目标函数梯度 \( \nabla f(x) = [ 2(x_ 1 - 3), 2(x_ 2 - 4) ] \)。在 \( x^{(0)} = (0, 0) \) 处，梯度为 \( \nabla f(x^{(0)}) = (-6, -8) \)。 求解线性规划子问题 ：在可行域上最小化线性函数 \( \nabla f(x^{(0)})^T s = -6s_ 1 - 8s_ 2 \)。该线性规划问题为： \[ \begin{aligned} \min_ {s} &\quad -6s_ 1 - 8s_ 2 \\ \text{s.t.} &\quad s_ 1 + s_ 2 \leq 5, \\ &\quad 2s_ 1 - s_ 2 \leq 6, \\ &\quad s_ 1, s_ 2 \geq 0. \end{aligned} \] 由于目标函数系数全为负，最大值出现在可行域极点。通过枚举极点（如 (0,0)、(5,0)、(3,0)、(11/3, 4/3) 等），代入目标函数比较，得最优解 \( s^{(0)} = (5, 0) \)（对应目标值 -30，最小）。 确定下降方向 ：方向 \( d^{(0)} = s^{(0)} - x^{(0)} = (5, 0) - (0, 0) = (5, 0) \)。 一维搜索 ：沿射线 \( x^{(0)} + \alpha d^{(0)} = (5\alpha, 0) \)（\( \alpha \in [ 0, 1 ] \)）最小化 \( f(x) \)。代入目标函数： \[ f(5\alpha, 0) = (5\alpha - 3)^2 + (0 - 4)^2 = 25\alpha^2 - 30\alpha + 25. \] 这是关于 \( \alpha \) 的二次函数，导数 \( 50\alpha - 30 = 0 \) 得 \( \alpha = 0.6 \)。由于 \( \alpha \in [ 0,1] \)，取步长 \( \alpha_ 0 = 0.6 \)。 更新迭代点 ：\( x^{(1)} = x^{(0)} + \alpha_ 0 d^{(0)} = (0, 0) + 0.6 \times (5, 0) = (3, 0) \)。 步骤3: 第二次迭代（k=1） 计算梯度 ：在 \( x^{(1)} = (3, 0) \) 处，梯度 \( \nabla f(x^{(1)}) = (2(3-3), 2(0-4)) = (0, -8) \)。 求解线性规划子问题 ：最小化 \( \nabla f(x^{(1)})^T s = 0 \cdot s_ 1 - 8s_ 2 \)。等价于最小化 \( -8s_ 2 \)，即最大化 \( s_ 2 \)。在约束下，当 \( s_ 1 = 0, s_ 2 = 5 \) 时（满足 \( s_ 1 + s_ 2 \leq 5 \)，其他约束自动满足），\( s_ 2 \) 最大。故 \( s^{(1)} = (0, 5) \)。 确定下降方向 ：\( d^{(1)} = s^{(1)} - x^{(1)} = (0, 5) - (3, 0) = (-3, 5) \)。 一维搜索 ：沿 \( x^{(1)} + \alpha d^{(1)} = (3 - 3\alpha, 5\alpha) \) 最小化 \( f(x) \)： \[ f(3-3\alpha, 5\alpha) = ((3-3\alpha) - 3)^2 + (5\alpha - 4)^2 = 9\alpha^2 + (5\alpha - 4)^2 = 34\alpha^2 - 40\alpha + 16. \] 对 \( \alpha \) 求导：\( 68\alpha - 40 = 0 \)，得 \( \alpha = 40/68 \approx 0.5882 \)。检查可行性：代入约束，例如 \( (3-3\alpha) + 5\alpha = 3 + 2\alpha \leq 5 \) 要求 \( \alpha \leq 1 \)，成立。故步长 \( \alpha_ 1 \approx 0.5882 \)。 更新迭代点 ：\( x^{(2)} = (3, 0) + 0.5882 \times (-3, 5) \approx (1.2354, 2.9410) \). 步骤4: 结果分析 两次迭代后，解从 (0,0) 经 (3,0) 更新至约 (1.235, 2.941)。目标函数值从 \( f(0,0)=25 \) 降至 \( f(3,0)=16 \)，再降至约 10.88。继续迭代将逼近理论最优解（本例中为约束交点 (1,4)，f=4）。Frank-Wolfe算法通过线性子问题生成可行方向，适合线性约束的凸优化。