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

字数 3066 2025-11-04 11:59:17

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

题目描述
考虑一个简单的线性规划问题：
最小化目标函数 \(z = -x_1 - 2x_2\)，
约束条件为：

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

要求使用投影梯度法求解该问题。投影梯度法是一种处理约束优化问题的迭代算法，通过在每次梯度下降后将解投影回可行域来满足约束。

解题过程

步骤1: 问题标准化

将不等式约束转换为等式形式，引入松弛变量 \(x_3, x_4 \geq 0\)：

\[\begin{aligned} x_1 + x_2 + x_3 &= 4, \\ x_1 - x_2 + x_4 &= 2, \\ x_1, x_2, x_3, x_4 &\geq 0. \end{aligned} \]

目标函数变为 \(z = -x_1 - 2x_2\)。此时可行域是一个多面体，定义为 \(\{ x \in \mathbb{R}^4 \mid Ax = b, x \geq 0 \}\)，其中

\[A = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & -1 & 0 & 1 \end{bmatrix}, \quad b = \begin{bmatrix} 4 \\ 2 \end{bmatrix}. \]

步骤2: 投影梯度法原理

投影梯度法的迭代格式为：

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

其中：

\(P_\Omega\) 是到可行域 \(\Omega = \{ x \mid Ax = b, x \geq 0 \}\) 的投影算子；
\(\alpha_k\) 是步长（通过线搜索确定）；
\(\nabla f(x) = (-1, -2, 0, 0)^\top\) 是目标函数的梯度（常数）。

投影操作需解决一个二次规划问题：

\[P_\Omega(y) = \arg\min_{x \in \Omega} \| x - y \|^2. \]

步骤3: 投影计算简化

由于约束 \(Ax = b\) 是线性的，投影可分解为两步：

投影到线性约束空间 \(\{ x \mid Ax = b \}\)：

\[ x \mapsto x + A^\top (AA^\top)^{-1} (b - Ax). \]

投影到非负象限 \(x \geq 0\)：简单将负分量置零。
但直接处理非负约束较复杂，通常使用有效集方法或数值工具。这里我们手动模拟迭代。

步骤4: 初始点选择

选择可行点 \(x^{(0)} = (1, 1, 2, 2)^\top\)（满足 \(Ax = b\) 且 \(x \geq 0\)）。
验证：

\[A x^{(0)} = \begin{bmatrix} 1+1+2 \\ 1-1+2 \end{bmatrix} = \begin{bmatrix} 4 \\ 2 \end{bmatrix} = b. \]

步骤5: 第一次迭代

梯度 \(\nabla f = (-1, -2, 0, 0)^\top\)。
取步长 \(\alpha_0 = 0.5\)（需满足目标函数下降和可行性，这里手动选择）。
更新：

\[y = x^{(0)} - \alpha_0 \nabla f = (1, 1, 2, 2)^\top - 0.5 \cdot (-1, -2, 0, 0)^\top = (1.5, 2, 2, 2)^\top. \]

投影到可行域：

首先满足 \(Ax = b\)：计算残差 \(r = b - A y = (4 - (1.5+2+2), 2 - (1.5-2+2))^\top = (-1.5, 0.5)^\top\)。
修正量：

\[ \Delta = A^\top (AA^\top)^{-1} r. \]

计算 \(AA^\top = \begin{bmatrix} 3 & 0 \\ 0 & 3 \end{bmatrix}\)，逆矩阵为 \(\frac{1}{3} I\)。
故

\[ \Delta = \frac{1}{3} A^\top r = \frac{1}{3} \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} -1.5 \\ 0.5 \end{bmatrix} = \frac{1}{3} (-1, -2, -1.5, 0.5)^\top = (-0.333, -0.667, -0.5, 0.167)^\top. \]

得到临时点 \(y + \Delta = (1.167, 1.333, 1.5, 2.167)^\top\)。

