非线性规划中的序列二次约束规划法基础题
字数 2272 2025-10-26 21:06:54

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

题目描述
考虑一个非线性约束优化问题：
最小化目标函数 \(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)\)。要求使用序列二次约束规划法（SQCP）求解该问题，并解释其逐步逼近过程。

解题过程
序列二次约束规划法（SQCP）通过迭代求解一系列二次约束子问题来逼近原问题。每个子问题在当前迭代点对目标函数和约束进行二阶近似，并添加信赖域约束以保证收敛。以下是详细步骤：

1. 初始化
设置初始点 \(x^{(0)} = (0, 0)\)，初始信赖域半径 \(\Delta_0 = 0.5\)，收敛容差 \(\epsilon = 10^{-6}\)，迭代计数器 \(k = 0\)。

2. 构建第k次迭代的二次约束子问题
在点 \(x^{(k)}\) 处，对目标函数 \(f(x)\) 进行二阶泰勒展开，对约束 \(g_i(x)\) 进行一阶泰勒展开（保留非线性项），形成子问题：
最小化：

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

满足约束：

\[g_i(x^{(k)}) + \nabla g_i(x^{(k)})^T d \leq 0 \quad (i=1,2) \]

\[\|d\|_\infty \leq \Delta_k \]

其中 \(d = x - x^{(k)}\) 是搜索方向，\(\|d\|_\infty \leq \Delta_k\) 是信赖域约束，防止近似误差过大。

3. 求解二次约束子问题
以第一次迭代（\(k=0\)）为例：

  • 计算梯度与Hessian矩阵：
    \(\nabla f(x) = [2(x_1-2), 2(x_2-1)]^T\)，在 \(x^{(0)} = (0,0)\) 处：
    \(\nabla f(x^{(0)}) = [-4, -2]^T\)
    \(\nabla^2 f(x^{(0)}) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}\)（常数矩阵）
  • 约束的梯度：
    \(\nabla g_1(x) = [2x_1, -1]^T\)，在 \(x^{(0)}\) 处： \([0, -1]^T\)
    \(\nabla g_2(x) = [1, 1]^T\)（常数）
  • 约束函数值：
    \(g_1(x^{(0)}) = 0\)，\(g_2(x^{(0)}) = -2\)
  • 子问题化为：
    最小化 \(f_0 + [-4, -2] d + \frac{1}{2} d^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} d\)（其中 \(f_0 = f(0,0) = 5\) 为常数，可忽略）
    约束为：
    \(0 + [0, -1] d \leq 0\) → \(-d_2 \leq 0\)
    \(-2 + [1, 1] d \leq 0\) → \(d_1 + d_2 - 2 \leq 0\)
    \(\|d\|_\infty \leq 0.5\)
    求解该二次规划得 \(d^{(0)} \approx (0.5, 0.5)\)（需数值求解，此处简化表示）。

4. 接受步长与更新信赖域半径
计算实际下降量 \(\text{Actual Reduction} = f(x^{(k)}) - f(x^{(k)}+d)\)
预测下降量 \(\text{Predicted Reduction} = f(x^{(k)}) - \text{子问题最优值}\)
比值 \(r_k = \frac{\text{Actual Reduction}}{\text{Predicted Reduction}}\)

  • 若 \(r_k > 0.75\)，接受步长，并扩大信赖域： \(\Delta_{k+1} = 2\Delta_k\)
  • 若 \(r_k < 0.25\)，拒绝步长，缩小信赖域： \(\Delta_{k+1} = \Delta_k / 2\)
  • 否则保持信赖域不变。
    本例中，若 \(r_k > 0.75\)，则更新 \(x^{(1)} = x^{(0)} + d^{(0)} = (0.5, 0.5)\)。

5. 检查收敛条件
重复步骤2-4，直到满足 \(\|d\| < \epsilon\) 或达到最大迭代次数。最终解将逼近真实最优解 \(x^* \approx (1, 1)\)，此时 \(f(x^*) = 1\)，约束 \(g_1(1,1)=0\)，\(g_2(1,1)=0\) 处于活动状态。

总结
SQCP通过序列化地处理二次约束模型，平衡近似精度与计算效率，尤其适用于非线性约束较强的优化问题。其核心是动态调整信赖域，确保迭代稳定收敛。

