非线性规划中的序列线性化方法(SLM)基础题

字数 2802 2025-10-30 08:32:20

非线性规划中的序列线性化方法(SLM)基础题

题目描述：
考虑非线性规划问题：
最小化 \(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 - 4 \leq 0\)
初始点为 \(x^{(0)} = (2, 1)\)，使用序列线性化方法(SLM)进行一次迭代，找到下一个迭代点。

解题过程：

1. 方法原理介绍
序列线性化方法(SLM)是一种通过将非线性问题在当前点进行线性化，然后求解线性子问题来逐步逼近原问题解的方法。其核心步骤是：

在当前迭代点 \(x^{(k)}\) 处对目标函数和约束函数进行一阶泰勒展开
构建线性规划子问题
求解该子问题得到搜索方向
通过线搜索确定步长，得到新迭代点

2. 初始点可行性验证
首先验证初始点 \(x^{(0)} = (2, 1)\) 的可行性：

\(g_1(2,1) = 2^2 - 1 = 4 - 1 = 3 > 0\) ❌ 不满足约束
\(g_2(2,1) = 2^2 + 1^2 - 4 = 4 + 1 - 4 = 1 > 0\) ❌ 不满足约束

由于初始点不满足约束条件，我们需要先找到第一个可行点。在实际应用中，SLM通常从可行点开始，但这里我们演示如何处理不可行初始点。

3. 构建线性化子问题
在当前点 \(x^{(0)} = (2,1)\) 处进行线性化：

目标函数线性化：
\(f(x) ≈ f(x^{(0)}) + ∇f(x^{(0)})^T (x - x^{(0)})\)

计算梯度：\(∇f(x) = \begin{bmatrix} 4(x_1-2)^3 + 2(x_1-2x_2) \\ -4(x_1-2x_2) \end{bmatrix}\)
在 \(x^{(0)} = (2,1)\) 处：
\(∇f(2,1) = \begin{bmatrix} 4(0)^3 + 2(2-2) \\ -4(2-2) \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}\)
\(f(2,1) = (0)^4 + (0)^2 = 0\)

因此线性化目标：\(f(x) ≈ 0 + [0, 0] \begin{bmatrix} x_1-2 \\ x_2-1 \end{bmatrix} = 0\)

约束函数线性化：
\(g_1(x) ≈ g_1(x^{(0)}) + ∇g_1(x^{(0)})^T (x - x^{(0)})\)
\(∇g_1(x) = \begin{bmatrix} 2x_1 \\ -1 \end{bmatrix}\)，在 \(x^{(0)}\) 处：\(∇g_1(2,1) = \begin{bmatrix} 4 \\ -1 \end{bmatrix}\)
\(g_1(2,1) = 3\)
线性化：\(g_1(x) ≈ 3 + [4, -1] \begin{bmatrix} x_1-2 \\ x_2-1 \end{bmatrix} ≤ 0\)

\(g_2(x) ≈ g_2(x^{(0)}) + ∇g_2(x^{(0)})^T (x - x^{(0)})\)
\(∇g_2(x) = \begin{bmatrix} 2x_1 \\ 2x_2 \end{bmatrix}\)，在 \(x^{(0)}\) 处：\(∇g_2(2,1) = \begin{bmatrix} 4 \\ 2 \end{bmatrix}\)
\(g_2(2,1) = 1\)
线性化：\(g_2(x) ≈ 1 + [4, 2] \begin{bmatrix} x_1-2 \\ x_2-1 \end{bmatrix} ≤ 0\)

4. 构建线性规划子问题
最小化：\(0\)（常数目标函数）
满足：
\(3 + 4(x_1-2) - (x_2-1) ≤ 0\) → \(4x_1 - x_2 - 4 ≤ 0\)
\(1 + 4(x_1-2) + 2(x_2-1) ≤ 0\) → \(4x_1 + 2x_2 - 9 ≤ 0\)

由于目标函数为常数，我们实际上是在寻找可行点，即求解：
\(4x_1 - x_2 ≤ 4\)
\(4x_1 + 2x_2 ≤ 9\)

