非线性规划中的序列二次约束二次规划（SQCQP）算法基础题
字数 7334 2025-12-08 08:07:16

非线性规划中的序列二次约束二次规划（SQCQP）算法基础题

题目描述

考虑如下非线性规划问题：
最小化 \(f(x) = (x_1 - 3)^2 + (x_2 - 4)^2\)
约束条件：

\[\begin{aligned} g_1(x) &= x_1^2 + x_2^2 - 9 \le 0, \\ g_2(x) &= (x_1 - 2)^2 + (x_2 - 3)^2 - 4 \le 0, \\ & -5 \le x_1, x_2 \le 5. \end{aligned} \]

我们将使用序列二次约束二次规划（SQCQP）算法来求解此问题。SQCQP是一种迭代算法，它在每一步迭代中构建并求解一个二次约束二次规划（QCQP）子问题，这个子问题是在当前迭代点对原问题（可能包含非线性目标函数和约束）进行局部近似得到的，然后通过求解这个QCQP子问题得到搜索方向，并沿此方向进行线搜索或信赖域步长控制，以更新迭代点，逐步逼近原问题的最优解。

解题过程

第一步：理解SQCQP算法的基本思想

  1. 核心思想：将复杂的非线性规划问题，在每一步迭代点 \(x^k\) 附近，近似为一个二次目标函数和二次约束的优化子问题（即QCQP子问题）。然后求解这个相对“容易处理”的子问题，得到搜索方向 \(d^k\)，进而更新迭代点 \(x^{k+1} = x^k + \alpha^k d^k\)，其中 \(\alpha^k\) 是步长。
  2. 近似方式：
    • 目标函数 \(f(x)\) 在 \(x^k\) 处进行二阶泰勒展开近似。
    • 约束函数 \(g_i(x)\) 也在 \(x^k\) 处进行二阶泰勒展开近似，但通常只保留到二阶项，使其变为二次约束。有时为了简化计算或保证子问题的凸性，可能会用近似的Hessian矩阵（如BFGS更新）或只使用约束的一阶近似（此时约束变为线性，子问题退化为QP问题）。在SQCQP的严格定义中，子问题的约束是二次的。
  3. 子问题形式（在第k次迭代）：

\[ \begin{aligned} \min_{d \in \mathbb{R}^n} \quad & f(x^k) + \nabla f(x^k)^T d + \frac{1}{2} d^T B_k d \\ \text{s.t.} \quad & g_i(x^k) + \nabla g_i(x^k)^T d + \frac{1}{2} d^T H_{i,k} d \le 0, \quad i = 1, \dots, m, \\ & x_L \le x^k + d \le x_U. \end{aligned} \]

其中：
* $ B_k $ 是目标函数 $ f $ 在 $ x^k $ 处的Hessian矩阵 $ \nabla^2 f(x^k) $ 或其近似（确保子问题易解，如保持正定性）。
* $ H_{i,k} $ 是约束函数 $ g_i $ 在 $ x^k $ 处的Hessian矩阵 $ \nabla^2 g_i(x^k) $ 或其近似。
* 最后一行是变量的简单边界约束，在子问题中通常直接作为线性约束处理（因为 $ x^k $ 是常数）。
  1. 求解与更新：求解上述QCQP子问题，得到最优解 \(d^k\)。然后通过线搜索（如Armijo准则）或信赖域方法确定步长 \(\alpha^k\)，并更新 \(x^{k+1} = x^k + \alpha^k d^k\)。

第二步：应用于具体问题

给定问题中，\(f(x)\) 和 \(g_1(x), g_2(x)\) 本身都是二次函数。因此，它们的二阶泰勒展开是精确的，没有近似误差。这意味着，如果我们精确使用它们的Hessian矩阵来构造SQCQP子问题，那么子问题的解 \(d^k\) 在步长 \(\alpha^k = 1\) 时，只要子问题可行，就能一步（或少数几步）达到原问题的最优解。这非常适合演示SQCQP的流程。

  1. 计算目标函数和约束的梯度与Hessian矩阵：
    • 目标函数：

