新的、未在列表中出现过的非线性规划算法题目
字数 7589 2025-12-19 07:49:56

好的，我将为你生成一个新的、未在列表中出现过的非线性规划算法题目，并详细讲解。

非线性规划中的连续二次规划（Sequential Quadratic Programming, SQP）算法基础题

题目描述

考虑一个标准的非线性规划问题：

\[\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & c_i(x) = 0, \quad i \in \mathcal{E} \quad (\text{等式约束}), \\ & c_i(x) \ge 0, \quad i \in \mathcal{I} \quad (\text{不等式约束}), \end{aligned} \]

其中，目标函数 \(f(x)\) 和约束函数 \(c_i(x)\) 都是二阶连续可微的（即 \(f, c_i \in C^2\)）。

给定一个初始点 \(x_0\)，该点不一定是可行的（即可能不满足所有约束）。要求你利用 连续二次规划（SQP） 方法的基本思想，迭代求解该问题，最终找到一个满足 Karush-Kuhn-Tucker（KKT） 条件的局部最优解。

为了具体说明，我们假设一个简单实例：

\[\begin{aligned} \min \quad & f(x) = (x_1 - 2)^2 + (x_2 - 1)^2 \\ \text{s.t.} \quad & c_1(x) = x_1 + x_2 - 2 = 0, \\ & c_2(x) = x_1^2 - x_2 \ge 0. \end{aligned} \]

初始点设为 \(x_0 = (0, 0)\)。

请描述SQP方法的核心迭代步骤，并针对这个具体实例，手工推导出第一次迭代（从 \(x_0\) 到 \(x_1\) ）的完整计算过程。

解题过程详解

连续二次规划（SQP）是求解中小规模、光滑非线性规划问题最有效的方法之一。其核心思想是：在每一步迭代，用一个二次规划（QP）子问题来近似原问题，求解这个QP子问题得到搜索方向，然后沿此方向进行线性搜索，更新迭代点。

第一步：理解SQP的基本迭代格式

SQP算法从一个初始点 \(x_k\) 和对拉格朗日乘子 \(\lambda_k\)、\(\mu_k\) 的估计开始（初始乘子可以设为0）。在第 \(k\) 次迭代，我们构造一个二次规划（QP）子问题。

原问题的拉格朗日函数为：

\[\mathcal{L}(x， \lambda， \mu) = f(x) - \sum_{i \in \mathcal{E}} \lambda_i c_i(x) - \sum_{i \in \mathcal{I}} \mu_i c_i(x)。 \]

第k次迭代的QP子问题为：

\[\begin{aligned} \min_{d \in \mathbb{R}^n} \quad & \frac{1}{2} d^T \nabla_{xx}^2 \mathcal{L}(x_k， \lambda_k， \mu_k) d + \nabla f(x_k)^T d \\ \text{s.t.} \quad & \nabla c_i(x_k)^T d + c_i(x_k) = 0, \quad i \in \mathcal{E}, \\ & \nabla c_i(x_k)^T d + c_i(x_k) \ge 0, \quad i \in \mathcal{I}. \end{aligned} \]

其中：

  • \(d = x - x_k\) 是我们要寻找的搜索方向。
  • 目标函数是原拉格朗日函数在 \(x_k\) 处的二阶泰勒展开（关于 \(x\) ）去掉常数项。
  • 约束条件是原约束函数在 \(x_k\) 处的一阶线性近似。

解这个QP子问题，得到搜索方向 \(d_k\) 和对应的QP乘子估计 \(\hat{\lambda}_{k+1}, \hat{\mu}_{k+1}\)。

然后更新迭代点：

\[x_{k+1} = x_k + \alpha_k d_k， \]

其中步长 \(\alpha_k \in (0, 1]\) 通常通过一个线性搜索（如Wolfe条件或罚函数）来确定，以保证收敛性。拉格朗日乘子也更新为QP子问题给出的估计值：\(\lambda_{k+1} = \hat{\lambda}_{k+1}, \mu_{k+1} = \hat{\mu}_{k+1}\)。

