非线性规划中的序列线性规划法基础题

字数 2827 2025-10-26 19:15:23

非线性规划中的序列线性规划法基础题

题目描述
考虑非线性规划问题：
最小化 \(f(x) = (x_1 - 2)^4 + (x_1 - 2x_2)^2\)
满足约束：
\(g_1(x) = x_1^2 - x_2 \leq 0\)
\(g_2(x) = x_1^2 + x_2^2 - 2 \leq 0\)
初始点 \(x^{(0)} = (0, 1)^T\)，采用序列线性规划法求解该问题。

解题过程

序列线性规划法的核心思想是将非线性规划问题在迭代点 \(x^{(k)}\) 处线性化（即用一阶泰勒展开近似），转化为线性规划子问题，通过求解子问题得到搜索方向，再沿该方向进行线搜索确定新迭代点。

步骤1：问题线性化
在点 \(x^{(k)}\) 处，对目标函数和约束函数进行线性化：

目标函数线性化：用一阶泰勒展开近似 \(f(x)\)，即 \(f(x) ≈ f(x^{(k)}) + \nabla f(x^{(k)})^T (x - x^{(k)})\)。由于常数项 \(f(x^{(k)})\) 不影响优化方向，子问题可简化为最小化 \(\nabla f(x^{(k)})^T d\)，其中 \(d = x - x^{(k)}\) 为搜索方向。
约束线性化：\(g_j(x) ≈ g_j(x^{(k)}) + \nabla g_j(x^{(k)})^T d \leq 0\)。

因此，在 \(x^{(k)}\) 处的线性规划子问题为：
最小化 \(\nabla f(x^{(k)})^T d\)
满足：
\(g_j(x^{(k)}) + \nabla g_j(x^{(k)})^T d \leq 0 \quad (j=1,2)\)
以及信赖域约束 \(\|d\|_\infty \leq \Delta^{(k)}\)（防止线性化误差过大，需限制步长）。

步骤2：计算初始点梯度及约束值
在 \(x^{(0)} = (0, 1)^T\)：

梯度 \(\nabla f(x) = \left[ 4(x_1 - 2)^3 + 2(x_1 - 2x_2), -4(x_1 - 2x_2) \right]^T\)，代入得 \(\nabla f(x^{(0)}) = [4(0-2)^3 + 2(0-2), -4(0-2)] = [-32 -4, 8] = [-36, 8]^T\)。
约束值：\(g_1(x^{(0)}) = 0^2 - 1 = -1\)，\(g_2(x^{(0)}) = 0^2 + 1^2 - 2 = -1\)。
约束梯度：\(\nabla g_1(x) = [2x_1, -1]^T\)，得 \(\nabla g_1(x^{(0)}) = [0, -1]^T\)；\(\nabla g_2(x) = [2x_1, 2x_2]^T\)，得 \(\nabla g_2(x^{(0)}) = [0, 2]^T\)。

设初始信赖域半径 \(\Delta^{(0)} = 0.5\)。

步骤3：构建并求解第一个线性规划子问题
子问题形式：
最小化 \(-36d_1 + 8d_2\)
满足：

\(g_1\) 线性化：\(-1 + [0, -1]d \leq 0\) → \(-1 - d_2 \leq 0\) → \(d_2 \geq -1\)。
\(g_2\) 线性化：\(-1 + [0, 2]d \leq 0\) → \(-1 + 2d_2 \leq 0\) → \(d_2 \leq 0.5\)。
信赖域约束：\(|d_1| \leq 0.5\)，\(|d_2| \leq 0.5\)。

子问题简化：目标函数中 \(d_1\) 的系数为负，为使目标最小化，应取 \(d_1\) 的最大值 \(d_1 = 0.5\)；\(d_2\) 的系数为正，应取最小值。结合约束：

\(d_2 \geq -1\) 且 \(d_2 \geq -0.5\)（信赖域），故下界为 \(d_2 = -0.5\)。
\(d_2 \leq 0.5\) 且 \(d_2 \leq 0.5\)，故上界为 \(d_2 = 0.5\)。
由于目标函数中 \(d_2\) 系数为正，取 \(d_2 = -0.5\) 可降低目标值。
因此最优解为 \(d^{(0)} = (0.5, -0.5)^T\)。

