非线性规划中的序列仿射尺度法基础题
题目描述
考虑以下非线性规划问题：
\[\min f(x) = x_1^2 + 2x_2^2 - 2x_1x_2 + e^{x_1+x_2} \]
\[\text{s.t.} \quad x_1 + x_2 \geq 1, \quad x_1, x_2 > 0 \]
要求使用序列仿射尺度法（Sequential Affine Scaling Method）求解该问题。该方法通过迭代将非线性约束问题转化为一系列线性约束子问题，并利用仿射尺度变换保证迭代点始终位于可行域内部。
解题过程
1. 问题分析
目标函数 \(f(x)\) 非凸（因指数项），约束为线性不等式和变量正性条件。序列仿射尺度法的核心思想是：
- 通过仿射缩放变换将当前迭代点映射到空间中心，避免触碰约束边界。
- 在变换后的空间中构造线性或二次近似子问题。
- 求解子问题后逆变换回原空间，并更新迭代点。
2. 算法步骤
步骤 1：初始化
选择初始点 \(x^0 = (x_1^0, x_2^0)\) 满足严格内点条件（即 \(x_1^0 + x_2^0 > 1, x_1^0, x_2^0 > 0\)），例如 \(x^0 = (1, 1)\)。设定容忍误差 \(\epsilon = 10^{-6}\)。
步骤 2：构造缩放矩阵
在第 \(k\) 次迭代中，定义对角缩放矩阵 \(D_k\)：
\[D_k = \text{diag}(x_1^k, x_2^k) \]
该矩阵将当前点 \(x^k\) 映射为 \(D_k^{-1} x^k = (1, 1)\)，即变换后坐标系的中心。
步骤 3：线性化目标函数
在变换后的空间 \(y = D_k^{-1} x\) 中，对目标函数进行一阶泰勒展开。原变量 \(x = D_k y\)，代入 \(f(x)\)：
\[f(D_k y) \approx f(x^k) + \nabla f(x^k)^T D_k (y - 1) \]
其中 \(\nabla f(x^k) = \left(2x_1^k - 2x_2^k + e^{x_1^k+x_2^k}, 4x_2^k - 2x_1^k + e^{x_1^k+x_2^k}\right)\)，\(1 = (1,1)^T\)。
步骤 4：变换约束条件
原约束 \(x_1 + x_2 \geq 1\) 在 \(y\)-空间中变为：
\[(D_k y)_1 + (D_k y)_2 \geq 1 \implies x_1^k y_1 + x_2^k y_2 \geq 1 \]
由于 \(x^k\) 是内点，该约束在 \(y=1\) 处严格成立。
步骤 5：求解线性规划子问题
在 \(y\)-空间中求解以下线性规划：
\[\min \nabla f(x^k)^T D_k y \]
\[\text{s.t.} \quad x_1^k y_1 + x_2^k y_2 \geq 1, \quad y_1, y_2 > 0 \]
通过解析法或简单线性规划求解器得最优解 \(y^*\)。
步骤 6：逆变换与步长控制
将解逆变换回原空间： \(x^{k+1} = D_k y^*\)。为保证新点仍为内点，可能需缩短步长（如 \(x^{k+1} = x^k + \alpha (D_k y^* - x^k)\)，\(\alpha \in (0,1)\)）。
步骤 7：收敛判断
若 \(\|x^{k+1} - x^k\| < \epsilon\)，停止迭代；否则返回步骤 2。
3. 数值演示（第一轮迭代）
以 \(x^0 = (1,1)\) 为例：
- \(\nabla f(1,1) = (2-2+e^2, 4-2+e^2) = (e^2, 2+e^2) \approx (7.389, 9.389)\)
- \(D_0 = \text{diag}(1,1)\)，子问题目标函数为 \(7.389 y_1 + 9.389 y_2\)
- 约束为 \(y_1 + y_2 \geq 1\)，最优解在边界 \(y_1^* + y_2^* = 1\) 上。通过最小化线性目标，得 \(y^* = (1,0)\)（但需保持 \(y_2>0\)，故需添加小的正数阈值，如 \(y^* = (0.999, 0.001)\)）。
- 逆变换后 \(x^1 \approx (0.999, 0.001)\)，通过步长控制调整。
4. 关键点说明
- 内点保持：缩放矩阵确保迭代点远离边界，避免过早陷入约束边界。
- 子问题构造：每次迭代仅需求解线性规划，计算效率高。
- 收敛性：需控制步长保证全局收敛，尤其适用于中等规模非线性问题。
通过以上步骤迭代，最终可逼近问题的最优解 \(x^* \approx (0.5, 0.5)\)（需实际验证）。