非线性规划中的序列二次规划(SQP)算法进阶题：带非线性不等式约束的优化问题

字数 4598 2025-12-06 22:40:12

非线性规划中的序列二次规划(SQP)算法进阶题：带非线性不等式约束的优化问题

题目描述
考虑如下非线性约束优化问题：

最小化目标函数：
\(f(x)1 = (x_1 - 2)^2 + (x_2 - 1)^2\)
满足约束：
\(g_1(x) = x_1^2 - x_2 \leq 0\)
\(g_2(x) = x_1 + x_2 - 2 \leq 0\)
初始点 \(x^{(0)} = (0, 0)^T\)。

使用序列二次规划（SQP）算法求解该问题，要求详细说明SQP算法的迭代过程，包括拉格朗日函数的构建、二次规划子问题的构造、步长的计算和迭代更新规则，并分析算法的收敛性。目标是最小化 \(f(x)\)，同时满足所有约束。

解题过程

SQP算法是一种通过序列求解二次规划子问题来逼近原问题的迭代方法。我们将逐步推导。

步骤1：构造拉格朗日函数
原问题的拉格朗日函数为：

\[L(x, \lambda) = f(x) + \lambda_1 g_1(x) + \lambda_2 g_2(x) \]

其中 \(\lambda = (\lambda_1, \lambda_2)^T\) 是拉格朗日乘子向量（非负，对应不等式约束）。

步骤2：SQP子问题的构造
在每次迭代点 \(x^{(k)}\)，SQP需要构造一个二次规划子问题。这个子问题的目标函数是原拉格朗日函数在 \(x^{(k)}\) 处的二阶近似，约束是原约束在 \(x^{(k)}\) 处的一阶线性近似。

(1) 计算当前点的梯度信息：
目标函数梯度：
\(\nabla f(x) = [2(x_1 - 2), \; 2(x_2 - 1)]^T\)
约束梯度：
\(\nabla g_1(x) = [2x_1, \; -1]^T\)
\(\nabla g_2(x) = [1, \; 1]^T\)

(2) 构造二次规划子问题的目标函数：
子问题的决策变量是步长 \(d = x - x^{(k)}\)。目标函数为：

\[Q(d) = \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_k d \]

其中 \(B_k\) 是拉格朗日函数的Hessian矩阵近似（初始可用单位矩阵，后续用拟牛顿法更新）。

(3) 构造线性化约束：
将 \(g_j(x) \approx g_j(x^{(k)}) + \nabla g_j(x^{(k)})^T d \leq 0\) 作为子问题的约束。

步骤3：第一次迭代（k=0）
初始点 \(x^{(0)} = (0, 0)^T\)，初始乘子 \(\lambda^{(0)} = (0, 0)^T\)（可任意初始化，通常取零）。

计算初始点的函数值和梯度：

\(f(x^{(0)}) = 4 + 1 = 5\)
\(\nabla f(x^{(0)}) = [-4, \; -2]^T\)
\(g_1(x^{(0)}) = 0\)（在边界上），\(g_2(x^{(0)}) = -2\)（严格满足）
\(\nabla g_1(x^{(0)}) = [0, \; -1]^T\)，\(\nabla g_2(x^{(0)}) = [1, \; 1]^T\)
初始 \(B_0 = I_2\)（单位矩阵）。

构建第一个二次规划子问题：
最小化 \(Q(d) = [-4, -2] d + \frac{1}{2} d^T I_2 d\)
满足约束：
\(0 + [0, -1] d \leq 0\) → \(-d_2 \leq 0\) → \(d_2 \geq 0\)
\(-2 + [1, 1] d \leq 0\) → \(d_1 + d_2 \leq 2\)

这是一个简单的二次规划，用KKT条件求解。
目标函数为凸二次函数，约束线性。解为 \(d_0 = (d_1, d_2)^T\) 满足：

从第一个约束：\(d_2 \ge 0\)。
第二个约束：\(d_1 + d_2 \le 2\)。
无约束最优解（梯度为零点）：由 \(\nabla Q(d) = 0\) 得 \(d = (4, 2)^T\)，但违反约束 \(d_1+d_2=6 > 2\)，因此最优解在约束边界上。

