非线性规划中的原始对偶内点法基础题

字数 3892 2025-10-26 19:15:23

非线性规划中的原始对偶内点法基础题

题目描述
考虑一个简单的非线性规划问题：
最小化 \(f(x) = x_1^2 + x_2^2\)
约束条件：
\(g(x) = x_1 + x_2 - 2 \geq 0\)
\(x_1 \geq 0, x_2 \geq 0\)
该问题要求最小化二次目标函数，并满足线性不等式约束。使用原始对偶内点法求解该问题，需详细说明如何构造障碍函数、中心路径方程、以及对偶变量的更新策略。

解题过程

1. 问题重构与障碍函数引入
原始问题含不等式约束 \(g(x) \geq 0\) 和 \(x \geq 0\)。为处理非负性，将约束统一为 \(x_1 \geq 0, x_2 \geq 0, x_1 + x_2 - 2 \geq 0\)。内点法通过引入障碍函数将约束问题转化为序列无约束问题。对于约束 \(c_i(x) \geq 0\)，对数障碍函数为：

\[\Phi(x) = f(x) - \mu \sum_i \ln(c_i(x)) \]

其中 \(\mu > 0\) 是障碍参数。本例中约束为 \(c_1(x) = x_1, c_2(x) = x_2, c_3(x) = x_1 + x_2 - 2\)，因此障碍问题为：

\[\min_{x} \left[ x_1^2 + x_2^2 - \mu \left( \ln(x_1) + \ln(x_2) + \ln(x_1 + x_2 - 2) \right) \right] \]

注意：需在可行域内点（即 \(x_1 > 0, x_2 > 0, x_1 + x_2 > 2\) ）求解。

2. 拉格朗日函数与KKT条件
定义拉格朗日函数（含对偶变量 \(\lambda = [\lambda_1, \lambda_2, \lambda_3] \geq 0\)）：

\[L(x, \lambda) = f(x) - \lambda_1 x_1 - \lambda_2 x_2 - \lambda_3 (x_1 + x_2 - 2) \]

互补松弛条件为 \(\lambda_1 x_1 = 0, \lambda_2 x_2 = 0, \lambda_3 (x_1 + x_2 - 2) = 0\)。内点法的核心是松弛这些条件：引入参数 \(\mu\)，要求 \(\lambda_i c_i(x) = \mu\)（中心路径条件）。

原始对偶系统：对 \(L(x, \lambda)\) 求梯度并加入松弛条件，得到修改的KKT方程：

\[\nabla f(x) - J_c(x)^T \lambda = 0 \quad \text{（原始可行性）} \]

\[c_i(x) \lambda_i = \mu, \quad i=1,2,3 \quad \text{（中心路径条件）} \]

其中 \(J_c(x)\) 是约束 \(c(x)\) 的雅可比矩阵。本例中：

\(\nabla f(x) = [2x_1, 2x_2]^T\)
约束梯度： \(\nabla c_1 = [1,0]^T, \nabla c_2 = [0,1]^T, \nabla c_3 = [1,1]^T\)
矩阵形式： \(J_c(x)^T \lambda = [\lambda_1 + \lambda_3, \lambda_2 + \lambda_3]^T\)

因此，原始可行性方程变为：

\[2x_1 - (\lambda_1 + \lambda_3) = 0, \quad 2x_2 - (\lambda_2 + \lambda_3) = 0 \]

中心路径条件：

\[\lambda_1 x_1 = \mu, \quad \lambda_2 x_2 = \mu, \quad \lambda_3 (x_1 + x_2 - 2) = \mu \]

3. 牛顿步方向计算
设当前迭代点为 \((x, \lambda)\)，需解非线性系统：

\[F(x, \lambda) = \begin{bmatrix} \nabla f(x) - J_c(x)^T \lambda \\ \Lambda c(x) - \mu e \end{bmatrix} = 0 \]

其中 \(\Lambda = \text{diag}(\lambda)\), \(c(x) = [x_1, x_2, x_1+x_2-2]^T\), \(e = [1,1,1]^T\)。
应用牛顿法： \(F'(x, \lambda) \begin{bmatrix} \Delta x \\ \Delta \lambda \end{bmatrix} = -F(x, \lambda)\)，雅可比矩阵 \(F'\) 为：

\[\begin{bmatrix} \nabla^2 f(x) - \sum \lambda_i \nabla^2 c_i(x) & -J_c(x)^T \\ \Lambda J_c(x) & \text{diag}(c(x)) \end{bmatrix} \]

本例中 \(\nabla^2 f(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}\)，线性约束的 \(\nabla^2 c_i = 0\)，故左上块为 \(\begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}\)。
雅可比矩阵 \(J_c(x) = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix}\)。

牛顿系统展开为：