步骤4：线搜索确定新迭代点
新点 \(x^{(1)} = x^{(0)} + \alpha d^{(0)} = (0, 1)^T + \alpha (0.5, -0.5)\)，其中 \(\alpha \in (0, 1]\) 为步长（通常取 \(\alpha = 1\)，若不可行或目标下降不足，则缩小）。
计算 \(x^{(1)} = (0.5, 0.5)^T\)（取 \(\alpha = 1\)）：

约束检查：\(g_1 = 0.5^2 - 0.5 = -0.25 \leq 0\)，\(g_2 = 0.5^2 + 0.5^2 - 2 = -1.5 \leq 0\)，可行。
目标值：\(f(x^{(1)}) = (0.5-2)^4 + (0.5-1)^2 = 5.0625 + 0.25 = 5.3125\)，较 \(f(x^{(0)}) = (0-2)^4 + (0-2)^2 = 16 + 4 = 20\) 下降，接受该点。

步骤5：迭代过程
以 \(x^{(1)} = (0.5, 0.5)^T\) 为新起点，重复线性化：

计算梯度：\(\nabla f(x^{(1)}) = [4(0.5-2)^3 + 2(0.5-1), -4(0.5-1)] = [-4(1.5^3) -1, 2] ≈ [-13.5 -1, 2] = [-14.5, 2]^T\)。
约束值：\(g_1 = -0.25\)，\(g_2 = -1.5\)；梯度：\(\nabla g_1 = [1, -1]^T\)，\(\nabla g_2 = [1, 1]^T\)。
构建新子问题并求解，逐步逼近最优解。通常迭代直至 \(\|d\|\) 足够小或目标函数变化不大。

总结
序列线性规划法通过反复求解线性规划子问题逼近非线性问题解。关键步骤包括线性化、求解方向、线搜索。本例中，经过一次迭代，目标函数从20降至5.31，后续迭代将继续收敛至更优解。

