非线性规划中的Frank-Wolfe算法基础题
题目描述
考虑非线性规划问题：
最小化 \(f(x) = x_1^2 + 2x_2^2 - 2x_1x_2 - 4x_1\)
约束条件为：
\(x_1 + x_2 \leq 2\)
\(x_1, x_2 \geq 0\)
初始点 \(x^{(0)} = (0, 0)\)，使用 Frank-Wolfe 算法（也称条件梯度法）求解该问题，要求进行两次迭代。
解题过程
Frank-Wolfe 算法适用于线性约束的非线性规划。其核心思想是：在每一步，用目标函数的一阶近似（线性化）在可行域上求解线性子问题，得到下降方向，再沿该方向线性搜索确定步长。
步骤 1：算法原理回顾
- 初始化：选择可行点 \(x^{(0)}\)，设 \(k = 0\)
- 求解线性子问题：计算梯度 \(\nabla f(x^{(k)})\)，求解
\[ \min_{s \in D} \nabla f(x^{(k)})^T s \]
得到解 \(s^{(k)}\)（称为条件梯度）
3. 确定步长：通过一维搜索
\[ \min_{0 \leq \lambda \leq 1} f(x^{(k)} + \lambda (s^{(k)} - x^{(k)})) \]
得到步长 \(\lambda_k\)，或直接设定 \(\lambda_k = \frac{2}{k+2}\)
4. 更新迭代点：
\[ x^{(k+1)} = x^{(k)} + \lambda_k (s^{(k)} - x^{(k)}) \]
- 重复直到收敛
步骤 2：第一次迭代（k=0）
初始点 \(x^{(0)} = (0, 0)\)
-
计算梯度：
\(\nabla f(x) = (2x_1 - 2x_2 - 4, 4x_2 - 2x_1)\)
代入 \(x^{(0)}\)：
\(\nabla f(x^{(0)}) = (-4, 0)\) -
求解线性子问题：
最小化 \(\nabla f(x^{(0)})^T s = -4s_1 + 0 \cdot s_2\)
约束：
\(s_1 + s_2 \leq 2\), \(s_1, s_2 \geq 0\)
由于目标函数只含 \(-4s_1\)，最小化需使 \(s_1\) 尽量大。约束下最大值在 \(s_1 = 2, s_2 = 0\)（可行域顶点）
故 \(s^{(0)} = (2, 0)\) -
确定步长（精确搜索）：
设 \(x(\lambda) = x^{(0)} + \lambda (s^{(0)} - x^{(0)}) = (2\lambda, 0)\)
\(f(x(\lambda)) = (2\lambda)^2 + 0 - 0 - 4(2\lambda) = 4\lambda^2 - 8\lambda\)
对 \(\lambda\) 求导：\(8\lambda - 8 = 0 \Rightarrow \lambda = 1\)（在 [0,1] 内）
故 \(\lambda_0 = 1\) -
更新迭代点：
\(x^{(1)} = (0,0) + 1 \cdot ((2,0) - (0,0)) = (2, 0)\)
步骤 3：第二次迭代（k=1）
当前点 \(x^{(1)} = (2, 0)\)
-
计算梯度：
\(\nabla f(x^{(1)}) = (2\cdot2 - 2\cdot0 - 4, 4\cdot0 - 2\cdot2) = (0, -4)\) -
求解线性子问题：
最小化 \(\nabla f(x^{(1)})^T s = 0\cdot s_1 - 4 s_2\)
约束同上。目标函数仅含 \(-4s_2\)，最小化需最大化 \(s_2\)。约束下最大值在 \(s_1 = 0, s_2 = 2\)
故 \(s^{(1)} = (0, 2)\) -
确定步长：
设 \(x(\lambda) = (2,0) + \lambda ((0,2) - (2,0)) = (2 - 2\lambda, 2\lambda)\)
代入目标函数：
\(f = (2-2\lambda)^2 + 2(2\lambda)^2 - 2(2-2\lambda)(2\lambda) - 4(2-2\lambda)\)
展开：
\(= 4 - 8\lambda + 4\lambda^2 + 8\lambda^2 - 2(4\lambda - 4\lambda^2) - 8 + 8\lambda\)
\(= 4 - 8\lambda + 4\lambda^2 + 8\lambda^2 - 8\lambda + 8\lambda^2 - 8 + 8\lambda\)
合并：\((4\lambda^2 + 8\lambda^2 + 8\lambda^2) = 20\lambda^2\)，常数项 \(4 - 8 = -4\)，一次项 \(-8\lambda -8\lambda + 8\lambda = -8\lambda\)
得 \(f(\lambda) = 20\lambda^2 - 8\lambda - 4\)
对 \(\lambda\) 求导：\(40\lambda - 8 = 0 \Rightarrow \lambda = 0.2\)（在 [0,1] 内）
故 \(\lambda_1 = 0.2\) -
更新迭代点：
\(x^{(2)} = (2,0) + 0.2 \cdot ((0,2) - (2,0)) = (2 - 0.4, 0 + 0.4) = (1.6, 0.4)\)
步骤 4：结果分析
两次迭代后得到 \(x^{(2)} = (1.6, 0.4)\)。
实际最优解可通过 KKT 条件验证：
梯度 \(\nabla f = (2x_1 - 2x_2 - 4, 4x_2 - 2x_1)\)
在约束 \(x_1 + x_2 = 2\) 的边界上求解，得最优解 \(x^* = (1.6, 0.4)\)，与第二次迭代结果一致。
Frank-Wolfe 算法在此例中两步收敛，因问题为凸二次规划，且最优解在可行域顶点连线边界上。