非线性规划中的序列凸近似(SCA)算法基础题

题目描述：考虑非线性规划问题 min f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)²，其中 x ∈ ℝ²。目标函数包含非凸项 (x₁ - 2)⁴ 和耦合项 (x₁ - 2x₂)²。要求使用序列凸近似（SCA）算法求解该问题，通过迭代构造凸替代函数逼近原问题，并分析收敛性。

解题过程：

1. 问题分析
   目标函数 f(x) 由两部分组成：(x₁ - 2)⁴ 是四阶非凸项，(x₁ - 2x₂)² 是二次项但耦合了变量。直接求解需处理非凸性。SCA的核心思想是：在每步迭代点 xᵏ 处，构造一个凸替代函数 f̃(x; xᵏ)，使其满足：

   • f̃(x; xᵏ) 在 xᵏ 处与 f(x) 函数值相等：f̃(xᵏ; xᵏ) = f(xᵏ)。
   • f̃(x; xᵏ) 是凸函数，便于优化。
   • f̃(x; xᵏ) 是 f(x) 的上界或局部近似。

2. 构造凸替代函数
   对于非凸项 (x₁ - 2)⁴，其在 xᵏ 处的凸近似可通过一阶泰勒展开或凸分解实现。这里采用凸包络思想：

   • 令 g(x₁) = (x₁ - 2)⁴，其二阶导数 g''(x₁) = 12(x₁ - 2)² ≥ 0，但四阶项整体非凸。我们将其在 x₁ᵏ 处线性化，并添加一个二次正则项以保持凸性：
     g̃(x₁; x₁ᵏ) = g(x₁ᵏ) + g'(x₁ᵏ)(x₁ - x₁ᵏ) + (τ/2)(x₁ - x₁ᵏ)²，
     其中 g'(x₁) = 4(x₁ - 2)³，τ 是足够大的正数（如 τ ≥ max|g''(x₁)| 的估计值）以确保凸性。
   • 对于耦合项 (x₁ - 2x₂)²，本身是凸函数（二次型正定），可直接保留。
     因此，替代函数为：
     f̃(x; xᵏ) = g̃(x₁; x₁ᵏ) + (x₁ - 2x₂)²。

3. 迭代步骤

   • 步骤 0：初始化
     选择初始点 x⁰ = (0, 0)，正则化参数 τ = 50（经验值，需满足 τ ≥ 12(x₁ - 2)² 在域内的上界）。设定容忍误差 ε = 10⁻⁶。
   • 步骤 1：构造子问题
     在第 k 步迭代点 xᵏ = (x₁ᵏ, x₂ᵏ) 处，计算：
     g(x₁ᵏ) = (x₁ᵏ - 2)⁴，
     g'(x₁ᵏ) = 4(x₁ᵏ - 2)³。
     子问题为凸优化问题：
     min f̃(x; xᵏ) = g(x₁ᵏ) + g'(x₁ᵏ)(x₁ - x₁ᵏ) + (τ/2)(x₁ - x₁ᵏ)² + (x₁ - 2x₂)²。
   • 步骤 2：求解子问题
     子问题目标函数是二次凸函数，可通过梯度为零求解析解。令 ∇f̃ = 0：
     ∂f̃/∂x₁ = g'(x₁ᵏ) + τ(x₁ - x₁ᵏ) + 2(x₁ - 2x₂) = 0，
     ∂f̃/∂x₂ = -4(x₁ - 2x₂) = 0。
     由第二式得 x₁ = 2x₂，代入第一式：
     g'(x₁ᵏ) + τ(x₁ - x₁ᵏ) + 2(0) = 0 → x₁ = x₁ᵏ - g'(x₁ᵏ)/τ。
     因此，更新解为 x₁ᵏ⁺¹ = x₁ᵏ - g'(x₁ᵏ)/τ，x₂ᵏ⁺¹ = x₁ᵏ⁺¹/2。
   • 步骤 3：收敛判断
     计算连续迭代点差 ‖xᵏ⁺¹ - xᵏ‖ ≤ ε 或函数值变化 |f(xᵏ⁺¹) - f(xᵏ)| ≤ ε。若满足，停止；否则 k = k+1，返回步骤 1。

4. 数值实验与收敛性

   • 从 x⁰ = (0,0) 开始：
     k=0: x₁⁰=0, g'(0)=4(-2)³=-32, x₁¹=0 - (-32)/50=0.64, x₂¹=0.32, f(x¹)= (0.64-2)⁴ + (0.64-0.64)² ≈ 5.31。
     k=1: x₁¹=0.64, g'(0.64)=4(-1.36)³≈-10.07, x₁²=0.64 - (-10.07)/50≈0.841, x₂²=0.4205, f(x²)≈2.90。
     迭代至 x* ≈ (1.5, 0.75) 时，f(x*) ≈ 0.0625，梯度接近零。
   • 收敛性分析：SCA 算法在替代函数满足局部上界条件（或梯度一致性条件）时，能收敛到驻点。本例中，由于正则项 τ 足够大，替代函数是 f(x) 的全局上界，保证单调下降。

5. 总结
   SCA 通过分解非凸函数为凸近似序列，将原问题转化为一系列凸子问题。关键点包括：替代函数的构造（如线性化加正则项）、子问题的高效求解、参数 τ 的选择以保持凸性。该方法适用于工程中的非凸优化，如资源分配和机器学习模型训练。