5. 求解线性子问题
这是一个可行性问题。我们可以添加一个目标函数，如最小化 \(x_1 + x_2\) 来找到"最中心"的可行点。

求解方程组：
从第一个约束：\(x_2 ≥ 4x_1 - 4\)
从第二个约束：\(x_2 ≤ \frac{9 - 4x_1}{2}\)

令 \(4x_1 - 4 = \frac{9 - 4x_1}{2}\)
\(8x_1 - 8 = 9 - 4x_1\)
\(12x_1 = 17\)
\(x_1 = 17/12 ≈ 1.4167\)
\(x_2 = 4×(17/12) - 4 = 68/12 - 48/12 = 20/12 = 5/3 ≈ 1.6667\)

验证：\(4×1.4167 - 1.6667 = 5.6668 - 1.6667 = 4.0001 ≈ 4\)
\(4×1.4167 + 2×1.6667 = 5.6668 + 3.3334 = 9.0002 ≈ 9\)

6. 确定新迭代点
由于从不可行点开始，我们直接取线性子问题的解作为新点：
\(x^{(1)} = (17/12, 5/3) ≈ (1.4167, 1.6667)\)

7. 验证新点的可行性
计算原约束在新点的值：
\(g_1(17/12, 5/3) = (17/12)^2 - 5/3 = 289/144 - 240/144 = 49/144 > 0\) ❌ 仍不可行
\(g_2(17/12, 5/3) = (289/144) + (25/9) - 4 = 289/144 + 400/144 - 576/144 = 113/144 > 0\) ❌ 仍不可行

这表明单次线性化可能不足以找到可行点，需要继续迭代。

8. 方法总结
序列线性化方法通过反复线性化和求解来逼近原问题解。当从不可行点开始时，前几次迭代主要目标是找到可行点，然后才优化目标函数。实际应用中会结合信赖域或罚函数来控制线性近似的有效性范围。

