非线性规划中的连续线性规划法基础题

字数 3495 2025-10-26 19:15:22

非线性规划中的连续线性规划法基础题

题目描述
考虑非线性规划问题：
最小化 \(f(x) = (x_1 - 2)^4 + (x_1 - 2x_2)^2\)
满足约束 \(x_1^2 - x_2 \geq 0\)。
初始点为 \(x^{(0)} = (0.0, 1.0)\)，使用连续线性规划法（Sequential Linear Programming, SLP）求解该问题，迭代两次（即计算 \(x^{(1)}\) 和 \(x^{(2)}\)），并控制步长避免违反约束。

解题过程

步骤1: 理解连续线性规划法的基本思想
SLP的核心是将非线性问题在每次迭代点 \(x^{(k)}\) 处线性化：

目标函数 \(f(x)\) 用一阶泰勒展开近似为线性函数 \(f(x) \approx f(x^{(k)}) + \nabla f(x^{(k)})^T (x - x^{(k)})\)。
非线性约束 \(g(x) \geq 0\) 线性化为 \(g(x^{(k)}) + \nabla g(x^{(k)})^T (x - x^{(k)}) \geq 0\)。
添加信任域约束 \(\|x - x^{(k)}\|_\infty \leq \delta^{(k)}\) 控制步长，防止线性近似失效。
求解线性规划子问题，得到新迭代点 \(x^{(k+1)}\)。

步骤2: 计算初始点 \(x^{(0)} = (0.0, 1.0)\) 的梯度和约束值

目标函数梯度：
\(\nabla f(x) = \left[ 4(x_1 - 2)^3 + 2(x_1 - 2x_2),\ -4(x_1 - 2x_2) \right]\)。
代入 \(x^{(0)}\)：
\(\nabla f(0,1) = [4(0-2)^3 + 2(0-2),\ -4(0-2)] = [4(-8) + 2(-2),\ 8] = [-32 - 4,\ 8] = [-36,\ 8]\)。
约束函数 \(g(x) = x_1^2 - x_2\)，约束要求 \(g(x) \geq 0\)。
梯度 \(\nabla g(x) = [2x_1,\ -1]\)，代入 \(x^{(0)}\)：
\(\nabla g(0,1) = [0,\ -1]\)，
\(g(0,1) = 0 - 1 = -1 < 0\)（初始点违反约束）。

步骤3: 第一次迭代（k=0）
子问题构建：
在 \(x^{(0)}\) 处线性化：

目标：最小化 \(\nabla f(x^{(0)})^T d = [-36,\ 8]^T d\)，其中 \(d = x - x^{(0)}\)。
约束线性化：
\(g(x^{(0)}) + \nabla g(x^{(0)})^T d \geq 0 \Rightarrow -1 + [0,\ -1]^T d \geq 0 \Rightarrow -1 - d_2 \geq 0 \Rightarrow d_2 \leq -1\)。
信任域约束：设 \(\delta^{(0)} = 0.5\)，要求 \(\|d\|_\infty \leq 0.5\)。

线性规划子问题：
最小化 \(-36d_1 + 8d_2\)
满足：

\(d_2 \leq -1\)（线性化约束），
\(-0.5 \leq d_1 \leq 0.5\)，
\(-0.5 \leq d_2 \leq 0.5\)（信任域约束）。

冲突分析：
约束 \(d_2 \leq -1\) 与信任域约束 \(d_2 \geq -0.5\) 矛盾，说明线性化约束不可行。此时需放松信任域或使用恢复阶段。这里采用放松信任域：忽略信任域约束，仅满足线性化约束，但需控制步长避免严重违反原始约束。

求解放松的子问题：
最小化 \(-36d_1 + 8d_2\)，满足 \(d_2 \leq -1\)。
目标函数系数中 \(d_1\) 的系数为负，因此增大 \(d_1\) 可降低目标值；\(d_2\) 系数为正，需取最小可能值 \(d_2 = -1\)。
无上界时问题无界，需限制步长。这里简单设 \(d_1 = 0.5\)（信任域允许的最大正值），得 \(d = (0.5,\ -1)\)。
新点 \(x^{(1)} = x^{(0)} + d = (0.5,\ 0.0)\)。

验证约束：
\(g(x^{(1)}) = 0.5^2 - 0 = 0.25 \geq 0\)（可行）。
目标函数值 \(f(x^{(1)}) = (0.5-2)^4 + (0.5 - 0)^2 = (-1.5)^4 + (0.5)^2 = 5.0625 + 0.25 = 5.3125\)。

步骤4: 第二次迭代（k=1）
在 \(x^{(1)} = (0.5, 0.0)\) 处线性化：

\(\nabla f(0.5,0) = [4(0.5-2)^3 + 2(0.5-0),\ -4(0.5-0)] = [4(-1.5)^3 + 2(0.5),\ -2] = [4(-3.375) + 1,\ -2] = [-13.5 + 1,\ -2] = [-12.5,\ -2]\)。
\(\nabla g(0.5,0) = [2 \times 0.5,\ -1] = [1,\ -1]\)，
\(g(0.5,0) = 0.25 - 0 = 0.25\)。

