非线性规划中的信赖域序列二次规划(TR-SQP)算法基础题
字数 3490 2025-11-01 09:19:03

非线性规划中的信赖域序列二次规划(TR-SQP)算法基础题

题目描述
考虑非线性规划问题：
最小化 \(f(x) = 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, 0)\)，信赖域半径初始值 \(\Delta_0 = 0.5\)。
要求使用信赖域序列二次规划（TR-SQP）算法，通过一次迭代计算下一个迭代点 \(x^{(1)}\)。

解题过程

1. 算法原理概述
TR-SQP结合了序列二次规划（SQP）和信赖域法的优点：

  • SQP通过求解二次规划子问题近似原问题，但需控制步长避免发散。
  • 信赖域法限制步长在半径Δ内，保证收敛性。
    TR-SQP的子问题形式为：
    最小化 \(Q(p) = \nabla f(x)^T p + \frac{1}{2} p^T H p\)
    约束于 \(\nabla h(x)^T p + h(x) = 0\)，
    \(\nabla g(x)^T p + g(x) \leq 0\)，
    \(\|p\| \leq \Delta\)，
    其中 \(H\) 是拉格朗日函数的Hessian近似，\(p\) 为待求步长。

2. 计算初始点信息
在 \(x^{(0)} = (0, 0)\) 处计算函数值、梯度及约束：

  • 目标函数值：\(f(x^{(0)}) = 0^2 + 2 \cdot 0^2 - 2 \cdot 0 \cdot 0 + e^0 = 1\)。
  • 梯度：
    \(\nabla f(x) = [2x_1 - 2x_2 + e^{x_1}, 4x_2 - 2x_1]^T\)
    \(\nabla f(x^{(0)}) = [1, 0]^T\)。
  • 等式约束：\(h(x^{(0)}) = 0 + 0 - 1 = -1\)，
    \(\nabla h(x) = [1, 1]^T\)（常数）。
  • 不等式约束：\(g(x^{(0)}) = 0 + 0 - 2 = -2 \leq 0\)（满足），
    \(\nabla g(x) = [2x_1, 2x_2]^T\)，
    \(\nabla g(x^{(0)}) = [0, 0]^T\)。
  • 拉格朗日函数 \(\mathcal{L} = f(x) + \lambda h(x) + \mu g(x)\)，初始拉格朗日乘子设为 \(\lambda^{(0)} = 0\)，\(\mu^{(0)} = 0\)。
  • Hessian近似 \(H_0\) 使用单位矩阵 \(I_2\)（简化计算）。

3. 构造二次规划子问题
子问题目标函数：
\(Q(p) = \nabla f(x^{(0)})^T p + \frac{1}{2} p^T H_0 p = [1, 0] \begin{bmatrix} p_1 \\ p_2 \end{bmatrix} + \frac{1}{2} [p_1, p_2] I_2 \begin{bmatrix} p_1 \\ p_2 \end{bmatrix} = p_1 + \frac{1}{2} (p_1^2 + p_2^2)\)。
约束条件：

  • 等式约束：\(\nabla h(x^{(0)})^T p + h(x^{(0)}) = [1, 1] p + (-1) = p_1 + p_2 - 1 = 0\)。
  • 不等式约束：\(\nabla g(x^{(0)})^T p + g(x^{(0)}) = [0, 0] p + (-2) = -2 \leq 0\)（恒成立，可忽略）。
  • 信赖域约束：\(\|p\| \leq \Delta_0 = 0.5\)。

子问题简化为：
最小化 \(p_1 + \frac{1}{2}(p_1^2 + p_2^2)\)
约束于 \(p_1 + p_2 = 1\)，\(p_1^2 + p_2^2 \leq 0.25\)。