非线性规划中的序列线性规划法基础题题目描述考虑非线性规划问题：最小化 \( f(x) = (x_ 1 - 2)^4 + (x_ 1 - 2x_ 2)^2 \) 满足约束： \( g_ 1(x) = x_ 1^2 - x_ 2 \leq 0 \) \( g_ 2(x) = x_ 1^2 + x_ 2^2 - 2 \leq 0 \) 初始点 \( x^{(0)} = (0, 1)^T \)，采用序列线性规划法求解该问题。解题过程序列线性规划法的核心思想是将非线性规划问题在迭代点 \( x^{(k)} \) 处线性化（即用一阶泰勒展开近似），转化为线性规划子问题，通过求解子问题得到搜索方向，再沿该方向进行线搜索确定新迭代点。步骤1：问题线性化在点 \( x^{(k)} \) 处，对目标函数和约束函数进行线性化：目标函数线性化：用一阶泰勒展开近似 \( f(x) \)，即 \( f(x) ≈ f(x^{(k)}) + \nabla f(x^{(k)})^T (x - x^{(k)}) \)。由于常数项 \( f(x^{(k)}) \) 不影响优化方向，子问题可简化为最小化 \( \nabla f(x^{(k)})^T d \)，其中 \( d = x - x^{(k)} \) 为搜索方向。约束线性化：\( g_ j(x) ≈ g_ j(x^{(k)}) + \nabla g_ j(x^{(k)})^T d \leq 0 \)。因此，在 \( x^{(k)} \) 处的线性规划子问题为：最小化 \( \nabla f(x^{(k)})^T d \) 满足： \( g_ j(x^{(k)}) + \nabla g_ j(x^{(k)})^T d \leq 0 \quad (j=1,2) \) 以及信赖域约束 \( \|d\|_ \infty \leq \Delta^{(k)} \)（防止线性化误差过大，需限制步长）。步骤2：计算初始点梯度及约束值在 \( x^{(0)} = (0, 1)^T \)：梯度 \( \nabla f(x) = \left[ 4(x_ 1 - 2)^3 + 2(x_ 1 - 2x_ 2), -4(x_ 1 - 2x_ 2) \right]^T \)，代入得 \( \nabla f(x^{(0)}) = [ 4(0-2)^3 + 2(0-2), -4(0-2)] = [ -32 -4, 8] = [ -36, 8 ]^T \)。约束值：\( g_ 1(x^{(0)}) = 0^2 - 1 = -1 \)，\( g_ 2(x^{(0)}) = 0^2 + 1^2 - 2 = -1 \)。约束梯度：\( \nabla g_ 1(x) = [ 2x_ 1, -1]^T \)，得 \( \nabla g_ 1(x^{(0)}) = [ 0, -1]^T \)；\( \nabla g_ 2(x) = [ 2x_ 1, 2x_ 2]^T \)，得 \( \nabla g_ 2(x^{(0)}) = [ 0, 2 ]^T \)。设初始信赖域半径 \( \Delta^{(0)} = 0.5 \)。步骤3：构建并求解第一个线性规划子问题子问题形式：最小化 \( -36d_ 1 + 8d_ 2 \) 满足： \( g_ 1 \) 线性化：\( -1 + [ 0, -1]d \leq 0 \) → \( -1 - d_ 2 \leq 0 \) → \( d_ 2 \geq -1 \)。 \( g_ 2 \) 线性化：\( -1 + [ 0, 2]d \leq 0 \) → \( -1 + 2d_ 2 \leq 0 \) → \( d_ 2 \leq 0.5 \)。信赖域约束：\( |d_ 1| \leq 0.5 \)，\( |d_ 2| \leq 0.5 \)。子问题简化：目标函数中 \( d_ 1 \) 的系数为负，为使目标最小化，应取 \( d_ 1 \) 的最大值 \( d_ 1 = 0.5 \)；\( d_ 2 \) 的系数为正，应取最小值。结合约束： \( d_ 2 \geq -1 \) 且 \( d_ 2 \geq -0.5 \)（信赖域），故下界为 \( d_ 2 = -0.5 \)。 \( d_ 2 \leq 0.5 \) 且 \( d_ 2 \leq 0.5 \)，故上界为 \( d_ 2 = 0.5 \)。由于目标函数中 \( d_ 2 \) 系数为正，取 \( d_ 2 = -0.5 \) 可降低目标值。因此最优解为 \( d^{(0)} = (0.5, -0.5)^T \)。步骤4：线搜索确定新迭代点新点 \( x^{(1)} = x^{(0)} + \alpha d^{(0)} = (0, 1)^T + \alpha (0.5, -0.5) \)，其中 \( \alpha \in (0, 1 ] \) 为步长（通常取 \( \alpha = 1 \)，若不可行或目标下降不足，则缩小）。计算 \( x^{(1)} = (0.5, 0.5)^T \)（取 \( \alpha = 1 \)）：约束检查：\( g_ 1 = 0.5^2 - 0.5 = -0.25 \leq 0 \)，\( g_ 2 = 0.5^2 + 0.5^2 - 2 = -1.5 \leq 0 \)，可行。目标值：\( f(x^{(1)}) = (0.5-2)^4 + (0.5-1)^2 = 5.0625 + 0.25 = 5.3125 \)，较 \( f(x^{(0)}) = (0-2)^4 + (0-2)^2 = 16 + 4 = 20 \) 下降，接受该点。步骤5：迭代过程以 \( x^{(1)} = (0.5, 0.5)^T \) 为新起点，重复线性化：计算梯度：\( \nabla f(x^{(1)}) = [ 4(0.5-2)^3 + 2(0.5-1), -4(0.5-1)] = [ -4(1.5^3) -1, 2] ≈ [ -13.5 -1, 2] = [ -14.5, 2 ]^T \)。约束值：\( g_ 1 = -0.25 \)，\( g_ 2 = -1.5 \)；梯度：\( \nabla g_ 1 = [ 1, -1]^T \)，\( \nabla g_ 2 = [ 1, 1 ]^T \)。构建新子问题并求解，逐步逼近最优解。通常迭代直至 \( \|d\| \) 足够小或目标函数变化不大。总结序列线性规划法通过反复求解线性规划子问题逼近非线性问题解。关键步骤包括线性化、求解方向、线搜索。本例中，经过一次迭代，目标函数从20降至5.31，后续迭代将继续收敛至更优解。