非线性规划中的序列无约束极小化技术(SUMT)基础题

题目描述
考虑一个简单的非线性规划问题：
最小化目标函数 \(f(x) = x^2\)
约束条件为 \(g(x) = x - 1 \geq 0\)
初始点 \(x_0 = 0\)。
使用序列无约束极小化技术（SUMT）中的外点罚函数法，通过构造罚函数并逐步求解无约束优化问题，逼近原问题的最优解。罚函数形式为 \(P(x, \mu) = f(x) + \mu \cdot (\min(0, g(x)))^2\)，其中 \(\mu\) 为罚因子，初始值 \(\mu_0 = 1\)，每次迭代增大罚因子（例如 \(\mu_{k+1} = 10 \mu_k\)），迭代直至解的变化小于阈值 \(\epsilon = 0.001\)。

解题过程

1. 问题分析

   • 目标函数 \(f(x) = x^2\) 是凸函数，约束 \(g(x) = x - 1 \geq 0\) 要求 \(x \geq 1\)。
   • 实际最优解在约束边界上： \(x^* = 1\)，此时 \(f(x^*) = 1\)。
   • 外点罚函数法通过惩罚违反约束的点，将约束问题转化为一系列无约束问题。

2. 罚函数构造

   • 罚函数定义为：

\[ P(x, \mu) = x^2 + \mu \cdot \left[ \min(0, x - 1) \right]^2 \]

• 当 \(x \geq 1\) 时，\(\min(0, x-1) = 0\)，罚项为0；当 \(x < 1\) 时，罚项为 \(\mu (x-1)^2\)。

3. 迭代求解
   • 初始设置：罚因子 \(\mu_0 = 1\)，初始点 \(x_0 = 0\)，阈值 \(\epsilon = 0.001\)。
   • 第1轮迭代（\( \mu = 1 \）：
     • 罚函数 \(P(x, 1) = x^2 + (x-1)^2\)。
     • 求解无约束极小化：对 \(P(x, 1)\) 求导，

\[ \frac{dP}{dx} = 2x + 2(x-1) = 4x - 2 = 0 \implies x = 0.5 \]

 - 检查约束：$ x = 0.5 < 1 $，违反约束，需继续迭代。  

• 第2轮迭代（\( \mu = 10 \）：
  • 罚函数 \(P(x, 10) = x^2 + 10(x-1)^2\)。
  • 求导：

\[ \frac{dP}{dx} = 2x + 20(x-1) = 22x - 20 = 0 \implies x \approx 0.909 \]

 - 仍违反约束（$ x < 1 $），但更接近边界。  

• 第3轮迭代（\( \mu = 100 \）：
  • 罚函数 \(P(x, 100) = x^2 + 100(x-1)^2\)。
  • 求导：

\[ \frac{dP}{dx} = 2x + 200(x-1) = 202x - 200 = 0 \implies x \approx 0.990 \]

• 第4轮迭代（\( \mu = 1000 \）：
  • 罚函数 \(P(x, 1000) = x^2 + 1000(x-1)^2\)。
  • 求导：

\[ \frac{dP}{dx} = 2x + 2000(x-1) = 2002x - 2000 = 0 \implies x \approx 0.999 \]

 - 与上一轮解的差 $ |0.999 - 0.990| = 0.009 > \epsilon $，继续迭代。  

• 第5轮迭代（\( \mu = 10000 \）：
  • 解得 \(x \approx 0.9999\)，与上一轮差 \(0.0009 < \epsilon\)，终止迭代。

4. 结果分析
   • 最终解 \(x \approx 0.9999\)，非常接近理论最优解 \(x^* = 1\)。
   • 随着 \(\mu\) 增大，罚函数迫使解向可行域边界逼近，但过大的 \(\mu\) 可能导致数值困难（如Hessian矩阵病态）。
   • SUMT的优点是将复杂约束问题转化为易求解的无约束问题，缺点是需要多次迭代且罚因子选择影响收敛速度。

总结
通过逐步增大罚因子并求解罚函数的无约束极小化问题，SUMT有效处理了约束优化。本例展示了外点罚函数法的基本流程和收敛特性。