投影到 \(x \geq 0\)：所有分量非负，故 \(x^{(1)} = (1.167, 1.333, 1.5, 2.167)^\top\)。
目标函数值 \(z^{(1)} = -1.167 - 2 \cdot 1.333 = -3.833\)，较初始值 \(z^{(0)} = -3\) 下降。

步骤6: 第二次迭代

梯度不变，步长 \(\alpha_1 = 0.5\)。
更新：

\[y = x^{(1)} - \alpha_1 \nabla f = (1.167, 1.333, 1.5, 2.167)^\top + (0.5, 1, 0, 0)^\top = (1.667, 2.333, 1.5, 2.167)^\top. \]

投影：

残差 \(r = b - A y = (4 - (1.667+2.333+1.5), 2 - (1.667-2.333+2.167))^\top = (-1.5, 0.5)^\top\)（巧合与上次相同）。
修正量 \(\Delta = (-0.333, -0.667, -0.5, 0.167)^\top\)。
临时点 \(y + \Delta = (1.333, 1.667, 1.0, 2.333)^\top\)。
非负投影：所有分量非负，故 \(x^{(2)} = (1.333, 1.667, 1.0, 2.333)^\top\)。
目标函数值 \(z^{(2)} = -1.333 - 2 \cdot 1.667 = -4.667\)。

步骤7: 收敛检查

继续迭代可逼近最优解。通过单纯形法验证：最优解在顶点 \((0, 4)\) 处（原变量空间），对应 \(z = -8\)。投影梯度法需更多迭代或自适应步长以加速收敛。最终解应满足 \(x_3 = 0\)（第一个约束紧）和 \(x_1 = 0\)（边界）。

总结
投影梯度法通过梯度下降与投影交替进行，确保迭代点始终可行。关键挑战是投影计算的高成本，尤其在约束复杂时。步长选择影响收敛速度，需通过线搜索平衡下降量与可行性。