非线性规划中的序列线性化方法(SLM)基础题题目描述：考虑非线性规划问题：最小化 \( 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 - 4 \leq 0 \) 初始点为 \( x^{(0)} = (2, 1) \)，使用序列线性化方法(SLM)进行一次迭代，找到下一个迭代点。解题过程： 1. 方法原理介绍序列线性化方法(SLM)是一种通过将非线性问题在当前点进行线性化，然后求解线性子问题来逐步逼近原问题解的方法。其核心步骤是：在当前迭代点 \( x^{(k)} \) 处对目标函数和约束函数进行一阶泰勒展开构建线性规划子问题求解该子问题得到搜索方向通过线搜索确定步长，得到新迭代点 2. 初始点可行性验证首先验证初始点 \( x^{(0)} = (2, 1) \) 的可行性： \( g_ 1(2,1) = 2^2 - 1 = 4 - 1 = 3 > 0 \) ❌ 不满足约束 \( g_ 2(2,1) = 2^2 + 1^2 - 4 = 4 + 1 - 4 = 1 > 0 \) ❌ 不满足约束由于初始点不满足约束条件，我们需要先找到第一个可行点。在实际应用中，SLM通常从可行点开始，但这里我们演示如何处理不可行初始点。 3. 构建线性化子问题在当前点 \( x^{(0)} = (2,1) \) 处进行线性化：目标函数线性化： \( f(x) ≈ f(x^{(0)}) + ∇f(x^{(0)})^T (x - x^{(0)}) \) 计算梯度：\( ∇f(x) = \begin{bmatrix} 4(x_ 1-2)^3 + 2(x_ 1-2x_ 2) \\ -4(x_ 1-2x_ 2) \end{bmatrix} \) 在 \( x^{(0)} = (2,1) \) 处： \( ∇f(2,1) = \begin{bmatrix} 4(0)^3 + 2(2-2) \\ -4(2-2) \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} \) \( f(2,1) = (0)^4 + (0)^2 = 0 \) 因此线性化目标：\( f(x) ≈ 0 + [ 0, 0] \begin{bmatrix} x_ 1-2 \\ x_ 2-1 \end{bmatrix} = 0 \) 约束函数线性化： \( g_ 1(x) ≈ g_ 1(x^{(0)}) + ∇g_ 1(x^{(0)})^T (x - x^{(0)}) \) \( ∇g_ 1(x) = \begin{bmatrix} 2x_ 1 \\ -1 \end{bmatrix} \)，在 \( x^{(0)} \) 处：\( ∇g_ 1(2,1) = \begin{bmatrix} 4 \\ -1 \end{bmatrix} \) \( g_ 1(2,1) = 3 \) 线性化：\( g_ 1(x) ≈ 3 + [ 4, -1] \begin{bmatrix} x_ 1-2 \\ x_ 2-1 \end{bmatrix} ≤ 0 \) \( g_ 2(x) ≈ g_ 2(x^{(0)}) + ∇g_ 2(x^{(0)})^T (x - x^{(0)}) \) \( ∇g_ 2(x) = \begin{bmatrix} 2x_ 1 \\ 2x_ 2 \end{bmatrix} \)，在 \( x^{(0)} \) 处：\( ∇g_ 2(2,1) = \begin{bmatrix} 4 \\ 2 \end{bmatrix} \) \( g_ 2(2,1) = 1 \) 线性化：\( g_ 2(x) ≈ 1 + [ 4, 2] \begin{bmatrix} x_ 1-2 \\ x_ 2-1 \end{bmatrix} ≤ 0 \) 4. 构建线性规划子问题最小化：\( 0 \)（常数目标函数）满足： \( 3 + 4(x_ 1-2) - (x_ 2-1) ≤ 0 \) → \( 4x_ 1 - x_ 2 - 4 ≤ 0 \) \( 1 + 4(x_ 1-2) + 2(x_ 2-1) ≤ 0 \) → \( 4x_ 1 + 2x_ 2 - 9 ≤ 0 \) 由于目标函数为常数，我们实际上是在寻找可行点，即求解： \( 4x_ 1 - x_ 2 ≤ 4 \) \( 4x_ 1 + 2x_ 2 ≤ 9 \) 5. 求解线性子问题这是一个可行性问题。我们可以添加一个目标函数，如最小化 \( x_ 1 + x_ 2 \) 来找到"最中心"的可行点。求解方程组：从第一个约束：\( x_ 2 ≥ 4x_ 1 - 4 \) 从第二个约束：\( x_ 2 ≤ \frac{9 - 4x_ 1}{2} \) 令 \( 4x_ 1 - 4 = \frac{9 - 4x_ 1}{2} \) \( 8x_ 1 - 8 = 9 - 4x_ 1 \) \( 12x_ 1 = 17 \) \( x_ 1 = 17/12 ≈ 1.4167 \) \( x_ 2 = 4×(17/12) - 4 = 68/12 - 48/12 = 20/12 = 5/3 ≈ 1.6667 \) 验证：\( 4×1.4167 - 1.6667 = 5.6668 - 1.6667 = 4.0001 ≈ 4 \) \( 4×1.4167 + 2×1.6667 = 5.6668 + 3.3334 = 9.0002 ≈ 9 \) 6. 确定新迭代点由于从不可行点开始，我们直接取线性子问题的解作为新点： \( x^{(1)} = (17/12, 5/3) ≈ (1.4167, 1.6667) \) 7. 验证新点的可行性计算原约束在新点的值： \( g_ 1(17/12, 5/3) = (17/12)^2 - 5/3 = 289/144 - 240/144 = 49/144 > 0 \) ❌ 仍不可行 \( g_ 2(17/12, 5/3) = (289/144) + (25/9) - 4 = 289/144 + 400/144 - 576/144 = 113/144 > 0 \) ❌ 仍不可行这表明单次线性化可能不足以找到可行点，需要继续迭代。 8. 方法总结序列线性化方法通过反复线性化和求解来逼近原问题解。当从不可行点开始时，前几次迭代主要目标是找到可行点，然后才优化目标函数。实际应用中会结合信赖域或罚函数来控制线性近似的有效性范围。