最优化方法

约定向量 x 大于常数等价于 x 的每个分量大于某个常数

基础知识

多面集的表示定理

定理：设 $S=\lbrace x|Ax\boldsymbol{=}b,x\boldsymbol{\geqslant}0\rbrace$ 为非空多面集，则有

(1) 极点集非空，且存在有限个极点$x^{(1)},\cdots,x^{(k)}.$

(2) 极方向集合为空集的充要条件是S有界；若S无界，则存在有限个极方向$d^{(1)},d^{(2)},\cdots,d^{(l)}.$

$x\in S$的充要条件是

$$ x=\sum_{j=1}^k\lambda_jx^{(j)}+\sum_{j=1}^l\mu_jd^{(j)} $$

其中$\lambda_j\geq0,j=1,2,\cdots,k,\sum_{j=1}^k\lambda_j=1$

$$ \mu_j\geq0,j=1,2,\cdots,l. $$

线性规划

LP 的标准形式

极小化型
约束方程为等式
所有的决策变量为非负值
约束方程的右端项系数为非负值

$$ \min z = cx, \\ s.t.\ Ax = b,\\ x \ge 0 $$

非标准型 LP 模型可以转化为标准型 LP 模型

取个负号
约束方程为不等式：加一个松弛变量变为等式。
变量无非负约束：令 $x_j = x_j^\prime - x_j^{\prime\prime}$
决策变量有上下界：平移到0处。

LP 问题的基本性质

可行解

线性规划的可行域是凸集。

最优极点

考虑标准形式：

$$ \begin{cases}\min&cx\\s.t.&Ax=b\\&x\geq0&\end{cases} $$

把多面集表示定理代入其中：

$$ \begin{cases}\min&\sum_{j=1}^k\lambda_jcx^{(j)}+\sum_{j=1}^l\mu_jcd^{(j)}=f\left(x\right)\\s.t.&\sum_{j=1}^k\lambda_j=1\\&\lambda_j\geq0,j=1,\cdots,k\\&\mu_j\geq0,j=1,\cdots,l.&\end{cases} $$

若存在 $j$ 使得 $cd^{(j)} \lt 0$，此时可以取 $\mu_j\to-\infty$，则 $f(x)\to-\infty$。

若所有的 d 都满足 $cd^{(j)} \ge 0$，取 $\mu_j = 0, j = 1, 2, \dots, l$，得到

$$ \begin{cases}\min&\sum_{j=1}^k\lambda_jcx^{(j)}=f\left(x\right)\\s.t.&\sum_{j=1}^k\lambda_j=1\\&\lambda_j\geq0,j=1,\cdots,k\end{cases} $$

此时只需要找到 $p = \arg\min_{j}cx^{(j)}$，取 $\lambda_p = 1$, $\lambda_j = 0 (j\ne p)$ 即可得到最大值。

定理2. 设线性规划(L)的可行域非空，则

（1）(L)存在最优解的充要条件是对任意的$j$, $cd^{(j)}≥0$, 其中$d^{(j)}$为可行域的极方向。

（2）若(L)存在最优解，则目标函数的最优值可在某个极点达到。

基和基本解

设标准形式中 $\text{rank}(A_{m\times n}) = m = (P_1\ P_2\ \dots\ P_n)$，$Ax = P_1x_1+\dots+P_nx_n$，则可以从 $A$ 的列中取出 $m$ 个 $P_j$组合成一个可逆矩阵 $B$ 称为基，与取出来的 $P_j$ 对应的 $x_j$ 称为基向量。

设 $A = [B\ N]$，$Ax = Bx_B + Nx_N = b$，解得

$$ x_B = B^{-1}b - B^{-1}Nx_N $$

取 $x_N = 0$，此时 $x = \begin{bmatrix}B^{-1}b\\0\end{bmatrix}$ 为 (LP) 的基本解。

若 $B^{-1}b \ge 0$，则 $x$ 称为基本可行解，$B$ 为可行基矩阵，$x_{B_1}, x_{B_2}, \dots, x_{B_m}$ 为一组可行基。

若 $B^{-1}b \gt 0$，则称基本可行解是非退化的，否则是退化的。

基本可行解与极点之间的关系

引理1：对于可行解 $\bar x$， $\bar x$ 是基本可行解的充要条件是 $\bar x$ 的非零分量对应到 $A$ 中的列向量线性无关。

定理2：设 $S$ 是 $(L)$ 的可行域，$\bar x \in S$，则 $\bar x$ 是 $S$ 极点的充要条件为 $\bar x$ 是 $(L)$ 的基本可行解。