基于线性规划的投影梯度法求解示例题目描述考虑一个简单的线性规划问题：最小化目标函数 \( z = -x_ 1 - 2x_ 2 \)，约束条件为： \[ \begin{aligned} x_ 1 + x_ 2 &\leq 4, \\ x_ 1 - x_ 2 &\leq 2, \\ x_ 1, x_ 2 &\geq 0. \end{aligned} \] 要求使用投影梯度法求解该问题。投影梯度法是一种处理约束优化问题的迭代算法，通过在每次梯度下降后将解投影回可行域来满足约束。解题过程步骤1: 问题标准化将不等式约束转换为等式形式，引入松弛变量 \( x_ 3, x_ 4 \geq 0 \)： \[ \begin{aligned} x_ 1 + x_ 2 + x_ 3 &= 4, \\ x_ 1 - x_ 2 + x_ 4 &= 2, \\ x_ 1, x_ 2, x_ 3, x_ 4 &\geq 0. \end{aligned} \] 目标函数变为 \( z = -x_ 1 - 2x_ 2 \)。此时可行域是一个多面体，定义为 \( \{ x \in \mathbb{R}^4 \mid Ax = b, x \geq 0 \} \)，其中 \[ A = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & -1 & 0 & 1 \end{bmatrix}, \quad b = \begin{bmatrix} 4 \\ 2 \end{bmatrix}. \] 步骤2: 投影梯度法原理投影梯度法的迭代格式为： \[ x^{(k+1)} = P_ \Omega \left( x^{(k)} - \alpha_ k \nabla f(x^{(k)}) \right), \] 其中： \( P_ \Omega \) 是到可行域 \( \Omega = \{ x \mid Ax = b, x \geq 0 \} \) 的投影算子； \( \alpha_ k \) 是步长（通过线搜索确定）； \( \nabla f(x) = (-1, -2, 0, 0)^\top \) 是目标函数的梯度（常数）。投影操作需解决一个二次规划问题： \[ P_ \Omega(y) = \arg\min_ {x \in \Omega} \| x - y \|^2. \] 步骤3: 投影计算简化由于约束 \( Ax = b \) 是线性的，投影可分解为两步：投影到线性约束空间 \( \{ x \mid Ax = b \} \)： \[ x \mapsto x + A^\top (AA^\top)^{-1} (b - Ax). \] 投影到非负象限 \( x \geq 0 \)：简单将负分量置零。但直接处理非负约束较复杂，通常使用有效集方法或数值工具。这里我们手动模拟迭代。步骤4: 初始点选择选择可行点 \( x^{(0)} = (1, 1, 2, 2)^\top \)（满足 \( Ax = b \) 且 \( x \geq 0 \)）。验证： \[ A x^{(0)} = \begin{bmatrix} 1+1+2 \\ 1-1+2 \end{bmatrix} = \begin{bmatrix} 4 \\ 2 \end{bmatrix} = b. \] 步骤5: 第一次迭代梯度 \( \nabla f = (-1, -2, 0, 0)^\top \)。取步长 \( \alpha_ 0 = 0.5 \)（需满足目标函数下降和可行性，这里手动选择）。更新： \[ y = x^{(0)} - \alpha_ 0 \nabla f = (1, 1, 2, 2)^\top - 0.5 \cdot (-1, -2, 0, 0)^\top = (1.5, 2, 2, 2)^\top. \] 投影到可行域：首先满足 \( Ax = b \)：计算残差 \( r = b - A y = (4 - (1.5+2+2), 2 - (1.5-2+2))^\top = (-1.5, 0.5)^\top \)。修正量： \[ \Delta = A^\top (AA^\top)^{-1} r. \] 计算 \( AA^\top = \begin{bmatrix} 3 & 0 \\ 0 & 3 \end{bmatrix} \)，逆矩阵为 \( \frac{1}{3} I \)。故 \[ \Delta = \frac{1}{3} A^\top r = \frac{1}{3} \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} -1.5 \\ 0.5 \end{bmatrix} = \frac{1}{3} (-1, -2, -1.5, 0.5)^\top = (-0.333, -0.667, -0.5, 0.167)^\top. \] 得到临时点 \( y + \Delta = (1.167, 1.333, 1.5, 2.167)^\top \)。投影到 \( x \geq 0 \)：所有分量非负，故 \( x^{(1)} = (1.167, 1.333, 1.5, 2.167)^\top \)。目标函数值 \( z^{(1)} = -1.167 - 2 \cdot 1.333 = -3.833 \)，较初始值 \( z^{(0)} = -3 \) 下降。步骤6: 第二次迭代梯度不变，步长 \( \alpha_ 1 = 0.5 \)。更新： \[ y = x^{(1)} - \alpha_ 1 \nabla f = (1.167, 1.333, 1.5, 2.167)^\top + (0.5, 1, 0, 0)^\top = (1.667, 2.333, 1.5, 2.167)^\top. \] 投影：残差 \( r = b - A y = (4 - (1.667+2.333+1.5), 2 - (1.667-2.333+2.167))^\top = (-1.5, 0.5)^\top \)（巧合与上次相同）。修正量 \( \Delta = (-0.333, -0.667, -0.5, 0.167)^\top \)。临时点 \( y + \Delta = (1.333, 1.667, 1.0, 2.333)^\top \)。非负投影：所有分量非负，故 \( x^{(2)} = (1.333, 1.667, 1.0, 2.333)^\top \)。目标函数值 \( z^{(2)} = -1.333 - 2 \cdot 1.667 = -4.667 \)。步骤7: 收敛检查继续迭代可逼近最优解。通过单纯形法验证：最优解在顶点 \( (0, 4) \) 处（原变量空间），对应 \( z = -8 \)。投影梯度法需更多迭代或自适应步长以加速收敛。最终解应满足 \( x_ 3 = 0 \)（第一个约束紧）和 \( x_ 1 = 0 \)（边界）。总结投影梯度法通过梯度下降与投影交替进行，确保迭代点始终可行。关键挑战是投影计算的高成本，尤其在约束复杂时。步长选择影响收敛速度，需通过线搜索平衡下降量与可行性。