通过分析，在 \(d_1+d_2=2\) 上求解最小化 \(Q(d) = -4d_1 -2d_2 + 0.5(d_1^2 + d_2^2)\)，代入 \(d_2=2-d_1\) 得单变量函数，求导得到最优解为 \(d_1 = 3, d_2 = -1\)，但 \(d_2 = -1 < 0\) 违反第一个约束。考虑两约束的交点：由 \(d_2=0\) 和 \(d_1+d_2=2\) 得 \(d=(2,0)\)。此时目标值 \(Q = -8 + 0.5(4+0) = -6\)；检查另一个边界点 \(d_2 \ge 0\) 和 \(d_1+d_2=2\) 且在 \(d_2\) 最小的点就是 \((2,0)\)。因此子问题最优解为 \(d_0 = (2, 0)^T\)。

计算步长 \(\alpha\)（通常用线搜索，这里为简化先取 \(\alpha=1\)）：
\(x^{(1)} = x^{(0)} + d_0 = (2, 0)^T\)。
更新乘子：子问题的解会给出新的乘子估计 \(\lambda^{(1)}\)（子问题对应的乘子）。

步骤4：拟牛顿法更新Hessian近似（BFGS公式）
SQP中常用BFGS公式更新 \(B_k\)，以近似拉格朗日函数的Hessian。定义：
\(s_k = x^{(k+1)} - x^{(k)}\)，
\(y_k = \nabla_x L(x^{(k+1)}, \lambda^{(k+1)}) - \nabla_x L(x^{(k)}, \lambda^{(k+1)})\)。
BFGS更新：

\[B_{k+1} = B_k + \frac{y_k y_k^T}{y_k^T s_k} - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k} \]

但第一次迭代时 \(B_0 = I\)，我们可用此公式逐步更新。

步骤5：收敛判断
SQP算法迭代终止条件通常包括：

步长足够小：\(\| d_k \| < \epsilon\)。
原问题的KKT条件残差足够小：
\(\| \nabla f(x^{(k)}) + \sum \lambda_j \nabla g_j(x^{(k)}) \| < \epsilon\)
\(|\lambda_j g_j(x^{(k)})| < \epsilon\)，且 \(g_j(x^{(k)}) \le 0, \lambda_j \ge 0\)。

步骤6：完整迭代示例（继续迭代一次）
第二次迭代（k=1）：
点 \(x^{(1)} = (2, 0)^T\)
计算：

\(f(x^{(1)}) = 0 + 1 = 1\)
\(\nabla f = [0, -2]^T\)
\(g_1 = 4 - 0 = 4 > 0\)（违反！说明 \(\alpha=1\) 不可行，需要回溯线搜索）

修正：实际上，第一次迭代中 \(\alpha=1\) 导致不可行点，因此必须引入线搜索，在SQP中通常使用“价值函数”（如精确罚函数）来确保收敛。常见的价值函数是 \(\phi(x) = f(x) + \mu \sum \max(0, g_j(x))\)，其中 \(\mu\) 是罚参数。

回溯线搜索：从 \(\alpha=1\) 开始，如果价值函数不下降，则减少 \(\alpha\)。这里，在 \(\alpha=1\) 时，\(g_1=4\) 违反，价值函数变大，因此需缩小 \(\alpha\)。设 \(\alpha=0.5\)，则：
\(x^{(1)} = (0,0) + 0.5*(2,0) = (1, 0)\)
检查：\(g_1 = 1 - 0 = 1 > 0\) 仍违反。再缩小，比如 \(\alpha=0.25\)：
\(x^{(1)} = (0.5, 0)\)
此时 \(g_1 = 0.25 - 0 = 0.25 > 0\) 还是违反。
直到 \(\alpha\) 很小时，约束才满足。这显示了SQP中初始点不可行时，需要恰当处理。实际算法通常允许子问题不可行或采用可行QP子问题形式。