第二步：应用于具体实例

现在我们针对给定的实例，手动执行第一次迭代 \(k=0\)。

  1. 定义函数与初始点

    • 目标函数：\(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)
    • 等式约束：\(c_1(x) = x_1 + x_2 - 2 = 0\)
    • 不等式约束：\(c_2(x) = x_1^2 - x_2 \ge 0\)
    • 初始点：\(x_0 = (0， 0)^T\)
    • 初始乘子估计（通常设为零）：\(\lambda_0 = 0\) (对应 \(c_1\))， \(\mu_0 = 0\) (对应 \(c_2\))。

  2. 计算在 \(x_0\) 处的梯度与约束值

    • 梯度：

\[ \nabla f(x) = \begin{pmatrix} 2(x_1 - 2) \\ 2(x_2 - 1) \end{pmatrix}, \quad \nabla f(x_0) = \begin{pmatrix} -4 \\ -2 \end{pmatrix} \]

\[ \nabla c_1(x) = \begin{pmatrix} 1 \\ 1 \end{pmatrix}, \quad \nabla c_1(x_0) = \begin{pmatrix} 1 \\ 1 \end{pmatrix} \]

\[ \nabla c_2(x) = \begin{pmatrix} 2x_1 \\ -1 \end{pmatrix}, \quad \nabla c_2(x_0) = \begin{pmatrix} 0 \\ -1 \end{pmatrix} \]

- 约束函数值：

\[ c_1(x_0) = 0 + 0 - 2 = -2 \quad (\text{不满足等式约束}) \]

\[ c_2(x_0) = 0 - 0 = 0 \quad (\text{满足不等式约束，且处于边界}) \]

  1. 构造拉格朗日函数并计算其Hessian矩阵
    • 拉格朗日函数：\(\mathcal{L}(x， \lambda， \mu) = f(x) - \lambda c_1(x) - \mu c_2(x)\)
    • 拉格朗日函数的Hessian（关于 \(x\) ）：

\[ \nabla_{xx}^2 \mathcal{L}(x， \lambda， \mu) = \nabla^2 f(x) - \lambda \nabla^2 c_1(x) - \mu \nabla^2 c_2(x) \]

- 计算各函数的Hessian：

\[ \nabla^2 f(x) = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}, \quad \nabla^2 c_1(x) = \mathbf{0}_{2 \times 2}, \quad \nabla^2 c_2(x) = \begin{pmatrix} 2 & 0 \\ 0 & 0 \end{pmatrix} \]

- 在点 $x_0$， 使用初始乘子 $\lambda_0 = 0， \mu_0 = 0$：

\[ \nabla_{xx}^2 \mathcal{L}(x_0， \lambda_0， \mu_0) = \nabla^2 f(x_0) = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} \]

  这个矩阵是正定的，非常好，意味着QP子问题是凸的，容易求解。

  1. 构造并求解第0次迭代的QP子问题
    将上面计算的梯度和约束函数值代入QP子问题公式。令搜索方向 \(d = (d_1， d_2)^T\)。

    QP子问题（在 \(x_0\) 处）：

\[ \begin{aligned} \min_{d} \quad & \frac{1}{2} (d_1， d_2) \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} \begin{pmatrix} d_1 \\ d_2 \end{pmatrix} + (-4， -2) \begin{pmatrix} d_1 \\ d_2 \end{pmatrix} \\ \text{s.t.} \quad & (1, 1) \begin{pmatrix} d_1 \\ d_2 \end{pmatrix} + (-2) = 0 \quad \Rightarrow \quad d_1 + d_2 = 2， \\ & (0, -1) \begin{pmatrix} d_1 \\ d_2 \end{pmatrix} + (0) \ge 0 \quad \Rightarrow \quad -d_2 \ge 0 \quad \Rightarrow \quad d_2 \le 0。 \end{aligned} \]

化简目标函数：

