非线性规划中的内点法基础题
题目描述
考虑一个简单的非线性规划问题：
最小化目标函数 \(f(x)1, x_2) = x_1^2 + x_2^2\)
约束条件为：
\(g(x_1, x_2) = x_1 + x_2 - 2 \geq 0\)
要求使用内点法（Interior Point Method） 求解该问题，并说明如何通过迭代逼近最优解。
解题过程
1. 问题分析
- 目标函数 \(f(x)\) 是一个凸二次函数，约束是线性的，因此问题是凸优化问题，存在唯一全局最优解。
- 内点法的核心思想是从可行域内部开始，通过引入障碍函数，将约束问题转化为一系列无约束问题，并沿路径逼近边界上的最优解。
2. 构造障碍函数
- 对于不等式约束 \(g(x) \geq 0\)，内点法使用对数障碍函数惩罚接近边界的点。
- 定义障碍参数 \(\mu > 0\)，构造障碍函数：
\[ B(x, \mu) = f(x) - \mu \ln(g(x)) \]
其中对数项确保当 \(g(x) \to 0^+\) 时惩罚趋于无穷大，从而保持迭代点始终在可行域内部（\(g(x) > 0\)）。
3. 求解无约束子问题
- 对于固定的 \(\mu\)，求解无约束问题：
\[ \min_{x} B(x, \mu) = x_1^2 + x_2^2 - \mu \ln(x_1 + x_2 - 2) \]
- 通过梯度为零求驻点。计算梯度：
\[ \frac{\partial B}{\partial x_1} = 2x_1 - \frac{\mu}{x_1 + x_2 - 2} = 0 \]
\[ \frac{\partial B}{\partial x_2} = 2x_2 - \frac{\mu}{x_1 + x_2 - 2} = 0 \]
- 由对称性得 \(x_1 = x_2\)。设 \(x_1 = x_2 = t\)，代入梯度方程：
\[ 2t - \frac{\mu}{2t - 2} = 0 \implies 2t(2t - 2) - \mu = 0 \]
整理得：
\[ 4t^2 - 4t - \mu = 0 \]
- 解二次方程（取满足 \(t > 1\) 的根，因为约束要求 \(x_1 + x_2 > 2\)）：
\[ t = \frac{4 + \sqrt{16 + 16\mu}}{8} = \frac{1 + \sqrt{1 + \mu}}{2} \]
因此解为：
\[ x_1^*(\mu) = x_2^*(\mu) = \frac{1 + \sqrt{1 + \mu}}{2} \]
4. 路径跟踪与收敛
- 当 \(\mu \to 0^+\) 时，障碍项的影响逐渐消失，解逼近原问题的最优解：
\[ \lim_{\mu \to 0} x_1^*(\mu) = \frac{1 + \sqrt{1 + 0}}{2} = 1 \]
即最优解为 \(x_1^* = x_2^* = 1\)。
- 此时目标函数值 \(f^* = 1^2 + 1^2 = 2\)，约束 \(g(x^*) = 0\)（紧约束）。
- 实际算法中，通过迭代减小 \(\mu\)（例如 \(\mu_{k+1} = 0.1 \mu_k\)），并以前一步解作为初值求解新障碍问题，直至满足收敛条件。
5. 结论
- 内点法通过连续调整障碍参数，将迭代点从可行域内部引导至边界上的最优点。
- 本例展示了如何通过解析推导得到障碍问题的解路径，实际应用中需配合数值优化方法（如牛顿法）求解梯度方程组。