非线性规划中的逐步二次逼近法基础题
字数 2403 2025-10-27 11:27:25

非线性规划中的逐步二次逼近法基础题

题目描述：
考虑非线性规划问题：

\[\min f(x) = (x_1 - 2)^4 + (x_1 - 2x_2)^2 \]

初始点为 \(x^{(0)} = (0, 3)^T\)，试用逐步二次逼近法（Sequential Quadratic Programming, SQP）进行一次迭代，并给出下一次迭代点 \(x^{(1)}\)。

解题过程：

1. 问题分析
逐步二次逼近法的核心思想是：在每次迭代中，将原非线性规划问题转化为一个二次规划（QP）子问题，通过求解该子问题得到搜索方向，再沿该方向更新迭代点。对于无约束问题（本题），SQP等价于牛顿法，但需构造拉格朗日函数的Hessian矩阵。

2. 构造拉格朗日函数
由于本题无约束，拉格朗日函数即为目标函数：

\[\mathcal{L}(x) = f(x) = (x_1 - 2)^4 + (x_1 - 2x_2)^2 \]

3. 计算梯度与Hessian矩阵

  • 梯度：

\[\nabla f(x) = \begin{bmatrix} 4(x_1 - 2)^3 + 2(x_1 - 2x_2) \\ -4(x_1 - 2x_2) \end{bmatrix} \]

在初始点 \(x^{(0)} = (0, 3)^T\) 处：

\[\nabla f(x^{(0)}) = \begin{bmatrix} 4(0-2)^3 + 2(0 - 6) \\ -4(0 - 6) \end{bmatrix} = \begin{bmatrix} 4(-8) + 2(-6) \\ 24 \end{bmatrix} = \begin{bmatrix} -32 - 12 \\ 24 \end{bmatrix} = \begin{bmatrix} -44 \\ 24 \end{bmatrix} \]

  • Hessian矩阵：

\[\nabla^2 f(x) = \begin{bmatrix} 12(x_1 - 2)^2 + 2 & -4 \\ -4 & 8 \end{bmatrix} \]

在 \(x^{(0)}\) 处：

\[\nabla^2 f(x^{(0)}) = \begin{bmatrix} 12(0-2)^2 + 2 & -4 \\ -4 & 8 \end{bmatrix} = \begin{bmatrix} 12 \cdot 4 + 2 & -4 \\ -4 & 8 \end{bmatrix} = \begin{bmatrix} 50 & -4 \\ -4 & 8 \end{bmatrix} \]

4. 构建二次规划子问题
在 \(x^{(0)}\) 处，二次逼近子问题为：

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

代入数值：

\[\min_{d} \quad \frac{1}{2} \begin{bmatrix} d_1 & d_2 \end{bmatrix} \begin{bmatrix} 50 & -4 \\ -4 & 8 \end{bmatrix} \begin{bmatrix} d_1 \\ d_2 \end{bmatrix} + \begin{bmatrix} -44 & 24 \end{bmatrix} \begin{bmatrix} d_1 \\ d_2 \end{bmatrix} \]

展开目标函数：

\[\frac{1}{2} (50d_1^2 - 8d_1d_2 + 8d_2^2) - 44d_1 + 24d_2 \]

5. 求解QP子问题
令梯度为零：

\[\begin{cases} 50d_1 - 4d_2 - 44 = 0 \\ -4d_1 + 8d_2 + 24 = 0 \end{cases} \]

解方程组：
由第二式得 \(-4d_1 + 8d_2 = -24\)，即 \(d_1 - 2d_2 = 6\)（式①）。
由第一式得 \(50d_1 - 4d_2 = 44\)（式②）。
将①代入②：

\[50(2d_2 + 6) - 4d_2 = 44 \implies 100d_2 + 300 - 4d_2 = 44 \implies 96d_2 = -256 \implies d_2 = -\frac{8}{3} \]

代入①得：

\[d_1 = 6 + 2 \cdot \left(-\frac{8}{3}\right) = 6 - \frac{16}{3} = \frac{2}{3} \]

故搜索方向 \(d = \left( \frac{2}{3}, -\frac{8}{3} \right)^T\)。

6. 更新迭代点
采用单位步长（牛顿法默认步长为1）：

\[x^{(1)} = x^{(0)} + d = \begin{bmatrix} 0 \\ 3 \end{bmatrix} + \begin{bmatrix} \frac{2}{3} \\ -\frac{8}{3} \end{bmatrix} = \begin{bmatrix} \frac{2}{3} \\ \frac{1}{3} \end{bmatrix} \]

结果：
一次迭代后得到新点 \(x^{(1)} = \left( \frac{2}{3}, \frac{1}{3} \right)^T\)。
该方法通过局部二次模型逼近原函数，收敛速度快，但需计算Hessian矩阵。

