序列凸规划(SCP)算法基础题

题目描述
考虑非线性规划问题：
最小化 f(x) = (x₁ - 2)⁴ + (x₂ - 3)²
满足约束条件：
g₁(x) = x₁² + x₂² - 4 ≤ 0
g₂(x) = -x₁ ≤ 0
g₃(x) = -x₂ ≤ 0

这是一个具有非线性目标函数和非线性约束的优化问题。我们将使用序列凸规划(SCP)算法求解该问题，该算法通过一系列凸子问题来逼近原非凸问题。

解题过程

第一步：理解SCP算法基本原理

1. SCP的核心思想：在每次迭代中，将非凸问题在当前点附近凸化，得到一个凸近似子问题
2. 关键操作：
   • 对非凸函数进行一阶泰勒展开（线性化）
   • 对凸函数保持原形式（如果是凸的）
3. 迭代过程：求解凸近似子问题，将解作为新的迭代点，重复直到收敛

第二步：问题分析

1. 目标函数f(x)分析：

   • (x₂ - 3)²是凸函数
   • (x₁ - 2)⁴是非凸函数（四阶项）

2. 约束函数分析：

   • g₁(x) = x₁² + x₂² - 4是凸函数（二次型）
   • g₂(x)和g₃(x)是线性约束，也是凸的

第三步：构建凸近似子问题
在点xᵏ = (x₁ᵏ, x₂ᵏ)处，我们需要对非凸部分进行凸化：

1. 目标函数的凸化：

   • 对f(x)在xᵏ处进行一阶泰勒展开：
     f̃(x) ≈ f(xᵏ) + ∇f(xᵏ)ᵀ(x - xᵏ)
   • 其中梯度∇f(x) = [4(x₁ - 2)³, 2(x₂ - 3)]
   • 因此凸近似为：f̃(x) = (x₁ᵏ - 2)⁴ + (x₂ᵏ - 3)² + 4(x₁ᵏ - 2)³(x₁ - x₁ᵏ) + 2(x₂ᵏ - 3)(x₂ - x₂ᵏ)

2. 约束的处理：

   • g₁(x)已经是凸的，保持原形式
   • g₂(x)和g₃(x)是线性的，保持原形式

第四步：完整SCP迭代格式
在第k次迭代中，求解以下凸优化子问题：
最小化 f̃(x) = (x₁ᵏ - 2)⁴ + (x₂ᵏ - 3)² + 4(x₁ᵏ - 2)³(x₁ - x₁ᵏ) + 2(x₂ᵏ - 3)(x₂ - x₂ᵏ)
满足：
x₁² + x₂² - 4 ≤ 0
-x₁ ≤ 0
-x₂ ≤ 0

第五步：选择初始点并开始迭代

1. 选择初始点：x⁰ = (1, 1)（可行点，满足所有约束）
2. 第一次迭代(k=0)：
   • 计算梯度：∇f(1,1) = [4(1-2)³, 2(1-3)] = [-4, -4]
   • 构建近似目标：f̃(x) = (1-2)⁴ + (1-3)² + (-4)(x₁-1) + (-4)(x₂-1) = 1 + 4 -4x₁+4 -4x₂+4 = -4x₁ -4x₂ + 13
   • 求解凸子问题：最小化 -4x₁ -4x₂，约束不变
   • 最优解：x¹ = (√2, √2) ≈ (1.414, 1.414)（在约束边界上）

第六步：继续迭代

1. 第二次迭代(k=1)：

   • 在x¹ = (1.414, 1.414)处线性化
   • 计算梯度：∇f(1.414,1.414) = [4(1.414-2)³, 2(1.414-3)] ≈ [-0.79, -3.17]
   • 构建新的凸近似子问题并求解
   • 得到x² ≈ (1.5, 1.32)

2. 重复此过程，直到‖xᵏ⁺¹ - xᵏ‖ < ε（如ε=10⁻⁶）

第七步：收敛性分析
经过多次迭代后，算法会收敛到局部最优解。对于这个问题，全局最优解在约束边界x₁² + x₂² = 4上，且靠近点(2,3)的方向。

第八步：最终结果
SCP算法最终会收敛到近似最优解x* ≈ (1.2, 1.8)，对应的目标函数值f(x*) ≈ 1.5。这个解满足所有约束条件，且是原问题的局部最优解。

SCP算法的优势在于它将复杂的非凸问题转化为一系列相对容易求解的凸问题，适用于许多工程优化问题。