非线性规划中的序列凸近似信赖域反射混合算法进阶题 题目描述： 考虑非线性规划问题： minimize f(x) = (x₁-2)⁴ + (x₁-2x₂)² subject to g₁(x) = x₁² - x₂ ≤ 0 g₂(x) = -x₁ ≤ 0 g₃(x) = -x₂ ≤ 0 其中x = (x₁, x₂) ∈ ℝ²。这是一个具有非凸目标函数和凸约束的非线性规划问题。 解题过程： 算法概述 序列凸近似信赖域反射混合算法结合了序列凸近似(SCA)和信赖域反射(TR)方法的优点。基本思想是在每个迭代点，将原问题近似为一个凸子问题，然后使用信赖域反射方法求解该子问题。 初始化 选择初始点x⁰ = (0.5, 0.5)，初始信赖域半径Δ₀ = 0.5，参数η = 0.1（接受阈值），γ₁ = 0.5（收缩因子），γ₂ = 2.0（扩张因子），最大迭代次数K = 100。 构建凸近似子问题 在当前迭代点xᵏ = (x₁ᵏ, x₂ᵏ)，构建目标函数的凸近似： f̃ᵏ(x) = f(xᵏ) + ∇f(xᵏ)ᵀ(x - xᵏ) + ½(x - xᵏ)ᵀBᵏ(x - xᵏ) 其中Hessian矩阵Bᵏ需要保证正定性。对于约束，由于原约束已经是凸的，可以直接使用： g̃₁(x) = x₁² - x₂ ≤ 0 g̃₂(x) = -x₁ ≤ 0 g̃₃(x) = -x₂ ≤ 0 计算梯度和Hessian近似 目标函数f(x) = (x₁-2)⁴ + (x₁-2x₂)²的梯度为： ∇f(x) = [ 4(x₁-2)³ + 2(x₁-2x₂), -4(x₁-2x₂) ]ᵀ 在x⁰ = (0.5, 0.5)处： ∇f(x⁰) = [ 4(0.5-2)³ + 2(0.5-1), -4(0.5-1)] = [ 4(-1.5)³ + 2(-0.5), -4(-0.5)] = [ -13.5 -1, 2] = [ -14.5, 2 ]ᵀ 精确Hessian为： ∇²f(x) = [ [ 12(x₁-2)² + 2, -4], [ -4, 8] ] 在x⁰处：∇²f(x⁰) = [ [ 12(2.25)+2, -4], [ -4, 8]] = [ [ 29, -4], [ -4, 8] ] 由于此Hessian是正定的，可直接用作B⁰。 求解凸子问题 在信赖域‖x - xᵏ‖ ≤ Δᵏ内求解： minimize f̃ᵏ(x) subject to g̃ᵢ(x) ≤ 0, i=1,2,3 ‖x - xᵏ‖ ≤ Δᵏ 使用信赖域反射方法求解该子问题： 计算候选步长d 投影到可行域 计算实际下降量ared = f(xᵏ) - f(xᵏ + d) 计算预测下降量pred = f̃ᵏ(xᵏ) - f̃ᵏ(xᵏ + d) 接受性检验和信赖域更新 计算比值ρ = ared/pred 如果ρ ≥ η，接受步长：xᵏ⁺¹ = xᵏ + d 否则拒绝步长：xᵏ⁺¹ = xᵏ 更新信赖域半径： 如果ρ < 0.25：Δᵏ⁺¹ = γ₁Δᵏ 如果ρ > 0.75：Δᵏ⁺¹ = γ₂Δᵏ 否则：Δᵏ⁺¹ = Δᵏ 收敛性检查 检查以下收敛条件： ‖∇f(xᵏ) + ∑λᵢ∇gᵢ(xᵏ)‖ ≤ ε₁ （KKT条件） |f(xᵏ) - f(xᵏ⁻¹)| ≤ ε₂|f(xᵏ⁻¹)| （函数值变化） ‖xᵏ - xᵏ⁻¹‖ ≤ ε₃ （变量变化） 其中ε₁, ε₂, ε₃为预设的容差。 迭代过程 重复步骤3-7直到满足收敛条件或达到最大迭代次数。该算法通过序列凸近似保证了子问题的可解性，通过信赖域反射方法保证了全局收敛性，特别适合处理非凸优化问题。