思考：本质上是因为“极点”的唯一性，正好对应了基矩阵可逆，求解出来的基本可行解也是唯一的。
从几何意义思考标准形式：1. $Ax=b$ 本质上代表了一个 k 维的子空间，k 是矩阵的秩，如果 k = 1 就是直线，k = 2 就是平面；2. $x\ge0$ 是一组边界，它会截取子空间的一部分，以 k = 2，n = 3 为例，这意味着我们用一个平面去与三维空间的第一卦限相交的部分作为可行域，不考虑退化的情况，通常它是一个 n 条边界的图形，正好对应 n 个变量分别等于 0 的情况。3. $cx$ 不用解释了，这就是一个 n - 1 维的空间。

定理3：设 $S = \lbrace x| Ax=b, x\ge 0\rbrace $ 的方向 $d$ 有 $k$ 个非零分量，则 $d$ 是 $S$ 的极方向等价于 $d$ 的非零分量对应到 A 的列向量的秩为 k - 1。

基本可行解的存在问题

定理1. 如果(LP)有可行解,则一定存在基本可行解.

定理2. 如果(LP)有最优解，则存在一个基本可行解是最优解。

单纯形法

设 $A = (B\ N)$，$x=(x_B\ x_N)^T$，则 $Bx_B + Nx_N = b$，取 $x_N = 0$ 得到 $x_B = B^{-1}b$，$f(x) = c_BB^{-1}b$。则 $x = (B^{-1}b\quad 0)^T$ 为基本可行解。

这里有个问题，$B^{-1}b \ge 0$ 一定成立吗？如果不成立那么这就不是可行解。

但是基本可行解未必是最优解，我们考虑 $x_N\ne0$ 的情况。一般地由 $Bx_B + Nx_N = b$ 得到 $x_B = B^{-1}b - B^{-1}Nx_N$，$f(x) = c_Bx_B + c_Nx_N = c_BB^{-1}b - (c_BB^{-1}N - c_N)x_N$。

如果 $c_BB^{-1}N - c_N \le 0$，则 $f(x) \ge c_BB^{-1}b$，当且仅当 $x_N = 0$ 的时候取等。此时 $x = (B^{-1}b\quad 0)^T$ 就是最优解。$c_BB^{-1}N - c_N = (z_i - c_j)_{m+1\le i \le n}$ 为判别数。

假如判别数里面有正数，假设其中最大的正数为 $z_r-c_r$，这就说明我们可以通过增大 $x_r$ 的方式来减小 $f(x)$ 的值。而 $x\ge 0$ 又约束了我的 $x_r$ 不能无限增加，因为 $x_B = B^{-1}b - B^{-1}Nx_N = B^{-1}b - \sum_{j=m+1}^{n}B^{-1}P_jx_j \ge 0$，因此 $B^{-1}P_rx_r \le B^{-1}(b-\sum_{j\ne r, m+1\le j \le n}B^{-1}P_jx_j) \le B^{-1}b$。设 $y_k = B^{-1}P_k$，$\bar b = B^{-1}b$，则此时有 $y_kx_r \le \bar b, \forall 1\le k \le m$。因此 $\max x_r = \min \lbrace \frac{\bar b_k}{y_k}|y_k \gt 0 \rbrace$。

假如所有的 $y_k \le 0$，则 $x_r$ 无上界，从而 $f(x)$ 也没有最大值。

假如存在 $y_k \gt 0$，则我们假设 $x_r = \frac{\bar b_k}{y_k}$ 时取得最大值。此时 $x_k = \bar b_k - y_kx_r = 0$，也就是说原来的基变量 $x_k$ 变成了 0，原来的非基变量 $x_r$ 变成了大于 0 的数。我们就需要把新的 $x_r$ 加入基变量中，$x_k$ 踢出基变量，从而 $f(x)$ 的值变得更小了。

如果某非基变量的检验数为零，则线性规划问题存在多个最优解。

两阶段法

有时候第一个基本可行解不太好求，特别是表格里没有单位矩阵的时候。我们可以用两阶段法简化计算。

第一阶段：引入人工变量 $x_a$，这时候就有单位矩阵了，用单纯形法解出下列问题的最优解：

$$ \begin{cases}&\min e^Tx_a, e=(1\ 1\ \dots\ 1)^T\\&Ax+x_a=b\\&x,(x_a)_{m\times1}\geq0&\end{cases} $$

最优解 $(\bar x\ \bar x_a)^T$。

如果 $\bar x_a \ne 0$，则原方程没有可行解。因为假如原方程有可行解 $x_0$，则$Ax_0 = b$，从而 $x_a = 0$ 成立，为最优解，矛盾。

如果 $\bar x_a = 0$，有两种情况：

（1）如果 $\bar x_a$ 都是非基变量，则 $\bar x$ 就是原来的基本可行解；

（2）如果 $\bar x_a$ 中存在基变量，那么就需要换基，把 $\bar x_a$ 换走。

此时，$\bar x_a$ 都等于 0，

大 M 法

和两阶段法思想类似，但是把两个函数合成一个了。

