非线性规划中的序列仿射尺度信赖域法基础题
字数 3559 2025-11-04 00:21:09

非线性规划中的序列仿射尺度信赖域法基础题

题目描述
考虑非线性规划问题：
最小化 \(f(x)1 = x_1^2 + 2x_2^2 - 2x_1x_2 + e^{x_1}\)
满足约束 \(h(x) = x_1 + x_2 - 1 = 0\) 和 \(g(x) = x_1^2 + x_2^2 - 2 \leq 0\)。
初始点 \(x^{(0)} = (0.5, 0.5)\)，初始信赖域半径 \(\Delta_0 = 0.5\)。
使用序列仿射尺度信赖域法进行一次迭代，要求：

  1. 在当前点构造仿射尺度变换，将问题转换为等价形式；
  2. 在变换空间建立信赖域子问题并求解；
  3. 根据实际下降与预测下降的比率调整信赖域半径。

解题过程

1. 问题分析与仿射尺度变换

  • 目标：将非线性约束问题通过仿射尺度变换简化，结合信赖域法控制步长。
  • 当前点 \(x^{(0)}\)：计算函数值与梯度：
    • \(f(x^{(0)}) = 0.5^2 + 2 \times 0.5^2 - 2 \times 0.5 \times 0.5 + e^{0.5} = 0.25 + 0.5 - 0.5 + 1.6487 = 1.8987\)；
    • 梯度 \(\nabla f(x) = [2x_1 - 2x_2 + e^{x_1}, 4x_2 - 2x_1]\)，代入得 \(\nabla f(x^{(0)}) = [2 \times 0.5 - 2 \times 0.5 + e^{0.5}, 4 \times 0.5 - 2 \times 0.5] = [1.6487, 1.0]\)；
    • 约束函数梯度： \(\nabla h(x) = [1, 1]\)， \(\nabla g(x) = [2x_1, 2x_2] = [1.0, 1.0]\)。
  • 仿射尺度变换：通过尺度矩阵 \(D\) 调整变量尺度，改善问题条件。令 \(D = \text{diag}(d_1, d_2)\)，其中 \(d_i = \frac{1}{\max(1, |x_i^{(0)}|)} = 1\)（因 \(|x_i^{(0)}| = 0.5 < 1\)），故 \(D = I\)（单位矩阵）。变换变量 \(y = D^{-1}x = x\)，此时问题在 \(y\)-空间与原问题一致。

2. 构造信赖域子问题并求解

  • 子问题形式：在 \(y\)-空间，当前点 \(y^{(0)} = x^{(0)}\)，构造二次模型近似目标函数，线性化约束：
    • 目标函数近似：\(m(s) = f(y^{(0)}) + \nabla f(y^{(0)})^T s + \frac{1}{2} s^T B s\)，其中 \(B\) 为Hessian近似。计算精确Hessian：
      \(\nabla^2 f(x) = \begin{bmatrix} 2 + e^{x_1} & -2 \\ -2 & 4 \end{bmatrix}\)，代入 \(x^{(0)}\) 得 \(B = \begin{bmatrix} 2 + e^{0.5} & -2 \\ -2 & 4 \end{bmatrix} = \begin{bmatrix} 3.6487 & -2 \\ -2 & 4 \end{bmatrix}\)。
    • 约束线性化：\(h(y^{(0)} + s) \approx h(y^{(0)}) + \nabla h(y^{(0)})^T s = 0 + [1, 1] s = 0\)，\(g(y^{(0)} + s) \approx g(y^{(0)}) + \nabla g(y^{(0)})^T s = (0.5^2 + 0.5^2 - 2) + [1.0, 1.0] s = -1.5 + [1, 1] s \leq 0\)。
  • 子问题数学形式：
    最小化 \(m(s) = 1.8987 + [1.6487, 1.0] s + \frac{1}{2} s^T \begin{bmatrix} 3.6487 & -2 \\ -2 & 4 \end{bmatrix} s\)
    满足 \([1, 1] s = 0\)，\([1, 1] s \leq 1.5\)，且 \(\| s \| \leq \Delta_0 = 0.5\)。
  • 求解子问题：
    • 等式约束 \(s_1 + s_2 = 0\) 代入，令 \(s_2 = -s_1\)，则 \(s = [s_1, -s_1]\)，\(\| s \| = \sqrt{2 s_1^2} = \sqrt{2} |s_1| \leq 0.5\)，故 \(|s_1| \leq 0.5 / \sqrt{2} \approx 0.3536\)。
    • 代入目标函数：\(m(s_1) = 1.8987 + 1.6487 s_1 + 1.0 \cdot (-s_1) + \frac{1}{2} [s_1, -s_1] \begin{bmatrix} 3.6487 & -2 \\ -2 & 4 \end{bmatrix} [s_1, -s_1]^T\)
      = \(1.8987 + 0.6487 s_1 + \frac{1}{2} (3.6487 s_1^2 + 4 s_1 s_1 + 4 s_1^2)\)（计算二次项：\(s_1 \cdot 3.6487 s_1 + (-s_1) \cdot (-2) s_1 + s_1 \cdot (-2)(-s_1) + (-s_1) \cdot 4 (-s_1) = 3.6487 s_1^2 + 2 s_1^2 + 2 s_1^2 + 4 s_1^2 = 11.6487 s_1^2\)）
      因此 \(m(s_1) = 1.8987 + 0.6487 s_1 + 5.8244 s_1^2\)。
    • 最小化该二次函数：导数 \(\frac{dm}{ds_1} = 0.6487 + 11.6488 s_1 = 0\) 得驻点 \(s_1^* = -0.0557\)。检查边界：
      • \(s_1 = -0.0557\) 时，\(|s_1| = 0.0557 \leq 0.3536\)，满足信赖域约束；
      • 不等式约束 \([1, 1] s = 0 \leq 1.5\) 自动成立。
    • 故最优解 \(s^* = [-0.0557, 0.0557]\)，对应预测下降 \(\text{pred} = m(0) - m(s^*) = 0 - (1.8987 + 0.6487 \times (-0.0557) + 5.8244 \times (-0.0557)^2) \approx 0.0181\)。

