运筹学笔记

$2023$ 秋运筹学（陈士祥）学习笔记。

线性规划

标准形式与一般形式

标准形式：

$\min c^T x \\ \text{s.t. }Ax=b \\ x\ge 0$

标准形式主要用于计算。

一般形式：

$\min c^T x \\ \text{s.t. }Ax\ge b$

一般形式在分析线性规划理论的时候比较方便。

Thm（等价性）：线性规划一般形式和标准形式等价。（两个优化问题等价的意义是指，对于一个优化问题的可行解，我们总可以找到另一个问题对应的可行解，使得它们的目标函数值相等。）

“数学上等价，但计算上不等效”。–冯康

Thm（行满秩假设）：对于标准形式，如果矩阵 $A \in \mathbb R^{m×n}$ 的秩为 $k\ (k < m)$，其行向量为 $a_1^T,a_2^T,\ldots,a_m^T$。那么 $A$ 的 $k$ 个线性无关的行向量 $a_{i_1}^T,a_{i_2}^T,\ldots,a_{i_k}^T$ 组成的子矩阵 $\tilde{A}$ 对应的 $\tilde{b}$，有 $P = Q$，这里 $P = \{x \in \mathbb R^n \mid Ax = b, x ≥ 0\},Q = \{x \mid \tilde{A}x= \tilde{b},x ≥ 0\}$。

Proof：假设 $A$ 的行向量集合线性相关，不妨设：$a_1=\sum\limits_{i>1} \lambda_i a_i$。

如果有：$b_1=\sum\limits_{i>1} \lambda_i b_i$，则第一个方程完全可以用后面的表示，可以直接省略。

如果不等于则整个方程组直接矛盾，可行域 $P$ 变为空，无意义，不考虑这种情况。

于是可以一直删去相关的行向量，最后得到 $\text{rank}(A)$ 个线性无关的行向量，并且保持可行域不变，即有 $P=Q$。$\Box$

因此，不失一般性，我们考虑标准形式可以假设 $A$ 是行满秩的。

理论分析

Defn（凸集）：一个集合 $S \subset \mathbb R^n$ 是一个凸集，如果 $\forall x,y\in S$ 以及 $t \in [0, 1],tx + (1 − t)y \in S$。

Defn（超平面，半空间）：给定 $n$ 维向量 $a$ 和实数 $b$：

• 集合 $\{x \in \mathbb R^n \mid a^Tx = b\}$ 为超平面（hyperplane）。
• 集合 $\{x \in \mathbb R^n \mid a^Tx ≥ b\}$ 为半空间（halfspace）。

Defn（多面集）：多面集是符合下述定义的集合

$P = \{x \in \mathbb R^n \mid Ax ≥ b\}$

其中，矩阵 $A \in \mathbb R^{m×n}$，向量 $b \in \mathbb R^m$。

可以证明多面体为凸集，一个一个半空间往上加就可以了。线性规划一般形式的可行域就是标准的凸集。实际上线性规划任意形式的可行域都是凸集，因为凸集加上一个超平面也是凸集。

通过对于二维的线性规划进行画图法求解（高中知识），我们可以大致观察出线性规划的最优解总是在凸多边形的顶点取到。在高维中我们改如何定义与找到顶点呢？有如下三个定义：

Defn（极点、顶点、基解与可行基解）：我们记 $P = \{x \mid Ax ≥ b\}$ 为一个凸多面集，不等式约束下标集 $\mathcal I = \{i \mid a_i^Tx ≥ 0\}$。

• 极点（extreme point）：$x \in P$ 被称作 $P$ 的极点，若 $x = λx^{(1)} + (1 − λ)x^{(2)}\ (λ \in (0, 1),\ x^{(1)}, x^{(2)} \in P)$，则必有 $x = x^{(1)} = x^{(2)}$，那么称 $x$ 是凸集 $P$ 的极点。
• 顶点（vertex）：$x$ 被称作 $P$ 的顶点，如果存在某个 $c \in \mathbb R^n$，使得 $c^Tx < c^Ty,\forall y \in P, y \ne x$。
• 基解（basic solution）和可行基解（basic feasible solution）:
  • $x$ 被称为一个基解，如果所有的等式约束（若有）都成立，或者说主动 / 激活（active）；等式约束下标集合 $\mathcal E$ 加上积极不等式约束下标集 $\mathcal I_e := \{i ∈ I \mid a_i^Tx = b_i\}$ 中，存在 $n$ 个下标 $i$，使得 $a_i$ 线性无关。
  • 一个基解如果也是可行解，我们称其为一个可行基解。

极点和顶点是几何层面的定义，基解是代数层面的定义。基解是最后服务于计算的。

基解有点难以理解，这里有一个例子：

实际上这三个定义等价（当集合为凸集时）：

Thm（极点、顶点、可行基解的等价性）：如果 $P = \{x \mid Ax ≥ b\}$ 是一个非空多面集，$x \in P$，那么下述三种情况等价：

• $x$ 是顶点；
• $x$ 是极点；
• $x$ 是可行基解。

Proof:

• 顶点 $\to$ 极点：

  假设 $x$ 是一个顶点，根据定义，可以找到 $c$ 使得 $c^Tx < c^Ty,\forall y \in P, y \ne x$。

  假设 $x = ty + (1 − t)z,t ∈ [0, 1], x \ne y \ne z$，那么 $c^Tx < c^T(ty + (1 − t)z)$。

  这与假设矛盾，因此 $x$ 不能被表示为其余两个可行点的凸组合。所以 $x$ 是一个极点。