子问题构建：
最小化 \(\nabla f(x^{(1)})^T d = -12.5d_1 - 2d_2\)。
线性化约束：
\(g(x^{(1)}) + \nabla g(x^{(1)})^T d \geq 0 \Rightarrow 0.25 + [1,\ -1]^T d \geq 0 \Rightarrow 0.25 + d_1 - d_2 \geq 0\)。
信任域约束：设 \(\delta^{(1)} = 0.5\)，\(\|d\|_\infty \leq 0.5\)。

线性规划子问题：
最小化 \(-12.5d_1 - 2d_2\)
满足：

\(d_1 - d_2 \geq -0.25\)，
\(-0.5 \leq d_1 \leq 0.5\)，
\(-0.5 \leq d_2 \leq 0.5\)。

求解：
目标函数中 \(d_1\) 系数负，增大 \(d_1\) 可降低目标值；\(d_2\) 系数负，减小 \(d_2\) 可降低目标值。
约束 \(d_1 - d_2 \geq -0.25\) 较宽松。取 \(d_1 = 0.5\)，\(d_2 = -0.5\)（极端值）：
检查约束： \(0.5 - (-0.5) = 1.0 \geq -0.25\)（满足）。
目标值： \(-12.5 \times 0.5 - 2 \times (-0.5) = -6.25 + 1 = -5.25\)。

新点 \(x^{(2)} = (0.5+0.5,\ 0.0-0.5) = (1.0,\ -0.5)\)。

验证：
\(g(x^{(2)}) = 1^2 - (-0.5) = 1 + 0.5 = 1.5 \geq 0\)（可行）。
\(f(x^{(2)}) = (1-2)^4 + (1 - 2(-0.5))^2 = (-1)^4 + (1+1)^2 = 1 + 4 = 5\)。

步骤5: 迭代结果分析
两次迭代后：

\(x^{(0)} = (0.0, 1.0)\)，\(f = 68\)，约束违反。
\(x^{(1)} = (0.5, 0.0)\)，\(f = 5.3125\)，可行。
\(x^{(2)} = (1.0, -0.5)\)，\(f = 5\)，可行。
目标函数值下降，且满足约束。SLM通过线性近似和步长控制逐步逼近最优解（该问题最优解在 \(x^* = (2, 1)\)，\(f = 0\)）。