3. 接受步长与调整信赖域半径

  • 计算实际下降：新点 \(x^{(1)} = x^{(0)} + s^* = [0.4443, 0.5557]\)，
    \(f(x^{(1)}) = 0.4443^2 + 2 \times 0.5557^2 - 2 \times 0.4443 \times 0.5557 + e^{0.4443} \approx 0.1974 + 0.6176 - 0.4938 + 1.5596 = 1.8808\)。
    实际下降 \(\text{ared} = f(x^{(0)}) - f(x^{(1)}) = 1.8987 - 1.8808 = 0.0179\)。
  • 计算比率：\(\rho = \frac{\text{ared}}{\text{pred}} = \frac{0.0179}{0.0181} \approx 0.989\)。
  • 调整信赖域半径：
    • 若 \(\rho > 0.75\)，接受步长并扩大信赖域；若 \(\rho < 0.25\)，缩小信赖域。此处 \(\rho \approx 0.989 > 0.75\)，故接受 \(x^{(1)}\)，并扩大半径 \(\Delta_1 = 2 \Delta_0 = 1.0\)。

迭代结果：一次迭代后，新点为 \(x^{(1)} = (0.4443, 0.5557)\)，函数值下降至 1.8808，信赖域半径更新为 1.0。

非线性规划中的序列仿射尺度信赖域法基础题 题目描述 考虑非线性规划问题： 最小化 \( f(x)1 = x_ 1^2 + 2x_ 2^2 - 2x_ 1x_ 2 + e^{x_ 1} \) 满足约束 \( h(x) = x_ 1 + x_ 2 - 1 = 0 \) 和 \( g(x) = x_ 1^2 + x_ 2^2 - 2 \leq 0 \)。 初始点 \( x^{(0)} = (0.5, 0.5) \)，初始信赖域半径 \( \Delta_ 0 = 0.5 \)。 使用序列仿射尺度信赖域法进行一次迭代，要求： 在当前点构造仿射尺度变换，将问题转换为等价形式； 在变换空间建立信赖域子问题并求解； 根据实际下降与预测下降的比率调整信赖域半径。 解题过程 1. 问题分析与仿射尺度变换 目标 ：将非线性约束问题通过仿射尺度变换简化，结合信赖域法控制步长。 当前点 \( x^{(0)} \) ：计算函数值与梯度： \( f(x^{(0)}) = 0.5^2 + 2 \times 0.5^2 - 2 \times 0.5 \times 0.5 + e^{0.5} = 0.25 + 0.5 - 0.5 + 1.6487 = 1.8987 \)； 梯度 \( \nabla f(x) = [ 2x_ 1 - 2x_ 2 + e^{x_ 1}, 4x_ 2 - 2x_ 1] \)，代入得 \( \nabla f(x^{(0)}) = [ 2 \times 0.5 - 2 \times 0.5 + e^{0.5}, 4 \times 0.5 - 2 \times 0.5] = [ 1.6487, 1.0 ] \)； 约束函数梯度： \( \nabla h(x) = [ 1, 1] \)， \( \nabla g(x) = [ 2x_ 1, 2x_ 2] = [ 1.0, 1.0 ] \)。 仿射尺度变换 ：通过尺度矩阵 \( D \) 调整变量尺度，改善问题条件。令 \( D = \text{diag}(d_ 1, d_ 2) \)，其中 \( d_ i = \frac{1}{\max(1, |x_ i^{(0)}|)} = 1 \)（因 \( |x_ i^{(0)}| = 0.5 < 1 \)），故 \( D = I \)（单位矩阵）。变换变量 \( y = D^{-1}x = x \)，此时问题在 \( y \)-空间与原问题一致。 2. 构造信赖域子问题并求解 子问题形式 ：在 \( y \)-空间，当前点 \( y^{(0)} = x^{(0)} \)，构造二次模型近似目标函数，线性化约束： 目标函数近似：\( m(s) = f(y^{(0)}) + \nabla f(y^{(0)})^T s + \frac{1}{2} s^T B s \)，其中 \( B \) 为Hessian近似。计算精确Hessian： \( \nabla^2 f(x) = \begin{bmatrix} 2 + e^{x_ 1} & -2 \\ -2 & 4 \end{bmatrix} \)，代入 \( x^{(0)} \) 得 \( B = \begin{bmatrix} 2 + e^{0.5} & -2 \\ -2 & 4 \end{bmatrix} = \begin{bmatrix} 3.6487 & -2 \\ -2 & 4 \end{bmatrix} \)。 约束线性化：\( h(y^{(0)} + s) \approx h(y^{(0)}) + \nabla h(y^{(0)})^T s = 0 + [ 1, 1] s = 0 \)，\( g(y^{(0)} + s) \approx g(y^{(0)}) + \nabla g(y^{(0)})^T s = (0.5^2 + 0.5^2 - 2) + [ 1.0, 1.0] s = -1.5 + [ 1, 1 ] s \leq 0 \)。 子问题数学形式 ： 最小化 \( m(s) = 1.8987 + [ 1.6487, 1.0 ] s + \frac{1}{2} s^T \begin{bmatrix} 3.6487 & -2 \\ -2 & 4 \end{bmatrix} s \) 满足 \( [ 1, 1] s = 0 \)，\( [ 1, 1] s \leq 1.5 \)，且 \( \| s \| \leq \Delta_ 0 = 0.5 \)。 求解子问题 ： 等式约束 \( s_ 1 + s_ 2 = 0 \) 代入，令 \( s_ 2 = -s_ 1 \)，则 \( s = [ s_ 1, -s_ 1] \)，\( \| s \| = \sqrt{2 s_ 1^2} = \sqrt{2} |s_ 1| \leq 0.5 \)，故 \( |s_ 1| \leq 0.5 / \sqrt{2} \approx 0.3536 \)。 代入目标函数：\( m(s_ 1) = 1.8987 + 1.6487 s_ 1 + 1.0 \cdot (-s_ 1) + \frac{1}{2} [ s_ 1, -s_ 1] \begin{bmatrix} 3.6487 & -2 \\ -2 & 4 \end{bmatrix} [ s_ 1, -s_ 1 ]^T \) = \( 1.8987 + 0.6487 s_ 1 + \frac{1}{2} (3.6487 s_ 1^2 + 4 s_ 1 s_ 1 + 4 s_ 1^2) \)（计算二次项：\( s_ 1 \cdot 3.6487 s_ 1 + (-s_ 1) \cdot (-2) s_ 1 + s_ 1 \cdot (-2)(-s_ 1) + (-s_ 1) \cdot 4 (-s_ 1) = 3.6487 s_ 1^2 + 2 s_ 1^2 + 2 s_ 1^2 + 4 s_ 1^2 = 11.6487 s_ 1^2 \)） 因此 \( m(s_ 1) = 1.8987 + 0.6487 s_ 1 + 5.8244 s_ 1^2 \)。 最小化该二次函数：导数 \( \frac{dm}{ds_ 1} = 0.6487 + 11.6488 s_ 1 = 0 \) 得驻点 \( s_ 1^* = -0.0557 \)。检查边界： \( s_ 1 = -0.0557 \) 时，\( |s_ 1| = 0.0557 \leq 0.3536 \)，满足信赖域约束； 不等式约束 \( [ 1, 1 ] s = 0 \leq 1.5 \) 自动成立。 故最优解 \( s^* = [ -0.0557, 0.0557] \)，对应预测下降 \( \text{pred} = m(0) - m(s^* ) = 0 - (1.8987 + 0.6487 \times (-0.0557) + 5.8244 \times (-0.0557)^2) \approx 0.0181 \)。 3. 接受步长与调整信赖域半径 计算实际下降 ：新点 \( x^{(1)} = x^{(0)} + s^* = [ 0.4443, 0.5557 ] \)， \( f(x^{(1)}) = 0.4443^2 + 2 \times 0.5557^2 - 2 \times 0.4443 \times 0.5557 + e^{0.4443} \approx 0.1974 + 0.6176 - 0.4938 + 1.5596 = 1.8808 \)。 实际下降 \( \text{ared} = f(x^{(0)}) - f(x^{(1)}) = 1.8987 - 1.8808 = 0.0179 \)。 计算比率 ：\( \rho = \frac{\text{ared}}{\text{pred}} = \frac{0.0179}{0.0181} \approx 0.989 \)。 调整信赖域半径 ： 若 \( \rho > 0.75 \)，接受步长并扩大信赖域；若 \( \rho < 0.25 \)，缩小信赖域。此处 \( \rho \approx 0.989 > 0.75 \)，故接受 \( x^{(1)} \)，并扩大半径 \( \Delta_ 1 = 2 \Delta_ 0 = 1.0 \)。 迭代结果 ：一次迭代后，新点为 \( x^{(1)} = (0.4443, 0.5557) \)，函数值下降至 1.8808，信赖域半径更新为 1.0。