• 极点 $\to$ 可行基解:

  我们证明：如果 $x$ 不是可行基解，那么 $x$ 也不是极点。

  如果 $x$ 非可行基解，记 $I = \{i \mid a_i^Tx = b_i\}$，那么 $|I| < n$。所以 $a_i, i \in I$ 在 $\mathbb R^n$ 的一个严格子空间中。可以找到 $d$，使得 $d^Ta_i = 0, \forall i \in I$。

  我们令 $y = x + ϵd, z = x − ϵd$，$ϵ$ 为一个很小的正数。我们有 $a_i^Ty = b_i = a_i^Tz, i \in I$。对于 $i \notin I$，可以令 $ϵ$ 充分小，使得 $a_i^Ty = a_i^Tx + ϵa_i^Td > b_i$ 且 $a_i^Tz = a_i^Tx - ϵa_i^Td > b_i$。故 $y, z \in P$，$x = (y + z)/2$ 不是极点。

• 可行基解 $\to$ 顶点：

  设可行基解为 $x$，假设 $\mathcal I$ 是 $x$ 的主动约束指标集。令 $c=\sum\limits_{i\in \mathcal I} a_i$。

  则：

  $c^T x=\sum_{i\in \mathcal I} a_i^T x=\sum_{i\in \mathcal I} b_i$

  而 $\forall y\in P$：

  $c^T y=\sum_{i\in \mathcal I} a_i^T y\ge\sum_{i\in \mathcal I}b_i=c^T x$

  分析等号成立的条件，显然等号成立的充分条件是 $\forall i\in \mathcal I,a_i^T y=b_i$。又因为 $x$ 是可行基解，故 $|\mathcal I|=n$，集合大小已经是最大的了（也就是说这个主动约束集合已经唯一确定 $x$ 这一个点了），所以当且仅当 $y=x$ 时等号成立。

  所以：$\forall y\ne x\in P,c^T x<c^T y$，故 $x$ 是顶点。$\Box$

可行基解的计算与存在性

定义等价性证明完成后我们着重来到可行基解的计算上。

Defn（直线）：对于一个多面集 $P = \{x \mid Ax ≥ b\} ⊂ \mathbb R^n$，如果存在 $x ∈ P$ 和一个非零向量 $d ∈ \mathbb R^n$，使得对任意实数 $λ$，有 $x + λd ∈ P$，那么称 $P$ 包含一条直线。

Thm（极点存在性定理）：假设 $P = \{x \mid Ax ≥ b\} ⊂ \mathbb R^n$ 非空，下列 $2$ 种情况等价：

• $P$ 中存在至少一个极点。
• $P$ 不包含直线。

Proof：

• 无直线 $\to$ 有极点：

  首先我们说明：$a_i\ (i\in [m])$ 中一定可以取出 $n$ 个线性无关的向量。若否，则 $A$ 表示的空间的正交补空间非平凡，即 $(\text{span}(A))^\bot\ne \{0\}$。任取 $d\in (\text{span}(A))^\bot$，则 $a_i^Td=0\ (i\in [m])$。那么任取 $x\in P$，则 $x+\lambda d$ 就是一条直线，矛盾了。

  于是我们从任意一点 $x^*$ 出发，设这一点的主动约束集为 $\mathcal I_e(x^*)$，而其中最大的线性无关组大小为 $L$。

  如果 $L<n$，那么就一直往 $(\text{span}(a_i,i\in \mathcal I_e(x^{*})))^{\bot}$ 中的某个非零方向 $d$ 走（这一定存在因为 $L<n$）。因为无直线，所以一定会碰到头。假设又走到了一个边界 $x'$，而因为 $d$ 与每个 $a_i\ (i\in \mathcal I_e(x^{*}))$ 都正交，所以 $\mathcal I_e(x^{*})\subsetneq \mathcal I_e(x')$，而 $L$ 显然不会减少。

  这样的过程一定会停止，因为$a_i\ (i\in [m])$ 中一定可以取出 $n$ 个线性无关的向量。那么我们就找到了一个可行基解，也就是极点。

• 有极点 $\to$ 无直线：

  因为有极点，所以 $a_i\ (i\in [m])$ 中一定可以取出 $n$ 个线性无关的向量，故 $A$ 表示的空间的正交补空间为平凡空间，即 $(\text{span}(A))^\bot= \{0\}$。所以 $\forall d\ne 0\in \mathbb R^n,\exists i\in [m],\text{s.t. }a_i^T d\ne 0$，不妨设 $a_i^T d<0$，则显然从任意点一直往 $d$ 走会走出 $P$，故无直线。$\Box$

极点的最优性

Thm（极点最优性）：考虑线性规划问题，在一般形式的多面集 $P = \{x \mid Ax ≥ b\}$ 或者标准形式的多面集 $P=\{x\mid Ax=b,x\ge 0\}$上，最小化 $c^Tx$。假设 $P$ 中存在至少一个极点。那么，要么最优值是 $−∞$，要么必定有某个极点是最优解。

最优解的约定：

• 可行域为空 $\to$ 无解；
• 可行域有界 $\to$ 唯一解 或者 不唯一解；
• 可行域无界 $\to$ (1) 唯一解 或者 (2) 无穷多解，$P$ 中可能不存在极点 或者 (3) 最优值为 $−∞$;
• 我们把“唯一解”和“无穷多解”称为模型存在最优解，而把“无界解 $−∞$”归入不存在最优解的情形。

