非线性规划中的Frank-Wolfe算法基础题
字数 2408 2025-11-09 19:43:49

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

题目描述
考虑如下非线性规划问题：

\[\min f(x) = (x_1 - 2)^2 + (x_2 - 3)^2 \]

约束条件为：

\[x_1 + x_2 \leq 4, \quad x_1 \geq 0, \quad x_2 \geq 0 \]

其中目标函数 \(f(x)\) 是凸二次函数，约束为线性不等式。要求使用 Frank-Wolfe算法（也称条件梯度法）求解该问题，并详细解释每一步的推导和计算过程。

解题过程
Frank-Wolfe算法适用于约束为凸集、目标函数可微的凸优化问题。其核心思想是：在每次迭代中，将目标函数线性化（即用一阶泰勒展开近似），然后在可行域上求解该线性规划子问题，得到搜索方向，最后沿该方向进行一维搜索确定步长。

步骤1: 算法初始化

  • 选择一个初始可行点 \(x^0\)，需满足所有约束。例如，取可行域内一点 \(x^0 = (0, 0)\)。
  • 设定收敛容差 \(\epsilon = 10^{-3}\)，最大迭代次数 \(K=100\)。

步骤2: 迭代过程（以第 \(k\) 次迭代为例）
设当前迭代点为 \(x^k = (x_1^k, x_2^k)\)。

  1. 计算梯度：

\[ \nabla f(x^k) = \begin{pmatrix} 2(x_1^k - 2) \\ 2(x_2^k - 3) \end{pmatrix} \]

例如，若 \(x^k = (0,0)\)，则 \(\nabla f = (-4, -6)\)。

  1. 求解线性规划子问题：
    构造线性化目标函数：

\[ \min_{s \in D} \langle \nabla f(x^k), s \rangle \]

其中 \(D = \{s \in \mathbb{R}^2 : s_1 + s_2 \leq 4, s_1 \geq 0, s_2 \geq 0\}\) 是可行域。
该问题等价于在单纯形约束下最小化线性函数。由于梯度分量为负，最优解必在约束边界顶点取得。通过比较顶点目标值：

  • 顶点 \((0,0)\)：\(\langle (-4,-6), (0,0) \rangle = 0\)
  • 顶点 \((4,0)\)：\(-4 \cdot 4 + (-6) \cdot 0 = -16\)
  • 顶点 \((0,4)\)：\(-4 \cdot 0 + (-6) \cdot 4 = -24\)
    故最优解为 \(s^k = (0, 4)\)（函数值最小）。

  1. 确定搜索方向：
    方向向量 \(d^k = s^k - x^k\)。例如，若 \(x^k = (0,0)\)，则 \(d^k = (0,4) - (0,0) = (0,4)\)。

  2. 一维搜索（精确线搜索）：
    求解步长 \(\alpha_k \in [0,1]\) 以最小化：

\[ \phi(\alpha) = f(x^k + \alpha d^k) \]

代入 \(x^k = (0,0), d^k = (0,4)\)：

\[ \phi(\alpha) = (0 - 2)^2 + (4\alpha - 3)^2 = 4 + (4\alpha - 3)^2 \]

对 \(\alpha\) 求导并令导数为零：

\[ \frac{d\phi}{d\alpha} = 2(4\alpha - 3) \cdot 4 = 0 \implies \alpha = 0.75 \]

验证 \(\alpha=0.75 \in [0,1]\)，故取 \(\alpha_k = 0.75\)。

  1. 更新迭代点：

\[ x^{k+1} = x^k + \alpha_k d^k = (0,0) + 0.75 \cdot (0,4) = (0,3) \]

步骤3: 收敛判断

  • 计算 对偶间隙（duality gap）：

\[ \text{Gap} = |\langle \nabla f(x^k), x^k - s^k \rangle| \]

例如，对 \(x^k=(0,0)\)，\(\text{Gap} = |(-4,-6) \cdot (0-0, 0-4)| = |0 + 24| = 24\)。

  • 若 \(\text{Gap} < \epsilon\)，则停止；否则返回步骤2继续迭代。

步骤4: 后续迭代示例

  • 第二次迭代：
    • \(x^1 = (0,3)\)，梯度 \(\nabla f = (2(0-2), 2(3-3)) = (-4, 0)\)
    • 线性子问题：顶点 \((4,0)\) 对应值 \(-16\)（最小），故 \(s^1 = (4,0)\)
    • 方向 \(d^1 = (4,0) - (0,3) = (4,-3)\)
    • 线搜索：最小化 \(f((0,3) + \alpha(4,-3)) = (4\alpha-2)^2 + (3-3\alpha-3)^2 = (4\alpha-2)^2 + 9\alpha^2\)
      求导得 \(\alpha = 8/25 = 0.32\)
    • 更新 \(x^2 = (0,3) + 0.32 \cdot (4,-3) = (1.28, 2.04)\)
  • 重复直到对偶间隙小于 \(\epsilon\)。最终解接近理论最优解 \(x^*=(0.5,3.5)\)（由KKT条件验证）。

关键点说明

  1. 线性子问题求解：利用单纯形顶点性质，避免调用线性规划求解器。
  2. 步长选择：精确线搜索可加速收敛，也可采用固定小步长或Armijo条件。
  3. 收敛性：由于目标函数强凸，算法线性收敛。对偶间隙同时衡量最优性和可行性。

通过以上步骤，Frank-Wolfe算法将复杂非线性问题转化为序列线性规划问题，特别适用于线性约束的凸优化。

