非线性规划中的可行方向法基础题
字数 4514 2025-10-25 22:15:07

非线性规划中的可行方向法基础题

题目描述
考虑非线性规划问题：
最小化 \(f(x)1, x_2) = (x_1 - 2)^2 + (x_2 - 1)^2\)
满足约束：

\[\begin{aligned} g_1(x_1, x_2) &= x_1 + x_2 - 2 \leq 0, \\ g_2(x_1, x_2) &= x_1^2 - x_2 \leq 0. \end{aligned} \]

初始点为 \(x^{(0)} = (0, 0)\)，该点满足所有约束。请使用可行方向法（Zoutendijk 可行方向法）执行一次迭代，找到下一个迭代点 \(x^{(1)}\)。

解题过程
可行方向法的核心思想是：在可行域内，沿着一个能使目标函数值下降且不违反约束的方向移动。Zoutendijk 法通过求解一个线性规划子问题来寻找这样的方向。

步骤 1: 计算当前点的梯度
在初始点 \(x^{(0)} = (0, 0)\)：

  • 目标函数梯度：
    \(\nabla f(x) = \left( 2(x_1 - 2),\ 2(x_2 - 1) \right)\)
    代入 \(x^{(0)}\)：
    \(\nabla f(0,0) = (-4, -2)\)
  • 约束函数梯度：
    \(\nabla g_1(x) = (1, 1)\)（恒为常数）
    \(\nabla g_2(x) = (2x_1, -1)\)
    代入 \(x^{(0)}\)：
    \(\nabla g_2(0,0) = (0, -1)\)

步骤 2: 确定起作用的约束（Active Constraints）
计算约束函数值：

  • \(g_1(0,0) = 0 + 0 - 2 = -2 < 0\)（非起作用约束）
  • \(g_2(0,0) = 0 - 0 = 0\)（等于 0，是起作用约束）

因此，起作用约束集合 \(I = \{2\}\)，只有 \(g_2\) 在 \(x^{(0)}\) 处起作用。

步骤 3: 构建寻找可行方向的线性规划子问题
我们需要找到一个方向 \(\mathbf{d} = (d_1, d_2)\) 和一个实数 \(\theta\)，使得：

  1. 可行性条件：沿方向 \(\mathbf{d}\) 移动不会立即违反起作用约束。即对于所有起作用约束 \(i \in I\)，有 \(\nabla g_i(x^{(0)})^T \mathbf{d} \leq 0\)。
  2. 下降条件：方向 \(\mathbf{d}\) 能使目标函数下降，即 \(\nabla f(x^{(0)})^T \mathbf{d} < 0\)。

为了将寻找 \(\mathbf{d}\) 的过程规范化，Zoutendijk 法求解以下线性规划问题：

\[\begin{aligned} \min_{\mathbf{d}, \theta} \quad & \theta \\ \text{s.t.} \quad & \nabla f(x^{(0)})^T \mathbf{d} \leq \theta, \\ & \nabla g_i(x^{(0)})^T \mathbf{d} \leq \theta, \quad \forall i \in I, \\ & -1 \leq d_j \leq 1, \quad j=1,2. \end{aligned} \]

这里 \(\theta\) 是一个辅助变量，如果最终求得 \(\theta < 0\)，则说明我们找到了一个下降可行方向。对 \(d_j\) 的边界约束是为了防止方向向量无限大。

代入已知的梯度和 \(I = \{2\}\)：

\[\begin{aligned} \min_{d_1, d_2, \theta} \quad & \theta \\ \text{s.t.} \quad & (-4, -2) \cdot (d_1, d_2) \leq \theta \quad \Rightarrow \quad -4d_1 - 2d_2 \leq \theta, \\ & \nabla g_2(0,0)^T \mathbf{d} \leq \theta \quad \Rightarrow \quad (0, -1) \cdot (d_1, d_2) \leq \theta \quad \Rightarrow \quad -d_2 \leq \theta, \\ & -1 \leq d_1 \leq 1, \\ & -1 \leq d_2 \leq 1. \end{aligned} \]

步骤 4: 求解线性规划子问题
我们需要最小化 \(\theta\)。观察约束：

  • 第一个约束：\(-4d_1 - 2d_2 - \theta \leq 0\)
  • 第二个约束：\(-d_2 - \theta \leq 0\)