简化处理：我们改为从可行初始点开始，比如 \(x^{(0)} = (0.5, 0.5)^T\)，然后迭代。但为保持原题初始点，我们采用“可行SQP”变体，在子问题中增加松弛变量保证可行性。

步骤7：最终收敛
经过多次迭代（调整步长、更新Bk、解QP子问题），序列会收敛到原问题的KKT点。对于本题，理论最优解是 \(x^* = (1, 1)^T\)，此时 \(f=1\)，约束 \(g_1=0\)（活跃），\(g_2=0\)（活跃）。对应的乘子 \(\lambda_1=2, \lambda_2=0\)（由KKT条件解出）。

算法总结：

初始化 \(x^{(0)}, \lambda^{(0)}, B_0\)（通常 \(B_0 = I\)）。
循环直到收敛：
a. 计算 \(f, g_j, \nabla f, \nabla g_j\) 在当前点的值。
b. 构造QP子问题：
最小化 \(\nabla f^T d + \frac12 d^T B d\)
满足 \(g_j + \nabla g_j^T d \le 0\)。
c. 求解该QP，得到步长 \(d_k\) 和乘子估计 \(\lambda_q\)。
d. 更新乘子：\(\lambda^{(k+1)} = \lambda_q\)。
e. 线搜索：沿 \(d_k\) 搜索，使用价值函数（如精确罚函数）确定步长 \(\alpha\)。
f. 更新迭代点：\(x^{(k+1)} = x^{(k)} + \alpha d_k\)。
g. 用BFGS公式更新 \(B_{k+1}\)。
输出 \(x^{(k+1)}\) 作为近似最优解。

收敛性分析：
在适当条件下（如目标与约束函数二阶连续可微，Hessian近似一致正定，严格互补条件等），SQP算法局部二阶收敛。如果初始点靠近解且乘子估计准确，通常几步即可达到很高精度。