非线性规划中的Frank-Wolfe算法基础题 题目描述 考虑如下非线性规划问题： \[ \min f(x) = (x_ 1 - 2)^2 + (x_ 2 - 3)^2 \] 约束条件为： \[ x_ 1 + x_ 2 \leq 4, \quad x_ 1 \geq 0, \quad x_ 2 \geq 0 \] 其中目标函数 \(f(x)\) 是凸二次函数，约束为线性不等式。要求使用 Frank-Wolfe算法 （也称条件梯度法）求解该问题，并详细解释每一步的推导和计算过程。 解题过程 Frank-Wolfe算法适用于约束为凸集、目标函数可微的凸优化问题。其核心思想是：在每次迭代中，将目标函数线性化（即用一阶泰勒展开近似），然后在可行域上求解该线性规划子问题，得到搜索方向，最后沿该方向进行一维搜索确定步长。 步骤1: 算法初始化 选择一个初始可行点 \(x^0\)，需满足所有约束。例如，取可行域内一点 \(x^0 = (0, 0)\)。 设定收敛容差 \(\epsilon = 10^{-3}\)，最大迭代次数 \(K=100\)。 步骤2: 迭代过程（以第 \(k\) 次迭代为例） 设当前迭代点为 \(x^k = (x_ 1^k, x_ 2^k)\)。 计算梯度 ： \[ \nabla f(x^k) = \begin{pmatrix} 2(x_ 1^k - 2) \\ 2(x_ 2^k - 3) \end{pmatrix} \] 例如，若 \(x^k = (0,0)\)，则 \(\nabla f = (-4, -6)\)。 求解线性规划子问题 ： 构造线性化目标函数： \[ \min_ {s \in D} \langle \nabla f(x^k), s \rangle \] 其中 \(D = \{s \in \mathbb{R}^2 : s_ 1 + s_ 2 \leq 4, s_ 1 \geq 0, s_ 2 \geq 0\}\) 是可行域。 该问题等价于在单纯形约束下最小化线性函数。由于梯度分量为负，最优解必在约束边界顶点取得。通过比较顶点目标值： 顶点 \((0,0)\)：\(\langle (-4,-6), (0,0) \rangle = 0\) 顶点 \((4,0)\)：\(-4 \cdot 4 + (-6) \cdot 0 = -16\) 顶点 \((0,4)\)：\(-4 \cdot 0 + (-6) \cdot 4 = -24\) 故最优解为 \(s^k = (0, 4)\)（函数值最小）。 确定搜索方向 ： 方向向量 \(d^k = s^k - x^k\)。例如，若 \(x^k = (0,0)\)，则 \(d^k = (0,4) - (0,0) = (0,4)\)。 一维搜索（精确线搜索） ： 求解步长 \(\alpha_ k \in [ 0,1 ]\) 以最小化： \[ \phi(\alpha) = f(x^k + \alpha d^k) \] 代入 \(x^k = (0,0), d^k = (0,4)\)： \[ \phi(\alpha) = (0 - 2)^2 + (4\alpha - 3)^2 = 4 + (4\alpha - 3)^2 \] 对 \(\alpha\) 求导并令导数为零： \[ \frac{d\phi}{d\alpha} = 2(4\alpha - 3) \cdot 4 = 0 \implies \alpha = 0.75 \] 验证 \(\alpha=0.75 \in [ 0,1]\)，故取 \(\alpha_ k = 0.75\)。 更新迭代点 ： \[ x^{k+1} = x^k + \alpha_ k d^k = (0,0) + 0.75 \cdot (0,4) = (0,3) \] 步骤3: 收敛判断 计算 对偶间隙（duality gap） ： \[ \text{Gap} = |\langle \nabla f(x^k), x^k - s^k \rangle| \] 例如，对 \(x^k=(0,0)\)，\(\text{Gap} = |(-4,-6) \cdot (0-0, 0-4)| = |0 + 24| = 24\)。 若 \(\text{Gap} < \epsilon\)，则停止；否则返回步骤2继续迭代。 步骤4: 后续迭代示例 第二次迭代 ： \(x^1 = (0,3)\)，梯度 \(\nabla f = (2(0-2), 2(3-3)) = (-4, 0)\) 线性子问题：顶点 \((4,0)\) 对应值 \(-16\)（最小），故 \(s^1 = (4,0)\) 方向 \(d^1 = (4,0) - (0,3) = (4,-3)\) 线搜索：最小化 \(f((0,3) + \alpha(4,-3)) = (4\alpha-2)^2 + (3-3\alpha-3)^2 = (4\alpha-2)^2 + 9\alpha^2\) 求导得 \(\alpha = 8/25 = 0.32\) 更新 \(x^2 = (0,3) + 0.32 \cdot (4,-3) = (1.28, 2.04)\) 重复直到对偶间隙小于 \(\epsilon\)。最终解接近理论最优解 \(x^* =(0.5,3.5)\)（由KKT条件验证）。 关键点说明 线性子问题求解 ：利用单纯形顶点性质，避免调用线性规划求解器。 步长选择 ：精确线搜索可加速收敛，也可采用固定小步长或Armijo条件。 收敛性 ：由于目标函数强凸，算法线性收敛。对偶间隙同时衡量最优性和可行性。 通过以上步骤，Frank-Wolfe算法将复杂非线性问题转化为序列线性规划问题，特别适用于线性约束的凸优化。