4. 求解子问题
从等式约束得 \(p_2 = 1 - p_1\)，代入目标函数：
\(Q(p) = p_1 + \frac{1}{2} [p_1^2 + (1 - p_1)^2] = p_1 + \frac{1}{2} (2p_1^2 - 2p_1 + 1) = p_1^2 + \frac{1}{2}\)。
问题转化为最小化 \(p_1^2\)（常数项忽略），约束于 \(p_1^2 + (1 - p_1)^2 \leq 0.25\)。
计算约束：\(p_1^2 + 1 - 2p_1 + p_1^2 = 2p_1^2 - 2p_1 + 1 \leq 0.25\)
→ \(2p_1^2 - 2p_1 + 0.75 \leq 0\) → \(4p_1^2 - 4p_1 + 1.5 \leq 0\)。
判别式 \(\Delta = 16 - 24 = -8 < 0\)，二次函数开口向上，无实数解（约束不可行）。
说明信赖域半径Δ太小，需放松约束。实际算法中会调整Δ，但本题要求固定Δ，故需在边界求解。
约束边界为 \(p_1^2 + p_2^2 = 0.25\)，结合 \(p_1 + p_2 = 1\)。
代入得 \(p_1^2 + (1 - p_1)^2 = 0.25\) → \(2p_1^2 - 2p_1 + 1 = 0.25\) → \(2p_1^2 - 2p_1 + 0.75 = 0\)。
解得 \(p_1 = \frac{2 \pm \sqrt{4 - 6}}{4} = \frac{2 \pm i\sqrt{2}}{4}\)（复数解，不可行）。
表明在Δ=0.5内无法满足等式约束，需使用约束松弛技术（如罚函数）或调整Δ。为简化，此处采用近似：忽略等式约束，在信赖域内最小化目标。
最小化 \(p_1 + \frac{1}{2}(p_1^2 + p_2^2)\)，约束 \(p_1^2 + p_2^2 \leq 0.25\)。
梯度为 \(\nabla Q(p) = [1 + p_1, p_2]^T\)，在无约束时最优解为 \(p = [-1, 0]\)，但超出信赖域。
在边界 \(\|p\| = 0.5\) 上，用拉格朗日法：最小化 \(Q(p) + \nu (\|p\|^2 - 0.25)\)。
得 \(1 + p_1 + 2\nu p_1 = 0\)，\(p_2 + 2\nu p_2 = 0\)。
若 \(p_2 \neq 0\)，则 \(1 + 2\nu = 0\) → \(\nu = -0.5\)，代入第一式：\(1 + p_1 - p_1 = 1 = 0\)矛盾。
故 \(p_2 = 0\)，则 \(p_1 = \pm 0.5\)。
代入目标：\(Q(0.5, 0) = 0.5 + 0.5 \cdot 0.25 = 0.625\)，
\(Q(-0.5, 0) = -0.5 + 0.5 \cdot 0.25 = -0.375\)。
最优步长 \(p = [-0.5, 0]^T\)。

5. 计算新迭代点
\(x^{(1)} = x^{(0)} + p = [0, 0]^T + [-0.5, 0]^T = [-0.5, 0]^T\)。
验证约束：
\(h(x^{(1)}) = -0.5 + 0 - 1 = -1.5 \neq 0\)（等式约束未满足，需在后续迭代中调整）。
\(g(x^{(1)}) = 0.25 + 0 - 2 = -1.75 \leq 0\)（满足）。

6. 算法总结
TR-SQP通过结合信赖域约束控制步长，确保迭代稳定性。本例中因固定Δ导致等式约束无法满足，实际应用会动态调整Δ或使用约束松弛。下一步需更新乘子和Hessian近似，继续迭代直至收敛。