$$ \begin{cases}\min&cx+Me^Tx_a,e=\left(11\cdots1\right)_{m\times1}^T,M>0\\s.t.&Ax+x_a=b\\&x,x_a\geq0&\end{cases} $$

用单纯形法求解上述问题最优解 $(\bar x^T\ \bar x_a^T)$：

（1）如果 $\bar x_a = 0$，则 $\bar x$ 为原问题的最优解；

（2）如果 $\bar x_a \ne 0$，则原问题无最优解。

函数无界的充要条件：$Ad=0$ 且 $cd < 0$。

（3）不存在最优解（函数无界）且 $\bar x_a = 0$，说明原问题没有最优解。

（4）不存在最优解（函数无界）且 $\bar x_a \ne 0$，说明原问题没有可行解。

这个方法怪就怪在 $M $ 是任意大的正数，并不是一个固定值。

单纯形法容易卡在循环之中，达不到最优解。

主要原因是基变量中有取值为 0 的项，即 $\bar b_k = 0$，按照单纯形法肯定会把 $x_k$ 出基，然后换进来另一个 $x_r$，但是你换进来的 $x_r$ 还是等于 0（这样取值显然为基本可行解），导致极点实际上始终不变，目标函数也一直不变。

解决退化的方法有:“摄动法”、“字典序法”、Bland规则等

对偶

对偶问题的定义

第一类对称形式

(L)

$$ \min cx\\ Ax \ge b\\ x \ge 0 $$

第二类对称形式

(D)

$$ \max wb\\ wA \le c\\ w\ge 0 $$

对偶的对偶是原问题。

对于 (D)，可以写成

$$ \min (-b^T)w^T\\ (-A^T)w^T \ge -c^T\\ w^T\ge 0 $$

这个问题的对偶问题是

$$ \max x^T(-c^T)\\ x^T(-A^T)^T \le -b^T\\ x^T\ge 0 $$

也就是

$$ \min cx\\ Ax \ge b\\ x \ge 0 $$

对称形式的对偶问题规划：

（1）min 变成 max

（2）价值系数和右端向量互换

（3）系数矩阵转置

（4）大于等于变成小于等于

原问题的约束方程的个数等于对偶问题中变量的个数，反过来原问题的变量个数就是对偶问题约束方程的个数。

非对称形式的对偶：

$$ \min cx\\ Ax = b\\ x \ge 0 $$

它的对偶形式为

$$ \max wb\\ wA \le c\\ w 无限制 $$

总结：

原问题	对偶问题
$\min$	$\max$
价值系数	右端向量
右端向量	价值系数
系数矩阵	系数矩阵转置
变量 $\le 0$	约束 $\ge$
变量 $\ge 0$	约束 $\le$
变量无限制	约束 $=$
约束 $\ge $	变量 $\ge 0$
约束 $\le $	变量 $\le 0$
约束 $=$	变量无限制

对偶问题的基本性质

弱对偶定理：$x^{(0)}, w^{(0)}$ 分别是 (L), (D) 的可行解，则 $cx^{(0)} \ge w^{(0)}b$。

对于对称形式的情况：

$$ cx^{(0)} \ge w^{(0)}Ax^{(0)} \ge w^{(0)}b $$

推论1：若 LP/DLP 有无界解，则其对偶问题无可行解；若 LP/DLP 无可行解，则其对偶问题或者无可行解，或者目标函数值趋于无穷。

推论2：极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界。

推论3：极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的上界。

定理2：最优性准则：若 $x^{(0)}, w^{(0)}$ 分别是 (L), (D) 的可行解，并且 $cx^{(0)} = w^{(0)}b$，则 $x^{(0)}, w^{(0)}$ 是各自问题的最优解。

定理3：强对偶定理：如果 (L), (D) 均有可行解，则 (L), (D) 均有最优解，且 (L), (D) 的最优目标函数值相等。

此时对偶问题的最优解 $w^{(0)}$ 恰好等于单纯形乘子 $c_BB^{-1}$.

1759975640473

定理4：互补松弛定理（对称形式）

(L):

$$ \begin{array}{ll} \min & cx \\ \text{s.t.} & Ax \ge b \\ & x \ge 0 \end{array} $$

(D):

$$ \begin{aligned}\max&&wb\\\mathbf{s.t.}&&wA\leq c\\&&w\geq0\end{aligned} $$

已知 $x^{(0)}, w^{(0)}$ 为 (L)，(D) 问题的可行解，则 $x^{(0)}, w^{(0)}$ 为 (L), (D) 最优解的充要条件为 $\forall 1 \le i \le m, 1 \le j \le n$，

(1) $x_j^{(0)} \gt 0 \Rightarrow w^{(0)}P_j = c_j$

(2) $w^{(0)}P_j \lt c_j \Rightarrow x_j^{(0)} = 0$

