非线性规划中的序列凸近似信赖域法基础题 题目描述： 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 满足约束条件： h(x) = x₁² - x₂ = 0 g(x) = x₁ + x₂ - 1 ≤ 0 其中 x = (x₁, x₂) ∈ ℝ²。 这是一个具有非线性目标函数、等式约束和不等式约束的优化问题。我们需要使用序列凸近似信赖域法来求解该问题。 解题过程： 算法基本原理 序列凸近似信赖域法结合了两种思想： 序列凸近似：在每次迭代时，将非凸函数近似为凸函数 信赖域：限制步长大小，确保近似的有效性 该方法通过迭代求解一系列凸优化子问题来逼近原问题的最优解。 构建凸近似子问题 在第k次迭代点x₍ᵏ⁾处，我们构建如下凸近似子问题： 最小化 f̂₍ᵏ⁾(d) = ∇f(x₍ᵏ⁾)ᵀd + ½dᵀB₍ᵏ⁾d 满足： ĥ₍ᵏ⁾(d) = h(x₍ᵏ⁾) + ∇h(x₍ᵏ⁾)ᵀd = 0 ĝ₍ᵏ⁾(d) = g(x₍ᵏ⁾) + ∇g(x₍ᵏ⁾)ᵀd ≤ 0 ‖d‖ ≤ Δ₍ᵏ⁾ 其中d = x - x₍ᵏ⁾是搜索方向，B₍ᵏ⁾是Hessian矩阵的近似，Δ₍ᵏ⁾是当前信赖域半径。 计算梯度和Hessian近似 首先计算目标函数和约束的梯度： ∇f(x) = [ 4(x₁ - 2)³ + 2(x₁ - 2x₂), -4(x₁ - 2x₂) ] ∇h(x) = [ 2x₁, -1 ] ∇g(x) = [ 1, 1 ] 我们使用BFGS公式更新Hessian近似B₍ᵏ⁾： B₍ᵏ⁺¹⁾ = B₍ᵏ⁾ + (y yᵀ)/(yᵀs) - (B₍ᵏ⁾s sᵀB₍ᵏ⁾)/(sᵀB₍ᵏ⁾s) 其中s = x₍ᵏ⁺¹⁾ - x₍ᵏ⁾，y = ∇L(x₍ᵏ⁺¹⁾, λ₍ᵏ⁺¹⁾) - ∇L(x₍ᵏ⁾, λ₍ᵏ⁺¹⁾) ∇L(x, λ)是拉格朗日函数的梯度。 初始点选择 选择初始点x₍⁰⁾ = (0, 0)，初始信赖域半径Δ₍⁰⁾ = 1.0，初始Hessian近似B₍⁰⁾ = I（单位矩阵）。 第一次迭代（k=0） 在x₍⁰⁾ = (0, 0)处： f(x₍⁰⁾) = 16 ∇f(x₍⁰⁾) = [ 4(-2)³ + 2(0), -4(0)] = [ -32, 0 ] h(x₍⁰⁾) = 0，∇h(x₍⁰⁾) = [ 0, -1 ] g(x₍⁰⁾) = -1 ≤ 0，∇g(x₍⁰⁾) = [ 1, 1 ] 子问题为： 最小化 f̂₍⁰⁾(d) = [ -32, 0 ]ᵀd + ½dᵀI d 满足： [ 0, -1 ]ᵀd = 0 [ 1, 1 ]ᵀd - 1 ≤ 0 ‖d‖ ≤ 1 求解得d₍⁰⁾ ≈ (0.5, 0.5)，x₍¹⁾ = x₍⁰⁾ + d₍⁰⁾ = (0.5, 0.5) 接受性检验 计算实际下降量：Δf_ actual = f(x₍⁰⁾) - f(x₍¹⁾) = 16 - 5.0625 = 10.9375 预测下降量：Δf_ predicted = f̂₍⁰⁾(0) - f̂₍⁰⁾(d₍⁰⁾) = 0 - (-14.5) = 14.5 比值ρ = Δf_ actual/Δf_ predicted ≈ 0.754 由于ρ > 0.25，接受该步长，更新x₍¹⁾ = (0.5, 0.5) 信赖域半径调整 由于ρ ≈ 0.754 > 0.75，扩大信赖域半径：Δ₍¹⁾ = 2.0 × Δ₍⁰⁾ = 2.0 继续迭代 重复上述过程，直到满足收敛条件‖∇L(x₍ᵏ⁾, λ₍ᵏ⁾)‖ < ε（如ε = 10⁻⁶） 经过约6次迭代后，算法收敛到近似最优解x* ≈ (1.0, 1.0)，f(x* ) ≈ 0.0 收敛性分析 序列凸近似信赖域法在适当条件下具有全局收敛性，能够处理非凸问题，同时通过信赖域机制保证算法的稳定性。