非线性规划中的序列凸近似信赖域反射混合算法基础题

字数 2677 2025-11-11 18:42:33

非线性规划中的序列凸近似信赖域反射混合算法基础题

题目描述：
考虑一个非线性规划问题：
最小化 \(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\)（线性约束），
其中 \(x = (x_1, x_2) \in \mathbb{R}^2\)。
要求使用序列凸近似信赖域反射混合算法求解该问题，初始点设为 \(x^{(0)} = (0.5, 0.5)\)，初始信赖域半径 \(\Delta_0 = 0.5\)，收敛容差 \(\epsilon = 10^{-6}\)。

解题过程：
该算法结合序列凸近似（将非线性约束局部线性化）、信赖域法（控制近似模型的可行性）和反射技术（处理约束违反）。以下是逐步推导：

初始化：
设迭代点 \(x^{(0)} = (0.5, 0.5)\)，信赖域半径 \(\Delta_0 = 0.5\)，迭代计数器 \(k = 0\)。
计算初始函数值 \(f(x^{(0)}) = (0.5-1)^2 + (0.5-2)^2 = 2.5\)，约束值 \(g_1(x^{(0)}) = 0.5^2 + 0.5^2 - 1 = -0.5\)（满足），\(g_2(x^{(0)}) = 0.5 + 0.5 - 2 = -1\)（满足）。
构建凸近似子问题：
在当前点 \(x^{(k)}\) 处，对非线性约束 \(g_1(x)\) 进行一阶泰勒展开（凸近似），保留线性约束 \(g_2(x)\) 的精确形式。子问题为：
最小化 \(\hat{f}(d) = \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_k d\)（二次模型），
约束为：
\(\hat{g}_1(d) = g_1(x^{(k)}) + \nabla g_1(x^{(k)})^T d \leq 0\)，
\(g_2(x^{(k)} + d) \leq 0\)，
\(\|d\| \leq \Delta_k\)（信赖域约束），
其中 \(d = x - x^{(k)}\) 是搜索方向，\(B_k\) 是Hessian近似（本例中取精确Hessian \(\nabla^2 f(x^{(k)}) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}\)）。
- 在 \(x^{(0)} = (0.5, 0.5)\) 时：
  \(\nabla f(x^{(0)}) = [2(0.5-1), 2(0.5-2)] = [-1, -3]\)，
  \(\nabla g_1(x^{(0)}) = [2 \times 0.5, 2 \times 0.5] = [1, 1]\)，
  \(g_1(x^{(0)}) = -0.5\)。
  子问题变为：
  最小化 \(\hat{f}(d) = -d_1 - 3d_2 + d_1^2 + d_2^2\)，
  约束为：
  \(-0.5 + d_1 + d_2 \leq 0\)，
  \((0.5 + d_1) + (0.5 + d_2) - 2 \leq 0 \Rightarrow d_1 + d_2 \leq 1\)，
  \(\|d\| \leq 0.5\)。
求解子问题：
子问题是凸二次规划，可用有效集法或内点法求解。
- 对于 \(k=0\)，约束简化后为 \(d_1 + d_2 \leq 0.5\)（由 \(\hat{g}_1\)）和 \(d_1 + d_2 \leq 1\)（由 \(g_2\)），前者更紧。结合信赖域约束，解得最优方向 \(d^{(0)} \approx (-0.25, -0.25)\)，对应 \(\hat{x} = x^{(0)} + d^{(0)} = (0.25, 0.25)\)。
接受性检验与反射技术：
- 计算实际减少量 \(\text{ared} = f(x^{(k)}) - f(\hat{x})\) 和预测减少量 \(\text{pred} = \hat{f}(0) - \hat{f}(d^{(k)})\)。
  在 \(k=0\)：
  \(f(\hat{x}) = (0.25-1)^2 + (0.25-2)^2 = 3.125\)，
  \(\text{ared} = 2.5 - 3.125 = -0.625\)（增加，不可接受），
  \(\text{pred} = 0 - (-0.875) = 0.875\)（预测减少，但实际未减少）。
- 由于 \(\text{ared} < 0\)，采用反射技术：计算反射点 \(x_r = x^{(k)} + 2d^{(k)} = (0, 0)\)，若 \(f(x_r) < f(x^{(k)})\) 且约束满足，则接受 \(x_r\)。
  此处 \(f(x_r) = 5\)，比当前点更差，故拒绝反射点。
- 调整信赖域半径：因 \(\rho = \frac{\text{ared}}{\text{pred}} = -0.714 < 0.25\)，缩小信赖域 \(\Delta_1 = 0.5 \times \Delta_0 = 0.25\)。
迭代与收敛：
更新 \(k = 1\)，以 \(x^{(1)} = x^{(0)} = (0.5, 0.5)\)（点未更新）和 \(\Delta_1 = 0.25\) 重复步骤2-4。
多次迭代后，当 \(\|d^{(k)}\| < \epsilon\) 且约束满足时停止。最终解趋近于 \(x^* \approx (0.5, 0.5)\)（受非线性约束 \(g_1(x) \leq 0\) 限制，最优解在约束边界 \(x_1^2 + x_2^2 = 1\) 上）。

关键点：

序列凸近似确保子问题可解，信赖域控制近似精度，反射技术增强全局收敛。
实际减少与预测减少的比例指导信赖域调整和迭代点更新。