\[ f(x) = (x_1-3)^2 + (x_2-4)^2, \quad \nabla f(x) = \begin{bmatrix} 2(x_1-3) \\ 2(x_2-4) \end{bmatrix}, \quad \nabla^2 f(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} = B. \]

* 约束 $ g_1(x) = x_1^2 + x_2^2 - 9 $：

\[ \nabla g_1(x) = \begin{bmatrix} 2x_1 \\ 2x_2 \end{bmatrix}, \quad \nabla^2 g_1(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} = H_1. \]

* 约束 $ g_2(x) = (x_1-2)^2 + (x_2-3)^2 - 4 $：

\[ \nabla g_2(x) = \begin{bmatrix} 2(x_1-2) \\ 2(x_2-3) \end{bmatrix}, \quad \nabla^2 g_2(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} = H_2. \]

注意，所有Hessian矩阵都是常数矩阵。
  1. 选择初始点：我们选择初始点 \(x^0 = (0, 0)\)。计算该点的函数值、梯度和约束值：

\[ f(x^0) = 25, \quad \nabla f(x^0) = [-6, -8]^T, \quad g_1(x^0) = -9, \quad g_2(x^0) = (4+9)-4=9. \]

可见，初始点满足 $ g_1(x^0) \le 0 $（可行），但不满足 $ g_2(x^0) \le 0 $（$ g_2(x^0)=9>0 $，不可行）。SQCQP算法可以从不可行点开始。
  1. 构造第一次迭代（k=0）的SQCQP子问题：
    在 \(x^0 = (0,0)\) 处，子问题为：

\[ \begin{aligned} \min_{d} \quad & 25 + [-6, -8] \begin{bmatrix} d_1 \\ d_2 \end{bmatrix} + \frac{1}{2} [d_1, d_2] \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \begin{bmatrix} d_1 \\ d_2 \end{bmatrix} \\ &= 25 -6d_1 -8d_2 + d_1^2 + d_2^2. \quad \text{(常数25可省略，不影响d的优化)} \end{aligned} \]

约束为：

\[ \begin{aligned} g_1(x^0) + \nabla g_1(x^0)^T d + \frac{1}{2} d^T H_1 d &= -9 + [0, 0] d + d_1^2 + d_2^2 \le 0, \\ g_2(x^0) + \nabla g_2(x^0)^T d + \frac{1}{2} d^T H_2 d &= 9 + [-4, -6] d + d_1^2 + d_2^2 \le 0, \\ &-5 \le 0+d_1 \le 5 \quad \Rightarrow \quad -5 \le d_1 \le 5, \\ &-5 \le 0+d_2 \le 5 \quad \Rightarrow \quad -5 \le d_2 \le 5. \end{aligned} \]

简化后，子问题为：

\[ \begin{aligned} \min_{d} \quad & d_1^2 + d_2^2 -6d_1 -8d_2 \\ \text{s.t.} \quad & d_1^2 + d_2^2 \le 9, \\ & d_1^2 + d_2^2 -4d_1 -6d_2 + 9 \le 0, \\ & -5 \le d_1, d_2 \le 5. \end{aligned} \]

