非线性规划中的逐步二次规划(SQP)算法基础题 我将为您讲解逐步二次规划(SQP)算法，这是一个重要的非线性规划算法家族。请注意，虽然您列表中包含"序列二次规划法"，但"逐步二次规划"是SQP算法的一种特定实现方式，更强调迭代过程中的逐步逼近特性。 题目描述 考虑以下非线性规划问题： 最小化：f(x) = x₁² + x₂² 约束条件：c(x) = x₁ + x₂ - 2 = 0 初始点：x₀ = (0, 0) 解题过程 1. 算法基本原理 逐步二次规划法的核心思想是：在每次迭代中，将原非线性规划问题近似为一个二次规划(QP)子问题，通过求解这个QP子问题得到搜索方向，然后沿该方向进行线性搜索得到新的迭代点。 2. 构建二次规划子问题 在第k次迭代点xₖ处，我们构建如下QP子问题： 最小化：∇f(xₖ)ᵀd + ½dᵀBₖd 约束条件：c(xₖ) + ∇c(xₖ)ᵀd = 0 其中： d是搜索方向 Bₖ是Hessian矩阵的近似（通常用BFGS公式更新） ∇f(xₖ)是目标函数的梯度 ∇c(xₖ)是约束函数的梯度 3. 计算初始点的梯度信息 在x₀ = (0, 0)处： f(x₀) = 0 ∇f(x₀) = [ 2x₁, 2x₂] = [ 0, 0 ] c(x₀) = 0 + 0 - 2 = -2 ∇c(x₀) = [ 1, 1 ] 初始Hessian近似B₀通常取单位矩阵：B₀ = [ [ 1, 0], [ 0, 1] ] 4. 构建第一个QP子问题 最小化：[ 0, 0]ᵀd + ½dᵀ[ [ 1, 0], [ 0, 1] ]d = ½(d₁² + d₂²) 约束条件：-2 + [ 1, 1 ]ᵀd = 0 ⇒ d₁ + d₂ = 2 5. 求解QP子问题 这是一个简单的等式约束二次规划问题。使用拉格朗日法： L(d, λ) = ½(d₁² + d₂²) + λ(2 - d₁ - d₂) 最优性条件： ∂L/∂d₁ = d₁ - λ = 0 ⇒ d₁ = λ ∂L/∂d₂ = d₂ - λ = 0 ⇒ d₂ = λ ∂L/∂λ = 2 - d₁ - d₂ = 0 解得：λ = 1，d₁ = 1，d₂ = 1 搜索方向d₀ = (1, 1) 6. 线性搜索确定步长 新的迭代点：x₁ = x₀ + αd₀ = (α, α) 其中α通过线性搜索确定，满足目标函数充分下降且满足约束条件。 由于约束是等式约束，我们希望新点满足约束：c(x₁) = α + α - 2 = 0 ⇒ α = 1 因此x₁ = (1, 1) 7. 检查收敛性 在x₁ = (1, 1)处： f(x₁) = 1 + 1 = 2 c(x₁) = 1 + 1 - 2 = 0（满足约束） ∇f(x₁) = [ 2, 2 ] 约束违反度为0 此时已找到最优解，因为： 满足约束条件 目标函数梯度与约束梯度平行：∇f(x) = λ∇c(x)，其中λ=2 8. 算法特点总结 逐步二次规划法的优势在于： 超线性收敛速度 能有效处理等式和不等式约束 通过QP子问题考虑约束的曲率信息 BFGS更新保证Hessian近似保持正定 这个简单例子展示了SQP算法的基本流程：构建QP子问题→求解搜索方向→线性搜索→更新迭代点，直到满足收敛条件。