非线性规划中的逐步二次逼近法基础题 题目描述 ： 考虑非线性规划问题： \[ \min f(x) = (x_ 1 - 2)^4 + (x_ 1 - 2x_ 2)^2 \] 初始点为 \( x^{(0)} = (0, 3)^T \)，试用逐步二次逼近法（Sequential Quadratic Programming, SQP）进行一次迭代，并给出下一次迭代点 \( x^{(1)} \)。 解题过程 ： 1. 问题分析 逐步二次逼近法的核心思想是：在每次迭代中，将原非线性规划问题转化为一个二次规划（QP）子问题，通过求解该子问题得到搜索方向，再沿该方向更新迭代点。对于无约束问题（本题），SQP等价于牛顿法，但需构造拉格朗日函数的Hessian矩阵。 2. 构造拉格朗日函数 由于本题无约束，拉格朗日函数即为目标函数： \[ \mathcal{L}(x) = f(x) = (x_ 1 - 2)^4 + (x_ 1 - 2x_ 2)^2 \] 3. 计算梯度与Hessian矩阵 梯度 ： \[ \nabla f(x) = \begin{bmatrix} 4(x_ 1 - 2)^3 + 2(x_ 1 - 2x_ 2) \\ -4(x_ 1 - 2x_ 2) \end{bmatrix} \] 在初始点 \( x^{(0)} = (0, 3)^T \) 处： \[ \nabla f(x^{(0)}) = \begin{bmatrix} 4(0-2)^3 + 2(0 - 6) \\ -4(0 - 6) \end{bmatrix} = \begin{bmatrix} 4(-8) + 2(-6) \\ 24 \end{bmatrix} = \begin{bmatrix} -32 - 12 \\ 24 \end{bmatrix} = \begin{bmatrix} -44 \\ 24 \end{bmatrix} \] Hessian矩阵 ： \[ \nabla^2 f(x) = \begin{bmatrix} 12(x_ 1 - 2)^2 + 2 & -4 \\ -4 & 8 \end{bmatrix} \] 在 \( x^{(0)} \) 处： \[ \nabla^2 f(x^{(0)}) = \begin{bmatrix} 12(0-2)^2 + 2 & -4 \\ -4 & 8 \end{bmatrix} = \begin{bmatrix} 12 \cdot 4 + 2 & -4 \\ -4 & 8 \end{bmatrix} = \begin{bmatrix} 50 & -4 \\ -4 & 8 \end{bmatrix} \] 4. 构建二次规划子问题 在 \( x^{(0)} \) 处，二次逼近子问题为： \[ \min_ {d} \quad \frac{1}{2} d^T \nabla^2 f(x^{(0)}) d + \nabla f(x^{(0)})^T d \] 代入数值： \[ \min_ {d} \quad \frac{1}{2} \begin{bmatrix} d_ 1 & d_ 2 \end{bmatrix} \begin{bmatrix} 50 & -4 \\ -4 & 8 \end{bmatrix} \begin{bmatrix} d_ 1 \\ d_ 2 \end{bmatrix} + \begin{bmatrix} -44 & 24 \end{bmatrix} \begin{bmatrix} d_ 1 \\ d_ 2 \end{bmatrix} \] 展开目标函数： \[ \frac{1}{2} (50d_ 1^2 - 8d_ 1d_ 2 + 8d_ 2^2) - 44d_ 1 + 24d_ 2 \] 5. 求解QP子问题 令梯度为零： \[ \begin{cases} 50d_ 1 - 4d_ 2 - 44 = 0 \\ -4d_ 1 + 8d_ 2 + 24 = 0 \end{cases} \] 解方程组： 由第二式得 \( -4d_ 1 + 8d_ 2 = -24 \)，即 \( d_ 1 - 2d_ 2 = 6 \)（式①）。 由第一式得 \( 50d_ 1 - 4d_ 2 = 44 \)（式②）。 将①代入②： \[ 50(2d_ 2 + 6) - 4d_ 2 = 44 \implies 100d_ 2 + 300 - 4d_ 2 = 44 \implies 96d_ 2 = -256 \implies d_ 2 = -\frac{8}{3} \] 代入①得： \[ d_ 1 = 6 + 2 \cdot \left(-\frac{8}{3}\right) = 6 - \frac{16}{3} = \frac{2}{3} \] 故搜索方向 \( d = \left( \frac{2}{3}, -\frac{8}{3} \right)^T \)。 6. 更新迭代点 采用单位步长（牛顿法默认步长为1）： \[ x^{(1)} = x^{(0)} + d = \begin{bmatrix} 0 \\ 3 \end{bmatrix} + \begin{bmatrix} \frac{2}{3} \\ -\frac{8}{3} \end{bmatrix} = \begin{bmatrix} \frac{2}{3} \\ \frac{1}{3} \end{bmatrix} \] 结果 ： 一次迭代后得到新点 \( x^{(1)} = \left( \frac{2}{3}, \frac{1}{3} \right)^T \)。 该方法通过局部二次模型逼近原函数，收敛速度快，但需计算Hessian矩阵。