注意第二个约束可化简为 $ d_1^2 + d_2^2 -4d_1 -6d_2 + 9 \le 0 $，即 $ (d_1-2)^2 + (d_2-3)^2 \le 4 $。这是一个QCQP问题。

  1. 求解第一个QCQP子问题：
    我们通过观察或数值求解器求解这个子问题。目标函数 \(d_1^2 + d_2^2 -6d_1 -8d_2 = (d_1-3)^2 + (d_2-4)^2 - 25\)，最小化它等价于最小化 \((d_1-3)^2 + (d_2-4)^2\)。约束是两个圆盘：一个是以(0,0)为心、半径为3的圆盘（\(d_1^2+d_2^2 \le 9\)），另一个是以(2,3)为心、半径为2的圆盘（\((d_1-2)^2+(d_2-3)^2 \le 4\)）。我们需要在这两个圆盘的交集内找到最接近点(3,4)的点。

    • 点(3,4)到第一个圆盘(0,0,半径3)的最近点是圆盘边界上从(0,0)到(3,4)射线与边界的交点，即(3,4)方向的单位向量乘以3：\((3*3/5, 4*3/5) = (1.8, 2.4)\)。计算距离：到(3,4)的距离为 \(\sqrt{(3-1.8)^2+(4-2.4)^2} = \sqrt{1.44+2.56}=2.0\)。
    • 点(3,4)到第二个圆盘(2,3,半径2)的最近点是圆盘边界上从(2,3)到(3,4)射线与边界的交点，即(2,3)加上(1,1)方向的单位向量乘以2：\((2+\sqrt{2}, 3+\sqrt{2}) \approx (3.414, 4.414)\)。但此点不在第一个圆盘内（距离原点约 \(\sqrt{3.414^2+4.414^2} \approx 5.55 >3\)），所以不可行。
    • 因此，最优解应在两个圆盘边界的交点上，或者在可行域内部。我们可以通过求解这个QCQP（例如使用凸优化求解器，因为这里目标函数是凸的，约束是凸的圆盘交集，整个QCQP是凸的）得到精确解。直观来看，可行域是两个圆盘的交集。点(3,4)在第一个圆盘外、第二个圆盘外。在交集内寻找最接近(3,4)的点，很可能在第一个圆盘的边界上，且靠近从(0,0)到(3,4)的连线与第二个圆盘的边界附近。通过求解（例如用拉格朗日乘子法或数值求解），我们得到近似最优解为 \(d^0 \approx (1.8, 2.4)\)。我们取此作为子问题的解。

  2. 更新迭代点：
    由于原函数和约束都是二次的，且子问题使用了精确的Hessian，理论上的理想步长 \(\alpha^0 = 1\)。但为了算法的一般性，我们通常进行线搜索以确保收敛（例如Armijo准则）。这里，我们假设线搜索接受了 \(\alpha^0 = 1\)。

\[ x^1 = x^0 + d^0 = (0,0) + (1.8, 2.4) = (1.8, 2.4). \]

计算新点的约束：$ g_1(x^1)=1.8^2+2.4^2-9=3.24+5.76-9=0 $（在边界上），$ g_2(x^1)=(1.8-2)^2+(2.4-3)^2-4=0.04+0.36-4=-3.6 $（可行）。此时第一个约束变为积极约束。
  1. 构造第二次迭代（k=1）的SQCQP子问题：
    在 \(x^1 = (1.8, 2.4)\) 处：
    • \(f(x^1) = (1.8-3)^2+(2.4-4)^2 = 1.44+2.56=4.0\)
    • \(\nabla f(x^1) = [2*(1.8-3), 2*(2.4-4)] = [-2.4, -3.2]\)
    • \(g_1(x^1)=0, \nabla g_1(x^1)=[3.6, 4.8]\)
    • \(g_2(x^1)=-3.6, \nabla g_2(x^1)=[2*(1.8-2), 2*(2.4-3)]=[-0.4, -1.2]\)
      子问题为：

\[ \begin{aligned} \min_{d} \quad & 4.0 + [-2.4, -3.2]d + d_1^2 + d_2^2 \\ \text{s.t.} \quad & 0 + [3.6, 4.8]d + d_1^2 + d_2^2 \le 0, \\ & -3.6 + [-0.4, -1.2]d + d_1^2 + d_2^2 \le 0, \\ & -5 \le 1.8+d_1 \le 5 \quad \Rightarrow \quad -6.8 \le d_1 \le 3.2, \\ & -5 \le 2.4+d_2 \le 5 \quad \Rightarrow \quad -7.4 \le d_2 \le 2.6. \end{aligned} \]

