基于梯度投影的序列二次规划(GP-SQP)算法基础题
我将为您讲解基于梯度投影的序列二次规划(Gradient Projection based Sequential Quadratic Programming, GP-SQP)算法。这是一种结合了梯度投影法和序列二次规划的高效优化算法。
问题描述
考虑如下非线性约束优化问题：
min f(x) = (x₁ - 2)² + (x₂ - 1)²
s.t. g₁(x) = x₁ + x₂ - 2 ≤ 0
g₂(x) = x₁² - x₂ ≤ 0
h(x) = x₁ - x₂ = 0
其中x = (x₁, x₂) ∈ ℝ²。这是一个典型的非线性规划问题，包含不等式约束和等式约束。
算法原理
GP-SQP算法的核心思想是：在每次迭代中，先使用梯度投影法将当前点投影到可行域附近，然后基于投影后的点构建二次规划子问题，通过求解该子问题获得搜索方向。
解题步骤
步骤1：初始化
选择初始点x⁰ = (0, 0)，设定容许误差ε = 10⁻⁶，最大迭代次数K = 100，令k = 0。
计算初始点的约束违反度：
- g₁(x⁰) = 0 + 0 - 2 = -2 ≤ 0 （满足）
- g₂(x⁰) = 0 - 0 = 0 ≤ 0 （满足）
- h(x⁰) = 0 - 0 = 0 = 0 （满足）
步骤2：梯度投影修正
对于当前迭代点xᵏ，计算其到可行域的投影。投影操作通过求解以下问题实现：
min ‖x - xᵏ‖²
s.t. g(x) ≤ 0, h(x) = 0
在实际计算中，我们采用简化方法：对于等式约束h(x) = x₁ - x₂ = 0，我们可以直接令x₂ = x₁，将问题降维。
投影后的点为：x̃ᵏ = (x₁, x₁)，其中x₁通过求解以下一维问题确定：
min (x₁ - x₁ᵏ)² + (x₁ - x₂ᵏ)²
s.t. 2x₁ - 2 ≤ 0, x₁² - x₁ ≤ 0
步骤3：构建二次规划子问题
在投影点x̃ᵏ处构建二次规划子问题：
目标函数二次近似：
min ∇f(x̃ᵏ)ᵀd + ½dᵀBᵏd
其中：
- ∇f(x̃ᵏ) = [2(x̃₁ - 2), 2(x̃₂ - 1)]ᵀ
- Bᵏ是Hessian矩阵的近似（初始为单位矩阵）
约束线性化：
∇g₁(x̃ᵏ)ᵀd + g₁(x̃ᵏ) ≤ 0
∇g₂(x̃ᵏ)ᵀd + g₂(x̃ᵏ) ≤ 0
∇h(x̃ᵏ)ᵀd + h(x̃ᵏ) = 0
具体计算：
- ∇g₁(x̃ᵏ) = [1, 1]ᵀ
- ∇g₂(x̃ᵏ) = [2x̃₁, -1]ᵀ
- ∇h(x̃ᵏ) = [1, -1]ᵀ
步骤4：求解二次规划子问题
通过拉格朗日乘子法或积极集法求解上述QP问题，得到搜索方向dᵏ和拉格朗日乘子估计λᵏ。
对于我们的具体问题，由于有等式约束x₁ = x₂，搜索方向d = (d₁, d₂)需要满足d₁ = d₂。
步骤5：线搜索确定步长
沿着方向dᵏ进行线搜索，找到步长αᵏ使得：
f(x̃ᵏ + αᵏdᵏ) < f(x̃ᵏ)
且满足约束条件或惩罚函数下降。
常用的线搜索准则包括Armijo准则、Wolfe条件等。
步骤6：更新迭代点
xᵏ⁺¹ = x̃ᵏ + αᵏdᵏ
更新Hessian近似矩阵Bᵏ⁺¹（通常采用BFGS公式）：
Bᵏ⁺¹ = Bᵏ - (Bᵏs)(Bᵏs)ᵀ/(sᵀBᵏs) + yyᵀ/(yᵀs)
其中s = xᵏ⁺¹ - x̃ᵏ，y = ∇L(xᵏ⁺¹, λᵏ⁺¹) - ∇L(x̃ᵏ, λᵏ)
步骤7：收敛性检验
检查是否满足收敛条件：
- ‖∇L(xᵏ⁺¹, λᵏ⁺¹)‖ ≤ ε
- ‖xᵏ⁺¹ - xᵏ‖ ≤ ε
- 约束违反度小于ε
如果满足则停止，否则令k = k+1，返回步骤2。
算法优势
GP-SQP算法结合了梯度投影法的快速可行性和SQP算法的超线性收敛性，特别适合处理中等规模的非线性约束优化问题。投影步骤能有效处理边界约束，而SQP步骤能精确处理非线性约束。