非线性规划中的Frank-Wolfe条件梯度法基础题
字数 2792 2025-12-02 14:51:05

非线性规划中的Frank-Wolfe条件梯度法基础题

题目描述
考虑一个非线性规划问题：
最小化 \(f(x) = (x_1 - 2)^2 + (x_2 - 3)^2\)
约束条件为 \(x_1 + x_2 \leq 4\)，\(x_1 \geq 0\)，\(x_2 \geq 0\)。
目标函数 \(f(x)\) 是凸二次函数，约束为线性不等式，构成一个凸可行域（多边形区域）。要求使用 Frank-Wolfe 条件梯度法求解该问题，从初始点 \(x^{(0)} = (0, 0)\) 开始，迭代两步，并分析收敛性。

解题过程
Frank-Wolfe 法适用于目标函数可微且约束为凸集的优化问题。其核心思想是：在每一步迭代中，将目标函数线性化（即用梯度近似），在可行域上求解该线性规划得到下降方向，再沿该方向进行一维搜索确定步长。

步骤1: 初始化及梯度计算

  • 初始点 \(x^{(0)} = (0, 0)\)，计算梯度 \(\nabla f(x) = [2(x_1 - 2), 2(x_2 - 3)]\)。
  • 在 \(x^{(0)}\) 处：\(\nabla f(x^{(0)}) = [2(0-2), 2(0-3)] = [-4, -6]\)。

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

  1. 求解线性规划子问题：

    • 目标：最小化 \(\nabla f(x^{(0)})^T s = [-4, -6]^T s\)（线性化目标），约束为 \(s_1 + s_2 \leq 4\)，\(s_1 \geq 0\)，\(s_2 \geq 0\)。
    • 该线性函数系数全为负，最小值在可行域中使 \(s_1\) 和 \(s_2\) 最大的点取得。约束 \(s_1 + s_2 \leq 4\) 的边界点 \(s = (4, 0)\) 或 \((0, 4)\) 需比较：
      • \(s = (4, 0)\)：函数值 \(-4 \times 4 + (-6) \times 0 = -16\)。
      • \(s = (0, 4)\)：函数值 \(-4 \times 0 + (-6) \times 4 = -24\)（更小）。
    • 因此，最优解 \(s^{(0)} = (0, 4)\)。
    • 下降方向 \(d^{(0)} = s^{(0)} - x^{(0)} = (0, 4) - (0, 0) = (0, 4)\)。

  2. 一维搜索确定步长 \(\alpha_0\)：

    • 沿方向 \(d^{(0)}\) 最小化 \(f(x^{(0)} + \alpha d^{(0)}) = f(0, 4\alpha) = (0-2)^2 + (4\alpha - 3)^2 = 4 + (4\alpha - 3)^2\)。
    • 对 \(\alpha\) 求导：\(\frac{d}{d\alpha} [4 + (4\alpha - 3)^2] = 2(4\alpha - 3) \times 4 = 32\alpha - 24\)。令导数为零得 \(\alpha_0 = 0.75\)。
    • 验证 \(\alpha_0 \in [0, 1]\)（确保新点在可行域内，因为凸组合保持可行性）。

  3. 更新迭代点：

    • \(x^{(1)} = x^{(0)} + \alpha_0 d^{(0)} = (0, 0) + 0.75 \times (0, 4) = (0, 3)\)。
    • 此时 \(f(x^{(1)}) = (0-2)^2 + (3-3)^2 = 4\)。

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

  1. 计算梯度：\(\nabla f(x^{(1)}) = [2(0-2), 2(3-3)] = [-4, 0]\)。

  2. 求解线性规划子问题：

    • 目标：最小化 \([-4, 0]^T s\)，约束同前。系数中 \(s_1\) 的系数为负，\(s_2\) 的系数为零，因此最小值在 \(s_1\) 最大且 \(s_2\) 任意满足约束的点。取 \(s_1 = 4\)，\(s_2 = 0\)（边界点），函数值 \(-4 \times 4 + 0 = -16\)。
    • 最优解 \(s^{(1)} = (4, 0)\)，下降方向 \(d^{(1)} = s^{(1)} - x^{(1)} = (4, 0) - (0, 3) = (4, -3)\)。

  3. 一维搜索确定步长 \(\alpha_1\)：

    • 最小化 \(f(x^{(1)} + \alpha d^{(1)}) = f(4\alpha, 3 - 3\alpha) = (4\alpha - 2)^2 + (3 - 3\alpha - 3)^2 = (4\alpha - 2)^2 + (-3\alpha)^2\)。
    • 简化：\(16\alpha^2 - 16\alpha + 4 + 9\alpha^2 = 25\alpha^2 - 16\alpha + 4\)。
    • 对 \(\alpha\) 求导：\(50\alpha - 16 = 0\) → \(\alpha_1 = 0.32\)。
    • 检查可行性：新点 \((1.28, 2.04)\) 满足 \(x_1 + x_2 = 3.32 \leq 4\)，且非负。

  4. 更新迭代点：

    • \(x^{(2)} = x^{(1)} + \alpha_1 d^{(1)} = (0, 3) + 0.32 \times (4, -3) = (1.28, 2.04)\)。
    • \(f(x^{(2)}) = (1.28-2)^2 + (2.04-3)^2 \approx 0.5184 + 0.9216 = 1.44\)。