\[ \frac{1}{2} (2d_1^2 + 2d_2^2) - 4d_1 - 2d_2 = d_1^2 + d_2^2 - 4d_1 - 2d_2。 \]

我们可以将其配方：$(d_1 - 2)^2 + (d_2 - 1)^2 - 5$。最小化这个目标等价于最小化 $(d_1-2)^2 + (d_2-1)^2$。

所以，QP子问题的几何意义是：在可行域（一条直线 $d_1+d_2=2$ 和半个平面 $d_2 \le 0$ 的交集）上，找到距离点 $(2， 1)$ 最近的点。
  1. 求解QP子问题
    • 首先，忽略不等式约束 \(d_2 \le 0\)。在直线 \(d_1+d_2=2\) 上距离 \((2,1)\) 最近的点可以通过投影得到。设该点为 \((p_1, p_2)\)，它满足 \(p_1+p_2=2\)，且向量 \((p_1-2， p_2-1)\) 与直线的方向向量 \((1，-1)\) （注意，直线法向量是 \((1,1)\)，方向向量与之垂直）垂直（即内积为0）。计算可得：

\[ (p_1-2) - (p_2-1) = 0 \quad \Rightarrow \quad p_1 - p_2 = 1。 \]

  联立 $p_1 + p_2 = 2$ 和 $p_1 - p_2 = 1$，解得 $p_1 = 1.5, p_2 = 0.5$。
- 检查不等式约束：$p_2 = 0.5 > 0$，不满足 $d_2 \le 0$。因此，该点不是可行解。
- 当不等式约束起作用（active）时，最优解应落在直线 $d_1+d_2=2$ 与直线 $d_2=0$ 的交点上。
- 联立 $d_1+d_2=2$ 和 $d_2=0$，得到 $d_1=2， d_2=0$。即 $d_0 = (2， 0)^T$。
- 验证：该点满足 $d_2=0 \le 0$。我们需要确认在可行域内没有其他点能给出更小的目标函数值。从几何上看，可行域是直线段 $d_1 \in [2， \infty)$， $d_2=0$。目标函数在 $d_2=0$ 时变为 $(d_1-2)^2 + 1$，在 $d_1=2$ 时取得最小值1。所以 $d_0=(2,0)$ 确实是QP子问题的解。
  1. 确定QP乘子
    • 对于这个解，不等式约束 \(d_2 \le 0\) 是起作用的（active）。
    • 我们需要找到乘子 \(\hat{\lambda}_1\) (对应 \(c_1\)) 和 \(\hat{\mu}_1\) (对应 \(c_2\)，且 \(\hat{\mu}_1 \ge 0\))。
    • 根据QP子问题的KKT条件：

\[ \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} \begin{pmatrix} 2 \\ 0 \end{pmatrix} + \begin{pmatrix} -4 \\ -2 \end{pmatrix} - \hat{\lambda}_1 \begin{pmatrix} 1 \\ 1 \end{pmatrix} - \hat{\mu}_1 \begin{pmatrix} 0 \\ -1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \]

  代入 $d_0 = (2,0)^T$：

\[ \begin{pmatrix} 4 \\ 0 \end{pmatrix} + \begin{pmatrix} -4 \\ -2 \end{pmatrix} - \hat{\lambda}_1 \begin{pmatrix} 1 \\ 1 \end{pmatrix} - \hat{\mu}_1 \begin{pmatrix} 0 \\ -1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \]

  即：

\[ \begin{pmatrix} 0 \\ -2 \end{pmatrix} - \begin{pmatrix} \hat{\lambda}_1 \\ \hat{\lambda}_1 \end{pmatrix} - \begin{pmatrix} 0 \\ -\hat{\mu}_1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \]

  分量形式为：

\[ 0 - \hat{\lambda}_1 = 0 \quad \Rightarrow \quad \hat{\lambda}_1 = 0 \]

