线性规划的原始-对偶势函数法求解示例
字数 2217 2025-11-02 00:38:44

线性规划的原始-对偶势函数法求解示例

题目描述
考虑以下标准形式的线性规划问题：
最小化 \(c^T x\)
满足约束 \(Ax = b\)，\(x \geq 0\)
其中 \(A \in \mathbb{R}^{m \times n}\)，\(c \in \mathbb{R}^n\)，\(b \in \mathbb{R}^m\)，且 \(\text{rank}(A) = m\)。原始-对偶势函数法是一种内点法，通过结合原始变量 \(x\) 和对偶变量 \((y, s)\)（对偶问题为 \(\max b^T y\)，\(A^T y + s = c\)，\(s \geq 0\)），利用势函数将问题转化为无约束优化，从而同时更新原始和对偶变量。本示例以具体问题演示该方法的完整求解流程。

解题过程

  1. 问题建模与对偶形式
    设具体问题为：
    最小化 \(-x_1 - 2x_2\)
    约束为 \(x_1 + x_2 + x_3 = 5\)，\(x_1 + x_4 = 3\)，\(x \geq 0\)。
    对偶问题：最大化 \(5y_1 + 3y_2\)，满足 \(y_1 + y_2 + s_1 = -1\)，\(y_1 + s_2 = -2\)，\(s_3 = 0\)，\(s_4 = 0\)，\(s \geq 0\)。
    互补松弛条件：\(x_i s_i = 0\)（\(i=1,\dots,4\)）。

  2. 势函数定义
    定义势函数 \(\Phi(x, s) = q \ln(x^T s) - \sum_{j=1}^n \ln(x_j s_j)\)，其中 \(q > n\)。常用取 \(q = n + \sqrt{n}\)。本例中 \(n=4\)，取 \(q=6\)。势函数结合了目标函数间隙 \(x^T s\) 和中心路径条件，迫使解趋向最优。

  3. 初始点选择
    需选严格内点 \(x^0 > 0\)，\(s^0 > 0\)，且满足原始和对偶约束。通过构造法：

    • 设 \(x^0 = (1, 1, 3, 2)^T\)（满足 \(Ax = b\)），
    • 解对偶约束得 \(y^0 = (0, 0)^T\)，则 \(s^0 = c - A^T y^0 = (-1, -2, 0, 0)^T\) 不满足 \(s \geq 0\)。
      调整：令 \(\delta_s = 1 - \min(s^0) = 3\)，则 \(s^0 = s^0 + \delta_s \mathbf{1} = (2, 1, 3, 3)^T\)，再缩放使 \(x^0^T s^0 = 1\)。最终得可行内点。

  4. 牛顿方向计算
    在每步迭代中，求解线性系统：

\[ \begin{bmatrix} 0 & A^T & I \\ A & 0 & 0 \\ S & 0 & X \end{bmatrix} \begin{bmatrix} \Delta y \\ \Delta x \\ \Delta s \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ -XSe + \sigma \mu e \end{bmatrix} \]

其中 \(\mu = x^T s / n\)，\(\sigma \in (0,1)\) 是中心参数，\(e\) 是全1向量。
本例首轮迭代：设当前 \(\mu = 1\)，取 \(\sigma = 0.1\)，解得牛顿方向 \((\Delta x, \Delta y, \Delta s)\)。

  1. 步长选择与更新
    为保证 \(x, s > 0\)，计算最大步长：
    \(\alpha_{\text{prim}} = \min(1, 0.9 \times \min(-\frac{x_j}{\Delta x_j} \mid \Delta x_j < 0))\)，
    \(\alpha_{\text{dual}} = \min(1, 0.9 \times \min(-\frac{s_j}{\Delta s_j} \mid \Delta s_j < 0))\)。
    更新：\(x \leftarrow x + \alpha_{\text{prim}} \Delta x\)，\((y, s) \leftarrow (y, s) + \alpha_{\text{dual}} (\Delta y, \Delta s)\)。

  2. 收敛判断
    迭代直至 \(x^T s < \varepsilon\)（如 \(\varepsilon = 10^{-8}\)）。最终得解：
    \(x^* = (3, 2, 0, 0)^T\)，目标值 \(-7\)，对偶变量 \(y^* = (-1, 0)^T\)，\(s^* = (0, 0, 1, 1)^T\)，满足互补松弛条件。

关键点
势函数法通过权衡目标间隙和中心性，避免单纯形法的边界遍历，具有多项式复杂度。实际中需处理数值稳定性，如通过预测-校正策略改进 \(\sigma\) 的选择。

