非线性规划中的信赖域反射-序列二次规划混合算法基础题

字数 3633 2025-11-06 22:52:24

非线性规划中的信赖域反射-序列二次规划混合算法基础题

题目描述

考虑非线性规划问题：

\[\min f(x) = (x_1 - 1)^2 + (x_2 - 2)^2 + (x_3 - 3)^2 \]

约束条件为：

\[g_1(x) = x_1 + x_2 + x_3 - 6 \leq 0, \quad g_2(x) = -x_1 \leq 0, \quad g_3(x) = -x_2 \leq 0, \quad g_4(x) = -x_3 \leq 0. \]

初始点 \(x^{(0)} = (0, 0, 0)\)，信赖域半径初始值 \(\Delta_0 = 0.5\)。要求使用信赖域反射-序列二次规划混合算法迭代两步，并说明每一步的更新逻辑。

解题过程

步骤1：算法背景与混合策略

信赖域反射（Trust Region Reflective, TRR）方法通过动态调整信赖域半径保证收敛性，而序列二次规划（SQP）通过求解二次子问题逼近原问题。混合算法的核心思想：

在每次迭代中，用SQP生成候选步长 \(s_k\)；
用TRR框架判断是否接受该步长，并调整信赖域半径 \(\Delta_k\)。

步骤2：第一次迭代（k=0）

初始点：\(x^{(0)} = (0,0,0)\)，\(\Delta_0 = 0.5\)。

2.1 计算梯度与Hessian
目标函数梯度：

\[\nabla f(x) = [2(x_1-1), 2(x_2-2), 2(x_3-3)]^T \Rightarrow \nabla f(x^{(0)}) = [-2, -4, -6]^T. \]

Hessian矩阵（常数）：

\[H = \nabla^2 f(x) = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{bmatrix}. \]

约束梯度：

\[\nabla g_1 = [1,1,1]^T, \quad \nabla g_2 = [-1,0,0]^T, \quad \nabla g_3 = [0,-1,0]^T, \quad \nabla g_4 = [0,0,-1]^T. \]

2.2 构建SQP子问题
在 \(x^{(0)}\) 处，积极约束为 \(g_2, g_3, g_4\)（边界约束激活）。子问题为：

\[\min_s \frac{1}{2} s^T H s + \nabla f(x^{(0)})^T s, \quad \text{s.t.} \quad \|s\| \leq \Delta_0, \quad s \geq 0 \ (\text{因边界约束激活}). \]

由于 \(H\) 正定，子问题等价于投影梯度问题。但需满足信赖域约束 \(\|s\| \leq 0.5\) 和 \(s \geq 0\)。

2.3 求解子问题
忽略边界约束，无约束解为 \(s_{\text{uc}} = -H^{-1} \nabla f = [1,2,3]^T\)，但 \(\|s_{\text{uc}}\| \approx 3.74 > \Delta_0\)。
考虑边界约束 \(s \geq 0\) 和信赖域约束，需截断。简单做法：沿投影梯度方向 \(d = -\nabla f = [2,4,6]^T\) 缩放至信赖域内：

\[s^{(0)} = \frac{\Delta_0}{\|d\|} d = \frac{0.5}{\sqrt{56}} [2,4,6]^T \approx [0.134, 0.267, 0.401]^T. \]

此步满足 \(s \geq 0\) 和 \(\|s\| = 0.5\)。

2.4 计算实际下降与预测下降
实际下降：

\[\text{ared} = f(x^{(0)}) - f(x^{(0)}+s^{(0)}) = 14 - \left[(0.134-1)^2 + (0.267-2)^2 + (0.401-3)^2\right] \approx 14 - 11.23 = 2.77. \]

预测下降（基于二次模型）：

\[\text{pred} = -\left( \frac{1}{2} s^{(0)T} H s^{(0)} + \nabla f^T s^{(0)} \right) = -\left( \frac{1}{2} \cdot 0.5^2 \cdot 2 + [2,4,6] \cdot s^{(0)} \right) \approx - (0.25 + 4.81) = -5.06. \]

比值 \(\rho = \frac{\text{ared}}{\text{pred}} \approx \frac{2.77}{5.06} \approx 0.55\)。

2.5 更新信赖域半径与迭代点
阈值 \(\eta = 0.25\)：

若 \(\rho < \eta\)，拒绝步长，缩小信赖域（\(\Delta_{k+1} = 0.5 \Delta_k\)）；
若 \(\rho \geq \eta\)，接受步长（\(x^{(k+1)} = x^{(k)} + s^{(k)}\)），并根据 \(\rho\) 调整 \(\Delta_{k+1}\)。
此处 \(\rho > 0.25\)，接受步长：

\[x^{(1)} = x^{(0)} + s^{(0)} \approx (0.134, 0.267, 0.401). \]