单纯形法

（鸽子了，只要算几个单纯形表大概就能掌握了）

对偶理论

针对任意一个最优化问题，可以定义它的一个对偶问题（Dual Problem）。

对偶理论将揭示原问题与对偶问题之间的内在联系，为进一步深入研究线性规划的求解算法提供理论依据。

考虑标准形式的线性规划问题：

$\min c^T x \\ \text{s.t. } Ax = b \\ x ≥ 0$

定义 Lagrange 函数 $L(x, λ, \mu) = c^Tx + λ^T(b − Ax) − \mu^Tx\ (\mu ≥ 0, λ ∈ \mathbb R^m)$。

我们记 $g(λ, \mu) = \min\limits_{x∈\mathbb R^n} L(x, λ, \mu)$。

对于任意原问题的可行解 $\bar{x}$，我们有：

$g(λ, \mu) ≤ c^T\bar{x} + λ^T(b − A\bar{x}) − \mu^Tx ≤ c^T\bar{x}$

故问题：

$\max_{λ,\mu\ge 0}g(λ, \mu)$

可以看作寻找原问题的最紧下界。

$\min\limits_{x∈\mathbb R^n} L(x, λ, µ) = \min_x (c − A ^Tλ − \mu)^Tx + λ^Tb= \begin{cases} b^Tλ & A^Tλ + \mu = c \\ −\infty & \text{otherwise} \end{cases}$

故有对偶问题：

$\max b^T λ \\ \text{s.t. }A^T λ ≤ c$

而一般优化问题：

$\min f(x) \\ g_i(x)\ge 0\ (i\in \mathcal I) \\ h_j(x)=0\ (j\in \mathcal E)$

的 Lagrange 对偶为：

$\max_{\lambda\ge 0,\mu}g(\lambda,\mu)\ (:=\min_x L(x,\lambda,\mu)\ (:=f(x)-\sum_{i\in \mathcal I} \lambda_i g_i(x)-\sum_{j\in \mathcal E}\mu_j h_j(x))\ )$

Lagrange 函数引出了弱对偶定理：

Thm（弱对偶定理）：任意优化问题及其对偶问题之间成立以下关系 $x$ 是原问题的可行解，$λ,\mu$ 是对偶问题的可行解，则 $f(x)\ge g(\lambda,\mu)$。

对偶的对偶是什么的？

Thm（对偶的对偶）：线性规划问题的对偶问题的对偶问题和原问题等价。

Proof：取线性规划的一般形式：

$\max c^T x \\ \text{s.t. } Ax\ge b$

求其 Langrange 对偶：

$\max\limits_{\mu\ge 0}\min\limits_x c^T x-\mu^T (Ax-b)$

而：

$\min\limits_x c^T x-\mu^T (Ax-b)=\min\limits_x (c^T-\mu^TA)x+\mu^T b= \begin{cases} b^T \mu & A^T\mu=c \\ -\infty & \text{otherwise} \end{cases}$

故对偶问题为：

$\max b^T \mu \\ \text{s.t. } A^T\mu = c \\ \mu\ge 0$

再由上面的推导可知这一问题的对偶又为：

$\max c^Tz$

$\text{s.t. } Az \le -c$

令 $y=-z$ 可将这个问题改写为：

$\min c^Ty$

$\text{s.t. } Ay \ge c$

即为原问题。故线性规划问题对偶的对偶是原问题。$\Box$

这一结论对一般优化问题中不一定成立，这是线性规划很好的一个性质。

Thm（线性规划的强对偶定理）：原问题有最优解，则对偶问题也有最优解，且此时两方的最优值一致。

Proof：设原问题的最优解为某个可行基解：$\bar{x} = (x_B , 0)^T$，那么最优值为 $c_B^Tx_B$。

由单纯形法的最优判定定理得：

$c^T − c_B^T B^{−1}A ≥ 0^T$

令 $\bar{λ} = (B^{−1})^T c_B ∈ \mathbb R^m$，那么：

$A^T\bar{λ} ≤ c$

并且：

$\bar{\lambda}^Tb = c_B^T B^{−1}b = c_B^T x_B$

由弱对偶定理，$\bar{λ}$ 是对偶问题的最优解，且两者最优值一致。$\Box$

Thm（互补松弛定理）： 设 $\bar{x}$ 和 $\bar λ$ 分别是原问题和对偶问题的可行解，那么 $\bar x$ 和 $\bar λ$ 是对应问题最优解的充要条件是：

$\begin{cases} \bar{x}^T (A^T \bar{\lambda} − c) = 0 \\ \bar{\lambda}^T (A\bar{x} − b) = 0 \end{cases}$

利用互补松弛定理，当知道一个问题的最优解时，可求出其对偶问题的最优解。具体地，第一个等式可以确定 $A^T\bar{\lambda}-c$ 的哪些分量是 $0$，这是一个方程组。如果方程组满秩则直接解出来，否则接出来的再带进不等式约束检验即可。

网络优化与动态规划

Dijkstra 算法、Ford-Fulkerson 算法、最大流最小割定理、背包问题。

网络流

最小成本流：

