非线性规划中的序列二次约束二次规划（SQCQP）算法基础题
字数 3312 2025-11-29 14:31:10

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

题目描述
考虑非线性规划问题：
最小化 \(f(x) = (x_1 - 1)^2 + (x_2 - 2)^2\)
约束条件为：

  1. \(g_1(x) = x_1^2 + x_2^2 - 1 \leq 0\)（非线性不等式约束）
  2. \(g_2(x) = x_1 + x_2 - 2 \leq 0\)（线性不等式约束）
  3. \(h(x) = x_1 - x_2^2 = 0\)（非线性等式约束）
    其中 \(x = (x_1, x_2) \in \mathbb{R}^2\)。要求使用序列二次约束二次规划（SQCQP）算法，从初始点 \(x^{(0)} = (0.5, 0.5)\) 出发，迭代求解该问题。

解题过程
SQCQP算法通过序列逼近策略处理非线性约束：每一步在当前迭代点 \(x^{(k)}\) 构造一个二次约束二次规划（QCQP）子问题，通过求解该子问题得到下一步迭代点 \(x^{(k+1)}\)。子问题的目标函数和约束均为原问题的二阶近似，但约束可能被凸化以保证子问题可解。

步骤1：构造第k步QCQP子问题
在点 \(x^{(k)}\) 处，对目标函数 \(f(x)\) 和约束函数进行二阶泰勒展开（忽略高阶项）：

  • 目标函数近似为：
    \(\hat{f}^{(k)}(d) = f(x^{(k)}) + \nabla f(x^{(k)})^T d + \frac{1}{2} d^T \nabla^2 f(x^{(k)}) d\)，
    其中 \(d = x - x^{(k)}\) 是搜索方向。
  • 非线性不等式约束 \(g_1(x) \leq 0\) 近似为：
    \(\hat{g}_1^{(k)}(d) = g_1(x^{(k)}) + \nabla g_1(x^{(k)})^T d + \frac{1}{2} d^T \nabla^2 g_1(x^{(k)}) d \leq 0\)。
  • 线性约束 \(g_2(x) \leq 0\) 保持原形式（因它是线性的，二阶导为零）。
  • 非线性等式约束 \(h(x) = 0\) 近似为：
    \(\hat{h}^{(k)}(d) = h(x^{(k)}) + \nabla h(x^{(k)})^T d + \frac{1}{2} d^T \nabla^2 h(x^{(k)}) d = 0\)。

子问题为：
最小化 \(\hat{f}^{(k)}(d)\)
满足 \(\hat{g}_1^{(k)}(d) \leq 0\), \(g_2(x^{(k)} + d) \leq 0\), \(\hat{h}^{(k)}(d) = 0\)，
并附加信赖域约束 \(\|d\| \leq \Delta^{(k)}\)（控制逼近精度，\(\Delta^{(k)} > 0\) 是信赖域半径）。

步骤2：计算初始点 \(x^{(0)} = (0.5, 0.5)\) 的梯度与Hessian矩阵

  • 目标函数 \(f(x)\)：
    \(\nabla f(x) = [2(x_1 - 1), 2(x_2 - 2)]^T\)，
    \(\nabla^2 f(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}\)（常数矩阵）。
    在 \(x^{(0)}\) 处：
    \(\nabla f(x^{(0)}) = [2(0.5-1), 2(0.5-2)]^T = [-1, -3]^T\)，
    \(f(x^{(0)}) = (0.5-1)^2 + (0.5-2)^2 = 2.5\)。

  • 约束 \(g_1(x) = x_1^2 + x_2^2 - 1\)：
    \(\nabla g_1(x) = [2x_1, 2x_2]^T\)，
    \(\nabla^2 g_1(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}\)。
    在 \(x^{(0)}\) 处：
    \(g_1(x^{(0)}) = 0.5^2 + 0.5^2 - 1 = -0.5\)，
    \(\nabla g_1(x^{(0)}) = [1, 1]^T\)。

  • 约束 \(h(x) = x_1 - x_2^2\)：
    \(\nabla h(x) = [1, -2x_2]^T\)，
    \(\nabla^2 h(x) = \begin{bmatrix} 0 & 0 \\ 0 & -2 \end{bmatrix}\)。
    在 \(x^{(0)}\) 处：
    \(h(x^{(0)}) = 0.5 - 0.5^2 = 0.25\)，
    \(\nabla h(x^{(0)}) = [1, -1]^T\)。