步骤4: 收敛性分析

  • 理论保证：Frank-Wolfe 法在凸可微问题中收敛到全局最优解，但收敛速度较慢（通常为次线性收敛）。
  • 本问题的最优解在约束边界 \(x_1 + x_2 = 4\) 上，通过梯度投影可求得精确解为 \(x^* = (1.5, 2.5)\)，\(f(x^*) = 0.5\)。
  • 迭代两步后 \(x^{(2)}\) 接近最优解，后续迭代会继续沿边界逼近 \(x^*\)。
  • 特点：Frank-Wolfe 法每一步只需求解线性规划，适合约束结构简单（如多面体）的问题，但方向可能不是最优下降方向，尤其靠近解时进展缓慢。

通过以上步骤，Frank-Wolfe 法以简单子问题迭代求解非线性规划，体现了条件梯度法的基本思想。

非线性规划中的Frank-Wolfe条件梯度法基础题 题目描述 考虑一个非线性规划问题： 最小化 \( f(x) = (x_ 1 - 2)^2 + (x_ 2 - 3)^2 \) 约束条件为 \( x_ 1 + x_ 2 \leq 4 \)，\( x_ 1 \geq 0 \)，\( x_ 2 \geq 0 \)。 目标函数 \( f(x) \) 是凸二次函数，约束为线性不等式，构成一个凸可行域（多边形区域）。要求使用 Frank-Wolfe 条件梯度法求解该问题，从初始点 \( x^{(0)} = (0, 0) \) 开始，迭代两步，并分析收敛性。 解题过程 Frank-Wolfe 法适用于目标函数可微且约束为凸集的优化问题。其核心思想是：在每一步迭代中，将目标函数线性化（即用梯度近似），在可行域上求解该线性规划得到下降方向，再沿该方向进行一维搜索确定步长。 步骤1: 初始化及梯度计算 初始点 \( x^{(0)} = (0, 0) \)，计算梯度 \( \nabla f(x) = [ 2(x_ 1 - 2), 2(x_ 2 - 3) ] \)。 在 \( x^{(0)} \) 处：\( \nabla f(x^{(0)}) = [ 2(0-2), 2(0-3)] = [ -4, -6 ] \)。 步骤2: 第一次迭代（k=0） 求解线性规划子问题 ： 目标：最小化 \( \nabla f(x^{(0)})^T s = [ -4, -6]^T s \)（线性化目标），约束为 \( s_ 1 + s_ 2 \leq 4 \)，\( s_ 1 \geq 0 \)，\( s_ 2 \geq 0 \)。 该线性函数系数全为负，最小值在可行域中使 \( s_ 1 \) 和 \( s_ 2 \) 最大的点取得。约束 \( s_ 1 + s_ 2 \leq 4 \) 的边界点 \( s = (4, 0) \) 或 \( (0, 4) \) 需比较： \( s = (4, 0) \)：函数值 \( -4 \times 4 + (-6) \times 0 = -16 \)。 \( s = (0, 4) \)：函数值 \( -4 \times 0 + (-6) \times 4 = -24 \)（更小）。 因此，最优解 \( s^{(0)} = (0, 4) \)。 下降方向 \( d^{(0)} = s^{(0)} - x^{(0)} = (0, 4) - (0, 0) = (0, 4) \)。 一维搜索确定步长 \( \alpha_ 0 \)： 沿方向 \( d^{(0)} \) 最小化 \( f(x^{(0)} + \alpha d^{(0)}) = f(0, 4\alpha) = (0-2)^2 + (4\alpha - 3)^2 = 4 + (4\alpha - 3)^2 \)。 对 \( \alpha \) 求导：\( \frac{d}{d\alpha} [ 4 + (4\alpha - 3)^2] = 2(4\alpha - 3) \times 4 = 32\alpha - 24 \)。令导数为零得 \( \alpha_ 0 = 0.75 \)。 验证 \( \alpha_ 0 \in [ 0, 1 ] \)（确保新点在可行域内，因为凸组合保持可行性）。 更新迭代点 ： \( x^{(1)} = x^{(0)} + \alpha_ 0 d^{(0)} = (0, 0) + 0.75 \times (0, 4) = (0, 3) \)。 此时 \( f(x^{(1)}) = (0-2)^2 + (3-3)^2 = 4 \)。 步骤3: 第二次迭代（k=1） 计算梯度 ：\( \nabla f(x^{(1)}) = [ 2(0-2), 2(3-3)] = [ -4, 0 ] \)。 求解线性规划子问题 ： 目标：最小化 \( [ -4, 0]^T s \)，约束同前。系数中 \( s_ 1 \) 的系数为负，\( s_ 2 \) 的系数为零，因此最小值在 \( s_ 1 \) 最大且 \( s_ 2 \) 任意满足约束的点。取 \( s_ 1 = 4 \)，\( s_ 2 = 0 \)（边界点），函数值 \( -4 \times 4 + 0 = -16 \)。 最优解 \( s^{(1)} = (4, 0) \)，下降方向 \( d^{(1)} = s^{(1)} - x^{(1)} = (4, 0) - (0, 3) = (4, -3) \)。 一维搜索确定步长 \( \alpha_ 1 \)： 最小化 \( f(x^{(1)} + \alpha d^{(1)}) = f(4\alpha, 3 - 3\alpha) = (4\alpha - 2)^2 + (3 - 3\alpha - 3)^2 = (4\alpha - 2)^2 + (-3\alpha)^2 \)。 简化：\( 16\alpha^2 - 16\alpha + 4 + 9\alpha^2 = 25\alpha^2 - 16\alpha + 4 \)。 对 \( \alpha \) 求导：\( 50\alpha - 16 = 0 \) → \( \alpha_ 1 = 0.32 \)。 检查可行性：新点 \( (1.28, 2.04) \) 满足 \( x_ 1 + x_ 2 = 3.32 \leq 4 \)，且非负。 更新迭代点 ： \( x^{(2)} = x^{(1)} + \alpha_ 1 d^{(1)} = (0, 3) + 0.32 \times (4, -3) = (1.28, 2.04) \)。 \( f(x^{(2)}) = (1.28-2)^2 + (2.04-3)^2 \approx 0.5184 + 0.9216 = 1.44 \)。 步骤4: 收敛性分析 理论保证：Frank-Wolfe 法在凸可微问题中收敛到全局最优解，但收敛速度较慢（通常为次线性收敛）。 本问题的最优解在约束边界 \( x_ 1 + x_ 2 = 4 \) 上，通过梯度投影可求得精确解为 \( x^* = (1.5, 2.5) \)，\( f(x^* ) = 0.5 \)。 迭代两步后 \( x^{(2)} \) 接近最优解，后续迭代会继续沿边界逼近 \( x^* \)。 特点：Frank-Wolfe 法每一步只需求解线性规划，适合约束结构简单（如多面体）的问题，但方向可能不是最优下降方向，尤其靠近解时进展缓慢。 通过以上步骤，Frank-Wolfe 法以简单子问题迭代求解非线性规划，体现了条件梯度法的基本思想。