(3) $w^{(0)}_j \gt 0 \Rightarrow A_ix^{(0)} = b_i$

(4) $A_ix^{(0)} \gt b_i \Rightarrow w^{(0)}_i = 0$

实际上 (1)(2) 等价于 $(c - w^{0}A)x^{(0)} = 0$，(3)(4) 等价于 $w^{(0)}(Ax^{(0)} - b) = 0$。

互补松弛定理（非对称形式）

(L):

$$ \begin{cases}\min cx\\s.t.&Ax=b\\&x\geq0&\end{cases} $$

(D):

$$ \begin{cases}\max&wb\\s.t.&wA\leq c&&\end{cases} $$

已知 $x^{(0)}, w^{(0)}$ 为 (L)，(D) 问题的可行解，则 $x^{(0)}, w^{(0)}$ 为 (L), (D) 最优解的充要条件为 $\forall 1 \le i \le m, 1 \le j \le n$，

(1) $x_j^{(0)} \gt 0 \Rightarrow w^{(0)}P_j = c_j$

(2) $w^{(0)}P_j \lt c_j \Rightarrow x_j^{(0)} = 0$

利用上述定理我们可以先求解对偶问题的最优解，再根据互补定理推出原问题的最优解。

定理：KKT 条件（在线性规划中的特例）

(L):

$$ \begin{array}{ll} \min & cx \\ \text{s.t.} & Ax \ge b \\ & x \ge 0 \end{array} $$

对于线性规划 (L) 来说，$x^*$ 是它的最优解的充要条件为存在 $w_{m\times 1}, r_{n \times 1}$ 使得

$$ \begin{align} Ax^*\geq b,\quad x^*\geq0\\ c^T-A^Tw-r=0,\quad w\geq0,\quad r\geq0\\ w^T(Ax^*-b)=0,\quad r^Tx^*=0 \end{align} $$

这和互补松弛定理是等价的。因此，互补松弛定理是 KKT 条件的一个特例。

对偶问题最优解在经济学上称为影子价格。

原问题：给定资源供应约束，寻找最小的供应成本。

$$ f^* = cx^* = w^*b $$

此时

$$ \frac{\partial f^*}{\partial b_i} = w^*_i $$

意味着当资源要求 $b_i$ 增加一个单位时，最低成本会增加 $w^_i$。因此 $w^_i$ 描述了“资源的稀缺性/珍贵性”，$w^*_i$ 越大，则意味着对应的资源越珍贵，想要增大该资源的供应量，付出的代价就越高。

对偶单纯形法

(L):

$$ \begin{aligned}\min&\quad cx\\\mathbf{s.t.}&\quad Ax=b\\&\quad x\geq0\end{aligned} $$

(D):

$$ \begin{aligned}\max&&wb\\\mathbf{s.t.}&&wA\leq c\end{aligned} $$

对偶可行的基本解：如果 (L) 的一个基本解（不一定是可行解）$x^{(0)}$ 对应的单纯形乘子 $w = c_BB^{-1}$ 是对偶问题 (D) 的可行解，则称 $x^{(0)}$ 为对偶可行的基本解。

如果对偶可行的基本解在 (L) 中也可行，则可知原问题的判别数 $\le 0$，从而 $x^{(0)}$ 就是原问题的最优解。

原先用两阶段和大 M 法的问题现在可以用对偶单纯性法求解了。

若初始对偶可行的基本解不易直接得到，则解一个扩充问题，通过这个问题的求解，给出原问题的解答:

$$ x_B + \sum_{j\in R} y_j\bar x_j = \bar b\\ \sum_{j\in R}x_j + x_{n+1} = M\\ x_j \ge 0, j=1,2,\dots, n+1 $$

此时表格扩充了一行。如果判别数那一行有大于 0 的数，选取其中最大的那个判别数进基，$x_{n+1}$ 进基，这时候由于出基的 $z_k-c_k$ 是最大的判别数，通过高斯消元一减，判别数这一行全部都小于 0 了。于是我们就得到了扩充问题的对偶可行基本解。

此时有以下的可能：

若扩充问题没有最优解，则原问题没有最优解。
若扩充问题的最优解为 $(x^{(0)}_1, x^{(0)}_2,\dots, x^{(0)}_n, x^{(0)}_{n+1})^T$，$(x^{(0)}_1, x^{(0)}_2,\dots, x^{(0)}_n)$ 若不含 $M$，则是原问题的可行解；若含 $M$，取任何 $M$ 使得 $x^{(0)}\ge0$ 都是原问题的可行解。如果此时得到的最优值与 $M$ 无关，则上面找到的还是原问题的最优解。

灵敏度分析

价值系数 $c$ 变化

非基变量变化

此时只有对应的检验数发生变化：$z_k - c_k + (c_k - c_k^\prime)$，在原来的单纯性表中将对应的替换即可。