非线性规划中的信赖域序列二次规划(TR-SQP)算法基础题 题目描述 考虑非线性规划问题： 最小化 \( f(x) = 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, 0) \)，信赖域半径初始值 \( \Delta_ 0 = 0.5 \)。 要求使用信赖域序列二次规划（TR-SQP）算法，通过一次迭代计算下一个迭代点 \( x^{(1)} \)。 解题过程 1. 算法原理概述 TR-SQP结合了序列二次规划（SQP）和信赖域法的优点： SQP通过求解二次规划子问题近似原问题，但需控制步长避免发散。 信赖域法限制步长在半径Δ内，保证收敛性。 TR-SQP的子问题形式为： 最小化 \( Q(p) = \nabla f(x)^T p + \frac{1}{2} p^T H p \) 约束于 \( \nabla h(x)^T p + h(x) = 0 \)， \( \nabla g(x)^T p + g(x) \leq 0 \)， \( \|p\| \leq \Delta \)， 其中 \( H \) 是拉格朗日函数的Hessian近似，\( p \) 为待求步长。 2. 计算初始点信息 在 \( x^{(0)} = (0, 0) \) 处计算函数值、梯度及约束： 目标函数值：\( f(x^{(0)}) = 0^2 + 2 \cdot 0^2 - 2 \cdot 0 \cdot 0 + e^0 = 1 \)。 梯度： \( \nabla f(x) = [ 2x_ 1 - 2x_ 2 + e^{x_ 1}, 4x_ 2 - 2x_ 1 ]^T \) \( \nabla f(x^{(0)}) = [ 1, 0 ]^T \)。 等式约束：\( h(x^{(0)}) = 0 + 0 - 1 = -1 \)， \( \nabla h(x) = [ 1, 1 ]^T \)（常数）。 不等式约束：\( g(x^{(0)}) = 0 + 0 - 2 = -2 \leq 0 \)（满足）， \( \nabla g(x) = [ 2x_ 1, 2x_ 2 ]^T \)， \( \nabla g(x^{(0)}) = [ 0, 0 ]^T \)。 拉格朗日函数 \( \mathcal{L} = f(x) + \lambda h(x) + \mu g(x) \)，初始拉格朗日乘子设为 \( \lambda^{(0)} = 0 \)，\( \mu^{(0)} = 0 \)。 Hessian近似 \( H_ 0 \) 使用单位矩阵 \( I_ 2 \)（简化计算）。 3. 构造二次规划子问题 子问题目标函数： \( Q(p) = \nabla f(x^{(0)})^T p + \frac{1}{2} p^T H_ 0 p = [ 1, 0] \begin{bmatrix} p_ 1 \\ p_ 2 \end{bmatrix} + \frac{1}{2} [ p_ 1, p_ 2] I_ 2 \begin{bmatrix} p_ 1 \\ p_ 2 \end{bmatrix} = p_ 1 + \frac{1}{2} (p_ 1^2 + p_ 2^2) \)。 约束条件： 等式约束：\( \nabla h(x^{(0)})^T p + h(x^{(0)}) = [ 1, 1] p + (-1) = p_ 1 + p_ 2 - 1 = 0 \)。 不等式约束：\( \nabla g(x^{(0)})^T p + g(x^{(0)}) = [ 0, 0 ] p + (-2) = -2 \leq 0 \)（恒成立，可忽略）。 信赖域约束：\( \|p\| \leq \Delta_ 0 = 0.5 \)。 子问题简化为： 最小化 \( p_ 1 + \frac{1}{2}(p_ 1^2 + p_ 2^2) \) 约束于 \( p_ 1 + p_ 2 = 1 \)，\( p_ 1^2 + p_ 2^2 \leq 0.25 \)。 4. 求解子问题 从等式约束得 \( p_ 2 = 1 - p_ 1 \)，代入目标函数： \( Q(p) = p_ 1 + \frac{1}{2} [ p_ 1^2 + (1 - p_ 1)^2] = p_ 1 + \frac{1}{2} (2p_ 1^2 - 2p_ 1 + 1) = p_ 1^2 + \frac{1}{2} \)。 问题转化为最小化 \( p_ 1^2 \)（常数项忽略），约束于 \( p_ 1^2 + (1 - p_ 1)^2 \leq 0.25 \)。 计算约束：\( p_ 1^2 + 1 - 2p_ 1 + p_ 1^2 = 2p_ 1^2 - 2p_ 1 + 1 \leq 0.25 \) → \( 2p_ 1^2 - 2p_ 1 + 0.75 \leq 0 \) → \( 4p_ 1^2 - 4p_ 1 + 1.5 \leq 0 \)。 判别式 \( \Delta = 16 - 24 = -8 < 0 \)，二次函数开口向上，无实数解（约束不可行）。 说明信赖域半径Δ太小，需放松约束。实际算法中会调整Δ，但本题要求固定Δ，故需在边界求解。 约束边界为 \( p_ 1^2 + p_ 2^2 = 0.25 \)，结合 \( p_ 1 + p_ 2 = 1 \)。 代入得 \( p_ 1^2 + (1 - p_ 1)^2 = 0.25 \) → \( 2p_ 1^2 - 2p_ 1 + 1 = 0.25 \) → \( 2p_ 1^2 - 2p_ 1 + 0.75 = 0 \)。 解得 \( p_ 1 = \frac{2 \pm \sqrt{4 - 6}}{4} = \frac{2 \pm i\sqrt{2}}{4} \)（复数解，不可行）。 表明在Δ=0.5内无法满足等式约束，需使用约束松弛技术（如罚函数）或调整Δ。为简化，此处采用近似：忽略等式约束，在信赖域内最小化目标。 最小化 \( p_ 1 + \frac{1}{2}(p_ 1^2 + p_ 2^2) \)，约束 \( p_ 1^2 + p_ 2^2 \leq 0.25 \)。 梯度为 \( \nabla Q(p) = [ 1 + p_ 1, p_ 2]^T \)，在无约束时最优解为 \( p = [ -1, 0 ] \)，但超出信赖域。 在边界 \( \|p\| = 0.5 \) 上，用拉格朗日法：最小化 \( Q(p) + \nu (\|p\|^2 - 0.25) \)。 得 \( 1 + p_ 1 + 2\nu p_ 1 = 0 \)，\( p_ 2 + 2\nu p_ 2 = 0 \)。 若 \( p_ 2 \neq 0 \)，则 \( 1 + 2\nu = 0 \) → \( \nu = -0.5 \)，代入第一式：\( 1 + p_ 1 - p_ 1 = 1 = 0 \)矛盾。 故 \( p_ 2 = 0 \)，则 \( p_ 1 = \pm 0.5 \)。 代入目标：\( Q(0.5, 0) = 0.5 + 0.5 \cdot 0.25 = 0.625 \)， \( Q(-0.5, 0) = -0.5 + 0.5 \cdot 0.25 = -0.375 \)。 最优步长 \( p = [ -0.5, 0 ]^T \)。 5. 计算新迭代点 \( x^{(1)} = x^{(0)} + p = [ 0, 0]^T + [ -0.5, 0]^T = [ -0.5, 0 ]^T \)。 验证约束： \( h(x^{(1)}) = -0.5 + 0 - 1 = -1.5 \neq 0 \)（等式约束未满足，需在后续迭代中调整）。 \( g(x^{(1)}) = 0.25 + 0 - 2 = -1.75 \leq 0 \)（满足）。 6. 算法总结 TR-SQP通过结合信赖域约束控制步长，确保迭代稳定性。本例中因固定Δ导致等式约束无法满足，实际应用会动态调整Δ或使用约束松弛。下一步需更新乘子和Hessian近似，继续迭代直至收敛。