$\min \sum_{e\in E}w(e)f(e) \\ \text{s.t. } \sum_{e\in \text{Out}(v)}f(e)-\sum_{e\in \text{In}(v)}f(e)=0,\forall v\in V-\{s,t\} \\ \sum_{e\in \text{Out}(s)}f(e)-\sum_{e\in \text{In}(s)}f(e)=f^* \\ 0\le f(e)\le c(e),\forall e\in E$

最小成本流问题具有很好的模型化能力：

Thm（最短路、最大流 $\in$ 最小成本流）：最短路问题和最大流问题是最小成本流的特殊情况。

Proof：（1）最短路：设图为 $G=(V,E)$ 且有边权函数 $f:E\to \mathbb R$，要求 $s$ 到点集 $S\subset V$ 中点距离之和。

则建一流网络图 $G'$，其点集为 $V\cup\{t\}$（$t$ 为新建的汇点），边集为 $E\cup\{(v,t)\mid v\in S\}$，且 $c(v,t)=1,w(v,t)=0$，而 $E$ 中的边 $e$ 有 $c(e)=+\infty,w(e)=f(e)$。

这样从 $s$ 到 $t$ 的限定流量为 $|S|$ 的最小成本流即为 $s$ 到点集 $S$ 中点距离之和。

（2）最大流：设原流网络图为 $G=(V,E)$ 且有容量函数 $f:E\to \mathbb R^+$，而源汇点分别为 $S,T$。

