基于线性规划的投影梯度法求解示例
字数 2847 2025-10-27 17:41:11

基于线性规划的投影梯度法求解示例

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

\[\begin{aligned} \min \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & x \geq 0 \end{aligned} \]

其中 \(A \in \mathbb{R}^{m \times n}\)（行满秩），\(b \in \mathbb{R}^m\)，\(c \in \mathbb{R}^n\)。投影梯度法通过将梯度下降与可行性保持结合，在约束集上迭代求解。本示例以具体数值演示该过程：

\[A = \begin{bmatrix}1 & 2 & 1\end{bmatrix},\ b = 4,\ c = \begin{bmatrix}-2 & -3 & -1\end{bmatrix}^T. \]

目标是在约束 \(x_1 + 2x_2 + x_3 = 4\) 和 \(x \geq 0\) 下最小化 \(c^T x\)。

解题过程

1. 问题重构与投影矩阵
等式约束 \(Ax = b\) 定义了一个仿射空间。令 \(x_0\) 为任意特解（如 \(x_0 = [4, 0, 0]^T\)），则解空间可表示为 \(x = x_0 + Fy\)，其中 \(F \in \mathbb{R}^{n \times (n-m)}\) 是 \(A\) 的零空间基矩阵（即 \(AF = 0\)）。
投影矩阵 \(P = I - A^T(AA^T)^{-1}A\) 将向量投影到 \(A\) 的零空间。对本例：

  • \(AA^T = [6]\)，\((AA^T)^{-1} = 1/6\)。
  • \(P = I_3 - \frac{1}{6}A^TA = \frac{1}{6}\begin{bmatrix}5 & -2 & -1 \\ -2 & 2 & -2 \\ -1 & -2 & 5\end{bmatrix}\)。
    梯度投影的更新公式为：

\[x^{k+1} = \pi\left(x^k - \alpha_k P \nabla f(x^k)\right), \]

其中 \(\pi\) 表示向非负象限的投影，\(\alpha_k\) 为步长，\(\nabla f(x^k) = c\)。

2. 初始点选择与梯度投影
取可行初始点 \(x^0 = [2, 1, 0]^T\)（满足 \(Ax^0 = 4\) 且 \(x^0 \geq 0\)）。
计算梯度投影方向 \(d^0 = -Pc\)：

  • \(c = [-2, -3, -1]^T\)，
  • \(Pc = \frac{1}{6}\begin{bmatrix}5\cdot(-2) + (-2)\cdot(-3) + (-1)\cdot(-1) \\ (-2)\cdot(-2) + 2\cdot(-3) + (-2)\cdot(-1) \\ (-1)\cdot(-2) + (-2)\cdot(-3) + 5\cdot(-1)\end{bmatrix} = \frac{1}{6}\begin{bmatrix}-3 \\ 0 \\ 3\end{bmatrix}\)，
  • \(d^0 = -Pc = [0.5, 0, -0.5]^T\)。
    方向 \(d^0\) 需满足可行下降条件：沿 \(d^0\) 移动时，\(A(x^0 + \beta d^0) = b\) 恒成立（因 \(Ad^0 = 0\)），但需检查非负约束。