调整 \(\Delta\)：若 \(\rho > 0.75\)，则扩大信赖域（\(\Delta_{k+1} = 2\Delta_k\)）；否则保持。此处 \(\Delta_1 = \Delta_0 = 0.5\)。

步骤3：第二次迭代（k=1）

当前点：\(x^{(1)} \approx (0.134, 0.267, 0.401)\)，\(\Delta_1 = 0.5\)。

3.1 计算梯度与约束

\[\nabla f(x^{(1)}) \approx [2(0.134-1), 2(0.267-2), 2(0.401-3)]^T \approx [-1.732, -3.466, -5.198]^T. \]

约束情况：\(g_1 \approx -4.198 \leq 0\)（非积极），\(g_2, g_3, g_4\) 仍积极（因 \(x^{(1)} > 0\)）。

3.2 构建SQP子问题
子问题与第一次类似，但梯度变化。方向 \(d = -\nabla f \approx [1.732, 3.466, 5.198]^T\)，缩放至信赖域：

\[s^{(1)} = \frac{0.5}{\sqrt{1.732^2 + 3.466^2 + 5.198^2}} d \approx \frac{0.5}{6.481} d \approx [0.134, 0.267, 0.401]^T. \]

（注：由于梯度方向未变，步长与第一次相同。）

3.3 计算实际下降与预测下降
实际下降：

\[\text{ared} \approx f(x^{(1)}) - f(x^{(1)}+s^{(1)}) = 11.23 - 8.46 \approx 2.77. \]

预测下降：

\[\text{pred} \approx -\left( \frac{1}{2} \cdot 0.5^2 \cdot 2 + [1.732, 3.466, 5.198] \cdot s^{(1)} \right) \approx - (0.25 + 4.81) = -5.06. \]

比值 \(\rho \approx 0.55\)。

3.4 更新迭代点与信赖域
接受步长：

\[x^{(2)} = x^{(1)} + s^{(1)} \approx (0.268, 0.534, 0.802). \]

\(\Delta_2 = \Delta_1 = 0.5\)（因 \(\rho \in [0.25, 0.75]\)）。

结论

经过两次迭代，点从 \((0,0,0)\) 移动到 \((0.268, 0.534, 0.802)\)，目标函数值从14降至约8.46。混合算法通过SQP子问题生成方向，并用TRR机制控制步长，保证稳定收敛。