则建一新流网络图 $G'$，其点集为 $V\cup\{S'\}$（$S'$ 为新建的超级汇点），边集为 $E\cup\{(S',S),(S',T)\}$，且 $c(S',S)=+\infty,w(S',S)=0,c(S',T)=+\infty,w(S',T)=1$，而 $E$ 中的边 $e$ 有 $c(e)=f(e),w(e)=0$。

设 $G'$ 中从 $S'$ 到 $T$ 限定流量为 $\sum_{e\in E}f(e)$ 的最小成本流为 $f'$，则原图 $G$ 中从 $S$ 到 $T$ 的最大流 $f^*$ 就等于 $\sum_{e\in E}f(e)-f'$。$\Box$

设备更新问题

$r(t), c(t),s(t)$ 分别表示 $t$ 年龄机器的年营业收入，年运营成本及残余价值。状态转移方程为：

$f_{i}(t)=\begin{cases} r(t) − c(t) + f_{i+1}(t + 1),\ t ≤ 6 & \text{Keeping} \\ r(0) − c(0) + s(t) − I + f_{i+1}(1) & \text{Replacing} \end{cases} \\ f_{n+1}(t)=s(t)$

非线性规划的最优性条件

非线性规划的数学模型如下：

$\min f (x) \\ \text{s.t. } x \in S \subset \mathbb R^n$

在此，目标函数 $f$ 是定义在 $\mathbb R^n$ 上的实值函数，$S$ 是决策变量 $x$ 的可取值之集合，称为问题的可行域（feasible region）。通常可行域 $S$ 可由一组方程来描述，即：

$S = \{x \in \mathbb R^n\mid g_i(x) ≥ 0,i\in \mathcal I; h_j(x) = 0, j\in\mathcal E\}$

其中 $\mathcal I,\mathcal E$ 分别是不等式约束与等式约束的指标集。

Defn（可行解、全局最优解、局部最优解）：满足约束条件 $x \in S$ 的 $x$ 称为问题的可行解（feasible solution），如果可行解 $x^∗ ∈ S$ 进一步满足

$f (x^∗) \le f (x), \forall x \in S$

则称 $x^∗$ 为该问题的全局最优解（global optimal solution）。

另外，在包含可行解 $x^∗ \in S$ 的适当邻域 $U(x^∗)$ 里，成立

$f (x^*) \le f (x), \forall x \in S\cap U(x^*)$

此时称 $x^∗$ 为该问题的局部最优解（local optimal solution）。

优化领域中最重要的就是最优性条件了。最优化条件就是问题的最优解所满足的必要或者充分条件。最优性条件将为各种求解算法的设计、分析提供必不可少的理论基础。

无约束问题的最优性条件

若 $S=\mathbb R^n$，则称其为无约束问题。无约束问题的最优性条件完全是微分的内容：

• 一阶必要条件：设目标函数 $f (x)$ 在点 $\bar{x}$ 处可微，若 $\bar{x}$ 是局部极小点，则 $\nabla f (\bar{x}) = 0$。
• 二阶必要条件：设目标函数 $f (x)$ 在点 $\bar{x}$ 处二次可微，若 $\bar{x}$ 是局部极小点，则 $\nabla f(\bar{x})=0$，并且 Hesse 矩阵 $\nabla^2 f(\bar{x})\ge 0$。
• 二阶充分条件：设目标函数 $f (x)$ 在点 $\bar{x}$ 处二次可微，若 $\nabla f(\bar{x})=0$ 且 $\nabla^2 f(\bar{x})>0$，则 $\bar{x}$ 是局部极小点。
• 充要条件：设 $f (x)$ 是定义在 $\mathbb R^n$ 上的可微凸函数，则 $\bar{x}$ 是整体极小点（全局最优解）的充要条件是 $\nabla f(\bar{x})=0$。

约束问题的最优性条件

我们关心一个点往哪里走不会跑出可行域：

Defn（可行方向）：设 $\bar{x} \in S$，$d$ 是非零向量。若存在 $δ > 0$ 使得：

$\bar{x} + λd\in S, \forall λ \in (0, δ)$

则称 $d$ 为在 $\bar{x}$ 处（关于 $S$）的可行方向，可行方向集定义为 $F(\bar{x},S)$。

我们还关心一个点往哪里走更优秀：

Defn（下降方向）：设 $f (x)$ 是 $\mathbb R^n$ 上的实函数，$\bar{x} \in \mathbb R^n$，$d$ 是非零向量。若存在 $δ > 0$ 使得：

$f (\bar{x} + λd) < f (\bar{x}), \forall λ \in (0, δ)$

则称 $d$ 为函数 $f (x)$ 在 $\bar{x}$ 处的下降方向。

我们可以利用梯度给出下降方向集的一个比较好求的子集：

Defn（利用梯度给出的下降方向集的子集）：如果 $f (x)$ 是可微函数，且 $\nabla f (\bar{x})^T d < 0$。显然，此处的 $d$ 为 $f (x)$ 在 $\bar{x}$ 处的下降方向。记这样的方向集合为

$D(\bar{x}, f ) := \{d \mid \nabla f (\bar{x})^T d < 0\}$

有时会省略 $\bar{x}$ 直接简记为 $D_f$。

根据这两个定义可以显然地给出一个局部最优点的一个必要条件：

Thm（局部最优则无可行下降）：对于问题 $\min\{f (x) \mid x \in S\}$，设 $\bar{x} \in S$，$f (x)$ 在 $\bar{x}$ 处可微。如果 $\bar{x}$ 是问题的局部最优解，则可行方向集中无下降方向，那么必有：

$F(\bar{x}, S) \cap D(\bar{x}, f ) = \varnothing$

值得注意的是这里考虑的只是下降方向集的子集。

但是有一个尴尬的地方在于，如果等式约束非线性，比如 $x^2+y^2=1$ 这样一个圆，则按照定义它在任何一点都没有可行方向，它只能“弯着走”。于是我们再给出一种基于极限定义的“可行方向”。

Defn（切锥）：对于 $x\in S$，定义 $x$ 的切锥为：

$T(x \mid S) := \{d \mid \exists\tau_i ↘ 0, \{x_i\} \subset S, x_i → x,\text{s.t. }\dfrac{x_i − x}{τ_i}→ d\}$

用这样极限的方式定义出来的「可行方向」是否包含所有真的可行方向呢？下面这个定理给出了解答：

Thm（切锥包含可行方向集）：对于问题 $\min\{f (x) \mid x ∈ S\}$，设 $\bar{x} ∈ S$，$f (x)$ 在 $\bar{x}$ 处可微。如果 $\bar{x}$ 是问题的局部最优解，则

$\nabla f (\bar{x})^Td ≥ 0, \forall d ∈ T(x \mid S)$

Proof：若 $d\in T(\bar{x}\mid S)$，则存在 $\{x_k\}\subset S,\tau_k \searrow 0$，使得：$\dfrac{x_k-\bar{x}}{\tau_k}\to d$。

设 $d_k=\dfrac{x_k-\bar{x}}{\tau_k}$，则：

$\nabla f(\bar{x})^T d=\lim_{k\to \infty}\nabla f(\bar{x})^T d_k =\lim_{k\to\infty} \dfrac{f(\bar{x})+\tau_k \nabla f(\bar{x})^Td_k+o(\tau_k)-f(\bar{x})}{\tau_k} =\lim_{k\to\infty} \dfrac{f(x_k)-f(\bar{x})}{\tau_k}\ge 0$

而对于不等式约束 $g_i(x)$ 与等式约束 $h_j(x)$，用同样的方法可以证明：$\nabla g_i(\bar{x})^Td\ge 0,\nabla h_j(x)^T d=0$。$\Box$

切锥使用极限定义了「可行方向」，但是有的时候极限还是不好求。利用梯度这一信息、以及切锥的性质，我们给出可行方向集的比较好求的子集与超集：

Defn（利用梯度给出的可行方向集的子集与超集）：如果 $g_i (x)\ (i\in \mathcal I)$ 与 $h_j\ (j\in \mathcal E)$ 在 $\bar{x}$ 处可微，则定义不等式约束可行方向集的子集：

$F'(\bar{x},g) := \{d\mid \nabla g_i(\bar{x})^T d > 0, i ∈ \mathcal I_e(\bar{x})\}$

如果把条件 $\nabla g_i(\bar{x})^T d > 0$ 放宽到 $\nabla g_i(\bar{x})^T d \ge 0$，则有不等式约束的线性可行方向集：

$L(\bar{x},g) := \{d\mid \nabla g_i(\bar{x})^T d \ge 0, i ∈ \mathcal I_e(\bar{x})\}$

其中 $\mathcal I_e(\bar{x})$ 为 $\bar{x}$ 处的积极不等式约束指标集。

同理有等式约束的线性可行方向集：

$L(\bar{x},h) := \{d\mid \nabla h_i(\bar{x})^T d = 0, i ∈ \mathcal E\}$

有时会省略 $\bar{x}$ 直接简记为 $F'_g,L_g,L_h$。

所以我们得到这样一个包含关系图：

$\color{red}{F'_g ⊂ F(\bar{x}, g) ⊂ T(\bar{x} \mid g) ⊂ L_g} \\ \color{red}{F(\bar{x}, h) ⊂ T(\bar{x} \mid h) ⊂ L_h}$

正则性条件

线性可行方向与约束的表示形式有关。

Example：令 $S = \{x ∈ \mathbb R^2\mid x_1^2 + x_2^2 ≤ 1,(x_1 − 2)^2 + x_2^2 ≤ 1\}$。则 $S = \{(1, 0)^T \}$。我们有 $T(S) = \{(0, 0)^T \}$，然而 $L_S = \{(0,t) \mid t ∈ R\}$。但是，如果我们直接考虑约束的一种直接表示：$S = \{(1, 0)^T \}$，那么 $T(S) = L_S$。

我们希望切锥和线性可行方向集是相等的，但是有的时候这无法做到。在前一种情况中，切锥就不能很好的刻画可行方向。这是因为前一种情况不满足正则性条件，里面的约束不够“规范”从而导致了一些奇怪的问题。下面给出两种正则性条件：

Defn（线性独立约束规范条件，short for LICQ）：若 $\bar{x}$ 满足：$f$ 和 $g_i\ (i ∈ \mathcal I_e)$ 在点 $\bar{x}$ 可微，$g_i\ (i ∈ \mathcal I \backslash \mathcal I_e)$ 在点 $\bar{x}$ 连续，$h_i\ (i ∈ \mathcal E)$ 在点 $\bar{x}$ 连续可微，向量集 $\{\nabla g_i(\bar{x}) \mid i ∈ \mathcal I_e\}\cup\{\nabla h_i(\bar{x}) \mid i ∈ \mathcal E\}$ 线性无关，则称该点处满足 LICQ 约束规范条件。

Defn（Mangasarian-Fromovitz 约束规范条件，short for MFCQ）：若 $\bar{x}$ 满足：$f$ 和 $g_i\ (i ∈ \mathcal I_e)$ 在点 $\bar{x}$ 可微，$g_i\ (i ∈ \mathcal I \backslash \mathcal I_e)$ 在点 $\bar{x}$ 连续， $h_j\ (j\in \mathcal E)$ 在点 $\bar{x}$ 连续可微，且 $\{\nabla h_j(\bar{x})\mid j\in \mathcal E\}$ 线性无关，并且 $F_g \cap L_h$ 非空，则称该点处满足 MFCQ 约束规范条件。

可以看出 LICQ 是严格比 MFCQ 强的。

当正则性条件被满足，则切锥和线性可行方向集就是相等的：

Lemma（规范性引理）：若在可行点 $\bar{x} ∈ S$ 处满足 LICQ（MFCQ），则

$L_h ∩ L_g = T(\bar{x} \mid S)$

Proof（只证明 LICQ 的情况）：显然有 $T(\bar{x} \mid S)\subset L_h\cap L_g$，接下来我们证明另一个方向。

$\forall d\in L_h\cap L_g$，我们记：

$A_{\bar{x}}=\begin{pmatrix} \nabla g_i(\bar{x})^T\ (i\in \mathcal I_e(\bar{x})) \\ \nabla h_j(\bar{x})^T\ (j\in \mathcal E) \end{pmatrix}\in \mathbb R^{m\times n}$

即是所有积极约束的梯度组成的矩阵。因为 $\bar{x}$ 处满足 LICQ 条件，所以 $A_{\bar{x}}$ 是行满秩的。我们记 $B$ 为 $A_{\bar{x}}$ 的核空间的基矩阵，即：$B\in \mathbb R^{n\times(n-m)}$ 是列满秩的，且 $A_{\bar{x}}B=O$。

定义一个方程组 $R(z,t)\ (z\in \mathbb R^n,t\in \mathbb R)$ 为：

$R(z,t)=\begin{pmatrix} \begin{pmatrix} g_i(z)\ (i\in \mathcal I_e(\bar{x})) \\ h_j(z)\ (j\in \mathcal E) \end{pmatrix}-tA_{\bar{x}}d \\ B^T(z-\bar{x}-td) \end{pmatrix} =\begin{pmatrix} 0 \\ 0 \end{pmatrix}$

$R(z,t)$ 在 $z=\bar{x},t=0$ 处对 $z$ 的雅可比矩阵为：

$\nabla_z R(z,t)=\begin{pmatrix} A_{\bar{x}} \\ B^T \end{pmatrix}\in \mathbb R^{n\times n}$

由 $A_{\bar{x}},B^T$ 行满秩且 $A_{\bar{x}}B=O$ 知 $\nabla_z R(z,t)$ 是可逆的。故由隐函数存在定理知：存在一个函数 $\varphi(t)\in \mathbb R^n$ 和一个正数 $\delta$，当 $|t|<\delta$ 时，有 $R(\varphi(t),t)=0$。

我们在 $(0,\delta)$ 范围内选出 $t_k↘0$，并令 $z_k=\varphi(t_k)$。那么由 $d\in L_g\cap L_h$ 与 $R(z_k,t_k)=0$ 得：

$g_i(z_k)=t_k\nabla g_i(z_k)^T d\ge 0,\ i\in \mathcal I_e(\bar{x}) \\ h_j(z_k)=t_k\nabla h_j(z_k)^T d=0,\ i\in \mathcal E$

于是乎 $z_k\in S$。

由微分展开可得：

$0=R(z_k,t_k)=\begin{pmatrix} \begin{pmatrix} g_i(z_k)\ (i\in \mathcal I_e(\bar{x})) \\ h_j(z_k)\ (j\in \mathcal E) \end{pmatrix}-t_kA_{\bar{x}}d \\ B^T(z-\bar{x}-t_kd) \end{pmatrix} \\ =\begin{pmatrix} \begin{pmatrix} g_i(\bar{x})+\nabla g_i(\bar{x})^T(z_k-\bar{x})+o(\|z_k-\bar{x}\|)\ (i\in \mathcal I_e(\bar{x})) \\ h_j(\bar{x})+\nabla h_j(\bar{x})^T(z_k-\bar{x})+o(\|z_k-\bar{x}\|)\ (j\in \mathcal E) \end{pmatrix}-t_kA_{\bar{x}}d \\ B^T(z_k-\bar{x}-t_kd) \end{pmatrix} \\ =\begin{pmatrix} A_{\bar{x}}(z_k-\bar{x})+o(\|z_k-\bar{x}\|)-t_kA_{\bar{x}}d \\ B^T(z_k-\bar{x}-t_kd) \end{pmatrix} \\ =\begin{pmatrix} A_{\bar{x}} \\ B^T \end{pmatrix} (z_k-\bar{x}-t_kd)+o(\|z_k-\bar{x}\|)$

因为 $\begin{pmatrix} A_{\bar{x}} \\ B^T \end{pmatrix}$ 可逆，所以有：

$\dfrac{z_k-\bar{x}}{t_k}=d+o\left(\dfrac{z_k-\bar{x}}{t_k}\right)\Longrightarrow \lim_{k\to\infty}\dfrac{z_k-\bar{x}}{t_k}=d$

所以 $d\in T(\bar{x}\mid S)$，所以 $L_h\cap L_g\subset T(\bar{x}\mid S)$。$\Box$

那么我们可以得到这样一个引理：

Lemma（LICQ 下的局部最优无可行下降）：设 $\bar{x}$ 为优化问题的局部最优解，且在 $\bar{x}$ 点满足 LICQ（MFCQ），则：

$D_f\cap L_g\cap L_h=\varnothing$

Proof：因为 $L_g\cap L_h=T(\bar{x}\mid S)$，而 $\forall d\in T(\bar{x}\mid S),\nabla f(\bar{x})^Td<0$。

但是 $\forall d\in D_f,\nabla f(\bar{x})^Td <0$，所以 $D_f\cap L_g\cap L_h=D_f\cap T(\bar{x}\mid S)=\varnothing$。$\Box$

KKT 条件

Thm（Karush-Kuhn-Tucker 必要条件，short for KKT）：设 $\bar{x}$ 为约束问题的可行点，定义 Lagrange 函数

$L(x, λ, \mu) = f(x) −\sum_{i\in \mathcal I}\lambda_i g_i(x)-\sum_{j\in \mathcal E}\mu_j h_j(x)$

若 $\bar{x}$ 为问题局部最优解，且在这一点满足 LICQ（MFCQ），则存在乘子向量 $\bar{λ} ≥ 0, \bar{\mu}$ 使得 $\nabla_x L(\bar{x}, \bar{λ}, \bar{\mu}) = 0$。

此时，一阶必要条件可以表达为

$(\text{KKT})\begin{cases} ∇_xL(x, λ, \mu) = 0 & （稳定条件）\\ g_i(x) \ge 0\ (i ∈ \mathcal I) & （原问题可行）\\ h_j(x) = 0\ (j ∈ \mathcal E) & （原问题可行）\\ λ_ig_i(x) = 0\ (i \in \mathcal I) & （松弛互补）\\ λ_i ≥ 0, i \in \mathcal I & （对偶可行） \end{cases}$

为证明 KKT 条件，我们先给出一个引理作为铺垫：

Lemma（Farkas 引理）：给定 $B\in \mathbb R^{n\times m},C\in \mathbb R^{n\times l}$，设 $K=\{By+Cw\mid y\ge 0\}$，则对任意的 $v\in \mathbb R^n$，下面二者有且只有一个成立：

• $v\in K$；
• $\exists d\in \mathbb R^n,\text{s.t. }v^Td<0,B^Td\ge 0,C^Td=0$。

Proof：鸽子。$\Box$

接下来我们就可以来证明 KKT 条件了：

Proof of KKT：因为在 $\bar{x}$ 处满足 LICQ，所以 $D_f\cap L_g\cap L_h=\varnothing$，即：关于 $d\in \mathbb R^n$ 的不等式组：

$\begin{cases} \nabla f(\bar{x})^T d<0 \\ \nabla g_i(\bar{x})^T d\ge 0\ (i\in \mathcal I_e(\bar{x})) \\ \nabla h_j(\bar{x})^T d=0\ (j\in \mathcal E) \end{cases}$

无解。

那么由 Farkas 引理，存在 $\lambda\ge 0,\mu$，使得：

$\nabla f(\bar{x})=\sum_{i\in \mathcal I_e(\bar{x})} \lambda_i\nabla g_i(\bar{x})+\sum_{j\in \mathcal E} \mu_j\nabla h_j(\bar{x})$

这样便是 KKT 条件的第一条。

对于任何的 $i\in \mathcal I\backslash\mathcal I_e(\bar{x})$，令 $\lambda_i=0$。那么就可以满足 KKT 条件的第四、五条。而原问题可行是自动满足的，所以 KKT 条件成立。$\Box$

当没有正则性条件的时候，KKT 条件不一定成立，但是只要加上一点东西，变成 Fritz-John 条件，那么最优性条件仍然可以满足。

Thm（Fritz-John 条件）：设 $\bar{x}\in S$ 为可行点，$f$ 和 $g_i\ (i ∈ \mathcal I_e(\bar{x}))$ 在点 $\bar{x}$ 可微，$g_i\ (i ∈ \mathcal I\backslash \mathcal I_e(\bar{x}))$ 在点 $\bar{x}$ 连续，$h_j$ 在点 $\bar{x}$ 连续可微。如果 $\bar{x}$ 是局部最优解，则存在不全为零的数 $λ_0, λ_i\ (i ∈ \mathcal I_e(\bar{x}))$ 和 $\mu_j\ (j\in \mathcal E)$ 使得

$\lambda_0 \nabla f(\bar{x})-\sum_{i\in \mathcal I_e(\bar{x})}\lambda_i \nabla g_i(\bar{x})-\sum_{j\in \mathcal E}\mu_j\nabla h_j(\bar{x})=0$

其中 $\lambda_0\ge 0,\lambda_i \ge 0\ (i\in \mathcal I_e(\bar{x}))$。

Proof：证明需要默认 MFCQ 也可以导出规范性引理，并且要用到凸集分离定理。除了这两个不同之外其他地方与 KKT 条件的证明没什么差别，略证。$\Box$

这里给出凸集分离定理的具体描述：

Thm（凸集分离定理）：假设 $C_1$ 和 $C_2$ 是两个不相交的非空凸集，那么存在一个非零向量 $w$ 和一个实数 $b$ 使得对于所有 $x_1 ∈ \text{CL}(C_1)$ 和 $x_2 ∈ \text{CL}(C_2)$ 有：

$w^Tx_1 ≥ b,w^Tx_2 ≤ b$

这里 $\text{CL}(C_1)$ 表示 $C_1$ 的闭包。这意味着超平面 $\{x \mid w^T x = b\}$ 将 $\text{CL}(C_1)$ 和 $\text{CL}(C_2)$ 分开。

Slater 条件

KKT 条件是必要条件，那么什么时候这一条件也是充分的呢？这就引出了 Slater 条件。

Defn（Slater 条件）：目标函数 $f(x)$ 为凸函数，等式约束函数 $h_j(x) (j \in \mathcal E)$ 是仿射函数（次数最高为一的多项式函数），不等式约束函数 $g_i(x)\ (i ∈ \mathcal I)$ 为凸函数，并且存在一个可行点 $x^∗$ 满足 $g_i(x^∗) > 0\ (i ∈ \mathcal I)$。

至于为什么当 Slater 条件成立的时候 KKT 条件是充分的，证明较为困难，略去。

可以发现线性规划就满足 Slater 条件。考虑标准形式线性规划的 KKT 条件：

$\begin{cases} c-A^T \mu -\lambda=0 \\ Ax-b=0 \\ x\ge 0 \\ \lambda^Tx= 0 \\ λ≥ 0 \end{cases}$

将二式两边左乘 $\lambda^T$，一式两边左乘 $x^T$ 并带入四式，便可得到：

$\begin{cases} x^T (A^T \mu − c) = 0 \\ \mu^T (Ax − b) = 0 \end{cases}$

这即是线性规划的互补松弛定理。

二阶最优性条件

Defn（临界锥）：设 $(x^∗, λ^∗, \mu^∗)$ 是满足 KKT 条件的 KKT 对, 定义临界锥为：

$C(x^∗, λ^∗, \mu^∗) = \{d ∈ T(x^∗\mid S)\mid∇g_i(x^∗)^Td = 0, ∀i ∈ \mathcal I(x^∗)\text{ and }λ^∗_i > 0\}$

临界锥是切锥的子集，也是线性化可行方向集 $L_g ∩ L_h$ 的子集。同时，沿着临界锥中的方向进行优化, 所有等式约束和 $λ^∗_i > 0$ 对应的不等式约束（此时这些不等式均取等）都会尽量保持不变。临界锥定义了依据一阶导数不能判断是否为下降或上升方向的线性化可行方向，必须使用高阶导数信息加以判断。

Thm（二阶最优性条件）：

必要性：假设 $x^∗$ 是问题的一个局部最优解，并且 $T(x^∗ \mid S) = L_g ∩ L_h$ 成立。令 $(x^∗, λ^∗, \mu^∗)$ 满足 KKT 条件，那么：

$d^T ∇^2_{xx}L(x^∗, λ^∗, \mu^∗)d ≥ 0,\ ∀d ∈ C(x^∗, λ^∗, \mu^∗)$

充分性：假设在可行点 $x^∗$ 处，存在一个拉格朗日乘子 $λ^∗,\mu^*$，使得 $(x^∗, λ^∗,\mu^*)$ 满足 KKT 条件。

如果：

$d^T ∇^2_{xx}L(x^∗, λ^∗, \mu^∗)d > 0,\ ∀d ∈ C(x^∗, λ^∗, \mu^*), d \ne 0$

那么 $x^∗$ 为问题的一个严格局部极小解。

Other

后面的摆了，不想敲 LaTeX 了，就放个复习时候自己整理的一些个东西上来吧。

参考文献

[1] 运筹学讲义. 陈士祥, 杨周旺.

[2] Numerical Optimization (2nd edit). Thomas V. Mikosch, Sidney I. Resnick, Stephen M. Robinson.

[3] https://zhuanlan.zhihu.com/p/163527928

[4] Introduction to Algorithm (3rd edition). Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.

[5] New Finite Pivoting Rules for the Simplex Method. Robert G. Bland, 1977.