尚未出现

字数 5621 2025-12-08 01:30:44

好的，我注意到在你的“已讲过的题目”列表中，虽然算法种类繁多，但有一个经典且重要的约束优化直接方法尚未出现。今天我将为你讲解这个方法的原理和应用。

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

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

\[\begin{aligned} \min_{x \in \mathbb{R}^2} \quad & f(x) = (x_1 - 3)^2 + (x_2 - 2)^2 \\ \text{s.t.} \quad & g_1(x) = x_1 + x_2 - 2 \le 0, \\ & g_2(x) = -x_1 + 2x_2 - 1 \le 0, \\ & x_1 \ge 0, \, x_2 \ge 0. \end{aligned} \]

请从初始可行点 $x^{(0)} = (0, 0)$ 出发，使用可行方向法（Specifically，我们使用Zoutendijk可行方向法的基本步骤）进行一次迭代，找到下一个可行点 $x^{(1)}$，使得目标函数值得以减小。我们要求搜索方向 $d$ 通过求解一个线性规划（LP）子问题来获得。

解题过程循序渐进讲解：

第一步：理解问题结构与初始点

我们的目标是最小化一个二次函数 $f(x)$，它实际上是以点 (3, 2) 为圆心的圆半径平方。约束是两个线性不等式和两个变量的非负约束，它们共同构成了一个凸可行域。

给定的初始点 $x^{(0)} = (0, 0)$：

检查可行性：
- $g_1(0,0) = 0+0-2 = -2 \le 0$ ✅
- $g_2(0,0) = -0+0-1 = -1 \le 0$ ✅
- $x_1 \ge 0, x_2 \ge 0$ ✅
  所以 $x^{(0)}$ 是可行点。
计算目标函数值：$f(0,0) = (0-3)^2 + (0-2)^2 = 9 + 4 = 13$。
判断约束的活跃性（Active Constraints）：在 $x^{(0)}$ 处，约束 $g_1$ 和 $g_2$ 都是严格小于0的（-2和-1），因此它们是非活跃约束。只有非负约束 $x_1 \ge 0$ 和 $x_2 \ge 0$ 是活跃的（因为 $x_1=0, x_2=0$）。

第二步：可行方向法的核心思想

可行方向法是一种迭代算法，在每次迭代中，从一个可行点 $x^{(k)}$ 出发：

寻找一个可行下降方向 $d$：这个方向需要满足两个条件：
- 下降条件：沿该方向移动，目标函数值会减小。数学上，要求方向 $d$ 与目标函数负梯度（即最速下降方向）的夹角为锐角，即 $\nabla f(x^{(k)})^T d < 0$。
- 可行条件：从当前点沿该方向移动一个足够小的步长，仍然保持在可行域内。对于活跃的约束，沿该方向移动不应违反它（对于线性约束，要求 $\nabla g_i(x^{(k)})^T d \le 0$）；对于非活跃约束，只要步长足够小，就不会违反。
沿方向 $d$ 进行一维搜索：确定一个步长 $\alpha > 0$，使得新点 $x^{(k+1)} = x^{(k)} + \alpha d$ 可行，且 $f(x^{(k+1)}) < f(x^{(k)})$。
更新迭代点，重复过程。

Zoutendijk可行方向法是实现这个思想的一种系统化方式，它将寻找方向 $d$ 的问题转化成一个线性规划问题。

第三步：在当前点 $x^{(0)}$ 计算梯度和活跃约束集

目标函数梯度：

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

在 $ x^{(0)} = (0,0) $ 处：

\[ \nabla f^{(0)} = \nabla f(0,0) = \begin{bmatrix} -6 \\ -4 \end{bmatrix} \]

负梯度方向是 $ (6, 4) $，即指向右上方，这正是函数值下降最快的方向。