基变量变化

$c_r^\prime = c_r + \Delta c_r$，此时：

$$ z_j^\prime - c_j^\prime = z_j - c_j + \Delta c_ry_{rj} (j\ne r)\\ z_r^\prime - c_r^\prime = 0 $$

只需要把第 $r$ 行乘上 $\Delta c_r$，再加到判别数那一行就行了。（第 $r$ 个判别数不变，还是 0）

右端向量 $b$ 变化

若 $B^{-1}b^\prime \ge 0$，则最优基不变，但是基变量取值，目标函数取值变化。

若 $B^{-1}b^\prime \not\ge 0$，此时原来问题的解是对偶可行解，需要把右端替换成 $B^{-1}b^\prime$，$c_BB^{-1}b$ 继续用对偶单纯形法求解。

其实就是给最后一列加上 $B^{-1}\Delta b$，$c_BB^{-1} \Delta b$。

改变约束矩阵 $A$

若非基列变了，影响对应的列 $y_j = B^{-1}P_j$，$z_j - c_j$，如果新的判别数仍然小于等于 0，则最优解，最优值不变；

基列变了，全部重新计算。

增加新的约束

$$ \begin{cases}\min&cx\\s.t.&Ax=b\\&P^{m+1}x\leq b_{m+1}\\&x\geq0&\end{cases} $$

若原最优解满足新增加的约束，则它也是新问题的最优解。
若原最优解不满足新增加约束

$$ \begin{cases}\min&cx\\s.t.&x_B+B^{-1}Nx_N=B^{-1}b\\ &P_B^{m+1}x_B+P_N^{m+1}x_N+x_{n+1}=b_{m+1}\\ &x,x_{n+1}\geq0&\end{cases} $$

对新加的行进行高斯消元，表格如下：

$$ \begin{array}{ccc|c} x_B&x_N&x_{n+1}\\ \hline I&B^{-1}N&0&B^{-1}b\\ 0&P_N^{m+1}-P_B^{m+1}B^{-1}N&1&b_{m+1}-P_B^{m+1}B^{-1}b\\ \hline 0&c_BB^{-1}N-c_N&0&c_BB^{-1}b\end{array} $$

判别数仍然保持小于等于0，因此可用对偶单纯形法求解。

整数规划

规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。

变量全限制为整数的，称纯（完全）整数规划。

变量部分限制为整数的，称混合整数规划。

要求决策变量仅取0或1,称为0-1规划问题

一般形式：

$\max cx$

$s.t.$ $\begin{cases} Ax= b\\ x_i\geq 0, x_i\text{部分或全部为整数 }& \end{cases}$

$\min cx$

$s.t.$ $\begin{cases} Ax= b\\ x_i\geq 0, x_i\text{部分或全部为整数 }& \end{cases}$

IP 问题可行域不为凸集。

整数规划特点

伴随规划有最优解，当自变量限制为整数后，其整数规划解出
现下述情况：①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。②整数规划无可行解。③有可行解（当然就存在最优解），但最优值变差。

求解方法分类：

割平面法——主要求解纯整数线性规划
分枝定界法——可求纯或混合整数线性规划
隐枚举法——求解“0-1”整数规划：
- 过滤隐枚举法；
- 分枝隐枚举法
匈牙利法——解决指派问题（“01”规划特殊情
形）。
蒙特卡洛法——求解各种类型规划

分枝定界法

设原问题 $(A_0)$

$$ \begin{cases}\max z=10x_1+20x_2\\s.t.\quad0.25x_1+0.4x_2\leq3\\x_1\leq8\\x_2\leq4\\x_1,x_2\geq0,\text{整数}&\end{cases} $$

伴随问题为 $(B_0)$

$$ \begin{aligned}\\&\begin{cases}\max&f=10x_1+20x_2\\s.t.&0.25x_1+0.4x_2\leq3\\&x_1\leq8\\&x_2\leq4\\&x_1,x_2\geq0&\end{cases}\end{aligned} $$

利用单纯形法求解 $B_0$ 得到 $x_0^* = (5.6, 4)^T$，$f_0^* = 136$，这个解不满足 $(A_0)$ 的条件。

那么原问题的初始上界为 $\bar z \le f_0^* = 136$。

显然 $(0, 0)^T$ 满足 $(A_0)$，可取初始下界 $\underline z = 0$

接下来，增加约束条件对原问题进行分支：

$(A_1)$

$$ \begin{cases}\max z=10x_1+20x_2\\s.t.&0.25x_1+0.4x_2\leq3\\x_1&\leq8\\&x_2\leq4\\&x_1&\leq5\\&x_1,x_2\geq0,\text{整数}&\end{cases} $$

$(A_2)$

$$ \begin{cases}\max z=10x_1+20x_2\\s.t.\quad0.25x_1+0.4x_2\leq3\\x_1&\leq8\\x_2\leq4\\x_1\geq6\\x_1,x_2\geq0,\text{整数}&\end{cases} $$