线性规划的原始-对偶势函数法求解示例 题目描述 考虑以下标准形式的线性规划问题： 最小化 \( c^T x \) 满足约束 \( Ax = b \)，\( x \geq 0 \) 其中 \( A \in \mathbb{R}^{m \times n} \)，\( c \in \mathbb{R}^n \)，\( b \in \mathbb{R}^m \)，且 \( \text{rank}(A) = m \)。原始-对偶势函数法是一种内点法，通过结合原始变量 \( x \) 和对偶变量 \( (y, s) \)（对偶问题为 \( \max b^T y \)，\( A^T y + s = c \)，\( s \geq 0 \)），利用势函数将问题转化为无约束优化，从而同时更新原始和对偶变量。本示例以具体问题演示该方法的完整求解流程。 解题过程 问题建模与对偶形式 设具体问题为： 最小化 \( -x_ 1 - 2x_ 2 \) 约束为 \( x_ 1 + x_ 2 + x_ 3 = 5 \)，\( x_ 1 + x_ 4 = 3 \)，\( x \geq 0 \)。 对偶问题：最大化 \( 5y_ 1 + 3y_ 2 \)，满足 \( y_ 1 + y_ 2 + s_ 1 = -1 \)，\( y_ 1 + s_ 2 = -2 \)，\( s_ 3 = 0 \)，\( s_ 4 = 0 \)，\( s \geq 0 \)。 互补松弛条件：\( x_ i s_ i = 0 \)（\( i=1,\dots,4 \)）。 势函数定义 定义势函数 \( \Phi(x, s) = q \ln(x^T s) - \sum_ {j=1}^n \ln(x_ j s_ j) \)，其中 \( q > n \)。常用取 \( q = n + \sqrt{n} \)。本例中 \( n=4 \)，取 \( q=6 \)。势函数结合了目标函数间隙 \( x^T s \) 和中心路径条件，迫使解趋向最优。 初始点选择 需选严格内点 \( x^0 > 0 \)，\( s^0 > 0 \)，且满足原始和对偶约束。通过构造法： 设 \( x^0 = (1, 1, 3, 2)^T \)（满足 \( Ax = b \)）， 解对偶约束得 \( y^0 = (0, 0)^T \)，则 \( s^0 = c - A^T y^0 = (-1, -2, 0, 0)^T \) 不满足 \( s \geq 0 \)。 调整：令 \( \delta_ s = 1 - \min(s^0) = 3 \)，则 \( s^0 = s^0 + \delta_ s \mathbf{1} = (2, 1, 3, 3)^T \)，再缩放使 \( x^0^T s^0 = 1 \)。最终得可行内点。 牛顿方向计算 在每步迭代中，求解线性系统： \[ \begin{bmatrix} 0 & A^T & I \\ A & 0 & 0 \\ S & 0 & X \end{bmatrix} \begin{bmatrix} \Delta y \\ \Delta x \\ \Delta s \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ -XSe + \sigma \mu e \end{bmatrix} \] 其中 \( \mu = x^T s / n \)，\( \sigma \in (0,1) \) 是中心参数，\( e \) 是全1向量。 本例首轮迭代：设当前 \( \mu = 1 \)，取 \( \sigma = 0.1 \)，解得牛顿方向 \( (\Delta x, \Delta y, \Delta s) \)。 步长选择与更新 为保证 \( x, s > 0 \)，计算最大步长： \( \alpha_ {\text{prim}} = \min(1, 0.9 \times \min(-\frac{x_ j}{\Delta x_ j} \mid \Delta x_ j < 0)) \)， \( \alpha_ {\text{dual}} = \min(1, 0.9 \times \min(-\frac{s_ j}{\Delta s_ j} \mid \Delta s_ j < 0)) \)。 更新：\( x \leftarrow x + \alpha_ {\text{prim}} \Delta x \)，\( (y, s) \leftarrow (y, s) + \alpha_ {\text{dual}} (\Delta y, \Delta s) \)。 收敛判断 迭代直至 \( x^T s < \varepsilon \)（如 \( \varepsilon = 10^{-8} \)）。最终得解： \( x^* = (3, 2, 0, 0)^T \)，目标值 \( -7 \)，对偶变量 \( y^* = (-1, 0)^T \)，\( s^* = (0, 0, 1, 1)^T \)，满足互补松弛条件。 关键点 势函数法通过权衡目标间隙和中心性，避免单纯形法的边界遍历，具有多项式复杂度。实际中需处理数值稳定性，如通过预测-校正策略改进 \( \sigma \) 的选择。