步骤3：求解第0步QCQP子问题
设信赖域半径 \(\Delta^{(0)} = 0.5\)。子问题为：
最小化 \(\hat{f}^{(0)}(d) = 2.5 + [-1, -3] d + \frac{1}{2} d^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} d\)
约束：

  1. \(\hat{g}_1^{(0)}(d) = -0.5 + [1, 1] d + \frac{1}{2} d^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} d \leq 0\)
  2. \(g_2(x^{(0)} + d) = (0.5 + d_1) + (0.5 + d_2) - 2 = d_1 + d_2 - 1 \leq 0\)
  3. \(\hat{h}^{(0)}(d) = 0.25 + [1, -1] d + \frac{1}{2} d^T \begin{bmatrix} 0 & 0 \\ 0 & -2 \end{bmatrix} d = 0\)
  4. \(\|d\| \leq 0.5\)。

简化后：

  • 目标函数： \(\hat{f}^{(0)}(d) = 2.5 - d_1 - 3d_2 + d_1^2 + d_2^2\)
  • 约束1： \(d_1^2 + d_2^2 + d_1 + d_2 - 0.5 \leq 0\)
  • 约束3： \(0.25 + d_1 - d_2 - d_2^2 = 0\)

该QCQP子问题可用数值方法（如内点法）求解。假设解得 \(d^{(0)} \approx (-0.2, 0.3)\)，则 \(x^{(1)} = x^{(0)} + d^{(0)} \approx (0.3, 0.8)\)。

步骤4：迭代与收敛判断
重复步骤1–3，更新 \(x^{(k)}\) 和 \(\Delta^{(k)}\)。每步需评估实际改进比 \(r = \frac{f(x^{(k)}) - f(x^{(k)} + d)}{ \hat{f}^{(k)}(0) - \hat{f}^{(k)}(d) }\)：

  • 若 \(r\) 接近1（逼近效果好），扩大 \(\Delta^{(k+1)}\)；
  • 若 \(r\) 很小（逼近差），缩小 \(\Delta^{(k+1)}\)。
    当 \(\|d^{(k)}\|\) 小于阈值（如 \(10^{-6}\)）且约束违反度足够小时，终止迭代。

结论
SQCQP通过序列二次模型逼近复杂约束，结合信赖域保证收敛。本题中，最终解将接近满足 \(h(x) = 0\) 和 \(g_1(x) = 0\) 的边界点，如 \(x^* \approx (0.6, 0.8)\)（需完整迭代验证）。