约束梯度：
- $\nabla g_1(x) = [1, 1]^T$
- $\nabla g_2(x) = [-1, 2]^T$
- $\nabla (x_1 \ge 0)$ 对应的约束可以写为 $-x_1 \le 0$，其梯度为 $[-1, 0]^T$。
- $\nabla (x_2 \ge 0)$ 对应的约束可以写为 $-x_2 \le 0$，其梯度为 $[0, -1]^T$。
确定活跃约束集 $I_A$：
在 $x^{(0)}$，$g_1$ 和 $g_2$ 非活跃。活跃的是两个边界约束：
$I_A = \{ \text{“非负约束1”}, \text{“非负约束2”} \}$，对应的梯度矩阵为：

\[ A = \begin{bmatrix} -1 & 0 \\ 0 & -1 \end{bmatrix} \]

第四步：构建并求解寻找可行下降方向的线性规划子问题

Zoutendijk法的标准子问题是：

\[\begin{aligned} \min_{\beta \in \mathbb{R}, \, d \in \mathbb{R}^n} \quad & \beta \\ \text{s.t.} \quad & \nabla f(x^{(k)})^T d \le \beta, \\ & \nabla g_i(x^{(k)})^T d \le \beta, \quad \forall i \in I_A, \\ & -1 \le d_j \le 1, \quad j=1,...,n. \end{aligned} \]

目标：最小化 $\beta$。如果最优解 $\beta^* < 0$，说明我们找到了一个方向 $d^*$ 使得所有活跃约束的“改善程度”和目标函数的“下降程度”都至少是 $\beta^*$（一个负数），这是一个严格的可行下降方向。
约束 $-1 \le d_j \le 1$：是为了防止方向 $d$ 的模无限大，将问题规范化。

代入我们的数据 $\nabla f^{(0)} = [-6, -4]^T$ 和 $A = \begin{bmatrix} -1 & 0 \\ 0 & -1 \end{bmatrix}$：

$\nabla f^{(0)})^T d = -6d_1 - 4d_2 \le \beta$
第一个活跃约束梯度：$[-1, 0]^T d = -d_1 \le \beta$
第二个活跃约束梯度：$[0, -1]^T d = -d_2 \le \beta$
$-1 \le d_1 \le 1, \, -1 \le d_2 \le 1$

因此，线性规划子问题为：

\[\begin{aligned} \min \quad & \beta \\ \text{s.t.} \quad & -6d_1 - 4d_2 - \beta \le 0, \\ & -d_1 - \beta \le 0, \\ & -d_2 - \beta \le 0, \\ & -1 \le d_1 \le 1, \\ & -1 \le d_2 \le 1. \end{aligned} \]

第五步：求解该线性规划

我们可以通过观察或简单推理来求解。我们希望 $\beta$ 尽可能小（负得越多越好）。

观察第一个约束 $-6d_1 -4d_2 \le \beta$。为了让 $\beta$ 小，我们希望左边尽可能小（负得多）。由于 $d_1, d_2$ 最大为1，那么 $-6d_1 -4d_2$ 在 $d_1=1, d_2=1$ 时取得最小值 -10。所以 $\beta$ 至少是 -10。
再检查其他约束：当 $d_1=1, d_2=1$ 时，$-d_1 = -1$，$-d_2 = -1$，它们都大于 -10，所以不会限制 $\beta$ 变得更小。
边界条件 $d_1 \le 1, d_2 \le 1$ 在 $d_1=1, d_2=1$ 时取到等号。
因此，一个最优解是 $d_1^* = 1, d_2^* = 1, \beta^* = -10$。

结论：我们找到了一个可行下降方向 $d^{(0)} = (1, 1)^T$。因为 $\beta^* = -10 < 0$，这验证了它同时满足：