非线性规划中的序列二次约束规划法基础题 题目描述 考虑一个非线性约束优化问题： 最小化目标函数 \( 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) \)。要求使用序列二次约束规划法（SQCP）求解该问题，并解释其逐步逼近过程。 解题过程 序列二次约束规划法（SQCP）通过迭代求解一系列二次约束子问题来逼近原问题。每个子问题在当前迭代点对目标函数和约束进行二阶近似，并添加信赖域约束以保证收敛。以下是详细步骤： 1. 初始化 设置初始点 \( x^{(0)} = (0, 0) \)，初始信赖域半径 \( \Delta_ 0 = 0.5 \)，收敛容差 \( \epsilon = 10^{-6} \)，迭代计数器 \( k = 0 \)。 2. 构建第k次迭代的二次约束子问题 在点 \( x^{(k)} \) 处，对目标函数 \( f(x) \) 进行二阶泰勒展开，对约束 \( g_ i(x) \) 进行一阶泰勒展开（保留非线性项），形成子问题： 最小化： \[ f(x^{(k)}) + \nabla f(x^{(k)})^T d + \frac{1}{2} d^T \nabla^2 f(x^{(k)}) d \] 满足约束： \[ g_ i(x^{(k)}) + \nabla g_ i(x^{(k)})^T d \leq 0 \quad (i=1,2) \] \[ \|d\| \infty \leq \Delta_ k \] 其中 \( d = x - x^{(k)} \) 是搜索方向，\( \|d\| \infty \leq \Delta_ k \) 是信赖域约束，防止近似误差过大。 3. 求解二次约束子问题 以第一次迭代（\( k=0 \)）为例： 计算梯度与Hessian矩阵： \( \nabla f(x) = [ 2(x_ 1-2), 2(x_ 2-1) ]^T \)，在 \( x^{(0)} = (0,0) \) 处： \( \nabla f(x^{(0)}) = [ -4, -2 ]^T \) \( \nabla^2 f(x^{(0)}) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \)（常数矩阵） 约束的梯度： \( \nabla g_ 1(x) = [ 2x_ 1, -1]^T \)，在 \( x^{(0)} \) 处： \( [ 0, -1 ]^T \) \( \nabla g_ 2(x) = [ 1, 1 ]^T \)（常数） 约束函数值： \( g_ 1(x^{(0)}) = 0 \)，\( g_ 2(x^{(0)}) = -2 \) 子问题化为： 最小化 \( f_ 0 + [ -4, -2] d + \frac{1}{2} d^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} d \)（其中 \( f_ 0 = f(0,0) = 5 \) 为常数，可忽略） 约束为： \( 0 + [ 0, -1] d \leq 0 \) → \( -d_ 2 \leq 0 \) \( -2 + [ 1, 1] d \leq 0 \) → \( d_ 1 + d_ 2 - 2 \leq 0 \) \( \|d\|_ \infty \leq 0.5 \) 求解该二次规划得 \( d^{(0)} \approx (0.5, 0.5) \)（需数值求解，此处简化表示）。 4. 接受步长与更新信赖域半径 计算实际下降量 \( \text{Actual Reduction} = f(x^{(k)}) - f(x^{(k)}+d) \) 预测下降量 \( \text{Predicted Reduction} = f(x^{(k)}) - \text{子问题最优值} \) 比值 \( r_ k = \frac{\text{Actual Reduction}}{\text{Predicted Reduction}} \) 若 \( r_ k > 0.75 \)，接受步长，并扩大信赖域： \( \Delta_ {k+1} = 2\Delta_ k \) 若 \( r_ k < 0.25 \)，拒绝步长，缩小信赖域： \( \Delta_ {k+1} = \Delta_ k / 2 \) 否则保持信赖域不变。 本例中，若 \( r_ k > 0.75 \)，则更新 \( x^{(1)} = x^{(0)} + d^{(0)} = (0.5, 0.5) \)。 5. 检查收敛条件 重复步骤2-4，直到满足 \( \|d\| < \epsilon \) 或达到最大迭代次数。最终解将逼近真实最优解 \( x^* \approx (1, 1) \)，此时 \( f(x^* ) = 1 \)，约束 \( g_ 1(1,1)=0 \)，\( g_ 2(1,1)=0 \) 处于活动状态。 总结 SQCP通过序列化地处理二次约束模型，平衡近似精度与计算效率，尤其适用于非线性约束较强的优化问题。其核心是动态调整信赖域，确保迭代稳定收敛。