非线性规划中的逐步凸逼近算法基础题 题目描述 考虑非线性规划问题： 最小化 f(x) = (x₁-2)⁴ + (x₂-3)² 满足约束条件： g₁(x) = x₁² + x₂² - 4 ≤ 0 g₂(x) = -x₁ ≤ 0 g₃(x) = -x₂ ≤ 0 这是一个具有非线性目标函数和非线性约束的优化问题。我们将使用逐步凸逼近算法（Successive Convex Approximation, SCA）求解该问题。 算法原理 SCA算法的核心思想是将原非凸问题在每次迭代时用凸近似问题替代，通过求解一系列凸子问题逐步逼近原问题的最优解。 解题步骤 步骤1：初始化 选择初始点 x⁰ = [ 1, 1 ]（满足约束条件） 设置收敛容差 ε = 10⁻⁴ 设置最大迭代次数 K = 100 令 k = 0 步骤2：构造凸近似子问题 在当前迭代点 xᵏ = [ x₁ᵏ, x₂ᵏ ] 处，我们需要构造原问题的凸近似： 目标函数 f(x) 的凸近似： f(x) = (x₁-2)⁴ + (x₂-3)² 在 xᵏ 处的一阶泰勒展开为： f̃(x; xᵏ) = f(xᵏ) + ∇f(xᵏ)ᵀ(x - xᵏ) + ½(x - xᵏ)ᵀD(x - xᵏ) 其中梯度 ∇f(x) = [ 4(x₁-2)³, 2(x₂-3) ] 为了确保凸性，我们添加正则化项，选择 D = diag(d₁, d₂)，其中 dᵢ 足够大以保证凸性。 约束函数 g₁(x) 的凸近似： g̃₁(x; xᵏ) = (x₁ᵏ)² + (x₂ᵏ)² + 2x₁ᵏ(x₁ - x₁ᵏ) + 2x₂ᵏ(x₂ - x₂ᵏ) - 4 ≤ 0 步骤3：求解凸子问题 在第 k 次迭代，我们需要求解以下凸优化问题： 最小化 f̃(x; xᵏ) 满足： g̃₁(x; xᵏ) ≤ 0 -x₁ ≤ 0 -x₂ ≤ 0 这是一个二次规划问题，可以使用标准凸优化方法求解。 步骤4：更新迭代点 设 yᵏ 为步骤3中求得的解，更新迭代点： xᵏ⁺¹ = xᵏ + γᵏ(yᵏ - xᵏ) 其中 γᵏ ∈ (0,1 ] 是步长参数，通常使用恒定步长或线搜索确定。 步骤5：收敛性检查 计算相邻两次迭代点的变化量： ∥xᵏ⁺¹ - xᵏ∥ ≤ ε 如果满足收敛条件或达到最大迭代次数，则停止；否则令 k = k+1，返回步骤2。 数值计算示例 以初始点 x⁰ = [ 1,1 ] 为例： 第一次迭代： ∇f([ 1,1]) = [ 4(1-2)³, 2(1-3)] = [ -4, -4 ] f([ 1,1 ]) = (1-2)⁴ + (1-3)² = 1 + 4 = 5 构造凸子问题并求解，假设得到 y⁰ = [ 1.2, 1.3 ] 取步长 γ⁰ = 0.5，则 x¹ = [ 1,1] + 0.5×([ 1.2,1.3]-[ 1,1]) = [ 1.1, 1.15 ] 重复此过程，算法将收敛到近似最优解。 算法特点 适用于非凸约束优化问题 每次迭代求解凸子问题，计算相对高效 收敛到局部最优解 需要合理选择近似函数和步长策略