\[ -2 - \hat{\lambda}_1 + \hat{\mu}_1 = 0 \quad \Rightarrow \quad -2 - 0 + \hat{\mu}_1 = 0 \quad \Rightarrow \quad \hat{\mu}_1 = 2 \quad (\text{满足} \ge 0) \]

- 所以，QP乘子为 $\hat{\lambda}_1 = 0$， $\hat{\mu}_1 = 2$。
  1. 更新迭代点与乘子（假设步长 \(\alpha_0 = 1\)）
    • 在基础SQP中，为了简化第一次迭代演示，我们常先取完全步长 \(\alpha_0 = 1\)。在实际算法中，会有一个线性搜索过程。
    • 更新迭代点：

\[ x_1 = x_0 + \alpha_0 d_0 = \begin{pmatrix} 0 \\ 0 \end{pmatrix} + 1 \cdot \begin{pmatrix} 2 \\ 0 \end{pmatrix} = \begin{pmatrix} 2 \\ 0 \end{pmatrix} \]

- 更新拉格朗日乘子：

\[ \lambda_1 = \hat{\lambda}_1 = 0， \quad \mu_1 = \hat{\mu}_1 = 2。 \]

第三步：第一次迭代后的结果与后续步骤

完成第一次SQP迭代后：

  • 新的迭代点 \(x_1 = (2， 0)^T\)。
  • 新的乘子估计 \(\lambda_1 = 0， \mu_1 = 2\)。

验证 \(x_1\) 的可行性：

  • \(c_1(x_1) = 2 + 0 - 2 = 0\) ✅ (满足等式约束)
  • \(c_2(x_1) = 2^2 - 0 = 4 \ge 0\) ✅ (满足不等式约束)
    可见，经过一步迭代，我们已经得到了一个可行点。

后续迭代：
算法不会就此停止，因为当前点不一定满足原问题的KKT条件。接下来，需要：

  1. 在 \(x_1\) 处重新计算梯度 \(\nabla f(x_1)\)， \(\nabla c_i(x_1)\)。
  2. 用新的乘子 \(\lambda_1， \mu_1\) 计算完整的拉格朗日函数Hessian \(\nabla_{xx}^2 \mathcal{L}(x_1， \lambda_1， \mu_1)\)。注意，这次Hessian中会包含来自不等式约束 \(c_2\) 的二阶项（因为 \(\mu_1 \neq 0\)）。
  3. 构造并求解在 \(x_1\) 处的新的QP子问题，得到新的搜索方向 \(d_1\) 和乘子估计。
  4. 进行线性搜索确定步长 \(\alpha_1\)， 更新 \(x_2 = x_1 + \alpha_1 d_1\)。
  5. 重复此过程，直到解的变化量或KKT条件的违反程度小于预设的容忍度。

总结

通过这个实例，我们完整演示了SQP算法一次迭代的核心流程：

  1. 线性化约束：将非线性约束在当前点线性化。
  2. 二次近似目标：用拉格朗日函数的二阶近似（Hessian矩阵）作为QP子问题的二次项，用目标函数的梯度作为一次项。
  3. 求解QP子问题：得到搜索方向 \(d_k\) 和新的乘子估计。
  4. 更新：沿 \(d_k\) 方向进行线性搜索更新 \(x_{k+1}\)，并用QP乘子更新拉格朗日乘子。

SQP的魅力在于，其QP子问题的解直接提供了对原问题KKT条件的一个牛顿型修正，因此通常具有超线性甚至二次收敛速度。这个例子中，第一步就从不可行点跳到了一个可行点，展示了它处理约束的强大能力。后续迭代会继续修正，直至找到满足所有一阶最优性条件（KKT条件）的点。