非线性规划中的序列凸近似信赖域反射混合算法基础题题目描述：考虑一个非线性规划问题：最小化 \( 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 \)（线性约束），其中 \( x = (x_ 1, x_ 2) \in \mathbb{R}^2 \)。要求使用序列凸近似信赖域反射混合算法求解该问题，初始点设为 \( x^{(0)} = (0.5, 0.5) \)，初始信赖域半径 \( \Delta_ 0 = 0.5 \)，收敛容差 \( \epsilon = 10^{-6} \)。解题过程：该算法结合序列凸近似（将非线性约束局部线性化）、信赖域法（控制近似模型的可行性）和反射技术（处理约束违反）。以下是逐步推导：初始化：设迭代点 \( x^{(0)} = (0.5, 0.5) \)，信赖域半径 \( \Delta_ 0 = 0.5 \)，迭代计数器 \( k = 0 \)。计算初始函数值 \( f(x^{(0)}) = (0.5-1)^2 + (0.5-2)^2 = 2.5 \)，约束值 \( g_ 1(x^{(0)}) = 0.5^2 + 0.5^2 - 1 = -0.5 \)（满足），\( g_ 2(x^{(0)}) = 0.5 + 0.5 - 2 = -1 \)（满足）。构建凸近似子问题：在当前点 \( x^{(k)} \) 处，对非线性约束 \( g_ 1(x) \) 进行一阶泰勒展开（凸近似），保留线性约束 \( g_ 2(x) \) 的精确形式。子问题为：最小化 \( \hat{f}(d) = \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_ k d \)（二次模型），约束为： \( \hat{g}_ 1(d) = g_ 1(x^{(k)}) + \nabla g_ 1(x^{(k)})^T d \leq 0 \)， \( g_ 2(x^{(k)} + d) \leq 0 \)， \( \|d\| \leq \Delta_ k \)（信赖域约束），其中 \( d = x - x^{(k)} \) 是搜索方向，\( B_ k \) 是Hessian近似（本例中取精确Hessian \( \nabla^2 f(x^{(k)}) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \)）。在 \( x^{(0)} = (0.5, 0.5) \) 时： \( \nabla f(x^{(0)}) = [ 2(0.5-1), 2(0.5-2)] = [ -1, -3 ] \)， \( \nabla g_ 1(x^{(0)}) = [ 2 \times 0.5, 2 \times 0.5] = [ 1, 1 ] \)， \( g_ 1(x^{(0)}) = -0.5 \)。子问题变为：最小化 \( \hat{f}(d) = -d_ 1 - 3d_ 2 + d_ 1^2 + d_ 2^2 \)，约束为： \( -0.5 + d_ 1 + d_ 2 \leq 0 \)， \( (0.5 + d_ 1) + (0.5 + d_ 2) - 2 \leq 0 \Rightarrow d_ 1 + d_ 2 \leq 1 \)， \( \|d\| \leq 0.5 \)。求解子问题：子问题是凸二次规划，可用有效集法或内点法求解。对于 \( k=0 \)，约束简化后为 \( d_ 1 + d_ 2 \leq 0.5 \)（由 \( \hat{g}_ 1 \)）和 \( d_ 1 + d_ 2 \leq 1 \)（由 \( g_ 2 \)），前者更紧。结合信赖域约束，解得最优方向 \( d^{(0)} \approx (-0.25, -0.25) \)，对应 \( \hat{x} = x^{(0)} + d^{(0)} = (0.25, 0.25) \)。接受性检验与反射技术：计算实际减少量 \( \text{ared} = f(x^{(k)}) - f(\hat{x}) \) 和预测减少量 \( \text{pred} = \hat{f}(0) - \hat{f}(d^{(k)}) \)。在 \( k=0 \)： \( f(\hat{x}) = (0.25-1)^2 + (0.25-2)^2 = 3.125 \)， \( \text{ared} = 2.5 - 3.125 = -0.625 \)（增加，不可接受）， \( \text{pred} = 0 - (-0.875) = 0.875 \)（预测减少，但实际未减少）。由于 \( \text{ared} < 0 \)，采用反射技术：计算反射点 \( x_ r = x^{(k)} + 2d^{(k)} = (0, 0) \)，若 \( f(x_ r) < f(x^{(k)}) \) 且约束满足，则接受 \( x_ r \)。此处 \( f(x_ r) = 5 \)，比当前点更差，故拒绝反射点。调整信赖域半径：因 \( \rho = \frac{\text{ared}}{\text{pred}} = -0.714 < 0.25 \)，缩小信赖域 \( \Delta_ 1 = 0.5 \times \Delta_ 0 = 0.25 \)。迭代与收敛：更新 \( k = 1 \)，以 \( x^{(1)} = x^{(0)} = (0.5, 0.5) \)（点未更新）和 \( \Delta_ 1 = 0.25 \) 重复步骤2-4。多次迭代后，当 \( \|d^{(k)}\| < \epsilon \) 且约束满足时停止。最终解趋近于 \( x^* \approx (0.5, 0.5) \)（受非线性约束 \( g_ 1(x) \leq 0 \) 限制，最优解在约束边界 \( x_ 1^2 + x_ 2^2 = 1 \) 上）。关键点：序列凸近似确保子问题可解，信赖域控制近似精度，反射技术增强全局收敛。实际减少与预测减少的比例指导信赖域调整和迭代点更新。