为了使 \(\theta\) 尽可能小（最好是负数），我们希望 \(d_1\) 和 \(d_2\) 在允许的范围内 \([-1,1]\)，使得左边表达式尽可能小。

  1. 看第二个约束 \(-d_2 \leq \theta\)。为了让 \(\theta\) 能取小值，我们希望 \(-d_2\) 小，即 \(d_2\) 要大。令 \(d_2 = 1\)（最大值），则约束变为 \(-1 \leq \theta\)。
  2. 看第一个约束 \(-4d_1 - 2d_2 \leq \theta\)。代入 \(d_2 = 1\)，得 \(-4d_1 - 2 \leq \theta\)。为了让 \(\theta\) 小，我们希望 \(-4d_1\) 小，即 \(d_1\) 要大。令 \(d_1 = 1\)（最大值），则约束变为 \(-4(1) - 2(1) = -6 \leq \theta\)。
  3. 现在，\(\theta\) 必须同时满足 \(\theta \geq -1\)（来自约束2）和 \(\theta \geq -6\)（来自约束1）。最紧的约束是 \(\theta \geq -1\)。
  4. 为了最小化 \(\theta\)，我们取它能取的最小值 \(\theta = -1\)。

检查 \(d_1=1, d_2=1, \theta=-1\) 是否满足所有约束：

  • 约束1：\(-4(1) - 2(1) = -6 \leq -1\) 成立。
  • 约束2：\(-1 = -1 \leq -1\) 成立。
  • 变量边界：\(d_1=1, d_2=1\) 在 \([-1,1]\) 内。

因此，最优解为 \(\mathbf{d} = (1, 1)\)，\(\theta = -1\)。由于 \(\theta = -1 < 0\)，我们成功找到了一个下降可行方向 \(\mathbf{d}\)。

步骤 5: 沿可行方向进行一维搜索
现在我们从 \(x^{(0)}\) 出发，沿方向 \(\mathbf{d} = (1, 1)\) 移动：
\(x = x^{(0)} + \alpha \mathbf{d} = (0, 0) + \alpha (1, 1) = (\alpha, \alpha)\)，其中步长 \(\alpha > 0\)。

我们需要找到最大的 \(\alpha\) 使得新点 \(x\) 仍在可行域内（满足所有约束），并且目标函数 \(f(x)\) 尽可能小。

  1. 确定最大允许步长 \(\alpha_{\text{max}}\)：

    • 约束 \(g_1(x) = x_1 + x_2 - 2 \leq 0\)：代入 \(x=(\alpha, \alpha)\)，得 \(\alpha + \alpha - 2 \leq 0 \Rightarrow 2\alpha \leq 2 \Rightarrow \alpha \leq 1\)。
    • 约束 \(g_2(x) = x_1^2 - x_2 \leq 0\)：代入 \(x=(\alpha, \alpha)\)，得 \(\alpha^2 - \alpha \leq 0 \Rightarrow \alpha(\alpha - 1) \leq 0\)。由于 \(\alpha \geq 0\)，此不等式等价于 \(\alpha \leq 1\)。
    • 因此，最大允许步长 \(\alpha_{\text{max}} = 1\)。当 \(\alpha=1\) 时，点 \(x=(1,1)\) 正好在约束 \(g_1\) 和 \(g_2\) 的边界上。

  2. 最小化 \(f(x)\) 关于 \(\alpha\)：
    目标函数 \(f(\alpha, \alpha) = (\alpha - 2)^2 + (\alpha - 1)^2 = (\alpha^2 - 4\alpha + 4) + (\alpha^2 - 2\alpha + 1) = 2\alpha^2 - 6\alpha + 5\)。
    这是一个关于 \(\alpha\) 的二次函数，开口向上。其最小值在导数零点处：\(\frac{d f}{d \alpha} = 4\alpha - 6 = 0 \Rightarrow \alpha^* = 1.5\)。
    然而，\(\alpha^* = 1.5\) 超过了最大允许步长 \(\alpha_{\text{max}} = 1\)。因此，在可行范围 \([0, 1]\) 内，函数 \(f(\alpha)\) 是单调递减的（因为顶点在 1.5，区间 [0,1] 在顶点左侧）。所以，在 \(\alpha = 1\) 处目标函数取得可行域内的最小值。

步骤 6: 得到新的迭代点
取步长 \(\alpha = 1\)（最大可行步长），得到下一个迭代点：
\(x^{(1)} = x^{(0)} + 1 \cdot \mathbf{d} = (0, 0) + (1, 1) = (1, 1)\)。

结果
通过一次 Zoutendijk 可行方向法迭代，我们从初始点 \(x^{(0)} = (0,0)\) 移动到了新点 \(x^{(1)} = (1,1)\)。在该点，目标函数值从 \(f(0,0)=5\) 下降到了 \(f(1,1)=1\)，并且新点仍然满足所有约束（实际上位于两个约束的边界上）。