对应的伴随规划 $(B_1), (B_2)$。

分别求解一对分支的伴随规划：

无可行解：说明该枝情况已查明，不需要再继续分枝，称该分枝为“树叶”．
得到整数最优解：说明该枝情况也已查明，不需要再继续分枝，称该分枝为“树叶”．
得到非整数解：
1. 若此时目标值小于当前的下界 $\underline z$，就说明这是一个“枯枝”，不用继续探索；
2. 若此时目标值大于当前的下界 $\underline z$，则需要继续分支，查明有没有更好的目标值。

$(B_1), (B_2)$ 的最优解和值：$x^_1 = (5, 4)^T, f_1^ = 130$，$x^_2 = (6, 3.75)^T, f_2^ = 135$。

接下来，需要修改下界和上界：

每求出一个整数解使目标值大于当前的下界，就证明最优值的下界可以继续提升，则更新 $\underline z$ 为当前最大的目标值；
每求完一对分支，就可以更新上界 $\bar z$，为当前所有分支中取值最大的那个。

当所有的分支都被查明，并且此时 $\bar z = \underline z$，则得到原问题的整数最优解。

一般整数规划的求解是 NP-complete 问题，只有少数特殊任务有好的算法。

割平面法

适用范围：纯整数规划问题、混合整数规划问题

$$ \begin{aligned}\min z&=cx\\s.t.&\sum_{j=1}^na_{ij}x_j=b_i(i=1,2,\cdots,m)\\ &x_j 为整数 \\ &x_j \ge 0 (i = 1, 2, \dots, m, j = 1, 2, \dots, n) \end{aligned} $$

$$ \min z=cx\\ Ax = b\\ x \ge 0\\ x_i为整数 $$

假设只考虑线性规划，算出单纯形表：

$$ \begin{array}{cc|ccccccc} &&x_1&x_2&\ldots&x_m&x_{m+1}&\ldots&x_n\\ \hline &x_1&1&0&\ldots&0&y_{1m+1}&\ldots&y_{1n}&b_1^{\prime}\\ &x_2&0&1&\ldots&0&y_{2m+1}&\ldots&y_{2n}&b_2^{\prime}\\&\ldots\\ &x_r&0&0&\ldots&0&y_{rm+1}&\ldots&y_{rn}&b_r^{\prime}\\ &\ldots\\ &x_m&0&0&\ldots&1&y_{mm+1}&\ldots&y_{mn}&b_m^{\prime}\\ &&0&&&C_BB^{-1}N-C_N&&&&C_BB^{-1}b\end{array} $$

若 $b_i^\prime$ 都是整数，则 $(b_1^\prime, \dots, b_m^\prime)$ 就是原问题的最优解。

假设 $b_r$ 不是整数，考虑第 $r$ 个方程：

$$ x_r + \sum_{j = m+1}^n x_jy_{rj} = b_r^\prime $$

设

$$ b_r^\prime = \lfloor b_r^\prime\rfloor + f_r\\ y_{rj} = \lfloor y_{rj}\rfloor + f_{rj} $$

原问题改写为

$$ \sum_{j = m+1}^n x_jf_{rj} = f_r + (\lfloor b_r^\prime\rfloor - x_r - \sum_{j = m+1}^n x_j\lfloor y_{rj} \rfloor) $$

如果 $(\lfloor b_r^\prime\rfloor - x_r - \sum_{j = m+1}^n x_j\lfloor y_{rj} \rfloor) \ge -1$，则 $\sum_{j = m+1}^n x_jf_{rj} \le f_r - 1 \lt 0$ 矛盾！

因此 $(\lfloor b_r^\prime\rfloor - x_r - \sum_{j = m+1}^n x_j\lfloor y_{rj} \rfloor) \ge 0$，即

$$ -\sum_{j = m+1}^n x_jf_{rj} \le -f_r $$

添加辅助变量：

$$ y_r -\sum_{j = m+1}^n x_jf_{rj} = -f_r\\ y_r \ge 0 为整数 $$

称为 Gomory 约束（割平面方程），从而使得原可行域中的非整数区域被删除。

通过不断添加割平面方程，极点会逐个变成整数，从而找到整数最优解。

内点法

计算复杂性

算法性能：

（1）在最坏情况下算法所表现出来的性能———–最坏性能
（2）在各种情况可能出现时，算法所表现出来的期望性能。———平均性能

问题(problem):需要回答的一种提问，通常包含一些参数和取值未定的自由变量，可以从两个方面加以描述：

（1）对所有参数的一般描述；
（2）对回答（也称为解）所需要满足的特性的描述。

实例(instance)：当对一个问题中的参数赋予特定的数值时，如何寻找相应的回答（解），这种提问称为该问题的一个实例。