非线性规划中的连续线性规划法基础题题目描述考虑非线性规划问题：最小化 \( f(x) = (x_ 1 - 2)^4 + (x_ 1 - 2x_ 2)^2 \) 满足约束 \( x_ 1^2 - x_ 2 \geq 0 \)。初始点为 \( x^{(0)} = (0.0, 1.0) \)，使用连续线性规划法（Sequential Linear Programming, SLP）求解该问题，迭代两次（即计算 \( x^{(1)} \) 和 \( x^{(2)} \)），并控制步长避免违反约束。解题过程步骤1: 理解连续线性规划法的基本思想 SLP的核心是将非线性问题在每次迭代点 \( x^{(k)} \) 处线性化：目标函数 \( f(x) \) 用一阶泰勒展开近似为线性函数 \( f(x) \approx f(x^{(k)}) + \nabla f(x^{(k)})^T (x - x^{(k)}) \)。非线性约束 \( g(x) \geq 0 \) 线性化为 \( g(x^{(k)}) + \nabla g(x^{(k)})^T (x - x^{(k)}) \geq 0 \)。添加信任域约束 \( \|x - x^{(k)}\|_ \infty \leq \delta^{(k)} \) 控制步长，防止线性近似失效。求解线性规划子问题，得到新迭代点 \( x^{(k+1)} \)。步骤2: 计算初始点 \( x^{(0)} = (0.0, 1.0) \) 的梯度和约束值目标函数梯度： \( \nabla f(x) = \left[ 4(x_ 1 - 2)^3 + 2(x_ 1 - 2x_ 2),\ -4(x_ 1 - 2x_ 2) \right ] \)。代入 \( x^{(0)} \)： \( \nabla f(0,1) = [ 4(0-2)^3 + 2(0-2),\ -4(0-2)] = [ 4(-8) + 2(-2),\ 8] = [ -32 - 4,\ 8] = [ -36,\ 8 ] \)。约束函数 \( g(x) = x_ 1^2 - x_ 2 \)，约束要求 \( g(x) \geq 0 \)。梯度 \( \nabla g(x) = [ 2x_ 1,\ -1 ] \)，代入 \( x^{(0)} \)： \( \nabla g(0,1) = [ 0,\ -1 ] \)， \( g(0,1) = 0 - 1 = -1 < 0 \)（初始点违反约束）。步骤3: 第一次迭代（k=0）子问题构建：在 \( x^{(0)} \) 处线性化：目标：最小化 \( \nabla f(x^{(0)})^T d = [ -36,\ 8 ]^T d \)，其中 \( d = x - x^{(0)} \)。约束线性化： \( g(x^{(0)}) + \nabla g(x^{(0)})^T d \geq 0 \Rightarrow -1 + [ 0,\ -1]^T d \geq 0 \Rightarrow -1 - d_ 2 \geq 0 \Rightarrow d_ 2 \leq -1 \)。信任域约束：设 \( \delta^{(0)} = 0.5 \)，要求 \( \|d\|_ \infty \leq 0.5 \)。线性规划子问题：最小化 \( -36d_ 1 + 8d_ 2 \) 满足： \( d_ 2 \leq -1 \)（线性化约束）， \( -0.5 \leq d_ 1 \leq 0.5 \)， \( -0.5 \leq d_ 2 \leq 0.5 \)（信任域约束）。冲突分析：约束 \( d_ 2 \leq -1 \) 与信任域约束 \( d_ 2 \geq -0.5 \) 矛盾，说明线性化约束不可行。此时需放松信任域或使用恢复阶段。这里采用放松信任域：忽略信任域约束，仅满足线性化约束，但需控制步长避免严重违反原始约束。求解放松的子问题：最小化 \( -36d_ 1 + 8d_ 2 \)，满足 \( d_ 2 \leq -1 \)。目标函数系数中 \( d_ 1 \) 的系数为负，因此增大 \( d_ 1 \) 可降低目标值；\( d_ 2 \) 系数为正，需取最小可能值 \( d_ 2 = -1 \)。无上界时问题无界，需限制步长。这里简单设 \( d_ 1 = 0.5 \)（信任域允许的最大正值），得 \( d = (0.5,\ -1) \)。新点 \( x^{(1)} = x^{(0)} + d = (0.5,\ 0.0) \)。验证约束： \( g(x^{(1)}) = 0.5^2 - 0 = 0.25 \geq 0 \)（可行）。目标函数值 \( f(x^{(1)}) = (0.5-2)^4 + (0.5 - 0)^2 = (-1.5)^4 + (0.5)^2 = 5.0625 + 0.25 = 5.3125 \)。步骤4: 第二次迭代（k=1）在 \( x^{(1)} = (0.5, 0.0) \) 处线性化： \( \nabla f(0.5,0) = [ 4(0.5-2)^3 + 2(0.5-0),\ -4(0.5-0)] = [ 4(-1.5)^3 + 2(0.5),\ -2] = [ 4(-3.375) + 1,\ -2] = [ -13.5 + 1,\ -2] = [ -12.5,\ -2 ] \)。 \( \nabla g(0.5,0) = [ 2 \times 0.5,\ -1] = [ 1,\ -1 ] \)， \( g(0.5,0) = 0.25 - 0 = 0.25 \)。子问题构建：最小化 \( \nabla f(x^{(1)})^T d = -12.5d_ 1 - 2d_ 2 \)。线性化约束： \( g(x^{(1)}) + \nabla g(x^{(1)})^T d \geq 0 \Rightarrow 0.25 + [ 1,\ -1]^T d \geq 0 \Rightarrow 0.25 + d_ 1 - d_ 2 \geq 0 \)。信任域约束：设 \( \delta^{(1)} = 0.5 \)，\( \|d\|_ \infty \leq 0.5 \)。线性规划子问题：最小化 \( -12.5d_ 1 - 2d_ 2 \) 满足： \( d_ 1 - d_ 2 \geq -0.25 \)， \( -0.5 \leq d_ 1 \leq 0.5 \)， \( -0.5 \leq d_ 2 \leq 0.5 \)。求解：目标函数中 \( d_ 1 \) 系数负，增大 \( d_ 1 \) 可降低目标值；\( d_ 2 \) 系数负，减小 \( d_ 2 \) 可降低目标值。约束 \( d_ 1 - d_ 2 \geq -0.25 \) 较宽松。取 \( d_ 1 = 0.5 \)，\( d_ 2 = -0.5 \)（极端值）：检查约束： \( 0.5 - (-0.5) = 1.0 \geq -0.25 \)（满足）。目标值： \( -12.5 \times 0.5 - 2 \times (-0.5) = -6.25 + 1 = -5.25 \)。新点 \( x^{(2)} = (0.5+0.5,\ 0.0-0.5) = (1.0,\ -0.5) \)。验证： \( g(x^{(2)}) = 1^2 - (-0.5) = 1 + 0.5 = 1.5 \geq 0 \)（可行）。 \( f(x^{(2)}) = (1-2)^4 + (1 - 2(-0.5))^2 = (-1)^4 + (1+1)^2 = 1 + 4 = 5 \)。步骤5: 迭代结果分析两次迭代后： \( x^{(0)} = (0.0, 1.0) \)，\( f = 68 \)，约束违反。 \( x^{(1)} = (0.5, 0.0) \)，\( f = 5.3125 \)，可行。 \( x^{(2)} = (1.0, -0.5) \)，\( f = 5 \)，可行。目标函数值下降，且满足约束。SLM通过线性近似和步长控制逐步逼近最优解（该问题最优解在 \( x^* = (2, 1) \)，\( f = 0 \)）。