下降条件：$\nabla f^{(0)})^T d = -6*1 -4*1 = -10 < 0$。
可行性条件（对于活跃约束）：对于 $-x_1 \le 0$，有 $[-1,0]^T d = -1 < 0$；对于 $-x_2 \le 0$，有 $[0,-1]^T d = -1 < 0 $。这意味着从原点沿 (1,1) 方向移动一点点，$x_1$ 和 $x_2$ 都会变成正数，严格满足约束。

第六步：沿方向 $d^{(0)}$ 进行一维搜索（确定步长 $\alpha$）

现在我们需要找到 $\alpha > 0$，使得 $x^{(1)} = (0,0) + \alpha(1,1) = (\alpha, \alpha)$ 可行，并且最小化（或减小）$f(x)$。

确定最大可行步长 $\alpha_{\text{max}}$：我们需要确保新点满足所有约束。
- $g_1(\alpha, \alpha) = \alpha + \alpha - 2 = 2\alpha - 2 \le 0 \Rightarrow \alpha \le 1$
- $g_2(\alpha, \alpha) = -\alpha + 2\alpha - 1 = \alpha - 1 \le 0 \Rightarrow \alpha \le 1$
- 非负约束自动满足（因为 $\alpha > 0$）。
  所以，最大可行步长 $\alpha_{\text{max}} = 1$。当 $\alpha = 1$ 时，点 (1,1) 使得 $g_1$ 和 $g_2$ 同时取等号（即同时触及两个约束边界）。
在 $[0, \alpha_{\text{max}}]$ 区间内最小化 $f(\alpha)$：
$f(x^{(1)}) = f(\alpha, \alpha) = (\alpha - 3)^2 + (\alpha - 2)^2 = 2\alpha^2 - 10\alpha + 13$。
这是一个关于 $\alpha$ 的二次凸函数。其导数 $f'(\alpha) = 4\alpha - 10$。
令 $f'(\alpha) = 0$ 得驻点 $\alpha^* = 2.5$。
然而，$\alpha^* = 2.5 > \alpha_{\text{max}} = 1$。这意味着在可行区间 $[0, 1]$ 内，函数 $f(\alpha)$ 是单调递减的（因为导数在 $\alpha=1$ 时为 $4*1-10 = -6 < 0$）。
选择最优步长：为了最大程度减小目标函数，同时保证可行性，我们应选择最大可行步长，即 $\alpha^{(0)} = 1$。

第七步：得到新迭代点并结束本次迭代

新点为：

\[x^{(1)} = x^{(0)} + \alpha^{(0)} d^{(0)} = (0,0) + 1 * (1,1) = (1, 1). \]

计算新点的目标函数值：

\[f(x^{(1)}) = (1-3)^2 + (1-2)^2 = 4 + 1 = 5. \]

与初始值 $f(x^{(0)}) = 13$ 相比，函数值显著减小了。

总结：
通过应用可行方向法（Zoutendijk法）的一次完整迭代，我们从初始可行点 $(0,0)$ 出发：

构造并求解了寻找可行下降方向的线性规划子问题，得到方向 $d = (1,1)$。
通过分析约束确定了最大可行步长为 1。
通过最小化沿射线 $f(\alpha, \alpha)$ 确定了最优步长为 1（在此问题中恰好等于最大步长）。
得到了新的可行点 $x^{(1)} = (1, 1)$，目标函数值从 13 降至 5，完成了一次成功的迭代。如果继续迭代，需要从 $x^{(1)}$ 点重新计算活跃约束集（此时 $g_1$ 和 $g_2$ 都活跃了），并构建新的线性规划子问题来寻找下一个可行下降方向。