算法：是一组含义明确的简单指令。一个问题是算法可解的(solvable)：存在一个求解该问题的算法，只要让算法运行足够长的时间，并且保证满足算法在运行过程中所需要的存储空间，它就能求解该问题的任何一个实例。

停机问题：不可能构造出一个程序来确定任意给出的程序是否会陷入无限循环。

算法复杂性：描述算法的存储要求和运行时间要求，分为算法的空间复杂性和算法的时间复杂性。

时间复杂性：利用算法需要的初等运算次数来表示算法的时间复杂性。

输入规模(input size)：表示一个实例所需要的字符串长度。

一般用 $\lceil1 + \log_2r\rceil$ 可以表示整数 $r$ 。

$$ \begin{aligned}&L=\left\lceil1+\log_2m\right\rceil+\left\lceil1+\log_2n\right\rceil+\sum_{j=1}^n\left\lbrace \left\lceil1+\log_2\mid c_j\mid\right\rceil\right\rbrace \\&+\sum_{i=1}^m\sum_{j=1}^n\left\{\left\lceil1+\log_2\mid a_{ij}\mid\right\rceil\right\}+\sum_{i=1}^m\left\{\left\lceil1+\log_2\mid b_j\mid\right\rceil\right\}\\ &\le mn + m + n + 2 + \log_2\underline{|P|}_{A, b, c中所有非零数乘积} \end{aligned} $$

旅行商问题，二进制输入长度的总量不超过 $L = n(n-1) + \log_2|P|$，$P$ 为所有非零 $d_{ij}$ 的乘积。假设每个 $d_{ij}$ 都有上限 $K$，则

$$ L \le n(n-1)(1 + \log_2K) $$

复杂度：基本计算总次数C(I)同实例I的计算机二进制输入长度d(I)的关系为

$$ C(I) \le ag(d(I)) $$

则称 $C(I) = O(g(d(I)))$。

假如某个算法使得 $g(x)$ 为多项式，则该算法对于实例 $I$ 是多项式时间算法。

如果 $g(x)$ 为指数函数，则称为指数时间算法。

多项式时间算法的优点：

随着问题输入规模的增加，算法的计算量（即算法复杂性）呈多项式增长；
一个多项式时间算法利用另一个多项式时间算法作为其“子程序”，构造一个新的复合型算法，则新算法仍是多项式时间算法。

线性规划问题的单纯性方法是指数时间算法：

$$ \begin{aligned}&\max&&\sum_{i=1}^n2^{n-i}x_i\\&s.t.&&x_i+2\sum_{j=1}^{i-1}2^{i-j}x_j\leq a^{i-1},i=2,\cdots,n\\&&&x_i\geq0,\quad i=1,2,\cdots,n\end{aligned} $$

定理：$a \gt 2$ 时，用单纯形算法求解上述问题时需要 $2^n - 1$ 次迭代。

最坏情况：指数；平均情况：多项式

椭球法是第一个可以在多項式时间內解决一般线性规划问题的解法。

定理：存在求解 LP 问题的多项式时间算法的充要条件是存在求解线性不等式组的多项式时间算法。

凸集分离定理

定理 1：若 $S$ 是 $E^n$ 的闭凸集, $y\not\in S$，存在唯一的 $\bar x \in S$ 使得

$$ ||y - \bar x || = \inf_{x \in S}||y - x|| \gt 0 $$

并且，$\forall x \in S$，总有

$$ (y - \bar x)(\bar x - x) \ge 0 $$

定理 2：若 $S$ 是 $E^n$ 的非空闭凸集，$y\not\in S$，存在非零向量 $p$ 和数 $\varepsilon \gt 0$，使得对任意 $x \in S$，有 $p^Ty \ge \varepsilon + p^Tx$。

定理 3：设 $S$ 是 $E^n$ 的非空凸集，$y \in \partial S$，则存在非零向量 $p$，使得 $\forall x \in clS$（即 $S$ 的闭包），有 $p^Ty \ge p^Tx$。

推论 4：（点和凸集的分离定理）设 $S$ 是 $E^n$ 的非空凸集，$y \not \in S$，则存在非零向量 $p$ 使得对任意 $x \in clS$，有 $p^T(x - y) \le 0$。

定理 5：（凸集分离定理）设 $S_1$，$S_2$ 是 $E^n$ 的两个非空凸集，$S_1 \cap S_2 = \varnothing$，则存在非零向量 $p$ 使得

$$ \inf \lbrace p^Tx | x \in S_1\rbrace \ge \sup \lbrace p^Tx | x \in S_2\rbrace $$

定理 6：设 $S_1$ 是 $E^n$ 的非空有界闭凸集，$S_2$ 是 $E^n$ 的非空闭凸集，$S_1 \cap S_2 = \varnothing$，则存在非零向量 $p$，数 $\varepsilon \gt 0$ 使得