好的，我将为你生成一个 新的、未在列表中出现过的非线性规划算法题目 ，并详细讲解。 非线性规划中的连续二次规划（Sequential Quadratic Programming, SQP）算法基础题 题目描述 考虑一个标准的非线性规划问题： \[ \begin{aligned} \min_ {x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & c_ i(x) = 0, \quad i \in \mathcal{E} \quad (\text{等式约束}), \\ & c_ i(x) \ge 0, \quad i \in \mathcal{I} \quad (\text{不等式约束}), \end{aligned} \] 其中，目标函数 \(f(x)\) 和约束函数 \(c_ i(x)\) 都是二阶连续可微的（即 \(f, c_ i \in C^2\)）。 给定一个初始点 \(x_ 0\)，该点不一定是可行的（即可能不满足所有约束）。要求你利用 连续二次规划（SQP） 方法的基本思想，迭代求解该问题，最终找到一个满足 Karush-Kuhn-Tucker（KKT） 条件的局部最优解。 为了具体说明，我们假设一个简单实例： \[ \begin{aligned} \min \quad & f(x) = (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \\ \text{s.t.} \quad & c_ 1(x) = x_ 1 + x_ 2 - 2 = 0, \\ & c_ 2(x) = x_ 1^2 - x_ 2 \ge 0. \end{aligned} \] 初始点设为 \(x_ 0 = (0, 0)\)。 请描述SQP方法的 核心迭代步骤 ，并针对这个具体实例， 手工推导出第一次迭代（从 \(x_ 0\) 到 \(x_ 1\) ）的完整计算过程 。 解题过程详解 连续二次规划（SQP）是求解中小规模、光滑非线性规划问题最有效的方法之一。其核心思想是：在每一步迭代，用一个二次规划（QP）子问题来近似原问题，求解这个QP子问题得到搜索方向，然后沿此方向进行线性搜索，更新迭代点。 第一步：理解SQP的基本迭代格式 SQP算法从一个初始点 \(x_ k\) 和对拉格朗日乘子 \(\lambda_ k\)、\(\mu_ k\) 的估计开始（初始乘子可以设为0）。在第 \(k\) 次迭代，我们构造一个二次规划（QP）子问题。 原问题的拉格朗日函数 为： \[ \mathcal{L}(x， \lambda， \mu) = f(x) - \sum_ {i \in \mathcal{E}} \lambda_ i c_ i(x) - \sum_ {i \in \mathcal{I}} \mu_ i c_ i(x)。 \] 第k次迭代的QP子问题 为： \[ \begin{aligned} \min_ {d \in \mathbb{R}^n} \quad & \frac{1}{2} d^T \nabla_ {xx}^2 \mathcal{L}(x_ k， \lambda_ k， \mu_ k) d + \nabla f(x_ k)^T d \\ \text{s.t.} \quad & \nabla c_ i(x_ k)^T d + c_ i(x_ k) = 0, \quad i \in \mathcal{E}, \\ & \nabla c_ i(x_ k)^T d + c_ i(x_ k) \ge 0, \quad i \in \mathcal{I}. \end{aligned} \] 其中： \(d = x - x_ k\) 是我们要寻找的搜索方向。 目标函数是原拉格朗日函数在 \(x_ k\) 处的二阶泰勒展开（关于 \(x\) ）去掉常数项。 约束条件是原约束函数在 \(x_ k\) 处的一阶线性近似。 解这个QP子问题，得到 搜索方向 \(d_ k\) 和对应的 QP乘子估计 \(\hat{\lambda} {k+1}, \hat{\mu} {k+1}\) 。 然后更新迭代点： \[ x_ {k+1} = x_ k + \alpha_ k d_ k， \] 其中步长 \(\alpha_ k \in (0, 1]\) 通常通过一个线性搜索（如Wolfe条件或罚函数）来确定，以保证收敛性。拉格朗日乘子也更新为QP子问题给出的估计值：\(\lambda_ {k+1} = \hat{\lambda} {k+1}, \mu {k+1} = \hat{\mu}_ {k+1}\)。 第二步：应用于具体实例 现在我们针对给定的实例，手动执行第一次迭代 \(k=0\)。 定义函数与初始点 目标函数：\(f(x) = (x_ 1 - 2)^2 + (x_ 2 - 1)^2\) 等式约束：\(c_ 1(x) = x_ 1 + x_ 2 - 2 = 0\) 不等式约束：\(c_ 2(x) = x_ 1^2 - x_ 2 \ge 0\) 初始点：\(x_ 0 = (0， 0)^T\) 初始乘子估计（通常设为零）：\(\lambda_ 0 = 0\) (对应 \(c_ 1\))， \(\mu_ 0 = 0\) (对应 \(c_ 2\))。 计算在 \(x_ 0\) 处的梯度与约束值 梯度： \[ \nabla f(x) = \begin{pmatrix} 2(x_ 1 - 2) \\ 2(x_ 2 - 1) \end{pmatrix}, \quad \nabla f(x_ 0) = \begin{pmatrix} -4 \\ -2 \end{pmatrix} \] \[ \nabla c_ 1(x) = \begin{pmatrix} 1 \\ 1 \end{pmatrix}, \quad \nabla c_ 1(x_ 0) = \begin{pmatrix} 1 \\ 1 \end{pmatrix} \] \[ \nabla c_ 2(x) = \begin{pmatrix} 2x_ 1 \\ -1 \end{pmatrix}, \quad \nabla c_ 2(x_ 0) = \begin{pmatrix} 0 \\ -1 \end{pmatrix} \] 约束函数值： \[ c_ 1(x_ 0) = 0 + 0 - 2 = -2 \quad (\text{不满足等式约束}) \] \[ c_ 2(x_ 0) = 0 - 0 = 0 \quad (\text{满足不等式约束，且处于边界}) \] 构造拉格朗日函数并计算其Hessian矩阵 拉格朗日函数：\(\mathcal{L}(x， \lambda， \mu) = f(x) - \lambda c_ 1(x) - \mu c_ 2(x)\) 拉格朗日函数的Hessian（关于 \(x\) ）： \[ \nabla_ {xx}^2 \mathcal{L}(x， \lambda， \mu) = \nabla^2 f(x) - \lambda \nabla^2 c_ 1(x) - \mu \nabla^2 c_ 2(x) \] 计算各函数的Hessian： \[ \nabla^2 f(x) = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}, \quad \nabla^2 c_ 1(x) = \mathbf{0}_ {2 \times 2}, \quad \nabla^2 c_ 2(x) = \begin{pmatrix} 2 & 0 \\ 0 & 0 \end{pmatrix} \] 在点 \(x_ 0\)， 使用初始乘子 \(\lambda_ 0 = 0， \mu_ 0 = 0\)： \[ \nabla_ {xx}^2 \mathcal{L}(x_ 0， \lambda_ 0， \mu_ 0) = \nabla^2 f(x_ 0) = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} \] 这个矩阵是正定的，非常好，意味着QP子问题是凸的，容易求解。 构造并求解第0次迭代的QP子问题 将上面计算的梯度和约束函数值代入QP子问题公式。令搜索方向 \(d = (d_ 1， d_ 2)^T\)。 QP子问题（在 \(x_ 0\) 处） ： \[ \begin{aligned} \min_ {d} \quad & \frac{1}{2} (d_ 1， d_ 2) \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} \begin{pmatrix} d_ 1 \\ d_ 2 \end{pmatrix} + (-4， -2) \begin{pmatrix} d_ 1 \\ d_ 2 \end{pmatrix} \\ \text{s.t.} \quad & (1, 1) \begin{pmatrix} d_ 1 \\ d_ 2 \end{pmatrix} + (-2) = 0 \quad \Rightarrow \quad d_ 1 + d_ 2 = 2， \\ & (0, -1) \begin{pmatrix} d_ 1 \\ d_ 2 \end{pmatrix} + (0) \ge 0 \quad \Rightarrow \quad -d_ 2 \ge 0 \quad \Rightarrow \quad d_ 2 \le 0。 \end{aligned} \] 化简目标函数： \[ \frac{1}{2} (2d_ 1^2 + 2d_ 2^2) - 4d_ 1 - 2d_ 2 = d_ 1^2 + d_ 2^2 - 4d_ 1 - 2d_ 2。 \] 我们可以将其配方：\((d_ 1 - 2)^2 + (d_ 2 - 1)^2 - 5\)。最小化这个目标等价于最小化 \((d_ 1-2)^2 + (d_ 2-1)^2\)。 所以，QP子问题的几何意义是：在可行域（一条直线 \(d_ 1+d_ 2=2\) 和半个平面 \(d_ 2 \le 0\) 的交集）上，找到距离点 \((2， 1)\) 最近的点。 求解QP子问题 首先，忽略不等式约束 \(d_ 2 \le 0\)。在直线 \(d_ 1+d_ 2=2\) 上距离 \((2,1)\) 最近的点可以通过投影得到。设该点为 \((p_ 1, p_ 2)\)，它满足 \(p_ 1+p_ 2=2\)，且向量 \((p_ 1-2， p_ 2-1)\) 与直线的方向向量 \((1，-1)\) （注意，直线法向量是 \((1,1)\)，方向向量与之垂直）垂直（即内积为0）。计算可得： \[ (p_ 1-2) - (p_ 2-1) = 0 \quad \Rightarrow \quad p_ 1 - p_ 2 = 1。 \] 联立 \(p_ 1 + p_ 2 = 2\) 和 \(p_ 1 - p_ 2 = 1\)，解得 \(p_ 1 = 1.5, p_ 2 = 0.5\)。 检查不等式约束：\(p_ 2 = 0.5 > 0\)，不满足 \(d_ 2 \le 0\)。因此，该点不是可行解。 当不等式约束起作用（active）时，最优解应落在直线 \(d_ 1+d_ 2=2\) 与直线 \(d_ 2=0\) 的交点上。 联立 \(d_ 1+d_ 2=2\) 和 \(d_ 2=0\)，得到 \(d_ 1=2， d_ 2=0\)。即 \(d_ 0 = (2， 0)^T\)。 验证：该点满足 \(d_ 2=0 \le 0\)。我们需要确认在可行域内没有其他点能给出更小的目标函数值。从几何上看，可行域是直线段 \(d_ 1 \in [ 2， \infty)\)， \(d_ 2=0\)。目标函数在 \(d_ 2=0\) 时变为 \((d_ 1-2)^2 + 1\)，在 \(d_ 1=2\) 时取得最小值1。所以 \(d_ 0=(2,0)\) 确实是QP子问题的解。 确定QP乘子 对于这个解，不等式约束 \(d_ 2 \le 0\) 是起作用的（active）。 我们需要找到乘子 \(\hat{\lambda}_ 1\) (对应 \(c_ 1\)) 和 \(\hat{\mu}_ 1\) (对应 \(c_ 2\)，且 \(\hat{\mu}_ 1 \ge 0\))。 根据QP子问题的KKT条件： \[ \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} \begin{pmatrix} 2 \\ 0 \end{pmatrix} + \begin{pmatrix} -4 \\ -2 \end{pmatrix} - \hat{\lambda}_ 1 \begin{pmatrix} 1 \\ 1 \end{pmatrix} - \hat{\mu}_ 1 \begin{pmatrix} 0 \\ -1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \] 代入 \(d_ 0 = (2,0)^T\)： \[ \begin{pmatrix} 4 \\ 0 \end{pmatrix} + \begin{pmatrix} -4 \\ -2 \end{pmatrix} - \hat{\lambda}_ 1 \begin{pmatrix} 1 \\ 1 \end{pmatrix} - \hat{\mu}_ 1 \begin{pmatrix} 0 \\ -1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \] 即： \[ \begin{pmatrix} 0 \\ -2 \end{pmatrix} - \begin{pmatrix} \hat{\lambda}_ 1 \\ \hat{\lambda}_ 1 \end{pmatrix} - \begin{pmatrix} 0 \\ -\hat{\mu}_ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \] 分量形式为： \[ 0 - \hat{\lambda}_ 1 = 0 \quad \Rightarrow \quad \hat{\lambda}_ 1 = 0 \] \[ -2 - \hat{\lambda}_ 1 + \hat{\mu}_ 1 = 0 \quad \Rightarrow \quad -2 - 0 + \hat{\mu}_ 1 = 0 \quad \Rightarrow \quad \hat{\mu}_ 1 = 2 \quad (\text{满足} \ge 0) \] 所以，QP乘子为 \(\hat{\lambda}_ 1 = 0\)， \(\hat{\mu}_ 1 = 2\)。 更新迭代点与乘子（假设步长 \(\alpha_ 0 = 1\)） 在基础SQP中，为了简化第一次迭代演示，我们常先取 完全步长 \(\alpha_ 0 = 1\)。在实际算法中，会有一个线性搜索过程。 更新迭代点： \[ x_ 1 = x_ 0 + \alpha_ 0 d_ 0 = \begin{pmatrix} 0 \\ 0 \end{pmatrix} + 1 \cdot \begin{pmatrix} 2 \\ 0 \end{pmatrix} = \begin{pmatrix} 2 \\ 0 \end{pmatrix} \] 更新拉格朗日乘子： \[ \lambda_ 1 = \hat{\lambda}_ 1 = 0， \quad \mu_ 1 = \hat{\mu}_ 1 = 2。 \] 第三步：第一次迭代后的结果与后续步骤 完成第一次SQP迭代后： 新的迭代点 \(x_ 1 = (2， 0)^T\)。 新的乘子估计 \(\lambda_ 1 = 0， \mu_ 1 = 2\)。 验证 \(x_ 1\) 的可行性 ： \(c_ 1(x_ 1) = 2 + 0 - 2 = 0\) ✅ (满足等式约束) \(c_ 2(x_ 1) = 2^2 - 0 = 4 \ge 0\) ✅ (满足不等式约束) 可见，经过一步迭代，我们已经得到了一个 可行点 。 后续迭代 ： 算法不会就此停止，因为当前点不一定满足原问题的KKT条件。接下来，需要： 在 \(x_ 1\) 处重新计算梯度 \(\nabla f(x_ 1)\)， \(\nabla c_ i(x_ 1)\)。 用新的乘子 \(\lambda_ 1， \mu_ 1\) 计算 完整的 拉格朗日函数Hessian \(\nabla_ {xx}^2 \mathcal{L}(x_ 1， \lambda_ 1， \mu_ 1)\)。注意，这次Hessian中会包含来自不等式约束 \(c_ 2\) 的二阶项（因为 \(\mu_ 1 \neq 0\)）。 构造并求解在 \(x_ 1\) 处的新的QP子问题，得到新的搜索方向 \(d_ 1\) 和乘子估计。 进行线性搜索确定步长 \(\alpha_ 1\)， 更新 \(x_ 2 = x_ 1 + \alpha_ 1 d_ 1\)。 重复此过程，直到解的变化量或KKT条件的违反程度小于预设的容忍度。 总结 通过这个实例，我们完整演示了SQP算法一次迭代的核心流程： 线性化约束 ：将非线性约束在当前点线性化。 二次近似目标 ：用拉格朗日函数的二阶近似（Hessian矩阵）作为QP子问题的二次项，用目标函数的梯度作为一次项。 求解QP子问题 ：得到搜索方向 \(d_ k\) 和新的乘子估计。 更新 ：沿 \(d_ k\) 方向进行线性搜索更新 \(x_ {k+1}\)，并用QP乘子更新拉格朗日乘子。 SQP的魅力在于， 其QP子问题的解直接提供了对原问题KKT条件的一个牛顿型修正 ，因此通常具有超线性甚至二次收敛速度。这个例子中，第一步就从不可行点跳到了一个可行点，展示了它处理约束的强大能力。后续迭代会继续修正，直至找到满足所有一阶最优性条件（KKT条件）的点。