简化目标（省略常数）：$ d_1^2+d_2^2 -2.4d_1 -3.2d_2 = (d_1-1.2)^2+(d_2-1.6)^2 - 1.44-2.56 $。
约束1：$ d_1^2+d_2^2 + 3.6d_1+4.8d_2 \le 0 $，即 $ (d_1+1.8)^2+(d_2+2.4)^2 \le 1.8^2+2.4^2=9 $。
约束2：$ d_1^2+d_2^2 -0.4d_1 -1.2d_2 -3.6 \le 0 $，即 $ (d_1-0.2)^2+(d_2-0.6)^2 \le 4 $。
边界约束略微移动。

  1. 求解第二个QCQP子问题并更新：
    我们需要在可行域（两个圆盘的交集）内最小化到点(1.2,1.6)的距离。此时，当前点 \(x^1\) 对应子问题中的 \(d=0\)，且位于约束1的边界上（因为约束1在 \(d=0\) 时取等号）。求解这个子问题，最优解 \(d^1\) 会试图在满足约束的前提下，让点向目标函数的最低点(3,4)对应的子问题目标点(1.2,1.6)移动。实际上，由于约束1是积极且紧的，子问题的解可能会沿着约束1的边界移动。通过数值求解（或分析），我们可以得到 \(d^1\) 的一个小步，然后更新 \(x^2 = x^1 + d^1\)。由于原问题是凸的（目标函数凸，约束为凸集），且子问题构造精确，算法会快速收敛到全局最优解。

  2. 检查收敛：
    重复上述过程，直到迭代点的变化 \(\|x^{k+1}-x^k\|\) 小于预设容差，或者约束违反度和目标函数梯度满足KKT条件的容差。对于这个具体问题，最优解在 \(g_1(x)=0\) 和 \(g_2(x)=0\) 的交点上，即解方程组：

\[ \begin{cases} x_1^2 + x_2^2 = 9, \\ (x_1-2)^2 + (x_2-3)^2 = 4. \end{cases} \]

相减得：$ x_1^2+x_2^2 - [(x_1-2)^2+(x_2-3)^2] = 9-4 \Rightarrow 4x_1+6x_2 = 18 \Rightarrow 2x_1+3x_2=9 $。代入第一个方程解得：$ x_1 = 1.8, x_2 = 1.8 $（另一解超出边界或不可行）。对应目标值 $ f^* = (1.8-3)^2+(1.8-4)^2 = 1.44+4.84=6.28 $。SQCQP迭代会收敛到这个点。

第三步：算法总结与关键点

  1. 初始化：选择初始点 \(x^0\)，设置收敛容差 \(\epsilon\)，迭代计数器 \(k=0\)。
  2. 迭代步骤：
    a. 构造QCQP子问题：在当前点 \(x^k\)，计算目标函数和约束函数的值、梯度，并获取或近似其Hessian矩阵（对于二次函数，Hessian是常数）。
    b. 求解子问题：求解该QCQP，得到搜索方向 \(d^k\)。如果子问题不可行，可能需要引入松弛变量或调整信赖域半径。
    c. 线搜索：确定步长 \(\alpha^k > 0\)（通常通过Armijo、Wolfe条件等不精确线搜索，或直接取 \(\alpha^k=1\) 如果模型足够精确）。
    d. 更新迭代点：\(x^{k+1} = x^k + \alpha^k d^k\)。
    e. 收敛检查：如果 \(\|x^{k+1}-x^k\| < \epsilon\) 且KKT条件近似满足，则停止；否则令 \(k=k+1\)，返回步骤a。
  3. 关键特性：SQCQP通过在每个迭代点求解一个QCQP子问题来逼近原问题。当原问题的目标函数和约束是二次函数时，若使用精确Hessian，子问题是原问题的精确局部模型，算法可能具有快速收敛性（如一步或两步收敛）。对于一般非线性问题，需要近似Hessian矩阵（例如用BFGS更新），并配合信赖域方法以保证全局收敛性。

这个例子清晰地展示了SQCQP算法如何逐步构造并求解二次约束二次规划子问题，通过迭代逼近原非线性规划问题的最优解。