$$ \inf \lbrace p^Tx | x \in S_1\rbrace \ge \varepsilon + \sup \lbrace p^Tx | x \in S_2\rbrace $$

Farkas 定理：$Ax \le 0, c^Tx \gt 0$ 有解的充要条件是 $A^Ty = c, y\ge0$ 无解。

可以写成一组对偶的优化问题：

(L)：

$$ \min 0^Ty\\ A^Ty = c\\ y \ge 0 $$

(D):

$$ \max c^Tx\\ Ax \le 0 $$

假设两个问题同时有解，根据弱对偶定理，$c^Tx \le 0^Tx = 0$，因此 $Ax \le 0, c^Tx \gt 0$ 无解。

显然 (D) 总是有解，假如 (L) 无解，只能说明 (D) 有无界解，即 $c^Tx \to \infty$，因此存在 $x$ 使得 $c^Tx \gt 0$.

Gordan 定理：$Ax \lt 0$ 有解的充要条件是不存在非零向量 $y \ge 0$，$A^T = 0$。

凸函数：$f(x) \le af(x^{(1)}) + (1-a)f(x^{(2)}), a \in [0, 1]$

凸函数的和仍然是凸函数。

凸函数乘上一个非负数，仍然是凸函数。因此，凸函数的非负线性组合仍然是凸函数。

$f(x)$ 为凸集 $S$ 上的凸函数，则集合 $S_c = \lbrace x|x\in S, f(x) \le c\rbrace$ 为凸集。

$S$ 是 $E^n$ 中的非空凸集，$f$ 是定义在 $S$ 上的凸函数，则 $f$ 在 $S$ 上的局部极小点是整体极小点，并且极小点的集合是凸集。

$g(x) = \max (f_1(x), f_2(x))$ 也是凸函数。

凸函数的判别

$$ \nabla f(x) = (\frac{\partial f(x)}{\partial x_1}\quad \dots \frac{\partial f(x)}{\partial x_n})^T $$

$$ \nabla^2 x = \begin{bmatrix} \frac{\partial^2 f(x)}{\partial x_1^2} &\dots& \frac{\partial^2 f(x)}{\partial x_1\partial x_n}\\ \vdots & \ddots & \vdots\\ \frac{\partial^2 f(x)}{\partial x_n\partial x_1} & \dots & \frac{\partial^2 f(x)}{\partial x_n^2} \end{bmatrix} $$

方向导数：$Df(x^0; p) = \nabla f(x^0)^T p$。

一阶充要条件：

$S$ 是 $E^n$ 中的非空凸集，$f$ 是定义在 $S$ 上的可微函数，则 $f(x)$ 为凸函数的充要条件为 $\forall x^{(1)}, x^{(2)} \in S$，有

$$ f(x^{(2)}) \ge f(x^{(1)}) + \nabla f(x^{(1)})^T(x^{(2)} - x^{(1)})\\ $$

$f(x)$ 为严格凸函数的充要条件为 $\forall x^{(1)}, x^{(2)} \in S$，有

$$ f(x^{(2)}) \gt f(x^{(1)}) + \nabla f(x^{(1)})^T(x^{(2)} - x^{(1)})\\ $$

二阶充要条件：

$S$ 是 $E^n$ 中的非空凸集，$f$ 是定义在 $S$ 上的二阶可微函数，则 $f(x)$ 为凸函数的充要条件为 $\forall x \in S$，$\nabla^2 f(x)$ 是半正定的。

如果 $\nabla^2 f(x)$ 是正定的，可以推出 $f(x)$ 为严格凸函数。

定理：$f(x)$ 是定义在凸集 $S$ 上的可微凸函数，如果存在 $x^\in S$ 使得 $\forall x \in S$ 都有 $\nabla f(x^)^T(x - x^*) \ge 0$，则 $x^*$ 是凸集 $S$ 上的全局极小点。

凸规划：

$$ \begin{aligned}&\min\quad f(x)\\&s.t.\quad g_i(x)\geq0,i=1,\cdots,m\\&h_j(x)=0,j=1,\cdots,l\end{aligned} $$

其中 $f(x)$ 是凸函数，$g_i(x)$ 是凹函数，$h_j(x)$ 是线性函数，则称该问题为凸规划。

最优性条件

无约束问题

$$ \min f(x)\\ s.t. x\in E^n $$

必要条件：

若 $\bar x$ 是局部极小点，则 $\nabla f(\bar x) = 0$.

$\nabla f(x^*) = 0$ 时称 $x^*$ 为驻点，如果 $x^*$ 既不是局部极大点也不是局部极小点，则 $x^*$ 称为鞍点。

若 $\bar x$ 是局部极小点，则 $\nabla f(\bar x) = 0$，且 $\nabla^2 f(x)$ 是半正定的。