线性规划
阅读数:223 评论数:0
跳转到新版页面分类
数学
正文
一、线性规划的基本性质
对于线性齐次方程组 $Ax = 0$，其中 $A$ 是一个 $m \times n$ 的矩阵，$x$ 是一个 $n$ 维列向量，基础解系是一组解向量 $\{x_1, x_2, \ldots, x_k\}$，它们满足以下条件：
- **线性独立**：基础解系中的解向量是线性独立的，即没有一个解向量可以表示为其他解向量的线性组合。
- **生成所有解**：方程组的任何解都可以表示为基础解系中解向量的线性组合。换句话说，基础解系生成了方程组的整个解空间。
- **数量**：基础解系中解向量的数量等于矩阵 $A$ 的列数 $n$ 减去 $A$ 的秩（即 $\text{rank}(A)$），这也是方程组的自由变量的数量。
（1）存在性定理
如果一个线性规划问题有可行解（即满足所有约束条件的解），并且目标函数在可行域上是有界的，则该问题必定有最优解。这意味着，只要目标函数在可行解集合上不是无限增大或减小，就一定存在至少一个解使得目标函数取得最大值或最小值。
（2）极点定理
如果线性规划问题有解，则至少有一个最优解位于可行域的一个极点（或顶点）上。由于线性规划的可行域是一个多面体（可能是无界的），这个定理表明我们可以通过检查有限个极点来找到最优解，而不是需要检查整个无限的可行域。
凸函数是定义在凸集上的实值函数，其任意两点上的割线位于函数图像之上。更正式地，函数 $f$ 是凸的，如果对于其定义域内的任意两点 $x$ 和 $y$，以及任意 $\lambda$ 满足 $0 \leq \lambda \leq 1$，都有：
$$
f(\lambda x + (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda)f(y).
$$
如果不等号反向，则函数被称为凹函数。
二、单纯形法
我们可以通过详细的步骤来解决前面提出的线性规划问题，使用单纯形法的矩阵形式。我们从问题的标准形式开始，引入松弛变量，然后进行迭代直到找到最优解。
（1）初始线性规划问题
目标函数:
$$
\text{maximize} \quad z = 3x_1 + 2x_2
$$
约束条件:
$$
\begin{align*}
x_1 + 2x_2 &\leq 10 \\
2x_1 + x_2 &\leq 8 \\
x_1, x_2 &\geq 0
\end{align*}
$$
（2）转换为标准形式
引入松弛变量 $s_1$ 和 $s_2$ 转换为等式约束：
$$
\begin{align*}
x_1 + 2x_2 + s_1 &= 10 \\
2x_1 + x_2 + s_2 &= 8 \\
x_1, x_2, s_1, s_2 &\geq 0
\end{align*}
$$
（3）构建初始单纯形表
我们构建一个初始的单纯形表，包括目标函数和约束条件：
$$
\begin{array}{c|ccc|c}
& x_1 & x_2 & s_1 & s_2 & RHS \\
\hline
s_1 & 1 & 2 & 1 & 0 & 10 \\
s_2 & 2 & 1 & 0 & 1 & 8 \\
\hline
z & -3 & -2 & 0 & 0 & 0 \\
\end{array}
$$
这里的 $RHS$ 列代表了每个约束的右手边的常数值。
（4）第一次迭代
- **选择进入变量**：目标函数中 $x_1$ 的系数最负（-3），所以 $x_1$ 是进入变量。
- **选择离开变量**：我们计算每个约束的 $RHS$ 与 $x_1$ 系数的比值，即 $10/1$ 和 $8/2$。最小的比值是 $8/2 = 4$，所以 $s_2$ 是离开变量。
- **执行行操作**：我们需要将 $s_2$ 行的 $x_1$ 系数变为1，并且消除 $s_1$ 行和目标函数 $z$ 行中 $x_1$ 的系数。
为了将 $s_2$ 行的 $x_1$ 系数变为1，我们将整个 $s_2$ 行除以2：
$$
\begin{array}{c|ccc|c}
& x_1 & x_2 & s_1 & s_2 & RHS \\
\hline
s_1 & 1 & 2 & 1 & 0 & 10 \\
x_1 & 1 & 0.5 & 0 & 0.5 & 4 \\
\hline
z & -3 & -2 & 0 & 0 & 0 \\
\end{array}
$$
然后，我们需要进行行操作以消除目标函数中 $x_1$ 的系数。我们将新的 $x_1$ 行乘以3并加到目标函数上：
$$
\begin{array}{c|ccc|c}
& x_1 & x_2 & s_1 & s_2 & RHS \\
\hline
s_1 & 0 & 1.5 & 1 & -0.5 & 8 \\
x_1 & 1 & 0.5 & 0 & 0.5 & 4 \\
\hline
z & 0 & -0.5 & 0 & 1.5 & 12 \\
\end{array}
$$
在这个点上，目标函数中还有一个负系数（$x_2$ 的系数），所以我们需要进行另一次迭代。
（5）第二次迭代
- **选择进入变量**：现在 $x_2$ 的系数是目标函数中唯一的负数（-0.5），所以 $x_2$ 是进入变量。
- **选择离开变量**：我们再次计算比值，$8/1.5$ 和 $4/0.5$。最小比值是 $4/0.5 = 8$，所以 $x_1$ 行保持不变。
- **执行行操作**：我们需要将 $s_1$ 行的 $x_2$ 系数变为1，并且消除目标函数中 $x_2$ 的系数。这可以通过将 $s_1$ 行除以1.5来实现，然后将适当的倍数加到目标函数上。
进行这些操作后，我们得到新的单纯形表：
$$
\begin{array}{c|ccc|c}
& x_1 & x_2 & s_1 & s_2 & RHS \\
\hline
s_1 & 0 & 1 & 2/3 & -1/3 & 16/3 \\
x_1 & 1 & 0 & -1/3 & 2/3 & 10/3 \\
\hline
z & 0 & 0 & 1/3 & 4/3 & 22 \\
\end{array}
$$
现在，由于目标函数中没有负系数，我们找到了最优解。
（6）最优解
从最终的单纯形表中，我们可以读出最优解：
$$
x_1 = \frac{10}{3}, \quad x_2 = 0, \quad s_1 = \frac{16}{3}, \quad s_2 = 0
$$
目标函数的最大值为：
$$
z = 22
$$
这就是使用单纯形法的矩阵形式求解线性规划问题的一个示例。
三、对偶与互补理论
对偶定理提供了原问题（称为原始问题）和对偶问题之间的联系，包括它们的目标函数值和解的关系。
（1）原始问题与对偶问题
假设我们有一个线性规划问题的原始形式（原问题）：
- **原始问题（Primal Problem）**:
- 目标函数：$\text{minimize } c^T x$
- 约束条件：$Ax \geq b$
- 变量条件：$x \geq 0$
- **对偶问题（Dual Problem）**:
- 目标函数：$\text{maximize } b^T y$
- 约束条件：$A^T y \leq c$
- 变量条件：$y \geq 0$
这里，$x$ 是原始问题的决策变量向量，$y$ 是对偶问题的决策变量向量。$A$ 是约束条件的系数矩阵，$b$ 和 $c$ 分别是与约束条件和目标函数相关的系数向量。
（2）对偶定理的主要结论
- **弱对偶性（Weak Duality）**：对任何原始问题的可行解 $x$ 和对偶问题的可行解 $y$，都有 $b^T y \leq c^T x$。这表明对偶问题的任何可行解的目标函数值都是原始问题目标函数值的一个下界。
- **强对偶性（Strong Duality）**：如果原始问题和对偶问题都有可行解，则它们都有最优解，并且这些最优解的目标函数值相等，即 $b^T y^* = c^T x^*$，其中 $x^*$ 和 $y^*$ 分别是原始问题和对偶问题的最优解。
- **互补松弛性（Complementary Slackness）**：对于原始问题和对偶问题的任何一对最优解 $x^*$ 和 $y^*$，对于所有的 $i$，要么原始问题的约束 $A_i x^* - b_i = 0$，要么对偶问题的变量 $y^*_i = 0$；同样，对于所有的 $j$，要么对偶问题的约束 $c_j - A^T_j y^* = 0$，要么原始问题的变量 $x^*_j = 0$。
- 单纯形法在寻找原始问题的最优解时，会通过基变换逐步改进解，直到找到一个满足所有约束的解，使得目标函数值最大或最小。在这个过程中，对偶问题的可行解也在同时被构造和改进。
- 互补松弛性条件是单纯形法在找到最优解时自然满足的。对于原问题的每个非基变量（在最优解中值为零的变量），其对应的对偶变量的约束是紧的（等式成立）。对于原问题的每个基变量（在最优解中值非零的变量），其对应的对偶约束是非紧的（对偶变量为零）。
（1）灵敏度分析
灵敏度分析在线性规划中用于评估模型参数变化对最优解的影响。这些参数通常包括目标函数系数、技术系数（即约束矩阵中的系数）、以及资源向量（即约束不等式中的常数项）。灵敏度分析的关键组成部分包括：
- 目标函数系数变化：分析目标函数中某个变量系数的变化范围，在不改变当前最优解基础结构的前提下，该变量可以在这个范围内变动而不影响最优性。
- 约束右侧变化（资源变化）：分析每个约束条件的资源量可以在不改变最优基的情况下变化的范围。
- 技术系数变化：评估约束矩阵中的系数变化对最优解的影响。
灵敏度分析可以告诉决策者哪些参数对最优解比较敏感，哪些参数的变化不会对最优解产生显著影响。
（2）互补松弛性
互补松弛性（Complementary Slackness）是线性规划中原问题与对偶问题之间的一种关系。为了使其更易于理解，我们可以用一个简单的经济学的类比来解释这个概念。
假设你是一个生产商，你需要决定生产哪些产品来最大化你的利润。你的生产能力是有限的，比如你只有一定数量的工厂时间和原材料。在这个情况下：
- 原问题（Primal Problem）: 你的目标是选择不同产品的生产量来最大化利润，受到工厂时间和原材料的限制。
- 对偶问题（Dual Problem）: 你想知道每一个限制（如工厂时间和原材料）对你利润的贡献，也就是它们的“价值”。
现在，互补松弛性告诉我们：
- 如果你在最优生产计划中没有完全用完一个资源（比如原材料），那么这个资源对你的总利润没有额外的贡献，它的“价值”（在对偶问题中的对偶变量值）是零。因为如果它有价值，你应该使用它直到耗尽以增加利润。
- 反之，如果一个资源被完全用完了（比如工厂时间被全部用于生产），那么这个资源是有价值的，它的价值（对偶变量的值）是正的。这意味着增加一点点工厂时间将会直接增加你的利润。
在数学上，这可以用以下方式表达：
- 对于每一个原问题的约束，如果约束的松弛变量（即未使用的资源量）大于零，则对应的对偶变量（资源的价值）等于零。
- 对于每一个对偶问题的约束，如果约束的松弛变量（即未使用的生产能力）大于零，则对应的原问题的变量（产品的生产量）等于零。
最大流-最小割定理是图论中的一个核心原理，它在网络流问题中非常重要。为了易于理解，我们可以通过一个简单的类比来解释这个概念。
想象一个城市的水系统，这个系统由水源、水管和水龙头组成。水源代表流的起点，水龙头代表流的终点。水管则是连接水源和水龙头的管道，每根水管都有它能承受的最大水流量（容量限制）。
- 最大流：在不超过任何水管容量限制的情况下，从水源到水龙头能够输送的最大水流量。
- 割：割是一种分割水系统的方式，它将水源和水龙头分开，可以想象为在某些水管上放置阀门关闭它们，使水无法流过。
- 最小割：在所有可能的割中，关闭的水管的容量总和最小的那个割。这表示为了完全切断水源和水龙头之间的流动，需要关闭的水管容量之和最小。
最大流-最小割定理表明，在任何网络中，从源点到汇点的最大流量等于如果要将源点和汇点完全隔离开来所需切断的最小管道容量总和。
对偶单纯形法是一种用于解决线性规划问题的算法，特别是当原始问题的初始基本可行解不可用，但对偶问题的初始基本可行解容易获得时。对偶单纯形法的基本思想是在对偶问题上应用单纯形法，从而间接地解决原问题。
原始-对偶算法是一种用于解决线性规划问题的算法，它同时利用了原始问题和对偶问题的信息。在原始-对偶算法中，原始问题和对偶问题是同时求解的，这有助于提高算法的稳定性和效率。这种方法特别适合于那些原始问题和对偶问题都没有明显初始基本可行解的情况。
原始-对偶方法的核心思想是，对于一个线性规划问题，原始问题和对偶问题中的每一个都有一个目标函数值的界限，即原始问题的最优值是对偶问题最优值的下界，而对偶问题的最优值是原始问题最优值的上界。算法的目的是同时缩小这两个界限，直到它们相遇，此时找到了最优解。
这里是原始-对偶算法的基本步骤：
（1）初始化：选择一个初始解，这个解不需要是可行的，但需要满足一定的条件，比如对偶可行性。
（2）迭代：在每次迭代中，算法执行以下步骤：
- 从当前解出发，寻找一个方向，沿此方向移动可以同时改善原始和对偶目标函数值。
- 确定步长，这个步长需要保证解的对偶可行性，并尽可能地改善目标函数。
- 更新解，包括原始变量和对偶变量。
（3）终止条件：当原始问题和对偶问题的目标函数值足够接近时（即它们的差距小于某个预设的容忍度），算法停止，当前的原始变量和对偶变量给出最优解。
四、内点法
内点法是一类用于求解线性和非线性优化问题的算法，其中最著名的是用于线性规划的Karmarkar算法，由Narendra Karmarkar于1984年提出。内点法代表了一种不同于单纯形法的方法，它在求解过程中穿行于可行域的内部，而不是在边界上跳跃。内点法在理论上和实践中都非常有效，尤其是对于大规模问题。
内点法的基本思想是从可行域内的一个点开始，通常是一个接近最优解的点，并在每一步中沿着某个方向移动，这个方向既向目标函数的最小值方向移动，又保持在可行域内。这种方法避免了单纯形法可能遇到的退化问题和在边界上的效率低下问题。
单纯形法的时间复杂度取决于它选择的路径穿过可行域的顶点数量，而这个数量在最坏情况下可能是指数级的。
与此相对，存在其他算法，如椭球法和内点法，它们在理论上具有多项式时间复杂度。这意味着它们的最坏情况下的性能可以用多项式来界定，不会随问题规模的增长而指数级增加。内点法特别有趣，因为它不仅在理论上是多项式时间的，而且在实际中也表现出了与单纯形法相媲美或有时甚至更好的性能。
椭球算法（Ellipsoid Algorithm）是第一个被证明能够在多项式时间内解决线性规划问题的算法。这个算法由Leonid Khachiyan在1979年提出，标志着线性规划理论中的一次重要突破。尽管椭球算法在理论上是一个突破，证明了线性规划问题可以在多项式时间内解决，但由于它在实际应用中的效率通常低于单纯形法和内点法，因此并不经常用于实践中的线性规划问题求解。
椭球算法的基本思想是围绕线性规划问题的可行域构造一个椭球，并通过迭代过程不断缩小椭球的体积，逼近最优解。每一步迭代中，算法都会检查椭球中心是否是可行解。如果是，则问题解决；如果不是，则算法会根据一个违反约束来切割椭球，并生成一个新的、体积更小的椭球，这个新椭球保证包含了原始椭球中所有可能的可行解。
五、锥线性规划
凸锥（Convex Cone）是凸分析和优化理论中的一个基本概念。一个集合 $ C $ 是一个凸锥，如果它满足以下两个条件：
（1）**凸性（Convexity）**：对于集合 $ C $ 中的任意两点 $ x $ 和 $ y $，以及任何非负实数 $ \alpha $ 和 $ \beta $，下面的线性组合仍然在集合 $ C $ 中：
$$
\alpha x + \beta y \in C
$$
这意味着集合 $ C $ 中任意两点之间的线段都包含在集合 $ C $ 中。
（2）**锥性（Conical property）**：对于集合 $ C $ 中的任意一点 $ x $ 和任何非负实数 $ \lambda $，下面的数乘结果也在集合 $ C $ 中：
$$
\lambda x \in C
$$
这意味着如果一个点属于集合 $ C $，那么沿着从原点出发到这个点的射线上的所有点也属于集合 $ C $。
Farkas引理的一个版本可以表述如下：
设有一个矩阵 $ A \in \mathbb{R}^{m \times n} $ 和一个向量 $ b \in \mathbb{R}^m $，那么下面两个陈述中恰好有一个是真的：
（1）存在一个向量 $ x \in \mathbb{R}^n $ 使得 $ Ax = b $ 且 $ x \geq 0 $（这里的不等号是逐分量的）。
（2）存在一个向量 $ y \in \mathbb{R}^m $ 使得 $ A^T y \geq 0 $ 且 $ b^T y < 0 $。
这个引理的几何直观是：要么存在一个非负解 $ x $ 使得 $ Ax = b $，要么存在一个向量 $ y $ 使得它与 $ A $ 的列空间中的所有向量的内积非负，但是与 $ b $ 的内积为负。这意味着 $ b $ 要么可以被 $ A $ 的列向量的非负线性组合表示，要么存在一个超平面（由 $ y $ 定义）将 $ b $ 严格地分离开来，使得 $ A $ 的所有列向量都在超平面的同一侧。
锥线性规划（Cone Linear Programming，也称为锥规划）是一类特殊的优化问题，其中目标函数是线性的，可行域由一个凸锥定义。对偶性在锥线性规划中扮演着重要角色，正如它在标准线性规划中的作用一样。
在锥线性规划中，给定凸锥 $K$，问题可以表述为寻找一个向量 $x$，使得：
原始问题（Primal Problem）:
$$
\begin{align*}
\text{minimize} \quad & c^T x \\
\text{subject to} \quad & Ax = b \\
& x \in K
\end{align*}
$$
其中，$c \in \mathbb{R}^n$ 是目标函数的系数，$A \in \mathbb{R}^{m \times n}$ 是约束矩阵，$b \in \mathbb{R}^m$ 是约束的右侧向量，$x \in \mathbb{R}^n$ 是决策变量，$K$ 是一个凸锥。
对应的对偶问题（Dual Problem）通常表述为：
$$
\begin{align*}
\text{maximize} \quad & b^T y \\
\text{subject to} \quad & A^T y + s = c \\
& s \in K^*
\end{align*}
$$
其中，$y \in \mathbb{R}^m$ 是对偶变量，$s \in \mathbb{R}^n$ 是松弛变量，$K^*$ 是原始锥 $K$ 的对偶锥。对偶锥 $K^*$ 定义为所有与 $K$ 中所有向量都有非负内积的向量 $s$ 的集合：
$$
K^* = \{ s \in \mathbb{R}^n | \forall x \in K, s^T x \geq 0 \}
$$
原始问题和对偶问题之间的关系是通过拉格朗日对偶性建立的。锥线性规划的对偶性质保证了在某些条件下（如Slater条件），原始问题和对偶问题的最优值相等，这称为强对偶性。
一个半正定矩阵是一个对称矩阵，其所有的特征值都是非负的。
半定规划（Semidefinite Programming，SDP）是锥线性规划的一个特例，其中涉及的锥是半正定矩阵构成的锥。半定规划问题可以表述为：
原始问题（Primal Problem）:
$$
\begin{align*}
\text{minimize} \quad & \text{Tr}(C^T X) \\
\text{subject to} \quad & \text{Tr}(A_i^T X) = b_i, \quad i = 1, \ldots, m \\
& X \succeq 0
\end{align*}
$$
其中，$C$ 和 $A_i$ 是给定的对称矩阵，$X$ 是需要求解的半正定矩阵变量（$X \succeq 0$ 表示 $X$ 是半正定的），$b_i$ 是给定的常数，而 $\text{Tr}(\cdot)$ 表示矩阵的迹，即矩阵对角元素的和。
对应的对偶问题（Dual Problem）是：
$$
\begin{align*}
\text{maximize} \quad & b^T y \\
\text{subject to} \quad & \sum_{i=1}^m y_i A_i + S = C \\
& S \succeq 0
\end{align*}
$$
其中，$y$ 是对偶变量，$S$ 是对偶松弛变量，也是一个半正定矩阵。
互补性（Complementarity）在SDP中扮演着关键角色。互补性条件表明，如果 $X$ 和 $S$ 是一对原始问题和对偶问题的最优解，则它们满足：
$$
XS = 0
$$
这意味着 $X$ 和 $S$ 是正交的，或者说，它们的乘积是零矩阵。这个条件也被称为互补松弛性（Complementary Slackness）。
在某些情况下，互补性条件可以用来推断最优解的某些性质，特别是它们的秩。例如，如果原始问题和对偶问题的最优解 $X$ 和 $S$ 的秩之和小于矩阵的大小，即：
$$
\text{rank}(X) + \text{rank}(S) < n
$$
则这表明存在非零解 $X$ 和 $S$ 满足互补性条件。这种情况下，互补性条件可以用来减少问题的复杂性，因为它暗示了最优解可能具有低秩结构，这在理论和实践中都很有用。
锥线性规划（Cone Linear Programming）是一类涉及锥约束的线性规划问题，其中最常见的例子是半定规划（SDP）和二次锥规划（SOCP）。内点算法是解决这类问题的一种非常有效的数值方法。这些算法的基本思想是从可行域的内部开始，沿着某种路径逼近最优解，而不是像单纯形方法那样在可行域的边界上移动。
内点算法的关键特性是它们遵循一条路径（称为中心路径），这条路径通过可行域并趋向于最优解。
六、解与算法的基本性质
在优化理论中，一阶必要条件是指在某些假设下，一个点如果是无约束优化问题的局部最小点，那么在该点的目标函数的梯度（或导数，对于单变量函数）必须为零。这是基于函数在局部最小点的斜率为零的直观概念。
对于一个无约束的多变量优化问题，如果函数 $f(\mathbf{x})$ 在点 $\mathbf{x}^*$ 处可微，并且 $\mathbf{x}^*$ 是 $f$ 的一个局部最小点，那么 $f$ 在 $\mathbf{x}^*$ 处的梯度为零：
$$
\nabla f(\mathbf{x}^*) = \mathbf{0}
$$
这里的 $\nabla f(\mathbf{x})$ 是目标函数关于向量 $\mathbf{x}$ 的梯度，它是一个包含所有偏导数的向量：
$$
\nabla f(\mathbf{x}) = \left[ \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \ldots, \frac{\partial f}{\partial x_n} \right]^T
$$
对于有约束的优化问题，特别是等式约束问题，一阶必要条件是通过拉格朗日乘数法来表达的。如果函数 $f(\mathbf{x})$ 在受到 $g_i(\mathbf{x}) = 0$（$i=1,\ldots,m$）约束的条件下在 $\mathbf{x}^*$ 处取得局部极小值，并且约束条件和目标函数都是可微的，那么存在一组拉格朗日乘数 $\lambda_1^*,\ldots,\lambda_m^*$，使得：
$$
\nabla f(\mathbf{x}^*) + \sum_{i=1}^{m} \lambda_i^* \nabla g_i(\mathbf{x}^*) = \mathbf{0}
$$
这个条件是说，在最优点，目标函数的梯度可以被约束函数的梯度线性组合抵消。
（1）二阶必要条件
如果函数 $f(\mathbf{x})$ 在点 $\mathbf{x}^*$ 是局部最小点，并且 $f$ 在 $\mathbf{x}^*$ 附近是二次可微的，则 $f$ 在 $\mathbf{x}^*$ 的Hessian矩阵 $H(\mathbf{x}^*)$ 必须是半正定的：
$$
\mathbf{v}^T H(\mathbf{x}^*) \mathbf{v} \geq 0 \quad \text{对于所有向量} \quad \mathbf{v}
$$
这里的 $H(\mathbf{x}^*)$ 是目标函数关于 $\mathbf{x}$ 的Hessian矩阵，它是一个包含所有二阶偏导数的方阵：
$$
H(\mathbf{x}) = \begin{bmatrix}
\frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \\
\frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\
\vdots & \vdots & \ddots & \vdots \\
\frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2}
\end{bmatrix}
$$
（2）二阶充分条件
如果函数 $f(\mathbf{x})$ 在点 $\mathbf{x}^*$ 是二次可微的，并且 $H(\mathbf{x}^*)$ 是正定的，则 $\mathbf{x}^*$ 是 $f$ 的局部最小点。换句话说，如果对于所有非零向量 $\mathbf{v}$，都有：
$$
\mathbf{v}^T H(\mathbf{x}^*) \mathbf{v} > 0
$$
那么 $\mathbf{x}^*$ 是 $f$ 的局部最小点。
（1）凸函数
一个定义在实数向量空间的某个凸集 $\mathcal{D}$ 上的函数 $f: \mathcal{D} \rightarrow \mathbb{R}$ 被称为凸函数，如果对于所有 $x, y \in \mathcal{D}$ 和所有 $\lambda \in [0, 1]$，都有：
$$
f(\lambda x + (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda)f(y)
$$
这个定义的直观含义是：函数在任意两点之间的线段上的值总是低于或等于这两点函数值的线性插值。这意味着函数的图形“弯曲”向下或者是直线。
凸函数的一些性质包括：
- 局部最小值也是全局最小值。
- 如果函数是二次可微的，那么函数是凸的当且仅当它的Hessian矩阵在定义域内是半正定的。
（2）凹函数
凹函数是凸函数的对立面。如果一个函数 $f$ 是凹的，那么 $-f$ 是凸的。形式上，函数 $f: \mathcal{D} \rightarrow \mathbb{R}$ 是凹的，如果对于所有 $x, y \in \mathcal{D}$ 和所有 $\lambda \in [0, 1]$，都有：
$$
f(\lambda x + (1 - \lambda)y) \geq \lambda f(x) + (1 - \lambda)f(y)
$$
这意味着函数的图形“弯曲”向上。
凹函数的性质与凸函数相反：
- 局部最大值也是全局最大值。
- 如果函数是二次可微的，那么函数是凹的当且仅当它的Hessian矩阵在定义域内是半负定的。
七、基本下降法
线搜索算法是用于在优化问题中寻找最优步长的一类算法。在迭代优化算法中，如梯度下降或牛顿方法，通常需要决定在每次迭代中沿着某个方向前进多远。这个方向通常由当前位置的负梯度（或牛顿方法中的海森矩阵和梯度的乘积）给出，而线搜索算法就是用来确定沿这个方向前进的最佳步长（也称为学习率或步长参数）。
线搜索算法的目标是选择步长 $\alpha$ 来最小化目标函数 $f(x + \alpha d)$，其中 $x$ 是当前迭代的位置，$d$ 是下降方向（通常是梯度的反方向）。
最速下降法（Steepest Descent Method）是一种用于求解无约束优化问题的迭代方法。该方法也被称为梯度下降法。在最速下降法中，每一步都沿着当前点的负梯度方向（即目标函数下降最快的方向）进行搜索，以找到目标函数的局部最小值。
最速下降法的基本步骤如下：
（1）**初始化**：选择一个起始点 $x^{(0)}$ 和一个足够小的正数 $\epsilon$ 作为终止准则的阈值，设置迭代计数器 $k=0$。
（2）**计算梯度**：计算当前点 $x^{(k)}$ 处的梯度 $\nabla f(x^{(k)})$。
（3）**终止准则**：如果 $||\nabla f(x^{(k)})|| < \epsilon$，则停止迭代，$x^{(k)}$ 被认为是近似最优解。
（4）**确定搜索方向**：确定最速下降方向，即当前点的负梯度方向 $d^{(k)} = -\nabla f(x^{(k)})$。
（5）**线搜索**：使用线搜索算法确定沿方向 $d^{(k)}$ 的步长 $\alpha_k$，使得 $f(x^{(k)} + \alpha_k d^{(k)})$ 最小。
（6）**更新解**：更新当前点 $x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}$。
（7）**迭代计数器**：令 $k = k + 1$，返回步骤 2 继续迭代。
最速下降法的关键在于如何有效地选择步长 $\alpha_k$。如果步长太小，算法可能会非常缓慢地收敛；如果步长太大，可能会越过最小值点，导致算法发散。因此，合适的线搜索策略对于最速下降法的性能至关重要。
尽管存在一些缺点，最速下降法仍然是一种简单且广泛应用的优化算法，特别是在问题规模较小或者梯度计算相对简单的情况下。在实践中，通常会使用一些改进的算法，例如共轭梯度法、BFGS或者Adam等，这些方法在某些情况下能够提供更快的收敛速度和更好的性能。
加速最速下降法，或者说加速梯度下降法，是一类通过特殊技巧提高梯度下降法性能的算法。这些技巧旨在加快收敛速度，减少迭代次数，或者改善算法在复杂优化问题中的表现。以下是一些常见的加速技术：
（1）动量法 (Momentum)
动量法借鉴了物理中的动量概念，通过累积过去梯度的信息来加速学习。在动量法中，更新规则不仅取决于当前的梯度，还取决于之前梯度的累积。这可以帮助算法加速收敛，并减少“之字形”路径。
更新规则如下：
$$
v^{(k+1)} = \beta v^{(k)} - \alpha \nabla f(x^{(k)}) \\
x^{(k+1)} = x^{(k)} + v^{(k+1)}
$$
其中，$v^{(k)}$ 是动量项，$\beta$ 是动量衰减参数，通常设置为接近 1 的值（例如 0.9）。
（2）Nesterov 加速梯度 (NAG)
Nesterov 加速梯度（NAG）是动量方法的一个变体，它在计算梯度前先在动量的方向上“看一步”。这种预测性的更新可以提高优化过程的效率。
NAG 的更新规则如下：
$$
v^{(k+1)} = \beta v^{(k)} - \alpha \nabla f(x^{(k)} + \beta v^{(k)}) \\
x^{(k+1)} = x^{(k)} + v^{(k+1)}
$$
在优化领域，牛顿法被用来求解无约束优化问题，即找到函数的极值点。牛顿法使用函数的一阶导数（梯度）和二阶导数（Hessian矩阵）来寻找函数的局部最小值或最大值。
牛顿法的基本思想是利用函数在当前点的泰勒展开式的前几项来近似函数，并求解这个近似函数的根。在优化的上下文中，牛顿法通过迭代的方式更新变量，使得目标函数的梯度趋近于零，从而找到极值点。
牛顿法的迭代公式如下：
$$
x^{(k+1)} = x^{(k)} - \left[ H(f(x^{(k)})) \right]^{-1} \nabla f(x^{(k)})
$$
其中，$x^{(k)}$ 是第 $k$ 次迭代的值，$\nabla f(x^{(k)})$ 是目标函数在 $x^{(k)}$ 处的梯度，$H(f(x^{(k)}))$ 是目标函数在 $x^{(k)}$ 处的Hessian矩阵，$H(f(x^{(k)}))^{-1}$ 表示Hessian矩阵的逆。
牛顿法的几个关键特点包括：
- **二阶收敛**：如果函数的二阶导数是连续的，并且初始点选得足够接近极值点，牛顿法通常具有二阶收敛速度，这意味着收敛速度非常快。
- **依赖于Hessian矩阵**：牛顿法的一个主要缺点是需要计算Hessian矩阵及其逆，这在高维问题中可能非常耗时。
- **局部方法**：牛顿法是一种局部优化方法，它可能收敛到局部最小值，而不是全局最小值。
- **初始点敏感**：牛顿法的表现高度依赖于初始点的选择。一个不好的初始点可能导致算法收敛到非最优点，或者根本不收敛。
- **对非凸问题可能失效**：如果目标函数是非凸的，牛顿法可能会遇到Hessian矩阵不是正定的情况，这时候直接应用牛顿法可能不会收敛。
坐标下降法（Coordinate Descent Method）是一种用于解决多变量优化问题的算法。它的核心思想是将多维优化问题分解为一系列的一维优化问题来求解。在每一步中，坐标下降法固定其他所有变量，只对当前选定的单个变量进行优化。通过迭代地对每个变量执行这个步骤，坐标下降法逐渐逼近全局最优解或局部最优解。
八、共轭方向法
共轭方向法是一种用于求解线性方程组或者无约束优化问题的迭代算法。在优化问题的背景下，共轭方向法旨在解决形如 $f(x) = \frac{1}{2} x^T A x - b^T x$ 的二次函数的最小化问题，其中 $A$ 是一个正定对称矩阵，$b$ 是一个常数向量。这种类型的问题通常出现在各种科学和工程领域中，尤其是在最小二乘问题和线性系统的求解中。
共轭方向法的基本思想是从一个初始点开始，沿着一系列彼此“共轭”的方向进行搜索。在这里，“共轭”通常是指方向之间满足一定的正交性条件。对于正定对称矩阵 $A$，两个非零向量 $u$ 和 $v$ 被称为 $A$-共轭（或 $A$-正交），如果它们满足 $u^T A v = 0$。
共轭方向法的步骤包括：
- 选择一个初始点 $x^{(0)}$ 和一个初始方向 $d^{(0)}$（通常选择梯度的负方向）。
- 对于每次迭代 $k$，计算步长 $\alpha_k$，使得沿方向 $d^{(k)}$ 的函数值最小化：
$$
\alpha_k = \frac{-d^{(k)T} \nabla f(x^{(k)})}{d^{(k)T} A d^{(k)}}
$$ - 更新解：
$$
x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}
$$ - 计算下一个方向 $d^{(k+1)}$，使其与之前的所有方向共轭。
- 重复步骤2到4，直到满足收敛条件。
在共轭方向法中，每一步的搜索方向不仅是梯度的下降方向，而且与之前的所有搜索方向共轭。这意味着每个新的搜索方向都与之前的搜索方向相对于矩阵 A 正交。这种共轭性保证了搜索过程中不会重复之前的搜索方向，从而避免循环，并确保每一步都朝着新的方向前进。
每个新的搜索方向 $d^{(k)}$ 都是一个下降方向，即沿这个方向移动会减少目标函数的值。这是因为每个新的方向都是基于当前的梯度信息（或残差）来选择的，确保了目标函数在新方向上的导数是负的。
共轭方向法中的方向不仅相互共轭，而且在理想情况下，每一步的最优步长 αk 都会使得当前方向上的残差（即目标函数梯度的负值）正交于所有之前的搜索方向。这意味着每一步不仅减少了当前方向上的目标函数值，而且不会破坏之前方向上已经取得的最小值。
对于一个n维的二次优化问题，共轭方向法理论上最多需要n步就可以找到精确解（在理想的数值精度下）。这是因为共轭方向法构造了一个完整的、互相共轭的方向集，这些方向跨越了整个解空间。
部分共轭梯度法（Preconditioned Conjugate Gradient, PCG）是共轭梯度法的一个变种，它通过引入一个预处理器来改进共轭梯度法的收敛速度。预处理器是一个设计用来改善系统条件数的矩阵。条件数是指矩阵的最大奇异值与最小奇异值之比，它是衡量矩阵“良态”程度的一个指标。矩阵的条件数越小，数值方法求解线性系统时的稳定性和收敛速度通常越好。
预处理器的目的是通过变换来使原问题更容易解决。在共轭梯度法中，预处理器 $M$ 通常是一个近似于 $A$ 的逆矩阵的正定矩阵，这样，预处理后的系统 $M^{-1}Ax = M^{-1}b$ 会有更好的条件数。
这个方法在数学上基于同伦概念，即在保持端点固定的情况下，可以将一条路径连续地变形为另一条路径。
平行切性法的基本思想是将原始问题转化为一个参数化的问题，然后逐渐改变参数，从而从一个简单问题（其解已知）连续地变化到实际问题（其解未知）。在每一步，算法都会沿着由上一步得到的解和参数值定义的路径前进一小步，然后根据新的参数值修正解。通过这种方式，可以逐步逼近实际问题的解。
九、拟牛顿法
修正牛顿法（Modified Newton's Method）是传统牛顿法的一个变体，用于求解非线性方程或方程组的根。牛顿法是一种迭代方法，它利用函数的一阶导数（即切线）来逼近方程的根。在每次迭代中，牛顿法使用当前估计值处的切线来预测函数零点的位置，并将此位置作为下一个估计值。
传统的牛顿法迭代公式如下：
$$
x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}
$$
其中 $x_n$ 是第 $n$ 次迭代的估计值，$f(x)$ 是要求解的方程，$f'(x)$ 是方程的导数。
修正牛顿法对这个迭代公式做了改进，以提高其稳定性和收敛速度。修正的方法通常包括以下几种：
（1） **使用更高阶导数**：在某些情况下，可以使用二阶或更高阶的导数来改善迭代的稳定性和收敛速度。
（2）**调整步长**：在每次迭代中，可以通过一个步长因子 $\lambda$ 来调整牛顿步长，即：
$$
x_{n+1} = x_n - \lambda \frac{f(x_n)}{f'(x_n)}
$$
其中 $\lambda \in (0, 1]$。当 $\lambda=1$ 时，修正牛顿法退化为传统牛顿法。当 $\lambda<1$ 时，步长减小，有助于在函数较为陡峭或牛顿法收敛性较差的情况下提高算法的稳定性。
Davidon-Fletcher-Powell (DFP) 法是一种在优化领域中用于解决无约束优化问题的迭代方法，特别是用于寻找多变量函数的局部极小值。它属于拟牛顿方法的一种，旨在解决牛顿法计算复杂且需要二阶导数（Hessian 矩阵）的问题。拟牛顿方法只需要一阶导数信息（即梯度），通过迭代更新一个近似的Hessian矩阵的逆或者近似的Hessian矩阵本身。
DFP方法的核心思想是利用梯度信息来构造一个正定矩阵，这个矩阵作为Hessian矩阵的近似，用于生成搜索方向。这个方法在每一步迭代中都会更新这个近似矩阵，从而避免了直接计算Hessian矩阵及其逆矩阵的需要。
DFP方法的迭代公式可以表示如下：
（1）选择一个初始点 $x_0$ 和一个初始的正定矩阵 $H_0$（通常为单位矩阵）。
（2）对于第 $k$ 次迭代，计算梯度 $g_k = \nabla f(x_k)$，如果 $g_k$ 是零向量，则停止迭代。
（3）计算搜索方向 $p_k = -H_k g_k$。
（4）确定步长 $\alpha_k$，通常通过线搜索方法使得 $f(x_k + \alpha_k p_k)$ 达到最小。
（5） 更新 $x_{k+1} = x_k + \alpha_k p_k$。
（6）计算新的梯度 $g_{k+1} = \nabla f(x_{k+1})$ 并计算梯度变化 $\Delta g_k = g_{k+1} - g_k$。
（7）更新Hessian近似的逆矩阵：
$$
H_{k+1} = H_k + \frac{\Delta x_k \Delta x_k^T}{\Delta x_k^T \Delta g_k} - \frac{H_k \Delta g_k \Delta g_k^T H_k}{\Delta g_k^T H_k \Delta g_k}
$$
其中 $\Delta x_k = x_{k+1} - x_k$。
(8) 如果满足终止条件（比如梯度的范数小于某个阈值），则停止迭代；否则，回到步骤3。
Broyden族方法是一类用于求解非线性方程组的迭代算法。在多变量非线性问题中，牛顿法是一种著名的迭代方法，它使用Jacobian矩阵（即函数的一阶偏导数矩阵）来寻找方程的根。然而，牛顿法需要在每次迭代中计算Jacobian矩阵和它的逆，这在某些情况下可能非常耗时。
Broyden族方法是对牛顿法的改进，它通过更新近似的Jacobian矩阵或其逆矩阵，从而避免每次迭代都重新计算它们。Broyden族包括两种主要方法：Broyden的好方法（Broyden's "good" method）和Broyden的坏方法（Broyden's "bad" method），它们分别更新Jacobian矩阵和其逆。
Broyden的好方法更新Jacobian矩阵，而Broyden的坏方法更新Jacobian的逆矩阵。"好"和"坏"的称呼并不意味着一种方法比另一种更优越，而是指在某些情况下一种方法的数值稳定性可能比另一种好。
（1）这里是Broyden的好方法的基本步骤：
- 从一个初始猜测$x_0$开始，并计算Jacobian矩阵$J_0$。
- 在第$k$次迭代中，通过解线性方程组$J_k \Delta x_k = -F(x_k)$来计算步长$\Delta x_k$。
- 更新解的估计值$x_{k+1} = x_k + \Delta x_k$。
- 使用Broyden公式更新Jacobian矩阵的近似$J_{k+1}$。
- 重复步骤2-4，直到满足收敛条件。
拟牛顿方法是一类广泛用于优化问题中的方法，它们试图在不需要二阶导数信息的情况下，模拟牛顿法的超线性收敛性质。Broyden族方法在科学计算和工程领域中应用广泛，特别是在处理大规模非线性方程组时。
拟牛顿法是一类用于求解无约束优化问题的迭代方法，它们通过构造目标函数的海森矩阵（Hessian matrix，即二阶导数矩阵）的近似来寻找函数的极小点。拟牛顿法的核心思想是用一个简单的矩阵来近似海森矩阵或其逆矩阵，以此来避免直接计算二阶导数，从而减少计算量。
拟牛顿法的收敛性质取决于多个因素，包括初始点的选择、目标函数的性质以及更新策略等。
（1）局部收敛性
在某些条件下，如果初始点足够接近最优解，拟牛顿法可以保证局部超线性甚至是二次收敛速度。超线性收敛意味着每一步迭代后，解的近似误差以超过线性速度下降。二次收敛则意味着误差以平方的速度减少，这是最快的收敛速度。
（2）条件
拟牛顿法的收敛性通常要求目标函数在最优解附近是二次可微的，并且其海森矩阵是正定的。此外，拟牛顿条件（也称为割线条件或拟牛顿方程）要求近似的海森矩阵或其逆能够满足某种特定的一致性条件。
在线性规划中，尺度法的目的是通过变换来平衡系数矩阵的量级，使其更加均匀。这是因为在实际问题中，不同变量的量级可能相差很大，直接使用单纯形法等算法可能会导致数值不稳定。通过适当的尺度变换，可以减少因为数值问题而导致的计算误差，提高算法的数值稳定性。
在非线性规划中，尺度法可以通过调整变量的尺度来改变问题的条件数，这有助于优化算法（如梯度下降法、牛顿法等）更快收敛到最优解。在某些情况下，尺度变换可以是动态的，即在迭代过程中不断调整以适应当前的迭代点。
（1）变量尺度调整
在拟牛顿法的每次迭代之前，可以通过尺度变换来调整变量，使得它们在数值上更加均衡。这有助于避免因为变量尺度差异较大而导致的数值不稳定性。
（2）海森矩阵尺度调整
在构造海森矩阵的近似时，可以对其进行尺度调整，以改善收敛性。这种调整可以基于当前迭代点的局部信息，比如梯度的大小或者目标函数的局部曲率。
（3）预处理技术
拟牛顿法中的线搜索步骤可以通过尺度变换作为预处理步骤来执行。这有助于在执行线搜索以找到适当步长时，保持不同方向上的均衡性。
（4）动态更新策略
在拟牛顿方法中，可以动态地调整尺度，这意味着在迭代过程中根据需要调整变量的尺度。这样的动态策略可以使得算法更加灵活地适应问题的特性。
（5）改善条件数
尺度法可以通过改善海森矩阵近似的条件数来提高算法的数值稳定性。条件数是衡量线性方程组解的敏感度的一个指标，条件数越低，数值解通常越稳定。
无记忆拟牛顿法（Limited-memory Broyden-Fletcher-Goldfarb-Shanno，简称L-BFGS）是拟牛顿法中的一种，它特别适合于处理大规模优化问题。在标准的拟牛顿方法中，需要存储和更新整个近似海森矩阵或其逆矩阵，这在变量数量很大时会导致巨大的存储和计算负担。L-BFGS方法通过只存储最近几步的信息来重建近似海森矩阵，从而大大减少了内存的需求。
在某些情况下，可以将最速下降法和拟牛顿法结合起来使用，以期望在不同阶段利用各自的优势。例如：
（1）初始阶段使用最速下降法
在优化的初始阶段，当我们远离最优解时，最速下降法可以快速地将解推进到一个更好的区域。
（2）接近最优解量切换到拟牛顿法
当我们接近最优解时，拟牛顿法的超线性收敛特性可以加速收敛。
（3）条件切换
可以设置一些条件来决定何时从最速下降法切换到拟牛顿法，比如当连续几次迭代的改进不大时，或者当梯度的方向变化开始减缓时。
（4）混合方向
有些先进的方法会考虑将最速下降方向和拟牛顿方向进行某种形式的组合，以期望在每一步都取得较好的下降效果。
（5）全局化策略
可以使用线搜索或信赖域策略来全局化组合方法，确保每一步都是对目标函数的有效下降。
十、约束最小化问题的条件
约束最小化问题是指在给定一组约束条件下，寻找目标函数的最小值的问题。这类问题在数学优化和工程设计中非常常见。约束可以是等式约束（equality constraints）或不等式约束（inequality constraints），或两者的组合。
一个典型的约束最小化问题可以表示为：
$$
\begin{align}
\text{minimize} \quad & f(\mathbf{x}) \\
\text{subject to} \quad & g_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m \\
& h_j(\mathbf{x}) = 0, \quad j = 1, \ldots, p
\end{align}
$$
在约束最小化问题中，切平面方法的核心思想是逐步加入新的线性约束（即切平面），这些切平面能够切除当前松弛问题解的非可行部分，从而逼近原问题的可行域。
（1）这种方法通常包含以下步骤：
- 求解松弛问题：首先忽略整数约束或是部分非线性约束，求解问题的松弛版本，即只考虑那些容易处理的约束。
- 检查可行性：如果松弛问题的解满足所有约束，则它也是原问题的解，此时算法终止。
- 生成切平面：如果松弛问题的解不满足某些约束，就生成一个或多个切平面，这些切平面通过线性约束排除当前解，但不排除任何可行解。
- 更新问题并重新求解：将新的切平面加入到松弛问题中，更新问题的定义，然后重新求解新的松弛问题。
- 迭代：不断重复上述过程，直到找到满足所有约束的解，或者达到某些停止准则（如迭代次数、时间限制、无法进一步改进解等）。
（1）对于线性规划
最优解必须是基本可行解，即在可行域的顶点。
（2）对于非线性规划
- 可行性。解必须满足所有约束。
- 稳定性。目标函数的梯度必须能够被约束的梯度线性表示（在不等式约束的情况下，只有当约束是活跃的，即等式成立时，该约束才参与表示）。
- 互补松弛性。对于每一个不等式约束，其拉格朗日乘数与约束函数的乘积必须为零。
- 拉格朗日乘数非负。对于不等式约束，相应的拉格朗日乘数必须非负。
（1）对于非线性规划
如果一个点是局部最优解，那么在该点的拉格朗日函数的二阶导数（Hessian）在约束定义的可行方向上必须是半正定的。
（1）切子空间
在约束最小化问题中，切子空间可以被定义为在某点处满足所有线性化约束的向量空间。例如，考虑以下约束最小化问题：
$$
\begin{align*}
\text{minimize} \quad & f(\mathbf{x}) \\
\text{subject to} \quad & g_i(\mathbf{x}) = 0, \quad i = 1, \ldots, m,
\end{align*}
$$
其中 $f(\mathbf{x})$ 是目标函数，$g_i(\mathbf{x})$ 是约束函数。在某点 $\mathbf{x}_0$ 处，切子空间由满足约束函数在 $\mathbf{x}_0$ 处的一阶Taylor展开为零的所有向量组成。如果我们将约束函数的梯度向量 $\nabla g_i(\mathbf{x}_0)$ 视为定义切子空间的法向量，那么切子空间中的任何向量 $\mathbf{v}$ 必须满足 $\nabla g_i(\mathbf{x}_0) \cdot \mathbf{v} = 0$ 对于所有 $i$。
（2）特征值在切子空间中的角色
在优化问题中，特别是在需要进行二次近似的情况下，目标函数 $f(\mathbf{x})$ 在 $\mathbf{x}_0$ 处的Hessian矩阵 $\mathbf{H}$ 的特征值提供了关于函数曲率的信息。在切子空间中，我们对Hessian矩阵在该子空间上的限制感兴趣，因为这反映了在满足约束的方向上目标函数的局部行为。
- 如果切子空间中 $\mathbf{H}$ 的所有特征值都是正的，那么在 $\mathbf{x}_0$ 处沿着切子空间的任何方向，目标函数都是局部凸的，这意味着 $\mathbf{x}_0$ 是一个局部最小点。
- 如果切子空间中 $\mathbf{H}$ 的所有特征值都是负的，那么目标函数在这些方向上是局部凹的，$\mathbf{x}_0$ 是一个局部最大点。
- 如果特征值有正有负，那么 $\mathbf{x}_0$ 是一个鞍点。
在实际计算中，直接计算切子空间中的特征值可能很困难。通常，我们会使用数值方法，如拉格朗日乘数法（Lagrange multipliers）或KKT条件，来分析和解决这类问题。这些方法可以帮助我们找到满足约束的最优点，而不需要显式计算切子空间中的特征值。
（1）零阶条件
零阶优化方法仅仅依赖于目标函数值本身，而不是其导数。常见的零阶优化方法包括：
- 穷举法
- 随机搜索
- 模拟退火
- 遗传算法
这些方法不需要目标函数是可微的，因此适用于不连续或不光滑的目标函数。
（2）拉格朗日松弛
拉格朗日松弛技术是一种处理带有约束的优化问题的方法。在这种方法中，我们将一些或全部的约束条件通过拉格朗日乘子加入到目标函数中，转换为一个或多个没有这些约束的优化问题。拉格朗日松弛可以降低问题的复杂性，使得原始问题更容易解决。
例如，考虑以下带约束的优化问题：
$$
\begin{align}
\text{minimize} \quad & f(x) \\
\text{subject to} \quad & g_i(x) \leq 0, \quad i = 1, \ldots, m \\
& h_j(x) = 0, \quad j = 1, \ldots, p
\end{align}
$$
其中，$f(x)$ 是目标函数，$g_i(x)$ 是不等式约束，$h_j(x)$ 是等式约束。
通过拉格朗日松弛，我们可以选择某些不等式约束 $g_i(x)$，并将它们加入到目标函数中，形成一个新的目标函数：
$$
L(x, \lambda, \mu) = f(x) + \sum_{i=1}^{m} \lambda_i g_i(x) + \sum_{j=1}^{p} \mu_j h_j(x)
$$
其中，$\lambda_i$ 和 $\mu_j$ 是拉格朗日乘子。
通过适当选择乘子 $\lambda_i \geq 0$ 和 $\mu_j$，我们可以得到一个关于 $x$ 的无约束优化问题。这个无约束问题通常比原始的约束优化问题更容易求解。松弛后的问题提供了原问题的一个下界（对于最小化问题）或上界（对于最大化问题）。
在实际应用中，拉格朗日松弛可以与子梯度方法、对偶理论和分支定界法等结合使用，以求解复杂的优化问题。
十一、原始方法
在优化问题中，"原始方法"（Primal approach）通常指直接对原始优化问题进行求解的方法。原始问题是指最初提出的、包含所有约束条件的优化问题。与之相对的是"对偶方法"（Dual approach），它涉及将原始问题转化为对偶问题，然后求解对偶问题。
可行方向法（Feasible Directions Method）是一种用于求解有约束优化问题的数值方法。它属于迭代算法的一种，旨在逐步改进解，同时确保每一步都保持在可行域内。这种方法通常用于处理不等式约束的优化问题。
（1）基本思想
可行方向法的基本思想是，在每次迭代中从当前点寻找一个可行方向，沿着这个方向移动能够减少目标函数的值而不违反任何约束。一个方向是可行的，如果沿该方向移动一个小的正步长不会导致违反任何约束。
（2）算法步骤
- 初始化。选择一个满足所有约束的初始可行解$x^{(0)}$。
- 确定可行方向。在当前点$x^{(k)}$，找到一个可行方向$d^{(k)}$，使得对于某个$\alpha > 0$，点$x^{(k)} + \alpha d^{(k)}$仍然满足所有约束。
- 线搜索。沿着确定的可行方向$d^{(k)}$，使用线搜索方法找到一个步长$\alpha_k$，使得$f(x^{(k)} + \alpha_k d^{(k)})$尽可能小，同时点$x^{(k)} + \alpha_k d^{(k)}$仍然满足所有约束。
- 更新解。更新当前解$x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}$。
- 检查终止条件。如果满足终止条件（例如，可行方向改善目标函数的量小于某个阈值或达到最大迭代次数），则停止迭代；否则，返回步骤2。
确定可行方向是可行方向法的核心。这通常涉及到解一个线性规划问题或使用某种启发式方法。一个常用的方法是构造一个多面体近似于当前点的可行域，并在多面体内寻找一个减少目标函数值的方向。
起作用集（Active Set）方法是一种用于求解有约束优化问题的数值方法，特别是用于二次规划和更一般的非线性规划问题。这种方法的关键思想是在每一步迭代中维护并更新一个“起作用集”，这个集合包含了当前解处于边界上的约束。然后，算法试图在这个起作用集定义的较小的搜索空间中找到最优解。
（1）算法步骤
- 初始化。选择一个初始可行解$x^{(0)}$以及相应的起作用集$W^{(0)}$，其中包括所有在$x^{(0)}$点上起作用的约束（即等式约束和作为等式满足的不等式约束）。
- 求解子问题。在起作用集$W^{(k)}$定义的约束下，求解一个子问题来找到新的点$x^{(k+1)}$。这个子问题通常是一个无约束优化问题，或者是一个简化了的有约束优化问题。
- 更新起作用集。检查新解$x^{(k+1)}$是否满足所有的约束。如果满足，则检查是否有不在$W^{(k)}$中的约束变得起作用，如果有，则将其加入$W^{(k)}$。如果不满足某个约束，则从$W^{(k)}$中移除最不满足的约束。
- 线搜索。如果需要，进行线搜索以确定沿着$x^{(k+1)} - x^{(k)}$方向的步长，以确保所有的约束都得到满足。
- 检查终止条件。如果满足终止条件（例如，解的改进小于某个阈值或达到最大迭代次数），则停止迭代；否则，返回步骤2。
梯度投影法（Gradient Projection Method）是解决有约束优化问题的一种迭代算法，尤其适用于处理线性约束。它是可行方向法的一种特例，用于寻找目标函数在约束集合上的局部极小点。梯度投影法通过将梯度下降法与投影操作结合起来，以确保迭代点始终保持在可行域内。
（1）基本思想
梯度投影法的基本思想是在每次迭代中，首先对当前点进行梯度下降步骤，然后将得到的点投影回可行域。投影操作确保了新的迭代点满足所有约束条件。
（2）算法步骤
- 初始化。选择一个满足所有约束的初始可行解$x^{(0)}$。
- 计算梯度。计算当前点$x^{(k)}$处的目标函数梯度$\nabla f(x^{(k)})$。
- 梯度下降。计算一个临时点$x' = x^{(k)} - \alpha_k \nabla f(x^{(k)})$，其中$\alpha_k$是步长。
- 投影回可行域。找到最接近$x'$的可行域中的点$x^{(k+1)}$。这个操作可以视为解决以下优化问题：
$$
\min_{x \in C} \frac{1}{2}\|x - x'\|^2
$$
其中$C$是由所有约束定义的可行域。 - 检查终止条件。如果满足终止条件（例如，梯度的变化或函数值的变化小于某个阈值），则停止迭代；否则，返回步骤2。
（1）基本思想
在有约束优化问题中，某些变量受到约束的限制，而其他变量则是自由的。简化梯度法的思路是在每次迭代中只对自由变量进行优化，而保持受约束的变量不变。这样，问题的维度就降低了，因此这种方法被称为“简化梯度法”。
（2）算法步骤
- 初始化。选择一个满足所有约束的初始可行解$x^{(0)}$。
- 分离变量。将变量分为基变量（受约束）和非基变量（自由）。
- 计算简化梯度。对于非基变量，计算目标函数在这些自由变量方向上的梯度（简化梯度）。
- 选择可行该向。根据简化梯度确定一个可行的下降方向，这个方向必须保持基变量满足约束条件。
- 线搜索。在选定的可行方向上进行线搜索，确定步长$\alpha_k$。
- 更新解。更新非基变量的值$x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}$，其中$d^{(k)}$是选择的下降方向。
- 检查终止条件。如果满足终止条件（例如，简化梯度的大小小于某个阈值），则停止迭代；否则，可能需要重新选择基变量和非基变量，然后返回步骤3。
十二、罚函数法与障碍函数法
罚函数方法是一种求解有约束优化问题的数值方法，它通过将约束条件转化为目标函数的一部分来实现。这种方法使用一个额外的罚项（或罚函数）来量化解对于约束的违反程度，并将其加权后加到目标函数中。通过这种方式，原始的有约束问题被转化为一系列无约束问题，这些无约束问题可以使用标准的优化算法求解。
（1）罚函数的类型
- 外罚函数。它在可行域之外施加罚项，迫使解向可行域内移动。当解违反约束时，罚项的值会很大，因此这种方法会产生一系列在可行域边界上越来越紧的问题。
- 内罚函数（也称为障碍函数法）。它在可行域内部施加罚项，防止解越过约束边界。随着罚项系数的增大，解会被迫靠近边界但不会离开可行域。
（2）罚函数方法的基本步骤
- 构造罚函数。将原始的有约束优化问题转化为无约束问题，通过在目标函数中加入与约束违反程度相关的罚项。
- 选择罚参数。选择一个初始的罚参数值（通常是一个较大的数）。
- 迭代求解。使用无约束优化算法求解当前的罚函数问题。
- 更新罚参数。在每次迭代后，增加罚参数的值（对于外罚函数）或减小罚参数的值（对于内罚函数），使罚项的影响更大。
- 检查终止条件。如果解的变化较小或者罚项影响足够小，且约束满足程度足够好，则停止迭代。
牛顿法是一种在优化和求解方程中广泛使用的数值方法，它基于二阶泰勒展开来近似目标函数，从而找到函数的极值点或零点。当将牛顿法应用于优化问题时，它通过迭代求解目标函数梯度（一阶导数）为零的点来找到局部极小值。如果目标函数是二次的并且Hessian矩阵（二阶导数矩阵）是正定的，牛顿法通常能够快速收敛到全局最小值。
将牛顿法应用于有约束优化问题时，可以结合罚函数方法。罚函数方法通过将约束转化为目标函数的一部分来处理有约束问题，这可以通过在目标函数中加入与约束违反程度相关的罚项来实现。这样，原始的有约束优化问题就被转化为一系列的无约束问题，这些问题可以使用牛顿法等无约束优化算法来求解。
（1）结合牛顿法的罚函数方法
- 构造罚函数。首先将原始的有约束问题转化为无约束问题，通过在目标函数中加入罚项。对于等式约束 $h(x)=0$，罚项可能是 $r \cdot h(x)^2$ 的形式，其中 $r$ 是罚参数；对于不等式约束 $g(x) \leq 0$，罚项可能是 $r \cdot \max(0, g(x))^2$。
- 选择罚参数。选择一个初始的罚参数值，通常是一个较大的数。
- 迭代求解。使用牛顿法来求解罚函数的极小值。在每次迭代中，需要计算目标函数的梯度和Hessian矩阵，并进行牛顿步骤的更新。
- 更新罚参数。在每次迭代后，增加罚参数的值，使得罚项的影响更大，从而迫使解更加接近原始问题的可行域。
- 检查终止条件。如果解的变化较小或者罚项影响足够小，且约束满足程度足够好，则停止迭代。
共轭梯度法是一种解决大规模线性系统问题的迭代方法，特别是对于形式为 $Ax = b$ 的线性方程组，其中 $A$ 是一个大型稀疏对称正定矩阵。在优化领域，共轭梯度法也被用来求解无约束优化问题，尤其是对于二次型目标函数：
$$ f(x) = \frac{1}{2} x^T A x - b^T x + c $$
共轭梯度法的关键优势是它不需要显式地存储Hessian矩阵，而是通过迭代利用梯度信息来更新搜索方向，这些搜索方向在理论上是$A$-共轭（或者说是$A$-正交）的。对于一般的非线性优化问题，共轭梯度法可以用于找到无约束问题的局部极小值。
（1）共轭梯度法与罚函数结合的方法
当我们需要解决有约束优化问题时，可以结合罚函数方法将问题转化为一系列无约束问题，然后使用共轭梯度法来求解这些无约束问题。罚函数方法通过在目标函数中添加与约束违反程度相关的罚项，将有约束问题转化为无约束问题。对于等式约束 $h(x)=0$ 和不等式约束 $g(x) \leq 0$，罚项分别可能是 $r \cdot h(x)^2$ 和 $r \cdot \max(0, g(x))^2$ 的形式，其中 $r$ 是罚参数。
罚函数的规范化主要关注如何选择和构造罚项，以及如何设置罚参数，以确保解的质量和算法的有效性。
（1）罚项的构造
- 等式约束。对于等式约束 $h(x) = 0$，罚项通常是 $r \cdot h(x)^2$ 的形式。
- 不等式约束。对于不等式约束 $g(x) \leq 0$，罚项可以是 $r \cdot \max(0, g(x))^2$ 或其他形式，如对数障碍函数 $-r \cdot \ln(-g(x))$。
精确罚函数（Exact Penalty Function）是在优化理论中使用的一种罚函数，它具有这样一个特点：对于足够大的罚参数，原始有约束优化问题的任何局部最优解也是相应罚函数无约束问题的局部最优解，反之亦然。这意味着，通过解无约束优化问题，可以直接找到原始有约束问题的解，而不需要像传统罚函数方法那样逐渐增加罚参数并求解一系列无约束问题。
十三、对偶与对偶方法
全局对偶性（Global Duality）在优化理论中是一个非常重要的概念，特别是在凸优化问题中。对偶性涉及将原始优化问题（称为原问题）转换成另一个问题（称为对偶问题），这个对偶问题通常具有更好的数学或计算性质。
在最优化理论中，对于一个给定的原始问题，可以构造一个与之相关的对偶问题。原始问题与对偶问题之间存在一定的联系，这种联系可以帮助我们更好地理解和解决原始问题。全局对偶性特别关注原始问题和对偶问题解之间的关系。
（1）原始问题
原始问题通常是这样的形式：
$$
\begin{align*}
\text{minimize}\quad & f(x) \\
\text{subject to}\quad & g_i(x) \leq 0, \quad i = 1, \ldots, m \\
& h_j(x) = 0, \quad j = 1, \ldots, p \\
\end{align*}
$$
其中 $f(x)$ 是目标函数，$g_i(x)$ 是不等式约束，$h_j(x)$ 是等式约束。
（2）对偶问题
对偶问题是通过拉格朗日松弛原始问题中的约束条件得到的，形式如下：
$$
\begin{align*}
\text{maximize}\quad & \theta(\lambda, \nu) \\
\text{subject to}\quad & \lambda \geq 0 \\
\end{align*}
$$
其中，$\theta(\lambda, \nu)$ 是拉格朗日函数 $L(x, \lambda, \nu)$ 对 $x$ 的最小值，$\lambda$ 和 $\nu$ 分别是与不等式和等式约束相关的拉格朗日乘子。
（3）全局对偶性
当原始问题和对偶问题满足一定条件时，它们之间存在全局对偶性，这意味着：
- 弱对偶性。对偶问题的最优值总是小于或等于原始问题的最优值。
- 强对偶性。在某些条件下，如Slater条件（对于凸优化问题），原始问题的最优值与对偶问题的最优值相等。这种情况下，如果原始问题和对偶问题都有解，那么它们的最优解是相等的。
- 鞍点条件。拉格朗日函数在原始变量 x 上的最小值和在对偶变量 (λ,ν) 上的最大值相等时，我们说拉格朗日函数在这一点上有一个鞍点。
- 最优性条件。如果存在一个解 (x∗,λ∗,ν∗) 使得拉格朗日函数在该点有鞍点，则 x∗ 是原始问题的最优解，(λ∗,ν∗) 是对偶问题的最优解。
全局对偶性的概念是凸优化领域的核心，因为它为优化算法提供了强大的理论基础。在非凸情况下，强对偶性通常不成立，但在某些特定条件下可能仍有弱对偶性
增广拉格朗日函数（Augmented Lagrangian function）是拉格朗日乘数法的一个扩展，它在处理有约束优化问题时，特别是在约束条件难以满足或者拉格朗日乘数法难以找到可行解的情况下，能够提供更好的数值性能。
考虑以下具有等式约束的优化问题：
$$
\begin{align}
\text{minimize} \quad & f(x) \\
\text{subject to} \quad & g_i(x) = 0, \quad i = 1, \ldots, m
\end{align}
$$
其中 $f(x)$ 是目标函数，$g_i(x)$ 是约束函数。
传统的拉格朗日函数（Lagrangian）$L(x, \lambda)$ 对于上述问题是这样定义的：
$$
L(x, \lambda) = f(x) + \sum_{i=1}^{m} \lambda_i g_i(x)
$$
其中，$\lambda = (\lambda_1, \ldots, \lambda_m)$ 是拉格朗日乘数向量。
增广拉格朗日函数在拉格朗日函数的基础上增加了一个惩罚项，用以强化对约束的满足，定义如下：
$$
L_A(x, \lambda, \rho) = f(x) + \sum_{i=1}^{m} \lambda_i g_i(x) + \frac{1}{2}\rho \sum_{i=1}^{m} g_i(x)^2
$$
其中，$\rho > 0$ 是一个惩罚参数。
增广拉格朗日函数的关键思想是，通过惩罚项 $\frac{1}{2}\rho g_i(x)^2$ 的加入，当约束 $g_i(x)$ 远离零的时候，惩罚项会导致函数值显著增加，从而促使优化过程中的解更加靠近约束满足的区域。随着 $\rho$ 的增加，对约束违反的惩罚越来越大，解将越来越倾向于满足约束条件。
增广拉格朗日方法通常与迭代算法结合使用，如增广拉格朗日乘数法（Augmented Lagrange Multiplier method，ALM），在每一步迭代中，首先固定 $\lambda$ 和 $\rho$ 来最小化 $L_A(x, \lambda, \rho)$ 得到 $x$，然后更新 $\lambda$，最后可能还会调整 $\rho$。这个过程迭代进行，直至收敛到满足原始问题约束的解。
交替方向乘子法（Alternating Direction Method of Multipliers, 简称ADMM）是一种求解优化问题的算法，特别适用于分解和分布式计算。ADMM 结合了拉格朗日乘子法的分解能力和增广拉格朗日方法的收敛性，尤其适用于大规模和分布式优化问题。
ADMM 主要用于解决以下形式的优化问题：
$$
\begin{align}
\text{minimize} \quad & f(x) + g(z) \\
\text{subject to} \quad & Ax + Bz = c
\end{align}
$$
其中 \( f \) 和 \( g \) 是目标函数，\( A \) 和 \( B \) 是矩阵，\( c \) 是向量，\( x \) 和 \( z \) 是优化变量。
ADMM 通过将原问题分解为更易于解决的子问题来解决这类优化问题。这些子问题在每次迭代中交替求解，从而更新 \( x \)、\( z \) 和拉格朗日乘子 $( \lambda ) $或者等价的对偶变量 \( y \)。
ADMM 算法的基本迭代步骤通常如下：
1. **\( x \) 更新步骤**：固定 \( z \) 和 $( \lambda )$（或 \( y \)），求解以下问题以更新 \( x \)：
$$
x^{k+1} := \text{argmin}_x \left( f(x) + \left( \lambda^k \right)^T (Ax + Bz^k - c) + \frac{\rho}{2} \| Ax + Bz^k - c \|_2^2 \right)
$$
2. **\( z \) 更新步骤**：固定 \( x \) 和 $( \lambda )$（或 \( y \)），求解以下问题以更新 \( z \)：
$$
z^{k+1} := \text{argmin}_z \left( g(z) + \left( \lambda^k \right)^T (Ax^{k+1} + Bz - c) + \frac{\rho}{2} \| Ax^{k+1} + Bz - c \|_2^2 \right)
$$
3. **乘子（或对偶变量）更新步骤**：更新 $( \lambda )$（或 \( y \)）：
$$
\lambda^{k+1} := \lambda^k + \rho (Ax^{k+1} + Bz^{k+1} - c)
$$
其中，$( \rho > 0 )$ 是惩罚参数，\( k \) 表示迭代步数。
ADMM 的关键优点是能够将原问题分解为可以独立并行求解的子问题，每个子问题通常更容易或更快解决。此外，ADMM 对参数选择相对鲁棒，且在实践中表现出了良好的收敛性质，尤其是在处理大规模分布式数据时。
ADMM 已经被广泛应用于统计学习、信号处理、图像恢复、机器学习等领域，并且被证明在解决稀疏优化、分布式控制、大规模数据分析等问题上非常有效。