非线性规划中的序列二次规划(SQP)算法进阶题：带非线性不等式约束的优化问题题目描述考虑如下非线性约束优化问题：最小化目标函数： \( f(x)1 = (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \) 满足约束： \( g_ 1(x) = x_ 1^2 - x_ 2 \leq 0 \) \( g_ 2(x) = x_ 1 + x_ 2 - 2 \leq 0 \) 初始点 \( x^{(0)} = (0, 0)^T \)。使用序列二次规划（SQP）算法求解该问题，要求详细说明SQP算法的迭代过程，包括拉格朗日函数的构建、二次规划子问题的构造、步长的计算和迭代更新规则，并分析算法的收敛性。目标是最小化 \( f(x) \)，同时满足所有约束。解题过程 SQP算法是一种通过序列求解二次规划子问题来逼近原问题的迭代方法。我们将逐步推导。步骤1：构造拉格朗日函数原问题的拉格朗日函数为： \[ L(x, \lambda) = f(x) + \lambda_ 1 g_ 1(x) + \lambda_ 2 g_ 2(x) \] 其中 \( \lambda = (\lambda_ 1, \lambda_ 2)^T \) 是拉格朗日乘子向量（非负，对应不等式约束）。步骤2：SQP子问题的构造在每次迭代点 \( x^{(k)} \)，SQP需要构造一个二次规划子问题。这个子问题的目标函数是原拉格朗日函数在 \( x^{(k)} \) 处的二阶近似，约束是原约束在 \( x^{(k)} \) 处的一阶线性近似。 (1) 计算当前点的梯度信息：目标函数梯度： \( \nabla f(x) = [ 2(x_ 1 - 2), \; 2(x_ 2 - 1) ]^T \) 约束梯度： \( \nabla g_ 1(x) = [ 2x_ 1, \; -1 ]^T \) \( \nabla g_ 2(x) = [ 1, \; 1 ]^T \) (2) 构造二次规划子问题的目标函数：子问题的决策变量是步长 \( d = x - x^{(k)} \)。目标函数为： \[ Q(d) = \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_ k d \] 其中 \( B_ k \) 是拉格朗日函数的Hessian矩阵近似（初始可用单位矩阵，后续用拟牛顿法更新）。 (3) 构造线性化约束：将 \( g_ j(x) \approx g_ j(x^{(k)}) + \nabla g_ j(x^{(k)})^T d \leq 0 \) 作为子问题的约束。步骤3：第一次迭代（k=0）初始点 \( x^{(0)} = (0, 0)^T \)，初始乘子 \( \lambda^{(0)} = (0, 0)^T \)（可任意初始化，通常取零）。计算初始点的函数值和梯度： \( f(x^{(0)}) = 4 + 1 = 5 \) \( \nabla f(x^{(0)}) = [ -4, \; -2 ]^T \) \( g_ 1(x^{(0)}) = 0 \)（在边界上），\( g_ 2(x^{(0)}) = -2 \)（严格满足） \( \nabla g_ 1(x^{(0)}) = [ 0, \; -1]^T \)，\( \nabla g_ 2(x^{(0)}) = [ 1, \; 1 ]^T \) 初始 \( B_ 0 = I_ 2 \)（单位矩阵）。构建第一个二次规划子问题：最小化 \( Q(d) = [ -4, -2] d + \frac{1}{2} d^T I_ 2 d \) 满足约束： \( 0 + [ 0, -1] d \leq 0 \) → \( -d_ 2 \leq 0 \) → \( d_ 2 \geq 0 \) \( -2 + [ 1, 1] d \leq 0 \) → \( d_ 1 + d_ 2 \leq 2 \) 这是一个简单的二次规划，用KKT条件求解。目标函数为凸二次函数，约束线性。解为 \( d_ 0 = (d_ 1, d_ 2)^T \) 满足：从第一个约束：\( d_ 2 \ge 0 \)。第二个约束：\( d_ 1 + d_ 2 \le 2 \)。无约束最优解（梯度为零点）：由 \( \nabla Q(d) = 0 \) 得 \( d = (4, 2)^T \)，但违反约束 \( d_ 1+d_ 2=6 > 2 \)，因此最优解在约束边界上。通过分析，在 \( d_ 1+d_ 2=2 \) 上求解最小化 \( Q(d) = -4d_ 1 -2d_ 2 + 0.5(d_ 1^2 + d_ 2^2) \)，代入 \( d_ 2=2-d_ 1 \) 得单变量函数，求导得到最优解为 \( d_ 1 = 3, d_ 2 = -1 \)，但 \( d_ 2 = -1 < 0 \) 违反第一个约束。考虑两约束的交点：由 \( d_ 2=0 \) 和 \( d_ 1+d_ 2=2 \) 得 \( d=(2,0) \)。此时目标值 \( Q = -8 + 0.5(4+0) = -6 \)；检查另一个边界点 \( d_ 2 \ge 0 \) 和 \( d_ 1+d_ 2=2 \) 且在 \( d_ 2 \) 最小的点就是 \( (2,0) \)。因此子问题最优解为 \( d_ 0 = (2, 0)^T \)。计算步长 \( \alpha \)（通常用线搜索，这里为简化先取 \( \alpha=1 \)）： \( x^{(1)} = x^{(0)} + d_ 0 = (2, 0)^T \)。更新乘子：子问题的解会给出新的乘子估计 \( \lambda^{(1)} \)（子问题对应的乘子）。步骤4：拟牛顿法更新Hessian近似（BFGS公式） SQP中常用BFGS公式更新 \( B_ k \)，以近似拉格朗日函数的Hessian。定义： \( s_ k = x^{(k+1)} - x^{(k)} \)， \( y_ k = \nabla_ x L(x^{(k+1)}, \lambda^{(k+1)}) - \nabla_ x L(x^{(k)}, \lambda^{(k+1)}) \)。 BFGS更新： \[ B_ {k+1} = B_ k + \frac{y_ k y_ k^T}{y_ k^T s_ k} - \frac{B_ k s_ k s_ k^T B_ k}{s_ k^T B_ k s_ k} \] 但第一次迭代时 \( B_ 0 = I \)，我们可用此公式逐步更新。步骤5：收敛判断 SQP算法迭代终止条件通常包括：步长足够小：\( \| d_ k \| < \epsilon \)。原问题的KKT条件残差足够小： \( \| \nabla f(x^{(k)}) + \sum \lambda_ j \nabla g_ j(x^{(k)}) \| < \epsilon \) \( |\lambda_ j g_ j(x^{(k)})| < \epsilon \)，且 \( g_ j(x^{(k)}) \le 0, \lambda_ j \ge 0 \)。步骤6：完整迭代示例（继续迭代一次）第二次迭代（k=1）：点 \( x^{(1)} = (2, 0)^T \) 计算： \( f(x^{(1)}) = 0 + 1 = 1 \) \( \nabla f = [ 0, -2 ]^T \) \( g_ 1 = 4 - 0 = 4 > 0 \)（违反！说明 \( \alpha=1 \) 不可行，需要回溯线搜索）修正：实际上，第一次迭代中 \( \alpha=1 \) 导致不可行点，因此必须引入线搜索，在SQP中通常使用“价值函数”（如精确罚函数）来确保收敛。常见的价值函数是 \( \phi(x) = f(x) + \mu \sum \max(0, g_ j(x)) \)，其中 \( \mu \) 是罚参数。回溯线搜索：从 \( \alpha=1 \) 开始，如果价值函数不下降，则减少 \( \alpha \)。这里，在 \( \alpha=1 \) 时，\( g_ 1=4 \) 违反，价值函数变大，因此需缩小 \( \alpha \)。设 \( \alpha=0.5 \)，则： \( x^{(1)} = (0,0) + 0.5* (2,0) = (1, 0) \) 检查：\( g_ 1 = 1 - 0 = 1 > 0 \) 仍违反。再缩小，比如 \( \alpha=0.25 \)： \( x^{(1)} = (0.5, 0) \) 此时 \( g_ 1 = 0.25 - 0 = 0.25 > 0 \) 还是违反。直到 \( \alpha \) 很小时，约束才满足。这显示了SQP中初始点不可行时，需要恰当处理。实际算法通常允许子问题不可行或采用可行QP子问题形式。简化处理：我们改为从可行初始点开始，比如 \( x^{(0)} = (0.5, 0.5)^T \)，然后迭代。但为保持原题初始点，我们采用“可行SQP”变体，在子问题中增加松弛变量保证可行性。步骤7：最终收敛经过多次迭代（调整步长、更新Bk、解QP子问题），序列会收敛到原问题的KKT点。对于本题，理论最优解是 \( x^* = (1, 1)^T \)，此时 \( f=1 \)，约束 \( g_ 1=0 \)（活跃），\( g_ 2=0 \)（活跃）。对应的乘子 \( \lambda_ 1=2, \lambda_ 2=0 \)（由KKT条件解出）。算法总结：初始化 \( x^{(0)}, \lambda^{(0)}, B_ 0 \)（通常 \( B_ 0 = I \)）。循环直到收敛： a. 计算 \( f, g_ j, \nabla f, \nabla g_ j \) 在当前点的值。 b. 构造QP子问题：最小化 \( \nabla f^T d + \frac12 d^T B d \) 满足 \( g_ j + \nabla g_ j^T d \le 0 \)。 c. 求解该QP，得到步长 \( d_ k \) 和乘子估计 \( \lambda_ q \)。 d. 更新乘子：\( \lambda^{(k+1)} = \lambda_ q \)。 e. 线搜索：沿 \( d_ k \) 搜索，使用价值函数（如精确罚函数）确定步长 \( \alpha \)。 f. 更新迭代点：\( x^{(k+1)} = x^{(k)} + \alpha d_ k \)。 g. 用BFGS公式更新 \( B_ {k+1} \)。输出 \( x^{(k+1)} \) 作为近似最优解。收敛性分析：在适当条件下（如目标与约束函数二阶连续可微，Hessian近似一致正定，严格互补条件等），SQP算法局部二阶收敛。如果初始点靠近解且乘子估计准确，通常几步即可达到很高精度。