非线性规划中的序列二次约束二次规划（SQCQP）算法基础题 题目描述 考虑如下非线性规划问题： 最小化 \( f(x) = (x_ 1 - 3)^2 + (x_ 2 - 4)^2 \) 约束条件： \[ \begin{aligned} g_ 1(x) &= x_ 1^2 + x_ 2^2 - 9 \le 0, \\ g_ 2(x) &= (x_ 1 - 2)^2 + (x_ 2 - 3)^2 - 4 \le 0, \\ & -5 \le x_ 1, x_ 2 \le 5. \end{aligned} \] 我们将使用 序列二次约束二次规划（SQCQP）算法 来求解此问题。SQCQP是一种迭代算法，它在每一步迭代中构建并求解一个二次约束二次规划（QCQP）子问题，这个子问题是在当前迭代点对原问题（可能包含非线性目标函数和约束）进行局部近似得到的，然后通过求解这个QCQP子问题得到搜索方向，并沿此方向进行线搜索或信赖域步长控制，以更新迭代点，逐步逼近原问题的最优解。 解题过程 第一步：理解SQCQP算法的基本思想 核心思想 ：将复杂的非线性规划问题，在每一步迭代点 \( x^k \) 附近，近似为一个二次目标函数和二次约束的优化子问题（即QCQP子问题）。然后求解这个相对“容易处理”的子问题，得到搜索方向 \( d^k \)，进而更新迭代点 \( x^{k+1} = x^k + \alpha^k d^k \)，其中 \( \alpha^k \) 是步长。 近似方式 ： 目标函数 \( f(x) \) 在 \( x^k \) 处进行二阶泰勒展开近似。 约束函数 \( g_ i(x) \) 也在 \( x^k \) 处进行二阶泰勒展开近似，但通常只保留到二阶项，使其变为二次约束。有时为了简化计算或保证子问题的凸性，可能会用近似的Hessian矩阵（如BFGS更新）或只使用约束的一阶近似（此时约束变为线性，子问题退化为QP问题）。在SQCQP的严格定义中，子问题的约束是二次的。 子问题形式 （在第k次迭代）： \[ \begin{aligned} \min_ {d \in \mathbb{R}^n} \quad & f(x^k) + \nabla f(x^k)^T d + \frac{1}{2} d^T B_ k d \\ \text{s.t.} \quad & g_ i(x^k) + \nabla g_ i(x^k)^T d + \frac{1}{2} d^T H_ {i,k} d \le 0, \quad i = 1, \dots, m, \\ & x_ L \le x^k + d \le x_ U. \end{aligned} \] 其中： \( B_ k \) 是目标函数 \( f \) 在 \( x^k \) 处的Hessian矩阵 \( \nabla^2 f(x^k) \) 或其近似（确保子问题易解，如保持正定性）。 \( H_ {i,k} \) 是约束函数 \( g_ i \) 在 \( x^k \) 处的Hessian矩阵 \( \nabla^2 g_ i(x^k) \) 或其近似。 最后一行是变量的简单边界约束，在子问题中通常直接作为线性约束处理（因为 \( x^k \) 是常数）。 求解与更新 ：求解上述QCQP子问题，得到最优解 \( d^k \)。然后通过线搜索（如Armijo准则）或信赖域方法确定步长 \( \alpha^k \)，并更新 \( x^{k+1} = x^k + \alpha^k d^k \)。 第二步：应用于具体问题 给定问题中，\( f(x) \) 和 \( g_ 1(x), g_ 2(x) \) 本身都是二次函数。因此，它们的二阶泰勒展开是精确的，没有近似误差。这意味着，如果我们精确使用它们的Hessian矩阵来构造SQCQP子问题，那么子问题的解 \( d^k \) 在步长 \( \alpha^k = 1 \) 时，只要子问题可行，就能一步（或少数几步）达到原问题的最优解。这非常适合演示SQCQP的流程。 计算目标函数和约束的梯度与Hessian矩阵 ： 目标函数： \[ f(x) = (x_ 1-3)^2 + (x_ 2-4)^2, \quad \nabla f(x) = \begin{bmatrix} 2(x_ 1-3) \\ 2(x_ 2-4) \end{bmatrix}, \quad \nabla^2 f(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} = B. \] 约束 \( g_ 1(x) = x_ 1^2 + x_ 2^2 - 9 \)： \[ \nabla g_ 1(x) = \begin{bmatrix} 2x_ 1 \\ 2x_ 2 \end{bmatrix}, \quad \nabla^2 g_ 1(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} = H_ 1. \] 约束 \( g_ 2(x) = (x_ 1-2)^2 + (x_ 2-3)^2 - 4 \)： \[ \nabla g_ 2(x) = \begin{bmatrix} 2(x_ 1-2) \\ 2(x_ 2-3) \end{bmatrix}, \quad \nabla^2 g_ 2(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} = H_ 2. \] 注意，所有Hessian矩阵都是常数矩阵。 选择初始点 ：我们选择初始点 \( x^0 = (0, 0) \)。计算该点的函数值、梯度和约束值： \[ f(x^0) = 25, \quad \nabla f(x^0) = [ -6, -8]^T, \quad g_ 1(x^0) = -9, \quad g_ 2(x^0) = (4+9)-4=9. \] 可见，初始点满足 \( g_ 1(x^0) \le 0 \)（可行），但不满足 \( g_ 2(x^0) \le 0 \)（\( g_ 2(x^0)=9>0 \)，不可行）。SQCQP算法可以从不可行点开始。 构造第一次迭代（k=0）的SQCQP子问题 ： 在 \( x^0 = (0,0) \) 处，子问题为： \[ \begin{aligned} \min_ {d} \quad & 25 + [ -6, -8] \begin{bmatrix} d_ 1 \\ d_ 2 \end{bmatrix} + \frac{1}{2} [ d_ 1, d_ 2] \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \begin{bmatrix} d_ 1 \\ d_ 2 \end{bmatrix} \\ &= 25 -6d_ 1 -8d_ 2 + d_ 1^2 + d_ 2^2. \quad \text{(常数25可省略，不影响d的优化)} \end{aligned} \] 约束为： \[ \begin{aligned} g_ 1(x^0) + \nabla g_ 1(x^0)^T d + \frac{1}{2} d^T H_ 1 d &= -9 + [ 0, 0] d + d_ 1^2 + d_ 2^2 \le 0, \\ g_ 2(x^0) + \nabla g_ 2(x^0)^T d + \frac{1}{2} d^T H_ 2 d &= 9 + [ -4, -6] d + d_ 1^2 + d_ 2^2 \le 0, \\ &-5 \le 0+d_ 1 \le 5 \quad \Rightarrow \quad -5 \le d_ 1 \le 5, \\ &-5 \le 0+d_ 2 \le 5 \quad \Rightarrow \quad -5 \le d_ 2 \le 5. \end{aligned} \] 简化后，子问题为： \[ \begin{aligned} \min_ {d} \quad & d_ 1^2 + d_ 2^2 -6d_ 1 -8d_ 2 \\ \text{s.t.} \quad & d_ 1^2 + d_ 2^2 \le 9, \\ & d_ 1^2 + d_ 2^2 -4d_ 1 -6d_ 2 + 9 \le 0, \\ & -5 \le d_ 1, d_ 2 \le 5. \end{aligned} \] 注意第二个约束可化简为 \( d_ 1^2 + d_ 2^2 -4d_ 1 -6d_ 2 + 9 \le 0 \)，即 \( (d_ 1-2)^2 + (d_ 2-3)^2 \le 4 \)。这是一个QCQP问题。 求解第一个QCQP子问题 ： 我们通过观察或数值求解器求解这个子问题。目标函数 \( d_ 1^2 + d_ 2^2 -6d_ 1 -8d_ 2 = (d_ 1-3)^2 + (d_ 2-4)^2 - 25 \)，最小化它等价于最小化 \( (d_ 1-3)^2 + (d_ 2-4)^2 \)。约束是两个圆盘：一个是以(0,0)为心、半径为3的圆盘（\( d_ 1^2+d_ 2^2 \le 9 \)），另一个是以(2,3)为心、半径为2的圆盘（\( (d_ 1-2)^2+(d_ 2-3)^2 \le 4 \)）。我们需要在 这两个圆盘的交集 内找到最接近点(3,4)的点。 点(3,4)到第一个圆盘(0,0,半径3)的最近点是圆盘边界上从(0,0)到(3,4)射线与边界的交点，即(3,4)方向的单位向量乘以3：\( (3 3/5, 4 3/5) = (1.8, 2.4) \)。计算距离：到(3,4)的距离为 \( \sqrt{(3-1.8)^2+(4-2.4)^2} = \sqrt{1.44+2.56}=2.0 \)。 点(3,4)到第二个圆盘(2,3,半径2)的最近点是圆盘边界上从(2,3)到(3,4)射线与边界的交点，即(2,3)加上(1,1)方向的单位向量乘以2：\( (2+\sqrt{2}, 3+\sqrt{2}) \approx (3.414, 4.414) \)。但此点不在第一个圆盘内（距离原点约 \( \sqrt{3.414^2+4.414^2} \approx 5.55 >3 \)），所以不可行。 因此，最优解应在两个圆盘边界的交点上，或者在可行域内部。我们可以通过求解这个QCQP（例如使用凸优化求解器，因为这里目标函数是凸的，约束是凸的圆盘交集，整个QCQP是凸的）得到精确解。直观来看，可行域是两个圆盘的交集。点(3,4)在第一个圆盘外、第二个圆盘外。在交集内寻找最接近(3,4)的点，很可能在第一个圆盘的边界上，且靠近从(0,0)到(3,4)的连线与第二个圆盘的边界附近。通过求解（例如用拉格朗日乘子法或数值求解），我们得到近似最优解为 \( d^0 \approx (1.8, 2.4) \)。我们取此作为子问题的解。 更新迭代点 ： 由于原函数和约束都是二次的，且子问题使用了精确的Hessian，理论上的理想步长 \( \alpha^0 = 1 \)。但为了算法的一般性，我们通常进行线搜索以确保收敛（例如Armijo准则）。这里，我们假设线搜索接受了 \( \alpha^0 = 1 \)。 \[ x^1 = x^0 + d^0 = (0,0) + (1.8, 2.4) = (1.8, 2.4). \] 计算新点的约束：\( g_ 1(x^1)=1.8^2+2.4^2-9=3.24+5.76-9=0 \)（在边界上），\( g_ 2(x^1)=(1.8-2)^2+(2.4-3)^2-4=0.04+0.36-4=-3.6 \)（可行）。此时第一个约束变为积极约束。 构造第二次迭代（k=1）的SQCQP子问题 ： 在 \( x^1 = (1.8, 2.4) \) 处： \( f(x^1) = (1.8-3)^2+(2.4-4)^2 = 1.44+2.56=4.0 \) \( \nabla f(x^1) = [ 2* (1.8-3), 2* (2.4-4)] = [ -2.4, -3.2 ] \) \( g_ 1(x^1)=0, \nabla g_ 1(x^1)=[ 3.6, 4.8 ] \) \( g_ 2(x^1)=-3.6, \nabla g_ 2(x^1)=[ 2* (1.8-2), 2* (2.4-3)]=[ -0.4, -1.2 ] \) 子问题为： \[ \begin{aligned} \min_ {d} \quad & 4.0 + [ -2.4, -3.2]d + d_ 1^2 + d_ 2^2 \\ \text{s.t.} \quad & 0 + [ 3.6, 4.8]d + d_ 1^2 + d_ 2^2 \le 0, \\ & -3.6 + [ -0.4, -1.2]d + d_ 1^2 + d_ 2^2 \le 0, \\ & -5 \le 1.8+d_ 1 \le 5 \quad \Rightarrow \quad -6.8 \le d_ 1 \le 3.2, \\ & -5 \le 2.4+d_ 2 \le 5 \quad \Rightarrow \quad -7.4 \le d_ 2 \le 2.6. \end{aligned} \] 简化目标（省略常数）：\( d_ 1^2+d_ 2^2 -2.4d_ 1 -3.2d_ 2 = (d_ 1-1.2)^2+(d_ 2-1.6)^2 - 1.44-2.56 \)。 约束1：\( d_ 1^2+d_ 2^2 + 3.6d_ 1+4.8d_ 2 \le 0 \)，即 \( (d_ 1+1.8)^2+(d_ 2+2.4)^2 \le 1.8^2+2.4^2=9 \)。 约束2：\( d_ 1^2+d_ 2^2 -0.4d_ 1 -1.2d_ 2 -3.6 \le 0 \)，即 \( (d_ 1-0.2)^2+(d_ 2-0.6)^2 \le 4 \)。 边界约束略微移动。 求解第二个QCQP子问题并更新 ： 我们需要在可行域（两个圆盘的交集）内最小化到点(1.2,1.6)的距离。此时，当前点 \( x^1 \) 对应子问题中的 \( d=0 \)，且位于约束1的边界上（因为约束1在 \( d=0 \) 时取等号）。求解这个子问题，最优解 \( d^1 \) 会试图在满足约束的前提下，让点向目标函数的最低点(3,4)对应的子问题目标点(1.2,1.6)移动。实际上，由于约束1是积极且紧的，子问题的解可能会沿着约束1的边界移动。通过数值求解（或分析），我们可以得到 \( d^1 \) 的一个小步，然后更新 \( x^2 = x^1 + d^1 \)。由于原问题是凸的（目标函数凸，约束为凸集），且子问题构造精确，算法会快速收敛到全局最优解。 检查收敛 ： 重复上述过程，直到迭代点的变化 \( \|x^{k+1}-x^k\| \) 小于预设容差，或者约束违反度和目标函数梯度满足KKT条件的容差。对于这个具体问题，最优解在 \( g_ 1(x)=0 \) 和 \( g_ 2(x)=0 \) 的交点上，即解方程组： \[ \begin{cases} x_ 1^2 + x_ 2^2 = 9, \\ (x_ 1-2)^2 + (x_ 2-3)^2 = 4. \end{cases} \] 相减得：\( x_ 1^2+x_ 2^2 - [ (x_ 1-2)^2+(x_ 2-3)^2] = 9-4 \Rightarrow 4x_ 1+6x_ 2 = 18 \Rightarrow 2x_ 1+3x_ 2=9 \)。代入第一个方程解得：\( x_ 1 = 1.8, x_ 2 = 1.8 \)（另一解超出边界或不可行）。对应目标值 \( f^* = (1.8-3)^2+(1.8-4)^2 = 1.44+4.84=6.28 \)。SQCQP迭代会收敛到这个点。 第三步：算法总结与关键点 初始化 ：选择初始点 \( x^0 \)，设置收敛容差 \( \epsilon \)，迭代计数器 \( k=0 \)。 迭代步骤 ： a. 构造QCQP子问题 ：在当前点 \( x^k \)，计算目标函数和约束函数的值、梯度，并获取或近似其Hessian矩阵（对于二次函数，Hessian是常数）。 b. 求解子问题 ：求解该QCQP，得到搜索方向 \( d^k \)。如果子问题不可行，可能需要引入松弛变量或调整信赖域半径。 c. 线搜索 ：确定步长 \( \alpha^k > 0 \)（通常通过Armijo、Wolfe条件等不精确线搜索，或直接取 \( \alpha^k=1 \) 如果模型足够精确）。 d. 更新迭代点 ：\( x^{k+1} = x^k + \alpha^k d^k \)。 e. 收敛检查 ：如果 \( \|x^{k+1}-x^k\| < \epsilon \) 且KKT条件近似满足，则停止；否则令 \( k=k+1 \)，返回步骤a。 关键特性 ：SQCQP通过在每个迭代点求解一个QCQP子问题来逼近原问题。当原问题的目标函数和约束是二次函数时，若使用精确Hessian，子问题是原问题的精确局部模型，算法可能具有快速收敛性（如一步或两步收敛）。对于一般非线性问题，需要近似Hessian矩阵（例如用BFGS更新），并配合信赖域方法以保证全局收敛性。 这个例子清晰地展示了SQCQP算法如何逐步构造并求解二次约束二次规划子问题，通过迭代逼近原非线性规划问题的最优解。