\[\begin{bmatrix} 2 & 0 & -1 & 0 & -1 \\ 0 & 2 & 0 & -1 & -1 \\ \lambda_1 & 0 & x_1 & 0 & 0 \\ 0 & \lambda_2 & 0 & x_2 & 0 \\ \lambda_3 & \lambda_3 & 0 & 0 & x_1+x_2-2 \end{bmatrix} \begin{bmatrix} \Delta x_1 \\ \Delta x_2 \\ \Delta \lambda_1 \\ \Delta \lambda_2 \\ \Delta \lambda_3 \end{bmatrix} = - \begin{bmatrix} 2x_1 - (\lambda_1 + \lambda_3) \\ 2x_2 - (\lambda_2 + \lambda_3) \\ \lambda_1 x_1 - \mu \\ \lambda_2 x_2 - \mu \\ \lambda_3 (x_1+x_2-2) - \mu \end{bmatrix} \]

解此线性系统得牛顿步 \((\Delta x, \Delta \lambda)\)。

4. 迭代与参数更新
步骤：

初始化：选择可行内点 \(x^{(0)} = (1.5, 1.5)\)，对偶变量 \(\lambda^{(0)} = [1,1,1]^T\)，初始 \(\mu = 1\)。
循环直到收敛（如 \(\mu < 10^{-6}\)）：
- 解牛顿系统得 \((\Delta x, \Delta \lambda)\)。
- 计算步长 \(\alpha \in (0,1]\)，确保 \(x + \alpha \Delta x > 0\), \(x_1 + x_2 - 2 > 0\), \(\lambda + \alpha \Delta \lambda \geq 0\)。
- 更新 \(x \leftarrow x + \alpha \Delta x\), \(\lambda \leftarrow \lambda + \alpha \Delta \lambda\)。
- 减小 \(\mu \leftarrow \sigma \mu\)（\(\sigma \in (0,1)\)，如 0.1）。

5. 收敛性与结果分析
当 \(\mu \to 0\)，解趋近原始问题的最优解。本例理论最优解在 \(x_1 = x_2 = 1\)（约束边界 \(x_1 + x_2 = 2\)），且非负约束非活跃（\(\lambda_1 = \lambda_2 = 0\)）。代入KKT条件：

\(2x_1 - \lambda_3 = 0\), \(2x_2 - \lambda_3 = 0\) ⇒ \(x_1 = x_2\)。
由 \(x_1 + x_2 = 2\) 得 \(x_1 = x_2 = 1\), \(\lambda_3 = 2\)。
内点法通过追踪中心路径（\(\mu > 0\) 时解平滑变化）逼近此点。