好的，我注意到在你的“已讲过的题目”列表中，虽然算法种类繁多，但有一个经典且重要的约束优化直接方法尚未出现。今天我将为你讲解这个方法的原理和应用。非线性规划中的可行方向法基础题题目描述：考虑以下非线性规划问题： $$ \begin{aligned} \min_ {x \in \mathbb{R}^2} \quad & f(x) = (x_ 1 - 3)^2 + (x_ 2 - 2)^2 \\ \text{s.t.} \quad & g_ 1(x) = x_ 1 + x_ 2 - 2 \le 0, \\ & g_ 2(x) = -x_ 1 + 2x_ 2 - 1 \le 0, \\ & x_ 1 \ge 0, \, x_ 2 \ge 0. \end{aligned} $$ 请从初始可行点 $ x^{(0)} = (0, 0) $ 出发，使用可行方向法（Specifically，我们使用 Zoutendijk可行方向法的基本步骤）进行一次迭代，找到下一个可行点 $ x^{(1)} $，使得目标函数值得以减小。我们要求搜索方向 $ d $ 通过求解一个线性规划（LP）子问题来获得。解题过程循序渐进讲解：第一步：理解问题结构与初始点我们的目标是最小化一个二次函数 $ f(x) $，它实际上是以点 (3, 2) 为圆心的圆半径平方。约束是两个线性不等式和两个变量的非负约束，它们共同构成了一个凸可行域。给定的初始点 $ x^{(0)} = (0, 0) $：检查可行性： $ g_ 1(0,0) = 0+0-2 = -2 \le 0 $ ✅ $ g_ 2(0,0) = -0+0-1 = -1 \le 0 $ ✅ $ x_ 1 \ge 0, x_ 2 \ge 0 $ ✅ 所以 $ x^{(0)} $ 是可行点。计算目标函数值：$ f(0,0) = (0-3)^2 + (0-2)^2 = 9 + 4 = 13 $。判断约束的活跃性（Active Constraints）：在 $ x^{(0)} $ 处，约束 $ g_ 1 $ 和 $ g_ 2 $ 都是严格小于0的（-2和-1），因此它们是非活跃约束。只有非负约束 $ x_ 1 \ge 0 $ 和 $ x_ 2 \ge 0 $ 是活跃的（因为 $ x_ 1=0, x_ 2=0 $）。第二步：可行方向法的核心思想可行方向法是一种迭代算法，在每次迭代中，从一个可行点 $ x^{(k)} $ 出发：寻找一个可行下降方向 $ d $ ：这个方向需要满足两个条件：下降条件：沿该方向移动，目标函数值会减小。数学上，要求方向 $ d $ 与目标函数负梯度（即最速下降方向）的夹角为锐角，即 $ \nabla f(x^{(k)})^T d < 0 $。可行条件：从当前点沿该方向移动一个足够小的步长，仍然保持在可行域内。对于活跃的约束，沿该方向移动不应违反它（对于线性约束，要求 $ \nabla g_ i(x^{(k)})^T d \le 0 $）；对于非活跃约束，只要步长足够小，就不会违反。沿方向 $ d $ 进行一维搜索：确定一个步长 $ \alpha > 0 $，使得新点 $ x^{(k+1)} = x^{(k)} + \alpha d $ 可行，且 $ f(x^{(k+1)}) < f(x^{(k)}) $。更新迭代点，重复过程。 Zoutendijk可行方向法是实现这个思想的一种系统化方式，它将寻找方向 $ d $ 的问题转化成一个线性规划问题。第三步：在当前点 $ x^{(0)} $ 计算梯度和活跃约束集目标函数梯度： $$ \nabla f(x) = \begin{bmatrix} 2(x_ 1 - 3) \\ 2(x_ 2 - 2) \end{bmatrix} $$ 在 $ x^{(0)} = (0,0) $ 处： $$ \nabla f^{(0)} = \nabla f(0,0) = \begin{bmatrix} -6 \\ -4 \end{bmatrix} $$ 负梯度方向是 $ (6, 4) $，即指向右上方，这正是函数值下降最快的方向。约束梯度： $ \nabla g_ 1(x) = [ 1, 1 ]^T $ $ \nabla g_ 2(x) = [ -1, 2 ]^T $ $ \nabla (x_ 1 \ge 0) $ 对应的约束可以写为 $ -x_ 1 \le 0 $，其梯度为 $[ -1, 0 ]^T$。 $ \nabla (x_ 2 \ge 0) $ 对应的约束可以写为 $ -x_ 2 \le 0 $，其梯度为 $[ 0, -1 ]^T$。确定活跃约束集 $ I_ A $ ：在 $ x^{(0)} $，$ g_ 1 $ 和 $ g_ 2 $ 非活跃。活跃的是两个边界约束： $ I_ A = \{ \text{“非负约束1”}, \text{“非负约束2”} \} $，对应的梯度矩阵为： $$ A = \begin{bmatrix} -1 & 0 \\ 0 & -1 \end{bmatrix} $$ 第四步：构建并求解寻找可行下降方向的线性规划子问题 Zoutendijk法的标准子问题是： $$ \begin{aligned} \min_ {\beta \in \mathbb{R}, \, d \in \mathbb{R}^n} \quad & \beta \\ \text{s.t.} \quad & \nabla f(x^{(k)})^T d \le \beta, \\ & \nabla g_ i(x^{(k)})^T d \le \beta, \quad \forall i \in I_ A, \\ & -1 \le d_ j \le 1, \quad j=1,...,n. \end{aligned} $$ 目标：最小化 $ \beta $。如果最优解 $ \beta^* < 0 $，说明我们找到了一个方向 $ d^* $ 使得所有活跃约束的“改善程度”和目标函数的“下降程度”都至少是 $ \beta^* $（一个负数），这是一个严格的可行下降方向。约束 $ -1 \le d_ j \le 1 $ ：是为了防止方向 $ d $ 的模无限大，将问题规范化。代入我们的数据 $ \nabla f^{(0)} = [ -6, -4 ]^T $ 和 $ A = \begin{bmatrix} -1 & 0 \\ 0 & -1 \end{bmatrix} $： $ \nabla f^{(0)})^T d = -6d_ 1 - 4d_ 2 \le \beta $ 第一个活跃约束梯度：$ [ -1, 0]^T d = -d_ 1 \le \beta $ 第二个活跃约束梯度：$ [ 0, -1]^T d = -d_ 2 \le \beta $ $ -1 \le d_ 1 \le 1, \, -1 \le d_ 2 \le 1 $ 因此，线性规划子问题为： $$ \begin{aligned} \min \quad & \beta \\ \text{s.t.} \quad & -6d_ 1 - 4d_ 2 - \beta \le 0, \\ & -d_ 1 - \beta \le 0, \\ & -d_ 2 - \beta \le 0, \\ & -1 \le d_ 1 \le 1, \\ & -1 \le d_ 2 \le 1. \end{aligned} $$ 第五步：求解该线性规划我们可以通过观察或简单推理来求解。我们希望 $ \beta $ 尽可能小（负得越多越好）。观察第一个约束 $ -6d_ 1 -4d_ 2 \le \beta $。为了让 $ \beta $ 小，我们希望左边尽可能小（负得多）。由于 $ d_ 1, d_ 2 $ 最大为1，那么 $ -6d_ 1 -4d_ 2 $ 在 $ d_ 1=1, d_ 2=1 $ 时取得最小值 -10。所以 $ \beta $ 至少是 -10。再检查其他约束：当 $ d_ 1=1, d_ 2=1 $ 时，$ -d_ 1 = -1 $，$ -d_ 2 = -1 $，它们都大于 -10，所以不会限制 $ \beta $ 变得更小。边界条件 $ d_ 1 \le 1, d_ 2 \le 1 $ 在 $ d_ 1=1, d_ 2=1 $ 时取到等号。因此，一个最优解是 $ d_ 1^* = 1, d_ 2^* = 1, \beta^* = -10 $。结论：我们找到了一个可行下降方向 $ d^{(0)} = (1, 1)^T $。因为 $ \beta^* = -10 < 0 $，这验证了它同时满足：下降条件：$ \nabla f^{(0)})^T d = -6 1 -4 1 = -10 < 0 $。可行性条件（对于活跃约束）：对于 $ -x_ 1 \le 0 $，有 $ [ -1,0]^T d = -1 < 0 $；对于 $ -x_ 2 \le 0 $，有 $[ 0,-1]^T d = -1 < 0 $。这意味着从原点沿 (1,1) 方向移动一点点，$ x_ 1 $ 和 $ x_ 2 $ 都会变成正数，严格满足约束。第六步：沿方向 $ d^{(0)} $ 进行一维搜索（确定步长 $ \alpha $）现在我们需要找到 $ \alpha > 0 $，使得 $ x^{(1)} = (0,0) + \alpha(1,1) = (\alpha, \alpha) $ 可行，并且最小化（或减小）$ f(x) $。确定最大可行步长 $ \alpha_ {\text{max}} $ ：我们需要确保新点满足所有约束。 $ g_ 1(\alpha, \alpha) = \alpha + \alpha - 2 = 2\alpha - 2 \le 0 \Rightarrow \alpha \le 1 $ $ g_ 2(\alpha, \alpha) = -\alpha + 2\alpha - 1 = \alpha - 1 \le 0 \Rightarrow \alpha \le 1 $ 非负约束自动满足（因为 $ \alpha > 0 $）。所以，最大可行步长 $ \alpha_ {\text{max}} = 1 $。当 $ \alpha = 1 $ 时，点 (1,1) 使得 $ g_ 1 $ 和 $ g_ 2 $ 同时取等号（即同时触及两个约束边界）。在 $ [ 0, \alpha_ {\text{max}}] $ 区间内最小化 $ f(\alpha) $ ： $ f(x^{(1)}) = f(\alpha, \alpha) = (\alpha - 3)^2 + (\alpha - 2)^2 = 2\alpha^2 - 10\alpha + 13 $。这是一个关于 $ \alpha $ 的二次凸函数。其导数 $ f'(\alpha) = 4\alpha - 10 $。令 $ f'(\alpha) = 0 $ 得驻点 $ \alpha^* = 2.5 $。然而，$ \alpha^* = 2.5 > \alpha_ {\text{max}} = 1 $。这意味着在可行区间 $[ 0, 1]$ 内，函数 $ f(\alpha) $ 是单调递减的（因为导数在 $ \alpha=1 $ 时为 $ 4* 1-10 = -6 < 0 $）。选择最优步长：为了最大程度减小目标函数，同时保证可行性，我们应选择最大可行步长，即 $ \alpha^{(0)} = 1 $。第七步：得到新迭代点并结束本次迭代新点为： $$ x^{(1)} = x^{(0)} + \alpha^{(0)} d^{(0)} = (0,0) + 1 * (1,1) = (1, 1). $$ 计算新点的目标函数值： $$ f(x^{(1)}) = (1-3)^2 + (1-2)^2 = 4 + 1 = 5. $$ 与初始值 $ f(x^{(0)}) = 13 $ 相比，函数值显著减小了。总结：通过应用可行方向法（Zoutendijk法）的一次完整迭代，我们从初始可行点 $ (0,0) $ 出发：构造并求解了寻找可行下降方向的线性规划子问题，得到方向 $ d = (1,1) $。通过分析约束确定了最大可行步长为 1。通过最小化沿射线 $ f(\alpha, \alpha) $ 确定了最优步长为 1（在此问题中恰好等于最大步长）。得到了新的可行点 $ x^{(1)} = (1, 1) $，目标函数值从 13 降至 5，完成了一次成功的迭代。如果继续迭代，需要从 $ x^{(1)} $ 点重新计算活跃约束集（此时 $ g_ 1 $ 和 $ g_ 2 $ 都活跃了），并构建新的线性规划子问题来寻找下一个可行下降方向。