3. 步长选择与投影操作
步长限制：沿 \(d^0\) 移动时，若 \(d^0_i < 0\)，则 \(x_i\) 减少，需防止 \(x_i < 0\)。对 \(x^0 = [2, 1, 0]^T\)：

  • \(x_3 = 0\) 且 \(d^0_3 = -0.5 < 0\)，因此步长 \(\alpha\) 必须为 0（否则 \(x_3\) 变负）。
    此时直接投影到边界：由于 \(d^0\) 在 \(x_3\) 方向不可行，需将搜索方向修正为可行下降方向。实际中，我们采用梯度投影到活跃约束的策略：
  • 当前活跃约束为 \(x_3 \geq 0\)（因 \(x_3 = 0\)）。
  • 将梯度投影到满足 \(Ax = b\) 和 \(x_3 = 0\) 的子空间：约束变为 \(A'x = b'\)，其中 \(A' = \begin{bmatrix}1 & 2 & 1 \\ 0 & 0 & 1\end{bmatrix}\)，\(b' = [4, 0]^T\)。
    但更高效的方法是直接计算修正方向：
    令 \(M\) 为活跃约束矩阵（本例中为 \([0, 0, 1]\)），则投影矩阵更新为 \(P' = I - A_c^T(A_c A_c^T)^{-1}A_c\)，其中 \(A_c = \begin{bmatrix}A \\ M\end{bmatrix}\)。
    计算得 \(P'c\) 为下降方向，且满足 \(x_3 \equiv 0\)。

4. 迭代过程与收敛
简化计算：在子空间 \(x_3 = 0\) 中，问题退化为：

\[\min -2x_1 - 3x_2 \quad \text{s.t.} \quad x_1 + 2x_2 = 4,\ x_1, x_2 \geq 0. \]

梯度为 \([-2, -3]^T\)，约束梯度为 \([1, 2]\)。投影方向需垂直于约束梯度：

  • 解 \(d\) 满足 \(d_1 + 2d_2 = 0\)，且使目标下降（如 \(d = [2, -1]^T\) 需投影到非负域）。
    实际迭代：
  1. 从 \(x^0 = [2, 1, 0]^T\) 开始，沿方向 \(d = [1, -0.5, 0]^T\)（满足 \(Ad=0\)）移动，步长受 \(x_2 \geq 0\) 限制：最大步长 \(\beta_{\max} = 2\)（使 \(x_2\) 减至 0）。
  2. 取 \(\alpha = 2\)，得 \(x^1 = [4, 0, 0]^T\)，目标值 \(-8\)。
  3. 在 \(x^1\) 处，活跃约束为 \(x_2 = 0\) 和 \(x_3 = 0\)，投影梯度为零（验证：子问题达最优）。
    最优解为 \(x^* = [4, 0, 0]^T\)，最优值 \(-8\)。

5. 算法总结
投影梯度法的核心步骤：

  1. 从可行点开始，计算梯度 \(c\) 在约束空间的投影 \(Pc\)。
  2. 若 \(Pc \neq 0\)，确定最大可行步长并更新点；否则检查是否满足最优性条件（如 KKT 条件）。
  3. 遇到边界时，将梯度投影到活跃约束定义的子空间，重复直至收敛。
    本例中，算法在两步内收敛到顶点解，体现了其高效性。
基于线性规划的投影梯度法求解示例 题目描述 考虑线性规划问题： \[ \begin{aligned} \min \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & x \geq 0 \end{aligned} \] 其中 \(A \in \mathbb{R}^{m \times n}\)（行满秩），\(b \in \mathbb{R}^m\)，\(c \in \mathbb{R}^n\)。投影梯度法通过将梯度下降与可行性保持结合，在约束集上迭代求解。本示例以具体数值演示该过程： \[ A = \begin{bmatrix}1 & 2 & 1\end{bmatrix},\ b = 4,\ c = \begin{bmatrix}-2 & -3 & -1\end{bmatrix}^T. \] 目标是在约束 \(x_ 1 + 2x_ 2 + x_ 3 = 4\) 和 \(x \geq 0\) 下最小化 \(c^T x\)。 解题过程 1. 问题重构与投影矩阵 等式约束 \(Ax = b\) 定义了一个仿射空间。令 \(x_ 0\) 为任意特解（如 \(x_ 0 = [ 4, 0, 0]^T\)），则解空间可表示为 \(x = x_ 0 + Fy\)，其中 \(F \in \mathbb{R}^{n \times (n-m)}\) 是 \(A\) 的零空间基矩阵（即 \(AF = 0\)）。 投影矩阵 \(P = I - A^T(AA^T)^{-1}A\) 将向量投影到 \(A\) 的零空间。对本例： \(AA^T = [ 6 ]\)，\((AA^T)^{-1} = 1/6\)。 \(P = I_ 3 - \frac{1}{6}A^TA = \frac{1}{6}\begin{bmatrix}5 & -2 & -1 \\ -2 & 2 & -2 \\ -1 & -2 & 5\end{bmatrix}\)。 梯度投影的更新公式为： \[ x^{k+1} = \pi\left(x^k - \alpha_ k P \nabla f(x^k)\right), \] 其中 \(\pi\) 表示向非负象限的投影，\(\alpha_ k\) 为步长，\(\nabla f(x^k) = c\)。 2. 初始点选择与梯度投影 取可行初始点 \(x^0 = [ 2, 1, 0 ]^T\)（满足 \(Ax^0 = 4\) 且 \(x^0 \geq 0\)）。 计算梯度投影方向 \(d^0 = -Pc\)： \(c = [ -2, -3, -1 ]^T\)， \(Pc = \frac{1}{6}\begin{bmatrix}5\cdot(-2) + (-2)\cdot(-3) + (-1)\cdot(-1) \\ (-2)\cdot(-2) + 2\cdot(-3) + (-2)\cdot(-1) \\ (-1)\cdot(-2) + (-2)\cdot(-3) + 5\cdot(-1)\end{bmatrix} = \frac{1}{6}\begin{bmatrix}-3 \\ 0 \\ 3\end{bmatrix}\)， \(d^0 = -Pc = [ 0.5, 0, -0.5 ]^T\)。 方向 \(d^0\) 需满足可行下降条件：沿 \(d^0\) 移动时，\(A(x^0 + \beta d^0) = b\) 恒成立（因 \(Ad^0 = 0\)），但需检查非负约束。 3. 步长选择与投影操作 步长限制 ：沿 \(d^0\) 移动时，若 \(d^0_ i < 0\)，则 \(x_ i\) 减少，需防止 \(x_ i < 0\)。对 \(x^0 = [ 2, 1, 0 ]^T\)： \(x_ 3 = 0\) 且 \(d^0_ 3 = -0.5 < 0\)，因此步长 \(\alpha\) 必须为 0（否则 \(x_ 3\) 变负）。 此时直接投影到边界：由于 \(d^0\) 在 \(x_ 3\) 方向不可行，需将搜索方向修正为可行下降方向。实际中，我们采用 梯度投影到活跃约束 的策略： 当前活跃约束为 \(x_ 3 \geq 0\)（因 \(x_ 3 = 0\)）。 将梯度投影到满足 \(Ax = b\) 和 \(x_ 3 = 0\) 的子空间：约束变为 \(A'x = b'\)，其中 \(A' = \begin{bmatrix}1 & 2 & 1 \\ 0 & 0 & 1\end{bmatrix}\)，\(b' = [ 4, 0 ]^T\)。 但更高效的方法是直接计算修正方向： 令 \(M\) 为活跃约束矩阵（本例中为 \([ 0, 0, 1]\)），则投影矩阵更新为 \(P' = I - A_ c^T(A_ c A_ c^T)^{-1}A_ c\)，其中 \(A_ c = \begin{bmatrix}A \\ M\end{bmatrix}\)。 计算得 \(P'c\) 为下降方向，且满足 \(x_ 3 \equiv 0\)。 4. 迭代过程与收敛 简化计算：在子空间 \(x_ 3 = 0\) 中，问题退化为： \[ \min -2x_ 1 - 3x_ 2 \quad \text{s.t.} \quad x_ 1 + 2x_ 2 = 4,\ x_ 1, x_ 2 \geq 0. \] 梯度为 \([ -2, -3]^T\)，约束梯度为 \([ 1, 2 ]\)。投影方向需垂直于约束梯度： 解 \(d\) 满足 \(d_ 1 + 2d_ 2 = 0\)，且使目标下降（如 \(d = [ 2, -1 ]^T\) 需投影到非负域）。 实际迭代： 从 \(x^0 = [ 2, 1, 0]^T\) 开始，沿方向 \(d = [ 1, -0.5, 0]^T\)（满足 \(Ad=0\)）移动，步长受 \(x_ 2 \geq 0\) 限制：最大步长 \(\beta_ {\max} = 2\)（使 \(x_ 2\) 减至 0）。 取 \(\alpha = 2\)，得 \(x^1 = [ 4, 0, 0 ]^T\)，目标值 \(-8\)。 在 \(x^1\) 处，活跃约束为 \(x_ 2 = 0\) 和 \(x_ 3 = 0\)，投影梯度为零（验证：子问题达最优）。 最优解为 \(x^* = [ 4, 0, 0 ]^T\)，最优值 \(-8\)。 5. 算法总结 投影梯度法的核心步骤： 从可行点开始，计算梯度 \(c\) 在约束空间的投影 \(Pc\)。 若 \(Pc \neq 0\)，确定最大可行步长并更新点；否则检查是否满足最优性条件（如 KKT 条件）。 遇到边界时，将梯度投影到活跃约束定义的子空间，重复直至收敛。 本例中，算法在两步内收敛到顶点解，体现了其高效性。