非线性规划中的原始对偶内点法基础题题目描述考虑一个简单的非线性规划问题：最小化 \( f(x) = x_ 1^2 + x_ 2^2 \) 约束条件： \( g(x) = x_ 1 + x_ 2 - 2 \geq 0 \) \( x_ 1 \geq 0, x_ 2 \geq 0 \) 该问题要求最小化二次目标函数，并满足线性不等式约束。使用原始对偶内点法求解该问题，需详细说明如何构造障碍函数、中心路径方程、以及对偶变量的更新策略。解题过程 1. 问题重构与障碍函数引入原始问题含不等式约束 \( g(x) \geq 0 \) 和 \( x \geq 0 \)。为处理非负性，将约束统一为 \( x_ 1 \geq 0, x_ 2 \geq 0, x_ 1 + x_ 2 - 2 \geq 0 \)。内点法通过引入障碍函数将约束问题转化为序列无约束问题。对于约束 \( c_ i(x) \geq 0 \)，对数障碍函数为： \[ \Phi(x) = f(x) - \mu \sum_ i \ln(c_ i(x)) \] 其中 \( \mu > 0 \) 是障碍参数。本例中约束为 \( c_ 1(x) = x_ 1, c_ 2(x) = x_ 2, c_ 3(x) = x_ 1 + x_ 2 - 2 \)，因此障碍问题为： \[ \min_ {x} \left[ x_ 1^2 + x_ 2^2 - \mu \left( \ln(x_ 1) + \ln(x_ 2) + \ln(x_ 1 + x_ 2 - 2) \right) \right ] \] 注意：需在可行域内点（即 \( x_ 1 > 0, x_ 2 > 0, x_ 1 + x_ 2 > 2 \) ）求解。 2. 拉格朗日函数与KKT条件定义拉格朗日函数（含对偶变量 \( \lambda = [ \lambda_ 1, \lambda_ 2, \lambda_ 3 ] \geq 0 \)）： \[ L(x, \lambda) = f(x) - \lambda_ 1 x_ 1 - \lambda_ 2 x_ 2 - \lambda_ 3 (x_ 1 + x_ 2 - 2) \] 互补松弛条件为 \( \lambda_ 1 x_ 1 = 0, \lambda_ 2 x_ 2 = 0, \lambda_ 3 (x_ 1 + x_ 2 - 2) = 0 \)。内点法的核心是松弛这些条件：引入参数 \( \mu \)，要求 \( \lambda_ i c_ i(x) = \mu \)（中心路径条件）。原始对偶系统：对 \( L(x, \lambda) \) 求梯度并加入松弛条件，得到修改的KKT方程： \[ \nabla f(x) - J_ c(x)^T \lambda = 0 \quad \text{（原始可行性）} \] \[ c_ i(x) \lambda_ i = \mu, \quad i=1,2,3 \quad \text{（中心路径条件）} \] 其中 \( J_ c(x) \) 是约束 \( c(x) \) 的雅可比矩阵。本例中： \( \nabla f(x) = [ 2x_ 1, 2x_ 2 ]^T \) 约束梯度： \( \nabla c_ 1 = [ 1,0]^T, \nabla c_ 2 = [ 0,1]^T, \nabla c_ 3 = [ 1,1 ]^T \) 矩阵形式： \( J_ c(x)^T \lambda = [ \lambda_ 1 + \lambda_ 3, \lambda_ 2 + \lambda_ 3 ]^T \) 因此，原始可行性方程变为： \[ 2x_ 1 - (\lambda_ 1 + \lambda_ 3) = 0, \quad 2x_ 2 - (\lambda_ 2 + \lambda_ 3) = 0 \] 中心路径条件： \[ \lambda_ 1 x_ 1 = \mu, \quad \lambda_ 2 x_ 2 = \mu, \quad \lambda_ 3 (x_ 1 + x_ 2 - 2) = \mu \] 3. 牛顿步方向计算设当前迭代点为 \( (x, \lambda) \)，需解非线性系统： \[ F(x, \lambda) = \begin{bmatrix} \nabla f(x) - J_ c(x)^T \lambda \\ \Lambda c(x) - \mu e \end{bmatrix} = 0 \] 其中 \( \Lambda = \text{diag}(\lambda) \), \( c(x) = [ x_ 1, x_ 2, x_ 1+x_ 2-2]^T \), \( e = [ 1,1,1 ]^T \)。应用牛顿法： \( F'(x, \lambda) \begin{bmatrix} \Delta x \\ \Delta \lambda \end{bmatrix} = -F(x, \lambda) \)，雅可比矩阵 \( F' \) 为： \[ \begin{bmatrix} \nabla^2 f(x) - \sum \lambda_ i \nabla^2 c_ i(x) & -J_ c(x)^T \\ \Lambda J_ c(x) & \text{diag}(c(x)) \end{bmatrix} \] 本例中 \( \nabla^2 f(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \)，线性约束的 \( \nabla^2 c_ i = 0 \)，故左上块为 \( \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \)。雅可比矩阵 \( J_ c(x) = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix} \)。牛顿系统展开为： \[ \begin{bmatrix} 2 & 0 & -1 & 0 & -1 \\ 0 & 2 & 0 & -1 & -1 \\ \lambda_ 1 & 0 & x_ 1 & 0 & 0 \\ 0 & \lambda_ 2 & 0 & x_ 2 & 0 \\ \lambda_ 3 & \lambda_ 3 & 0 & 0 & x_ 1+x_ 2-2 \end{bmatrix} \begin{bmatrix} \Delta x_ 1 \\ \Delta x_ 2 \\ \Delta \lambda_ 1 \\ \Delta \lambda_ 2 \\ \Delta \lambda_ 3 \end{bmatrix} = - \begin{bmatrix} 2x_ 1 - (\lambda_ 1 + \lambda_ 3) \\ 2x_ 2 - (\lambda_ 2 + \lambda_ 3) \\ \lambda_ 1 x_ 1 - \mu \\ \lambda_ 2 x_ 2 - \mu \\ \lambda_ 3 (x_ 1+x_ 2-2) - \mu \end{bmatrix} \] 解此线性系统得牛顿步 \( (\Delta x, \Delta \lambda) \)。 4. 迭代与参数更新步骤：初始化：选择可行内点 \( x^{(0)} = (1.5, 1.5) \)，对偶变量 \( \lambda^{(0)} = [ 1,1,1 ]^T \)，初始 \( \mu = 1 \)。循环直到收敛（如 \( \mu < 10^{-6} \)）：解牛顿系统得 \( (\Delta x, \Delta \lambda) \)。计算步长 \( \alpha \in (0,1] \)，确保 \( x + \alpha \Delta x > 0 \), \( x_ 1 + x_ 2 - 2 > 0 \), \( \lambda + \alpha \Delta \lambda \geq 0 \)。更新 \( x \leftarrow x + \alpha \Delta x \), \( \lambda \leftarrow \lambda + \alpha \Delta \lambda \)。减小 \( \mu \leftarrow \sigma \mu \)（\( \sigma \in (0,1) \)，如 0.1）。 5. 收敛性与结果分析当 \( \mu \to 0 \)，解趋近原始问题的最优解。本例理论最优解在 \( x_ 1 = x_ 2 = 1 \)（约束边界 \( x_ 1 + x_ 2 = 2 \)），且非负约束非活跃（\( \lambda_ 1 = \lambda_ 2 = 0 \)）。代入KKT条件： \( 2x_ 1 - \lambda_ 3 = 0 \), \( 2x_ 2 - \lambda_ 3 = 0 \) ⇒ \( x_ 1 = x_ 2 \)。由 \( x_ 1 + x_ 2 = 2 \) 得 \( x_ 1 = x_ 2 = 1 \), \( \lambda_ 3 = 2 \)。内点法通过追踪中心路径（\( \mu > 0 \) 时解平滑变化）逼近此点。