非线性规划中的内点反射牛顿法基础题

题目描述
考虑一个简单的非线性规划问题：
最小化 \(f(x) = x_1^2 + x_2^2\)
约束条件为 \(g(x) = x_1 + x_2 - 1 \geq 0\)（即 \(x_1 + x_2 \geq 1\)）。
目标是在可行域内找到使 \(f(x)\) 最小的点。内点反射牛顿法结合了内点法（保持迭代点严格可行）和反射机制（处理边界约束），并利用牛顿法快速收敛。

解题过程

1. 问题重构与障碍函数
   • 内点法通过障碍函数将约束问题转化为无约束问题。对于不等式约束 \(g(x) \geq 0\)，使用对数障碍函数：

\[ B(x) = f(x) - \mu \ln(g(x)) \]

 其中 $ \mu > 0 $ 是障碍参数。本例中：  

\[ B(x) = x_1^2 + x_2^2 - \mu \ln(x_1 + x_2 - 1). \]

• 当 \(x\) 靠近边界 \(g(x) = 0\) 时，\(-\ln(g(x))\) 会急剧增大，迫使迭代点留在可行域内部。

2. 牛顿步计算
   • 牛顿法通过二阶近似最小化 \(B(x)\)。首先计算梯度 \(\nabla B(x)\) 和 Hessian 矩阵 \(H(x)\)：

\[ \nabla B(x) = \begin{bmatrix} 2x_1 - \frac{\mu}{x_1 + x_2 - 1} \\ 2x_2 - \frac{\mu}{x_1 + x_2 - 1} \end{bmatrix}, \quad H(x) = \begin{bmatrix} 2 + \frac{\mu}{(x_1 + x_2 - 1)^2} & \frac{\mu}{(x_1 + x_2 - 1)^2} \\ \frac{\mu}{(x_1 + x_2 - 1)^2} & 2 + \frac{\mu}{(x_1 + x_2 - 1)^2} \end{bmatrix}. \]

• 牛顿方向 \(d\) 通过解线性方程组 \(H(x) d = -\nabla B(x)\) 得到。

3. 反射机制
   • 若牛顿步 \(d\) 使新点 \(x + d\) 违反约束（即 \(g(x + d) < 0\)），需进行反射：
     • 计算从当前点 \(x\) 到边界 \(g(x) = 0\) 的投影距离，沿 \(d\) 方向移动时，找到与边界的交点。
     • 在交点处，将剩余步长沿边界法向量的反射方向继续移动，确保新点回到可行域内部。
   • 本例中，约束边界是直线 \(x_1 + x_2 = 1\)，法向量为 \(n = (1, 1)^T\)。反射方向 \(d_{\text{ref}}\) 可计算为：

\[ d_{\text{ref}} = d - 2 \frac{d \cdot n}{\|n\|^2} n. \]

4. 迭代与收敛

   • 从初始点 \(x^{(0)} = (1, 1)\)（满足 \(g(x) = 1 > 0\)）开始，设定 \(\mu = 0.1\)：
     • 计算牛顿步 \(d\)，若 \(g(x + d) \geq 0\)，直接接受 \(x + d\)；否则反射后得到新点。
     • 每轮迭代后减小 \(\mu\)（如 \(\mu \leftarrow 0.5\mu\)），使障碍函数逐渐逼近原问题。
   • 重复直到 \(\| \nabla B(x) \| < \epsilon\)（例如 \(\epsilon = 10^{-6}\)）。理论最优解在边界 \(x_1 + x_2 = 1\) 上，且 \(x_1 = x_2 = 0.5\)（由对称性和凸性可知）。

5. 关键点总结

   • 内点性：通过障碍函数避免违反约束。
   • 反射机制：处理牛顿步越界时，利用几何反射保持可行性。
   • 牛顿法加速：利用二阶信息快速收敛，尤其适用于凸问题。
   • 实际应用中需调节 \(\mu\) 的下降策略和步长控制，以平衡稳定性和效率。