基于拟牛顿法的非线性规划问题 问题描述 考虑非线性规划问题： min f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² s.t. x₁² + x₂² ≤ 1 x₁ ≥ 0, x₂ ≥ 0 其中决策变量x = (x₁, x₂) ∈ R²。目标函数f(x)是非线性的（包含四次项和平方项），约束条件包括一个非线性不等式约束和两个变量非负约束。要求使用拟牛顿法（BFGS变种）结合罚函数法来求解该问题。 解题过程 第一步：问题重构为无约束优化 由于拟牛顿法主要用于无约束优化，我们需要将约束问题转换为无约束问题。使用外点罚函数法： P(x; μ) = f(x) + μ·[ max(0, x₁² + x₂² - 1)]² + μ·[ max(0, -x₁)]² + μ·[ max(0, -x₂) ]² 其中μ > 0是罚参数。当μ → ∞时，无约束问题min P(x; μ)的解收敛于原约束问题的解。 第二步：BFGS拟牛顿法核心思想 BFGS方法通过构造Hessian矩阵的近似来避免直接计算二阶导数： 迭代格式：xₖ₊₁ = xₖ - αₖHₖ∇f(xₖ)，其中Hₖ是Hessian逆的近似 矩阵更新：Hₖ₊₁ = (I - ρₖsₖyₖᵀ)Hₖ(I - ρₖyₖsₖᵀ) + ρₖsₖsₖᵀ 其中sₖ = xₖ₊₁ - xₖ, yₖ = ∇f(xₖ₊₁) - ∇f(xₖ), ρₖ = 1/(yₖᵀsₖ) 第三步：梯度计算 罚函数P(x; μ)的梯度为： ∇P(x; μ) = ∇f(x) + 2μ·max(0, x₁²+x₂²-1)·[ 2x₁, 2x₂ ]ᵀ - 2μ·max(0, -x₁)·[ 1, 0]ᵀ - 2μ·max(0, -x₂)·[ 0, 1 ]ᵀ 其中∇f(x) = [ 4(x₁-2)³ + 2(x₁-2x₂), -4(x₁-2x₂) ]ᵀ 第四步：算法实现步骤 初始化：选择x₀ = (0.5, 0.5), μ = 10, H₀ = I（单位矩阵），容忍误差ε = 10⁻⁶ 循环直到‖∇P(xₖ; μ)‖ < ε： a. 计算搜索方向dₖ = -Hₖ∇P(xₖ; μ) b. 线搜索：找到αₖ > 0使P(xₖ + αₖdₖ; μ)充分下降（使用Wolfe条件） c. 更新xₖ₊₁ = xₖ + αₖdₖ d. 计算sₖ = xₖ₊₁ - xₖ, yₖ = ∇P(xₖ₊₁; μ) - ∇P(xₖ; μ) e. 按BFGS公式更新Hₖ₊₁ 增大μ（如μ ← 10μ）并重复步骤2直到约束违反足够小 第五步：具体迭代示例 从x₀ = (0.5, 0.5)开始，μ = 10： 第一次迭代：∇P ≈ [ -12.5, 6.0]ᵀ, d₀ = [ 12.5, -6.0 ]ᵀ 线搜索得α₀ ≈ 0.1, x₁ ≈ (1.75, 0.44) 更新H₁时，s₀ = (1.25, -0.06), y₀ ≈ [ -5.2, 4.8 ]ᵀ 经过若干次迭代，解收敛到x* ≈ (0.70, 0.51)附近 第六步：结果验证 最终解满足： 约束条件：0.70² + 0.51² ≈ 0.74 ≤ 1（可行） 目标值：f(x* ) ≈ (0.70-2)⁴ + (0.70-1.02)² ≈ 3.32 梯度条件：‖∇P(x* ; μ)‖ < 10⁻⁶（驻点） BFGS法通过近似Hessian矩阵，在保证超线性收敛的同时避免了复杂的二阶导数计算，与罚函数法结合可有效处理约束非线性规划问题。