非线性规划中的信赖域反射-序列二次规划混合算法基础题题目描述考虑非线性规划问题： \[ \min f(x) = (x_ 1 - 1)^2 + (x_ 2 - 2)^2 + (x_ 3 - 3)^2 \] 约束条件为： \[ g_ 1(x) = x_ 1 + x_ 2 + x_ 3 - 6 \leq 0, \quad g_ 2(x) = -x_ 1 \leq 0, \quad g_ 3(x) = -x_ 2 \leq 0, \quad g_ 4(x) = -x_ 3 \leq 0. \] 初始点 \( x^{(0)} = (0, 0, 0) \)，信赖域半径初始值 \( \Delta_ 0 = 0.5 \)。要求使用信赖域反射-序列二次规划混合算法迭代两步，并说明每一步的更新逻辑。解题过程步骤1：算法背景与混合策略信赖域反射（Trust Region Reflective, TRR）方法通过动态调整信赖域半径保证收敛性，而序列二次规划（SQP）通过求解二次子问题逼近原问题。混合算法的核心思想：在每次迭代中，用SQP生成候选步长 \( s_ k \)；用TRR框架判断是否接受该步长，并调整信赖域半径 \( \Delta_ k \)。步骤2：第一次迭代（k=0）初始点：\( x^{(0)} = (0,0,0) \)，\( \Delta_ 0 = 0.5 \)。 2.1 计算梯度与Hessian 目标函数梯度： \[ \nabla f(x) = [ 2(x_ 1-1), 2(x_ 2-2), 2(x_ 3-3)]^T \Rightarrow \nabla f(x^{(0)}) = [ -2, -4, -6 ]^T. \] Hessian矩阵（常数）： \[ H = \nabla^2 f(x) = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{bmatrix}. \] 约束梯度： \[ \nabla g_ 1 = [ 1,1,1]^T, \quad \nabla g_ 2 = [ -1,0,0]^T, \quad \nabla g_ 3 = [ 0,-1,0]^T, \quad \nabla g_ 4 = [ 0,0,-1 ]^T. \] 2.2 构建SQP子问题在 \( x^{(0)} \) 处，积极约束为 \( g_ 2, g_ 3, g_ 4 \)（边界约束激活）。子问题为： \[ \min_ s \frac{1}{2} s^T H s + \nabla f(x^{(0)})^T s, \quad \text{s.t.} \quad \|s\| \leq \Delta_ 0, \quad s \geq 0 \ (\text{因边界约束激活}). \] 由于 \( H \) 正定，子问题等价于投影梯度问题。但需满足信赖域约束 \( \|s\| \leq 0.5 \) 和 \( s \geq 0 \)。 2.3 求解子问题忽略边界约束，无约束解为 \( s_ {\text{uc}} = -H^{-1} \nabla f = [ 1,2,3]^T \)，但 \( \|s_ {\text{uc}}\| \approx 3.74 > \Delta_ 0 \)。考虑边界约束 \( s \geq 0 \) 和信赖域约束，需截断。简单做法：沿投影梯度方向 \( d = -\nabla f = [ 2,4,6 ]^T \) 缩放至信赖域内： \[ s^{(0)} = \frac{\Delta_ 0}{\|d\|} d = \frac{0.5}{\sqrt{56}} [ 2,4,6]^T \approx [ 0.134, 0.267, 0.401 ]^T. \] 此步满足 \( s \geq 0 \) 和 \( \|s\| = 0.5 \)。 2.4 计算实际下降与预测下降实际下降： \[ \text{ared} = f(x^{(0)}) - f(x^{(0)}+s^{(0)}) = 14 - \left[ (0.134-1)^2 + (0.267-2)^2 + (0.401-3)^2\right ] \approx 14 - 11.23 = 2.77. \] 预测下降（基于二次模型）： \[ \text{pred} = -\left( \frac{1}{2} s^{(0)T} H s^{(0)} + \nabla f^T s^{(0)} \right) = -\left( \frac{1}{2} \cdot 0.5^2 \cdot 2 + [ 2,4,6 ] \cdot s^{(0)} \right) \approx - (0.25 + 4.81) = -5.06. \] 比值 \( \rho = \frac{\text{ared}}{\text{pred}} \approx \frac{2.77}{5.06} \approx 0.55 \)。 2.5 更新信赖域半径与迭代点阈值 \( \eta = 0.25 \)：若 \( \rho < \eta \)，拒绝步长，缩小信赖域（\( \Delta_ {k+1} = 0.5 \Delta_ k \)）；若 \( \rho \geq \eta \)，接受步长（\( x^{(k+1)} = x^{(k)} + s^{(k)} \)），并根据 \( \rho \) 调整 \( \Delta_ {k+1} \)。此处 \( \rho > 0.25 \)，接受步长： \[ x^{(1)} = x^{(0)} + s^{(0)} \approx (0.134, 0.267, 0.401). \] 调整 \( \Delta \)：若 \( \rho > 0.75 \)，则扩大信赖域（\( \Delta_ {k+1} = 2\Delta_ k \)）；否则保持。此处 \( \Delta_ 1 = \Delta_ 0 = 0.5 \)。步骤3：第二次迭代（k=1）当前点：\( x^{(1)} \approx (0.134, 0.267, 0.401) \)，\( \Delta_ 1 = 0.5 \)。 3.1 计算梯度与约束 \[ \nabla f(x^{(1)}) \approx [ 2(0.134-1), 2(0.267-2), 2(0.401-3)]^T \approx [ -1.732, -3.466, -5.198 ]^T. \] 约束情况：\( g_ 1 \approx -4.198 \leq 0 \)（非积极），\( g_ 2, g_ 3, g_ 4 \) 仍积极（因 \( x^{(1)} > 0 \)）。 3.2 构建SQP子问题子问题与第一次类似，但梯度变化。方向 \( d = -\nabla f \approx [ 1.732, 3.466, 5.198 ]^T \)，缩放至信赖域： \[ s^{(1)} = \frac{0.5}{\sqrt{1.732^2 + 3.466^2 + 5.198^2}} d \approx \frac{0.5}{6.481} d \approx [ 0.134, 0.267, 0.401 ]^T. \] （注：由于梯度方向未变，步长与第一次相同。） 3.3 计算实际下降与预测下降实际下降： \[ \text{ared} \approx f(x^{(1)}) - f(x^{(1)}+s^{(1)}) = 11.23 - 8.46 \approx 2.77. \] 预测下降： \[ \text{pred} \approx -\left( \frac{1}{2} \cdot 0.5^2 \cdot 2 + [ 1.732, 3.466, 5.198 ] \cdot s^{(1)} \right) \approx - (0.25 + 4.81) = -5.06. \] 比值 \( \rho \approx 0.55 \)。 3.4 更新迭代点与信赖域接受步长： \[ x^{(2)} = x^{(1)} + s^{(1)} \approx (0.268, 0.534, 0.802). \] \( \Delta_ 2 = \Delta_ 1 = 0.5 \)（因 \( \rho \in [ 0.25, 0.75 ] \)）。结论经过两次迭代，点从 \( (0,0,0) \) 移动到 \( (0.268, 0.534, 0.802) \)，目标函数值从14降至约8.46。混合算法通过SQP子问题生成方向，并用TRR机制控制步长，保证稳定收敛。