非线性规划中的可行方向法基础题 题目描述 考虑非线性规划问题： 最小化 \( f(x)1, x_ 2) = (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \) 满足约束： \[ \begin{aligned} g_ 1(x_ 1, x_ 2) &= x_ 1 + x_ 2 - 2 \leq 0, \\ g_ 2(x_ 1, x_ 2) &= x_ 1^2 - x_ 2 \leq 0. \end{aligned} \] 初始点为 \( x^{(0)} = (0, 0) \)，该点满足所有约束。请使用可行方向法（Zoutendijk 可行方向法）执行一次迭代，找到下一个迭代点 \( x^{(1)} \)。 解题过程 可行方向法的核心思想是：在可行域内，沿着一个能使目标函数值下降且不违反约束的方向移动。Zoutendijk 法通过求解一个线性规划子问题来寻找这样的方向。 步骤 1: 计算当前点的梯度 在初始点 \( x^{(0)} = (0, 0) \)： 目标函数梯度： \( \nabla f(x) = \left( 2(x_ 1 - 2),\ 2(x_ 2 - 1) \right) \) 代入 \( x^{(0)} \)： \( \nabla f(0,0) = (-4, -2) \) 约束函数梯度： \( \nabla g_ 1(x) = (1, 1) \)（恒为常数） \( \nabla g_ 2(x) = (2x_ 1, -1) \) 代入 \( x^{(0)} \)： \( \nabla g_ 2(0,0) = (0, -1) \) 步骤 2: 确定起作用的约束（Active Constraints） 计算约束函数值： \( g_ 1(0,0) = 0 + 0 - 2 = -2 < 0 \)（非起作用约束） \( g_ 2(0,0) = 0 - 0 = 0 \)（等于 0，是起作用约束） 因此，起作用约束集合 \( I = \{2\} \)，只有 \( g_ 2 \) 在 \( x^{(0)} \) 处起作用。 步骤 3: 构建寻找可行方向的线性规划子问题 我们需要找到一个方向 \( \mathbf{d} = (d_ 1, d_ 2) \) 和一个实数 \( \theta \)，使得： 可行性条件 ：沿方向 \( \mathbf{d} \) 移动不会立即违反起作用约束。即对于所有起作用约束 \( i \in I \)，有 \( \nabla g_ i(x^{(0)})^T \mathbf{d} \leq 0 \)。 下降条件 ：方向 \( \mathbf{d} \) 能使目标函数下降，即 \( \nabla f(x^{(0)})^T \mathbf{d} < 0 \)。 为了将寻找 \( \mathbf{d} \) 的过程规范化，Zoutendijk 法求解以下线性规划问题： \[ \begin{aligned} \min_ {\mathbf{d}, \theta} \quad & \theta \\ \text{s.t.} \quad & \nabla f(x^{(0)})^T \mathbf{d} \leq \theta, \\ & \nabla g_ i(x^{(0)})^T \mathbf{d} \leq \theta, \quad \forall i \in I, \\ & -1 \leq d_ j \leq 1, \quad j=1,2. \end{aligned} \] 这里 \( \theta \) 是一个辅助变量，如果最终求得 \( \theta < 0 \)，则说明我们找到了一个下降可行方向。对 \( d_ j \) 的边界约束是为了防止方向向量无限大。 代入已知的梯度和 \( I = \{2\} \)： \[ \begin{aligned} \min_ {d_ 1, d_ 2, \theta} \quad & \theta \\ \text{s.t.} \quad & (-4, -2) \cdot (d_ 1, d_ 2) \leq \theta \quad \Rightarrow \quad -4d_ 1 - 2d_ 2 \leq \theta, \\ & \nabla g_ 2(0,0)^T \mathbf{d} \leq \theta \quad \Rightarrow \quad (0, -1) \cdot (d_ 1, d_ 2) \leq \theta \quad \Rightarrow \quad -d_ 2 \leq \theta, \\ & -1 \leq d_ 1 \leq 1, \\ & -1 \leq d_ 2 \leq 1. \end{aligned} \] 步骤 4: 求解线性规划子问题 我们需要最小化 \( \theta \)。观察约束： 第一个约束：\( -4d_ 1 - 2d_ 2 - \theta \leq 0 \) 第二个约束：\( -d_ 2 - \theta \leq 0 \) 为了使 \( \theta \) 尽可能小（最好是负数），我们希望 \( d_ 1 \) 和 \( d_ 2 \) 在允许的范围内 \([ -1,1 ]\)，使得左边表达式尽可能小。 看第二个约束 \( -d_ 2 \leq \theta \)。为了让 \( \theta \) 能取小值，我们希望 \( -d_ 2 \) 小，即 \( d_ 2 \) 要大。令 \( d_ 2 = 1 \)（最大值），则约束变为 \( -1 \leq \theta \)。 看第一个约束 \( -4d_ 1 - 2d_ 2 \leq \theta \)。代入 \( d_ 2 = 1 \)，得 \( -4d_ 1 - 2 \leq \theta \)。为了让 \( \theta \) 小，我们希望 \( -4d_ 1 \) 小，即 \( d_ 1 \) 要大。令 \( d_ 1 = 1 \)（最大值），则约束变为 \( -4(1) - 2(1) = -6 \leq \theta \)。 现在，\( \theta \) 必须同时满足 \( \theta \geq -1 \)（来自约束2）和 \( \theta \geq -6 \)（来自约束1）。最紧的约束是 \( \theta \geq -1 \)。 为了最小化 \( \theta \)，我们取它能取的最小值 \( \theta = -1 \)。 检查 \( d_ 1=1, d_ 2=1, \theta=-1 \) 是否满足所有约束： 约束1：\( -4(1) - 2(1) = -6 \leq -1 \) 成立。 约束2：\( -1 = -1 \leq -1 \) 成立。 变量边界：\( d_ 1=1, d_ 2=1 \) 在 \([ -1,1 ]\) 内。 因此，最优解为 \( \mathbf{d} = (1, 1) \)，\( \theta = -1 \)。由于 \( \theta = -1 < 0 \)，我们成功找到了一个下降可行方向 \( \mathbf{d} \)。 步骤 5: 沿可行方向进行一维搜索 现在我们从 \( x^{(0)} \) 出发，沿方向 \( \mathbf{d} = (1, 1) \) 移动： \( x = x^{(0)} + \alpha \mathbf{d} = (0, 0) + \alpha (1, 1) = (\alpha, \alpha) \)，其中步长 \( \alpha > 0 \)。 我们需要找到最大的 \( \alpha \) 使得新点 \( x \) 仍在可行域内（满足所有约束），并且目标函数 \( f(x) \) 尽可能小。 确定最大允许步长 \( \alpha_ {\text{max}} \) ： 约束 \( g_ 1(x) = x_ 1 + x_ 2 - 2 \leq 0 \)：代入 \( x=(\alpha, \alpha) \)，得 \( \alpha + \alpha - 2 \leq 0 \Rightarrow 2\alpha \leq 2 \Rightarrow \alpha \leq 1 \)。 约束 \( g_ 2(x) = x_ 1^2 - x_ 2 \leq 0 \)：代入 \( x=(\alpha, \alpha) \)，得 \( \alpha^2 - \alpha \leq 0 \Rightarrow \alpha(\alpha - 1) \leq 0 \)。由于 \( \alpha \geq 0 \)，此不等式等价于 \( \alpha \leq 1 \)。 因此，最大允许步长 \( \alpha_ {\text{max}} = 1 \)。当 \( \alpha=1 \) 时，点 \( x=(1,1) \) 正好在约束 \( g_ 1 \) 和 \( g_ 2 \) 的边界上。 最小化 \( f(x) \) 关于 \( \alpha \) ： 目标函数 \( f(\alpha, \alpha) = (\alpha - 2)^2 + (\alpha - 1)^2 = (\alpha^2 - 4\alpha + 4) + (\alpha^2 - 2\alpha + 1) = 2\alpha^2 - 6\alpha + 5 \)。 这是一个关于 \( \alpha \) 的二次函数，开口向上。其最小值在导数零点处：\( \frac{d f}{d \alpha} = 4\alpha - 6 = 0 \Rightarrow \alpha^* = 1.5 \)。 然而，\( \alpha^* = 1.5 \) 超过了最大允许步长 \( \alpha_ {\text{max}} = 1 \)。因此，在可行范围 \( [ 0, 1] \) 内，函数 \( f(\alpha) \) 是单调递减的（因为顶点在 1.5，区间 [ 0,1 ] 在顶点左侧）。所以，在 \( \alpha = 1 \) 处目标函数取得可行域内的最小值。 步骤 6: 得到新的迭代点 取步长 \( \alpha = 1 \)（最大可行步长），得到下一个迭代点： \( x^{(1)} = x^{(0)} + 1 \cdot \mathbf{d} = (0, 0) + (1, 1) = (1, 1) \)。 结果 通过一次 Zoutendijk 可行方向法迭代，我们从初始点 \( x^{(0)} = (0,0) \) 移动到了新点 \( x^{(1)} = (1,1) \)。在该点，目标函数值从 \( f(0,0)=5 \) 下降到了 \( f(1,1)=1 \)，并且新点仍然满足所有约束（实际上位于两个约束的边界上）。