非线性规划中的序列二次约束二次规划（SQCQP）算法基础题 题目描述 考虑非线性规划问题： 最小化 \( f(x) = (x_ 1 - 1)^2 + (x_ 2 - 2)^2 \) 约束条件为： \( g_ 1(x) = x_ 1^2 + x_ 2^2 - 1 \leq 0 \)（非线性不等式约束） \( g_ 2(x) = x_ 1 + x_ 2 - 2 \leq 0 \)（线性不等式约束） \( h(x) = x_ 1 - x_ 2^2 = 0 \)（非线性等式约束） 其中 \( x = (x_ 1, x_ 2) \in \mathbb{R}^2 \)。要求使用序列二次约束二次规划（SQCQP）算法，从初始点 \( x^{(0)} = (0.5, 0.5) \) 出发，迭代求解该问题。 解题过程 SQCQP算法通过序列逼近策略处理非线性约束：每一步在当前迭代点 \( x^{(k)} \) 构造一个二次约束二次规划（QCQP）子问题，通过求解该子问题得到下一步迭代点 \( x^{(k+1)} \)。子问题的目标函数和约束均为原问题的二阶近似，但约束可能被凸化以保证子问题可解。 步骤1：构造第k步QCQP子问题 在点 \( x^{(k)} \) 处，对目标函数 \( f(x) \) 和约束函数进行二阶泰勒展开（忽略高阶项）： 目标函数近似为： \( \hat{f}^{(k)}(d) = f(x^{(k)}) + \nabla f(x^{(k)})^T d + \frac{1}{2} d^T \nabla^2 f(x^{(k)}) d \)， 其中 \( d = x - x^{(k)} \) 是搜索方向。 非线性不等式约束 \( g_ 1(x) \leq 0 \) 近似为： \( \hat{g}_ 1^{(k)}(d) = g_ 1(x^{(k)}) + \nabla g_ 1(x^{(k)})^T d + \frac{1}{2} d^T \nabla^2 g_ 1(x^{(k)}) d \leq 0 \)。 线性约束 \( g_ 2(x) \leq 0 \) 保持原形式（因它是线性的，二阶导为零）。 非线性等式约束 \( h(x) = 0 \) 近似为： \( \hat{h}^{(k)}(d) = h(x^{(k)}) + \nabla h(x^{(k)})^T d + \frac{1}{2} d^T \nabla^2 h(x^{(k)}) d = 0 \)。 子问题为： 最小化 \( \hat{f}^{(k)}(d) \) 满足 \( \hat{g}_ 1^{(k)}(d) \leq 0 \), \( g_ 2(x^{(k)} + d) \leq 0 \), \( \hat{h}^{(k)}(d) = 0 \)， 并附加信赖域约束 \( \|d\| \leq \Delta^{(k)} \)（控制逼近精度，\( \Delta^{(k)} > 0 \) 是信赖域半径）。 步骤2：计算初始点 \( x^{(0)} = (0.5, 0.5) \) 的梯度与Hessian矩阵 目标函数 \( f(x) \)： \( \nabla f(x) = [ 2(x_ 1 - 1), 2(x_ 2 - 2) ]^T \)， \( \nabla^2 f(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \)（常数矩阵）。 在 \( x^{(0)} \) 处： \( \nabla f(x^{(0)}) = [ 2(0.5-1), 2(0.5-2)]^T = [ -1, -3 ]^T \)， \( f(x^{(0)}) = (0.5-1)^2 + (0.5-2)^2 = 2.5 \)。 约束 \( g_ 1(x) = x_ 1^2 + x_ 2^2 - 1 \)： \( \nabla g_ 1(x) = [ 2x_ 1, 2x_ 2 ]^T \)， \( \nabla^2 g_ 1(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \)。 在 \( x^{(0)} \) 处： \( g_ 1(x^{(0)}) = 0.5^2 + 0.5^2 - 1 = -0.5 \)， \( \nabla g_ 1(x^{(0)}) = [ 1, 1 ]^T \)。 约束 \( h(x) = x_ 1 - x_ 2^2 \)： \( \nabla h(x) = [ 1, -2x_ 2 ]^T \)， \( \nabla^2 h(x) = \begin{bmatrix} 0 & 0 \\ 0 & -2 \end{bmatrix} \)。 在 \( x^{(0)} \) 处： \( h(x^{(0)}) = 0.5 - 0.5^2 = 0.25 \)， \( \nabla h(x^{(0)}) = [ 1, -1 ]^T \)。 步骤3：求解第0步QCQP子问题 设信赖域半径 \( \Delta^{(0)} = 0.5 \)。子问题为： 最小化 \( \hat{f}^{(0)}(d) = 2.5 + [ -1, -3 ] d + \frac{1}{2} d^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} d \) 约束： \( \hat{g}_ 1^{(0)}(d) = -0.5 + [ 1, 1 ] d + \frac{1}{2} d^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} d \leq 0 \) \( g_ 2(x^{(0)} + d) = (0.5 + d_ 1) + (0.5 + d_ 2) - 2 = d_ 1 + d_ 2 - 1 \leq 0 \) \( \hat{h}^{(0)}(d) = 0.25 + [ 1, -1 ] d + \frac{1}{2} d^T \begin{bmatrix} 0 & 0 \\ 0 & -2 \end{bmatrix} d = 0 \) \( \|d\| \leq 0.5 \)。 简化后： 目标函数： \( \hat{f}^{(0)}(d) = 2.5 - d_ 1 - 3d_ 2 + d_ 1^2 + d_ 2^2 \) 约束1： \( d_ 1^2 + d_ 2^2 + d_ 1 + d_ 2 - 0.5 \leq 0 \) 约束3： \( 0.25 + d_ 1 - d_ 2 - d_ 2^2 = 0 \) 该QCQP子问题可用数值方法（如内点法）求解。假设解得 \( d^{(0)} \approx (-0.2, 0.3) \)，则 \( x^{(1)} = x^{(0)} + d^{(0)} \approx (0.3, 0.8) \)。 步骤4：迭代与收敛判断 重复步骤1–3，更新 \( x^{(k)} \) 和 \( \Delta^{(k)} \)。每步需评估实际改进比 \( r = \frac{f(x^{(k)}) - f(x^{(k)} + d)}{ \hat{f}^{(k)}(0) - \hat{f}^{(k)}(d) } \)： 若 \( r \) 接近1（逼近效果好），扩大 \( \Delta^{(k+1)} \)； 若 \( r \) 很小（逼近差），缩小 \( \Delta^{(k+1)} \)。 当 \( \|d^{(k)}\| \) 小于阈值（如 \( 10^{-6} \)）且约束违反度足够小时，终止迭代。 结论 SQCQP通过序列二次模型逼近复杂约束，结合信赖域保证收敛。本题中，最终解将接近满足 \( h(x) = 0 \) 和 \( g_ 1(x) = 0 \) 的边界点，如 \( x^* \approx (0.6, 0.8) \)（需完整迭代验证）。