运筹学

线性规划

标准形式

线性规划是一种优化函数和约束条件均为线性的优化问题，规定其标准形式为：

$\begin{equation} \begin{array}{ c l c } \ minimize\ \ & c_{1} x_{1} +\cdots +c_{n} x_{n} & \\ subject\ to & a_{11} x_{1} +\cdots +a_{1n} x_{n} & =b_{1}\\ & \vdots & \vdots \\ & a_{m1} x_{1} +\cdots +a_{mn} x_{n} & =b_{m}\\ & x_{1} \geq 0,\dotsc ,x_{n} \geq 0 & \end{array} \end{equation}$

即：

$\begin{equation} \begin{aligned} minimize\ \ & \boldsymbol{c}^{T}\boldsymbol{x}\\ subject\ to\ \ & \boldsymbol{Ax} =\boldsymbol{b} ,\ \ \boldsymbol{x} \geq \boldsymbol{0} \end{aligned} \end{equation}$

这里 $\displaystyle \boldsymbol{x} \in \mathbb{F}^{n\times 1} ,\ \boldsymbol{A} \in \mathbb{F}^{m\times n} ,\ \boldsymbol{b} ,\boldsymbol{c} \in \mathbb{F}^{m\times 1}$

所有线性规划问题均可转换成上述的标准形式

对于优化问题：

$\begin{equation} \begin{array}{ c l c } \ maximize\ \ & c_{1} x_{1} +\cdots +c_{n} x_{n} & \\ subject\ to & a_{11} x_{1} +\cdots +a_{1n} x_{n} & \leq b_{1}\\ & \vdots & \vdots \\ & a_{m1} x_{1} +\cdots +a_{mn} x_{n} & \leq b_{m}\\ & x_{1} \geq 0,\dotsc ,x_{n} \geq 0 & \end{array} \end{equation}$

可通过引入新的非负变量 $\displaystyle x_{n+i}( i=1,\dotsc ,m)$ ，将问题转化为：

$\begin{equation} \begin{array}{ c l c } \ minimize\ \ & -c_{1} x_{1} -\cdots -c_{n} x_{n} & \\ subject\ to & a_{11} x_{1} +\cdots +a_{1n} x_{n} +x_{n+1} & =b_{1}\\ & \vdots & \vdots \\ & a_{m1} x_{1} +\cdots +a_{mn} x_{n} +x_{n+m} & =b_{m}\\ & x_{1} \geq 0,\dotsc ,\ x_{n+m} \geq 0 & \end{array} \end{equation}$

此即为标准形式

对于优化问题：

$\begin{equation} \begin{array}{ c l c } \ maximize\ \ & c_{1} x_{1} +\cdots +c_{n} x_{n} & \\ subject\ to & a_{11} x_{1} +\cdots +a_{1n} x_{n} & \geq b_{1}\\ & \vdots & \vdots \\ & a_{m1} x_{1} +\cdots +a_{mn} x_{n} & \geq b_{m}\\ & x_{1} \geq 0,\dotsc ,x_{n} \geq 0 & \end{array} \end{equation}$

可通过引入新的非负变量 $\displaystyle y_{i}( i=1,\dotsc ,m)$ ，将问题转化为：

$\begin{equation} \begin{array}{ c l c } \ minimize\ \ & -c_{1} x_{1} -\cdots -c_{n} x_{n} & \\ subject\ to & a_{11} x_{1} +\cdots +a_{1n} x_{n} -y_{1} & =b_{1}\\ & \vdots & \vdots \\ & a_{m1} x_{1} +\cdots +a_{mn} x_{n} -y_{m} & =b_{m}\\ & x_{1} \geq 0,\dotsc ,\ x_{n} \geq 0,\ y_{i} \geq 0 & \end{array} \end{equation}$

此即为标准形式

对于形如：

$\begin{equation} \begin{array}{ c l c } \ minimize\ \ & c_{1} x_{1} +\cdots +c_{n} x_{n} & \\ subject\ to & a_{11} x_{1} +\cdots +a_{1n} x_{n} & =b_{1}\\ & \vdots & \vdots \\ & a_{m1} x_{1} +\cdots +a_{mn} x_{n} & =b_{m}\\ & x_{2} \geq 0,\dotsc ,x_{n} \geq 0 & \end{array} \end{equation}$

的有一个或多个变量不为非负的线性规划问题，我们可令：

$\begin{equation} x_{1} =u_{1} -v_{1} \quad \quad u_{1} ,v_{1} \geq 0 \end{equation}$

以将规划问题化成：

$\begin{equation} \begin{array}{ c r c } \ minimize\ \ & c_{1} u_{1} +( -c_{1}) v_{1} +\cdots +c_{n} x_{n} & \\ subject\ to & a_{11} u_{1} +( -a_{11}) v_{1} +\cdots +a_{1n} x_{n} & =b_{1}\\ & \vdots & \vdots \\ & a_{m1} u_{1} +( -a_{m1}) v_{1} +\cdots +a_{mn} x_{n} & =b_{m}\\ & u_{1} \geq 0,v_{1} \geq 0,x_{2} \geq 0,\dotsc ,x_{n} \geq 0 & \end{array} \end{equation}$

此即为标准形式

另解：若在（7）中 $\displaystyle a_{i1} =0,\ \forall i=1,\dotsc ,m$ ，则可直接将规划问题转换成标准形式；否则， $\displaystyle \exists \ k\ s.t.\ a_{k1} \neq 0$ ，随后由：

$\begin{equation} a_{k1} x_{1} +a_{k2} x_{2} +\cdots +a_{kn} x_{n} =b_{k} \end{equation}$

知 $\displaystyle x_{1}$ 可由 $\displaystyle x_{2} ,\dotsc ,x_{n}$ 表征，用 $\displaystyle x_{2} ,\dotsc ,x_{n}$ 代替原规划问题中所有出现的 $\displaystyle x_{1}$ ，可让规划问题降阶至 $\displaystyle ( m,n)\rightarrow ( m-1,n-1)$ ，并且恰为标准形式

应用

线性规划模型在许多分配以及经济学问题中都发挥了非常重要的作用，下面是一些例子：

食材采购问题

一个人为了饮食均衡，每天需要摄入 $\displaystyle b_{k}$ 的第 $\displaystyle k$ 种营养物质。与此同时，市场上有 $\displaystyle n$ 种不同的食物，第 $\displaystyle i$ 种食物的单位价格为 $\displaystyle c_{i}$ ，单位这种食物蕴含了 $\displaystyle a_{ij}$ 的第 $\displaystyle j$ 种营养物质

则在满足营养需求的前提下，计算最少的采购开销的问题可被约化为：

$\begin{equation} \begin{array}{ c l c } \ minimize\ \ & c_{1} x_{1} +\cdots +c_{n} x_{n} & \\ subject\ to & a_{11} x_{1} +\cdots +a_{1n} x_{n} & \geq b_{1}\\ & \vdots & \vdots \\ & a_{m1} x_{1} +\cdots +a_{mn} x_{n} & \geq b_{m}\\ & x_{1} \geq 0,\dotsc ,x_{n} \geq 0 & \end{array} \end{equation}$

产品生产问题

假设我们拥有一个工厂，工厂中存放着 $\displaystyle m$ 种原料，第 $\displaystyle k$ 种原料还存有 $\displaystyle b_{k}$ 。工厂可以生产 $\displaystyle n$ 种产品，单位第 $\displaystyle i$ 种产品的生产需要 $\displaystyle a_{ij}$ 的第 $\displaystyle j$ 种原料，并且单位这种产品的售价为 $\displaystyle \pi _{j}$

则最大化销售额的问题可被约化为：

$\begin{equation} \begin{array}{ c l c } \ maximize\ \ & \pi _{1} x_{1} +\cdots +\pi _{n} x_{n} & \\ subject\ to & a_{11} x_{1} +\cdots +a_{1n} x_{n} & \leq b_{1}\\ & \vdots & \vdots \\ & a_{m1} x_{1} +\cdots +a_{mn} x_{n} & \leq b_{m}\\ & x_{1} \geq 0,\dotsc ,x_{n} \geq 0 & \end{array} \end{equation}$

货物转运问题

假设我们将货物囤积在了 $\displaystyle m$ 个地点，其中第 $\displaystyle i$ 个地点囤积了 $\displaystyle a_{i}$ 的货物。现在我们需要将这些货物全部运送到 $\displaystyle n$ 个仓库中，其中第 $\displaystyle j$ 个仓库应当接收 $\displaystyle b_{j}$ 的货物，而从第 $\displaystyle i$ 个地点运送至第 $\displaystyle j$ 个仓库的运费为 $\displaystyle c_{ij}$

则最小化运费的问题可被约化为：

$\begin{array}{ c l c } \ minimize\ \ & \sum\limits _{ij} c_{ij} x_{ij} & \\ subject\ to & \sum\limits _{j=1}^{n} x_{ij} =a_{i} \quad i=1,\dotsc ,m & \\ & \sum\limits _{i=1}^{\ m} x_{ij} =b_{j} \quad j=1,\dotsc ,n & \\ & x_{ij} \geq 0\quad \forall i,j & \end{array}$

显然，该问题有解的必要条件为 $\displaystyle \sum _{i=1}^{m} a_{i} =\sum _{j=1}^{n} b_{j}$ ，即运出的货物与接受的货物数量一致

网络流量问题

考虑一个具有容量限制的网络，网络中存在两个特殊的节点，源节点与汇节点，源节点上信息净流出，汇节点上信息净流入，并且二者流量相等，记为 $\displaystyle f$ ，除此之外的所有节点应保证均无净流入流出。

假定第 $\displaystyle i$ 个节点将信息流入到底 $\displaystyle j$ 个节点的荷载为 $\displaystyle k_{ij}$ ，则计算最大流量 $\displaystyle f$ 的问题可被约化为：

$\begin{equation} \begin{array}{ c l c } \ maximize\ \ & f & \\ subject\ to & \sum\limits _{j=1}^{n} x_{1j} -\sum\limits _{j=1}^{n} x_{j1} -f=0 \quad & \\ & \sum\limits _{j=1}^{n} x_{ij} -\sum\limits _{j=1}^{n} x_{ji} =0\quad i\neq 1,m & \\ & \sum\limits _{j=1}^{n} x_{mj} -\sum\limits _{j=1}^{n} x_{jm} +f=0 \quad & \\ & 0\leq x_{ij} \leq k_{ij} \quad \forall i,j & \end{array} \end{equation}$

店铺运营问题

杂货店仓库的容量为 $\displaystyle C$ ，某种商品的价格随日期而波动，每天可售出或买入这种商品，且售出和买入的价格在第 $\displaystyle i$ 天时均为 $\displaystyle p_{i}$ 。

假定第一天开始时仓库没有库存，每日单位商品的储存开销为 $\displaystyle r$ ，并要求第 $\displaystyle n$ 天结束时仓库内应没有库存，则最大化利润的问题可约化为：

$\begin{equation} \begin{array}{ c l c } \ maximize\ \ & \sum\limits _{i=1}^{n}( p_{i}( s_{i} -u_{i}) -rx_{i}) & \\ subject\ to & x_{i+1} =x_{i} +u_{i} -s_{i} \quad i=1,\cdots ,n-1 & \\ & 0=x_{n} +u_{n} -s_{n} & \\ & x_{i} +z_{i} =C\quad \quad i=2,\dotsc ,n & \\ & x_{1} =0,\ x_{i} ,u_{i} ,s_{i} ,z_{i} \geq 0 & \end{array} \end{equation}$

赌马比赛

一场有 $\displaystyle m$ 个队伍的赌马比赛，有 $\displaystyle n$ 位参与者，第 $\displaystyle j$ 个人选择押注的队伍为 $\displaystyle \boldsymbol{a}_{j} =( a_{j1} ,\dotsc ,a_{jm}) ,a_{jk} \in \{0,1\}$ ，他所签订的合同价格为 $\displaystyle r_{j}$ ，内容为只要这些队伍中有人获胜，便可获得 $\displaystyle 1$ 美元

同时，每个人报出自己能够接受的合同的最高购买份数 $\displaystyle q_{j}$ ，那么作为比赛的组织者，求解在最糟糕的情况下，如何分配合同才可实现最大盈利的问题可被约化为：

$\begin{equation} \begin{array}{ c l c } \ maximize\ \ & \boldsymbol{r}^{T}\boldsymbol{x} -\max_{i}(\boldsymbol{Ax})_{i} & \\ subject\ to & \boldsymbol{0} \leq \boldsymbol{x} \leqslant \boldsymbol{q} & \end{array} \end{equation}$

可将其转化为：

$\begin{equation} \begin{array}{ c l c } \ maximize\ \ & \boldsymbol{r}^{T}\boldsymbol{x} -s & \\ subject\ to & \boldsymbol{Ax} -\boldsymbol{1} s\leq \boldsymbol{0} & \\ & \boldsymbol{0} \leq \boldsymbol{x} \leqslant \boldsymbol{q} & \end{array} \end{equation}$

马尔可夫决策过程

有 $\displaystyle m$ 种状态，每种状态都有一组可执行的操作，设第 $\displaystyle i$ 种状态的可执行操作所构成的集合为 $\displaystyle \mathcal{A}_{i}$ ， $\displaystyle j\in \mathcal{A}_{i}$ 为其中的一个操作，执行这个操作会带来开销 $\displaystyle c_{j}$ ，并且以 $\displaystyle \boldsymbol{p}_{j}$ 的概率分布转移到其他的状态

设 $\displaystyle 0\leq \gamma < 1$ ，求最佳的状态 $\displaystyle \rightarrow$ 操作策略 $\displaystyle \{\pi _{1} ,\dotsc ,\pi _{m}\}$ 使得：

$\begin{equation} \sum _{t=0}^{\infty } \gamma ^{t} E[ c_{\pi _{i^{t}}}] \end{equation}$

最小化

定义 $\displaystyle y_{i}^{*}$ 为从状态 $\displaystyle i$ 开始的最低开销的期望值，由贝尔曼最优原理知：

$\begin{equation} y_{i}^{*} =\underset{j\in \mathcal{A}_{i}}{\min}\left( c_{j} +\gamma \boldsymbol{p}_{j}^{T}\boldsymbol{y}^{*}\right) \end{equation}$

这里 $\displaystyle \boldsymbol{y}^{*} =\left( y_{1}^{*} ,\dotsc ,y_{m}^{*}\right)$

故而：

$\begin{equation} \pi _{i}^{*} =\arg\underset{j\in \mathcal{A}_{i}}{\min}\left( c_{j} +\gamma \boldsymbol{p}_{j}^{T}\boldsymbol{y}^{*}\right) \end{equation}$

并且 $\displaystyle \boldsymbol{y}^{*}$ 可通过：

$\begin{equation} \begin{array}{ c l c } \ maximize\ \ & \sum\limits _{i=1}^{m} y_{i} & \\ subject\ to & y_{i} -\gamma \boldsymbol{p}_{j}^{T}\boldsymbol{y} \leq c_{j} \ \forall i,j & \end{array} \end{equation}$

加以确定

规划问题求解

对于线性规划问题标准形式，出于为了消除冗余条件以及避免规划问题无解的考虑，我们作以下规定：

在标准形式中： $\displaystyle \boldsymbol{A} \in \mathbb{F}^{m\times n} \ s.t.\ m< n,\ rank( \boldsymbol{A}) =m$

对于线性方程组：

$\begin{equation} \boldsymbol{Ax} =\boldsymbol{b} \end{equation}$

设 $\displaystyle \boldsymbol{B} \in \mathbb{F}^{m\times m}$ 为 $\displaystyle \boldsymbol{A}$ 的一个非退化子阵，则 $\displaystyle \boldsymbol{x} =(\boldsymbol{x}_{B} ,\boldsymbol{0}) ,\ \boldsymbol{x}_{B} =\boldsymbol{B}^{-1}\boldsymbol{b}$ 为方程组的一个解，被称为相对于基 $\displaystyle \boldsymbol{B}$ 的基本解， $\displaystyle \boldsymbol{x}$ 中位于 $\displaystyle \boldsymbol{B}$ 所在列的分量被称为基本变量

若基本解中存在分量为零的基本变量，则称这个基本解为退化基本解

卡拉泰奥多里定理

给定一个标准形式下的规划问题，则：

（a）若存在可行解，则存在基本可行解

（b）若存在最优的可行解，则存在最优的基本可行解

(a) 设 $\displaystyle \boldsymbol{A} =(\boldsymbol{a}_{1} ,\dotsc \boldsymbol{a}_{n}) ,\ \boldsymbol{a}_{i} \in \mathbb{F}^{m\times 1}$ ， $\displaystyle \boldsymbol{x} =( x_{1} ,\dotsc ,x_{n})$ 为一个可行解，则：

$\begin{equation} x_{1}\boldsymbol{a}_{1} +\cdots +x_{n}\boldsymbol{a}_{n} =\boldsymbol{b} \end{equation}$

$\displaystyle \boldsymbol{x} \geq \boldsymbol{0} \Rightarrow$ 不失一般性，可设 $\displaystyle x_{i} >0,\ i=1,\dotsc ,p;\ x_{k} =0,\ k=p+1,\dotsc ,n$

$\begin{equation} \Rightarrow x_{1}\boldsymbol{a}_{1} +\cdots +x_{p}\boldsymbol{a}_{p} =\boldsymbol{b} \end{equation}$

若 $\displaystyle \boldsymbol{a}_{1} ,\dotsc ,\boldsymbol{a}_{p}$ 线性无关，则 $\displaystyle p\leq m$

$\displaystyle p=m \Rightarrow \boldsymbol{x}$ 为基本可行解； $\displaystyle p< m$ ， $\displaystyle rank( A) =m \Rightarrow \boldsymbol{a}_{p+1} ,\dotsc ,\boldsymbol{a}_{n}$ 中 $\displaystyle \exists \ \boldsymbol{a}_{\pi _{1}} ,\dotsc \boldsymbol{a}_{\pi _{m-p}} \ s.t. B:=(\boldsymbol{a}_{1} ,\dotsc ,\boldsymbol{a}_{p} ,\boldsymbol{a}_{\pi _{1}} ,\dotsc ,\boldsymbol{a}_{\pi _{m-p}})$ 非退化 $\displaystyle \Rightarrow \boldsymbol{x}$ 为相对于 $\displaystyle \boldsymbol{B}$ 的基本解

若 $\displaystyle \boldsymbol{a}_{1} ,\dotsc ,\boldsymbol{a}_{p}$ 线性相关，则 $\displaystyle \exists \ y_{1} ,\dotsc ,y_{p} \ s.t.$

$\begin{gather} y_{1}\boldsymbol{a}_{1} +\dotsc +y_{p}\boldsymbol{a}_{p} =0\\ \notag\\ \Longrightarrow ( x_{1} -\epsilon y_{1})\boldsymbol{a}_{1} +\cdots +( x_{p} -\epsilon y_{p})\boldsymbol{a}_{p} =\boldsymbol{b} ,\ \forall \epsilon \end{gather}$

$\displaystyle \Rightarrow \boldsymbol{x} -\epsilon \boldsymbol{y},\forall \epsilon$ 为方程组的一组解

不失一般性，可设 $\displaystyle \exists \ y_{k} \in \{y_{i}\} \ s.t.\ y_{k} >0$ ，随后令 $\displaystyle \epsilon =min\{x_{i} /y_{i} :y_{i} >0\}$ ，即得规划问题的一个可行解 $\displaystyle \boldsymbol{x} -\epsilon \boldsymbol{y}$ ，此时可行解仅有至多 $\displaystyle p-1$ 个正分量，重复此操作，可使得最后 $\displaystyle \boldsymbol{a}_{i}$ 线性无关

(b) 根据上面讨论，知：若 $\displaystyle \boldsymbol{a}_{1} ,\dotsc ,\boldsymbol{a}_{p}$ 线性无关，则 $\displaystyle \boldsymbol{x}$ 即为最优的基本可行解

若 $\displaystyle \boldsymbol{a}_{1} ,\dotsc ,\boldsymbol{a}_{p}$ 线性相关，则 $\displaystyle \boldsymbol{x}$ 为最优解 $\displaystyle \Rightarrow \epsilon =0$ 为函数：

$\begin{equation} \boldsymbol{c}^{T}\boldsymbol{x} -\epsilon \boldsymbol{c}^{T}\boldsymbol{y} =\boldsymbol{c}^{T}(\boldsymbol{x} -\epsilon \boldsymbol{y}) \end{equation}$

的极值点 $\displaystyle \Rightarrow \boldsymbol{c}^{T}\boldsymbol{y} =0\Rightarrow \boldsymbol{x} -\epsilon \boldsymbol{y}$ 也为最优解

设：

$\begin{equation} C=\left\{\boldsymbol{Ax} \in E^{m}\Bigl| \ \boldsymbol{x} \geq \boldsymbol{0}\right\} \quad \quad \boldsymbol{A} \in \mathbb{F}^{m\times n} \end{equation}$

则 $\displaystyle C$ 为闭凸集

法卡斯引理

$\displaystyle \boldsymbol{A} \in \mathbb{F}^{m\times n} ,\ \boldsymbol{b} \in \mathbb{F}^{m\times 1}$ ，则约束系统：

$\begin{equation} \boldsymbol{Ax} =\boldsymbol{b} \quad \quad \boldsymbol{x} \geq \boldsymbol{0} \end{equation}$

存在可行解 $\displaystyle \boldsymbol{x}\Leftrightarrow$ 约束系统：

$\begin{equation} -\boldsymbol{y}^{T}\boldsymbol{A} \geq \boldsymbol{0} ,\ \boldsymbol{y}^{T}\boldsymbol{b} =1 \end{equation}$

不存在可行解 $\displaystyle \boldsymbol{y}$

$\displaystyle \Rightarrow \ :$ 设约束系统（28）存在可行解 $\displaystyle \overline{\boldsymbol{x}}$ ：

$\boldsymbol{y}^{T}\boldsymbol{b} =\boldsymbol{y}^{T}(\boldsymbol{A}\overline{\boldsymbol{x}}) \leq 0\quad \quad if\ \ -\boldsymbol{y}^{T}\boldsymbol{A} \geq \boldsymbol{0}$

$\displaystyle \Rightarrow$ 约束系统（29）不存在可行解

$\displaystyle \Leftarrow$ : 设约束系统（28）不存在可行解，则 $\displaystyle \boldsymbol{b} \notin C:=\left\{\boldsymbol{Ax}\Bigl| \ \boldsymbol{x} \geq \boldsymbol{0}\right\}$ ，定理1.2.2 $\displaystyle \Rightarrow C$ 为闭凸集 $\displaystyle \Rightarrow \exists \ \boldsymbol{y} \ s.t.$

$\begin{equation} \boldsymbol{y}^{T}\boldsymbol{b} >\sup _{\boldsymbol{c} \in C}\boldsymbol{y}^{T}\boldsymbol{c} \end{equation}$

$\displaystyle \boldsymbol{c} \in C\Rightarrow \forall \boldsymbol{c} \in C,\ \exists \ \boldsymbol{x} \geq \boldsymbol{0} \ s.t.\ \boldsymbol{c} =\boldsymbol{Ax} \Rightarrow \ :$

$\begin{equation} \boldsymbol{y}^{T}\boldsymbol{b} >\sup _{\boldsymbol{x} \geq \boldsymbol{0}}\boldsymbol{y}^{T}(\boldsymbol{Ax}) =\sup _{\boldsymbol{x} \geq \boldsymbol{0}}\left(\boldsymbol{y}^{T}\boldsymbol{A}\right)\boldsymbol{x} \end{equation}$

$\displaystyle \Rightarrow \boldsymbol{y}^{T}\boldsymbol{b} >0,\ \boldsymbol{y}^{T}\boldsymbol{A} \leq \boldsymbol{0} \Rightarrow$ 总可通过对 $\displaystyle \boldsymbol{y}$ 的缩放来得到约束系统（29）的解

将定理中出现的两种系统称为替代系统，即一个系统存在可行解 $\displaystyle \Leftrightarrow$ 另一个系统不存在可行解

法卡斯引理存在多种变体，例如：

$\displaystyle \boldsymbol{A} \in \mathbb{F}^{m\times n} ,\ \boldsymbol{b} \in \mathbb{F}^{m\times 1}$ ，则约束系统：

$\begin{equation} \boldsymbol{A^{T} x} \leq \boldsymbol{b} \end{equation}$

存在可行解 $\displaystyle \boldsymbol{x}\Leftrightarrow$ 约束系统：

$\begin{equation} \boldsymbol{Ay} =\boldsymbol{0} ,\ \boldsymbol{y} \geq \boldsymbol{0} ,\ \boldsymbol{b}^{T}\boldsymbol{y} =-1 \end{equation}$

不存在可行解 $\displaystyle \boldsymbol{y}$

$\displaystyle \Rightarrow \ :$ 设约束系统（32）存在可行解 $\displaystyle \overline{\boldsymbol{x}}$ ，则若约束系统（33）存在可行解 $\displaystyle \overline{\boldsymbol{y}}\geq 0:$

$\begin{equation} -1=\boldsymbol{b}^{T}\overline{\boldsymbol{y}} \geq \overline{\boldsymbol{x}}\boldsymbol{A}\overline{\boldsymbol{y}} =0 \end{equation}$

矛盾， $\displaystyle \Rightarrow$ 约束系统（33）不存在可行解

$\displaystyle \Leftarrow \ :$ 约束系统（32）不存在可行解 $\displaystyle \Rightarrow \boldsymbol{b} \in \left\{\boldsymbol{z}\Bigl|\boldsymbol{z} < \boldsymbol{A}^{T}\boldsymbol{x} ,\ \forall \boldsymbol{x} \in \mathbb{F}^{m\times 1}\right\} \Rightarrow \exists \ \boldsymbol{y} \geq \boldsymbol{0} \ s.t.\; \boldsymbol{y}^{T}\boldsymbol{b} \leq \underset{\boldsymbol{x} \in \mathbb{F}^{m\times 1}}{\inf}\boldsymbol{y}^{T}\boldsymbol{A}^{T}\boldsymbol{x}$

$\displaystyle \Rightarrow \boldsymbol{y}^{T}\boldsymbol{b} < 0,\ \boldsymbol{Ay} =0$ ，对 $\displaystyle \boldsymbol{y}$ 进行缩放即可得约束系统（33）的可行解

以下两个约束互为替代系统：

$\begin{gather} \begin{aligned} \boldsymbol{Ax} =\boldsymbol{b} ,\ \boldsymbol{x} & \geq \boldsymbol{0}\\ \boldsymbol{A}^{T}\boldsymbol{y} & \leq \boldsymbol{c}\\ \boldsymbol{c}^{T}\boldsymbol{x} -\boldsymbol{b}^{T}\boldsymbol{y} & \leq 0 \end{aligned}\\ \notag\\ \begin{aligned} \boldsymbol{Ax} ' & =\boldsymbol{b} \tau \\ \boldsymbol{A}^{T}\boldsymbol{y} '-\boldsymbol{c} \tau & \leq \boldsymbol{0}\\ \boldsymbol{b}^{T}\boldsymbol{y} '-\boldsymbol{c}^{T}\boldsymbol{x} ' & =1\\ \boldsymbol{x} '\geq 0,\ \tau & \geq 0 \end{aligned} \end{gather}$

$\displaystyle \Rightarrow \ :$ 设约束系统 (35) 存在可行解 $\displaystyle (\boldsymbol{x} ',\boldsymbol{y} ')$ ：

$\begin{equation} \begin{aligned} 1 & =\boldsymbol{b}^{T}\boldsymbol{y} '-\boldsymbol{c}^{T}\boldsymbol{x} '\\ & =\boldsymbol{x}^{T}\boldsymbol{A}^{T}\boldsymbol{y} '-\boldsymbol{c}^{T}\boldsymbol{x} '\\ & \leq \tau \boldsymbol{x}^{T}\boldsymbol{c} -\left(\boldsymbol{y}^{T}\boldsymbol{A}\right)\boldsymbol{x} '=\tau \left(\boldsymbol{x}^{T}\boldsymbol{c} -\boldsymbol{y}^{T}\boldsymbol{b}\right)\\ & =\tau \left(\boldsymbol{c}^{T}\boldsymbol{x} -\boldsymbol{b}^{T}\boldsymbol{y}\right)^{T} \leq 0 \end{aligned} \end{equation}$

矛盾，故而约束系统 (35) 不存在可行解

$\displaystyle \Leftarrow \ :$ 设约束系统 (34) 不存在可行解，则 $\displaystyle :$

$\begin{equation} \text{若} \ \boldsymbol{Ax} =\boldsymbol{b} ,\ \boldsymbol{x} \geq \boldsymbol{0} ,\ \boldsymbol{A}^{T}\boldsymbol{y} \leq \boldsymbol{c} ,\ \text{则} \ \boldsymbol{c}^{T}\boldsymbol{x} -\boldsymbol{b}^{T}\boldsymbol{y} >0 \end{equation}$

令 $\displaystyle \tau =\left(\boldsymbol{c}^{T}\boldsymbol{x} -\boldsymbol{b}^{T}\boldsymbol{y}\right)^{-1} ,\ \boldsymbol{x} '=\tau \boldsymbol{x} ,\ \boldsymbol{y} '=\tau \boldsymbol{y}$ ， $\displaystyle (\boldsymbol{x} ',\boldsymbol{y} ',\tau )$ 即为约束系统 (35) 的可行解

几何对应

线性规划问题同凸集理论存在着千丝万缕的联系，如下所示：

极点与基本解的等价性

$\displaystyle \boldsymbol{A} \in \mathbb{F}^{m\times n} ,\ rank( A) =m,\ \boldsymbol{b} \in \mathbb{F}^{m\times 1}$ ，设 $\displaystyle K$ 为由约束条件：

$\begin{equation} \boldsymbol{Ax} =\boldsymbol{b} ,\ \boldsymbol{x} \geq 0 \end{equation}$

确定的可行解构成的凸多面体约束集，则： $\displaystyle \boldsymbol{x}$ 为 $\displaystyle K$ 的极点 $\displaystyle \Leftrightarrow \boldsymbol{x}$ 为基本解

$\displaystyle \Rightarrow \ :$ 设 $\displaystyle \boldsymbol{x}$ 仅有前 $\displaystyle k$ 个分量非零，则：

$\begin{equation} x_{1}\boldsymbol{a}_{1} +\cdots +x_{k}\boldsymbol{a}_{k} =\boldsymbol{b} \end{equation}$

若 $\displaystyle \boldsymbol{a}_{1} ,\dotsc ,\boldsymbol{a}_{k}$ 线性相关，则 $\displaystyle \exists \ y_{i} ,\ 1\leq i\leq k\ s.t.$

$y_{1}\boldsymbol{a}_{1} +\cdots +y_{k}\boldsymbol{a}_{k} =\boldsymbol{0}$

定义 $\displaystyle \boldsymbol{y} =( y_{1} ,\dotsc ,y_{k} ,0,\dotsc ,0)$ ，则 $\displaystyle \exists \ \epsilon >0\ s.t.$

$\begin{equation} \boldsymbol{x} +\epsilon \boldsymbol{y} \geq 0,\ \boldsymbol{x} -\epsilon \boldsymbol{y} \geq 0 \end{equation}$

显然 $\displaystyle \boldsymbol{x} +\epsilon \boldsymbol{y} ,\ \boldsymbol{x} -\epsilon \boldsymbol{y}$ 同为可行解，并且 $\displaystyle \boldsymbol{x} =\frac{1}{2}( x+\epsilon \boldsymbol{y}) +\frac{1}{2}( x-\epsilon \boldsymbol{y})$ ，与 $\displaystyle \boldsymbol{x}$ 为 $\displaystyle K$ 的极点矛盾

故而 $\displaystyle \boldsymbol{a}_{1} ,\dotsc ,\boldsymbol{a}_{k}$ 线性无关，根据定理1.2.1 (a) 中的讨论，可知 $\displaystyle \boldsymbol{x}$ 为基本解

$\displaystyle \Leftarrow \ :$ 不失一般性，设 $\displaystyle \boldsymbol{x} =( x_{1} ,\dotsc ,x_{m} ,0,\dotsc ,0)$ ，则：

$\begin{equation} x_{1}\boldsymbol{a}_{1} +\cdots +x_{m}\boldsymbol{a}_{m} =\boldsymbol{b} \end{equation}$

这里 $\displaystyle \boldsymbol{a}_{i} ,\ 1\leq i\leq m$ 线性无关

设 $\displaystyle \boldsymbol{x} =\alpha \boldsymbol{y} +( 1-\alpha )\boldsymbol{z} ,\ 0< \alpha < 1,\ \boldsymbol{y} ,\boldsymbol{z} \in K$ ，条件 $\displaystyle \boldsymbol{x} \geq \boldsymbol{0} \Rightarrow \boldsymbol{y} ,\boldsymbol{z}$ 的非零项仅存在于前 $\displaystyle m$ 个分量，故而：

$\begin{gather} y_{1}\boldsymbol{a}_{1} +\cdots +y_{m}\boldsymbol{a}_{m} =\boldsymbol{b}\\ \notag\\ z_{1}\boldsymbol{a}_{1} +\cdots +z_{m}\boldsymbol{a}_{m} =\boldsymbol{b} \end{gather}$

$\displaystyle \boldsymbol{a}_{i}$ 线性无关 $\displaystyle \Rightarrow \boldsymbol{x} =\boldsymbol{y} =\boldsymbol{z} \Rightarrow \boldsymbol{x}$ 为 $\displaystyle K$ 的极点

结合卡拉泰奥多里定理和极点与基本解等价性，可得如下的推论：

若在约束条件（27）中的约束集 $\displaystyle K$ 非空，则 $\displaystyle K$ 至少存在一个极点

若一个线性规划问题的最优解有限，则存在一个恰为此问题约束集极点的最优解

考虑到 $\displaystyle \boldsymbol{A}$ 中至多存在 $\displaystyle \begin{pmatrix} n\\ m \end{pmatrix}$ 个非退化 $\displaystyle n\times n$ 子阵，故而同时也有：

约束条件（27）所对应的约束集 $\displaystyle K$ 至多拥有有限个极点，并且这些极点有限

综合上面这些结论，我们可得：

若约束条件（27）所对应的约束集 $\displaystyle K$ 有界，则 $\displaystyle K$ 由有限个点的凸组合构成

主问题与对偶问题

我们将：

$\begin{equation} \begin{aligned} & Primal & \ \ \quad \quad & Dual\\ minmize\ \ & \boldsymbol{c}^{T}\boldsymbol{x} & \ \ \ \ \ \ \ \ maximize\ \ \ & \boldsymbol{y}^{T}\boldsymbol{b}\\ subject\ to\ \ & \boldsymbol{Ax} \geq \boldsymbol{b} & subject\ to\ \ \ & \boldsymbol{y}^{T}\boldsymbol{A} \leq \boldsymbol{c}^{T}\\ & \boldsymbol{x} \geq \boldsymbol{0} & & \boldsymbol{y} \geq \boldsymbol{0} \end{aligned} \end{equation}$

称为对偶关系的对称形式

任何线性规划主问题均有其对偶问题

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

其等价表述为：

$\begin{equation} \begin{aligned} minimize\ \ & \boldsymbol{c}^{T}\boldsymbol{x}\\ subject\ to\ \ & \boldsymbol{Ax} \geq \boldsymbol{b}\\ & -\boldsymbol{Ax} \geq -\boldsymbol{b}\\ & \boldsymbol{x} \geq \boldsymbol{0} \end{aligned} \quad \quad \Longleftrightarrow \quad \quad \begin{aligned} minmize\ \ & \boldsymbol{c}^{T}\boldsymbol{x}\\ subject\ to\ \ & \begin{pmatrix} \boldsymbol{A}\\ -\boldsymbol{A} \end{pmatrix}\boldsymbol{x} \geq \begin{pmatrix} \boldsymbol{b}\\ -\boldsymbol{b} \end{pmatrix}\\ & \boldsymbol{x} \geq \boldsymbol{0} \end{aligned} \end{equation}$

对偶关系的对称形式 $\displaystyle \Rightarrow$ 线性规划的对偶问题为：

$\begin{equation} \begin{aligned} \ \ \ \ \ \ \ \ maximize\ \ \ & \boldsymbol{u}^{T}\boldsymbol{b} -\boldsymbol{v}^{T}\boldsymbol{b}\\ subject\ to\ \ \ & \boldsymbol{u}^{T}\boldsymbol{A} -\boldsymbol{v}^{T}\boldsymbol{A} \leq \boldsymbol{c}^{T}\\ & \boldsymbol{u} \geq \boldsymbol{0} ,\ \boldsymbol{v} \geq \boldsymbol{0} \end{aligned} \end{equation}$

令 $\displaystyle \boldsymbol{y} =\boldsymbol{u}^{T} -\boldsymbol{v}^{T}$ ，我们即得：对偶关系的反对称形式：

$\begin{equation} \begin{aligned} & Primal & \ \ \quad \quad & Dual\\ minmize\ \ & \boldsymbol{c}^{T}\boldsymbol{x} & \ \ \ \ \ \ \ \ maximize\ \ \ & \boldsymbol{y}^{T}\boldsymbol{b}\\ subject\ to\ \ & \boldsymbol{Ax} =\boldsymbol{b} ,\ \boldsymbol{x} \geq \boldsymbol{0} & subject\ to\ \ \ & \boldsymbol{y}^{T}\boldsymbol{A} \leq \boldsymbol{c}^{T} \end{aligned} \end{equation}$

结合定理1.1.1 知任何线性规划主问题均有其对偶问题

$\begin{equation*} \begin{array}{ r l c r l c } & Primal & ( dual\ var.) \quad & & Dual & ( prime\ var.)\\ max\ \ & 2x_{1} +x_{2} & ( y_{1}) & min\ \ & 4y_{1} +2y_{2} +3y_{3} & ( x_{1})\\ s.t.\ \ & x_{1} +\frac{8}{3} x_{2} \leq 4 & ( y_{2}) & \ \ \ \ \ s.t.\ \ & y_{1} +y_{2} +2y_{3} \geq 2 & ( x_{2})\\ & 2x_{1} \leq 3 & ( y_{3}) & & \frac{8}{3} y_{1} +y_{2} \geq 1 & \\ & ( x_{1} ,x_{2}) \geq \boldsymbol{0} & & & ( y_{1} ,y_{2} ,y_{3}) \geq \boldsymbol{0} & \end{array} \end{equation*}$

在这样的例子中我们可以看出：在对偶关系中：

$\begin{equation} \displaystyle \boldsymbol{A} \in \mathbb{F}^{m\times n} ;\ \boldsymbol{y} ,\boldsymbol{b} \in \mathbb{F}^{m\times 1} ;\boldsymbol{x} ,\boldsymbol{c} \in \mathbb{F}^{n\times 1} \end{equation}$

故而若主问题的规模为 $\displaystyle ( m,n)$ ，对偶问题的规模为 $\displaystyle ( n,m)$ ，并且存在着如下的对应：

主问题的目标系数向量对应于对偶约束的右侧向量
主约束的右侧向量对应于对偶问题的目标系数向量
主问题约束矩阵的转置对应于对偶问题的约束矩阵
主问题的变量类型，即正定、负定，还是无约束，对应于对偶约束的不等号类型

（对偶）食材采购问题

在例4 中，我们已将问题约化为：

$\begin{equation} \begin{aligned} minimize\ \ & \boldsymbol{c}^{T}\boldsymbol{x}\\ subject\ to\ \ & \boldsymbol{Ax} \geq \boldsymbol{b} ,\ \ \boldsymbol{x} \geq \boldsymbol{0} \end{aligned} \end{equation}$

这里 $\displaystyle \boldsymbol{c}$ 为各食材的价格， $\displaystyle \boldsymbol{A}$ 为各食物所蕴含的营养素， $\displaystyle \boldsymbol{b}$ 为一个人一天饮食中所必需的营养素，由对称形式的对偶关系知其对偶问题为：

$\begin{equation} \begin{aligned} \ \ \ \ \ \ \ \ maximize\ \ \ & \boldsymbol{y}^{T}\boldsymbol{b}\\ subject\ to\ \ \ & \boldsymbol{y}^{T}\boldsymbol{A} \leq \boldsymbol{c}^{T} \ \boldsymbol{y} \geq \boldsymbol{0} \end{aligned} \end{equation}$

可将此对偶问题解释成：你经营着一家营养素公司，需要制定各营养素的价格，以在说服顾客直接购买营养素更有性价比的前提下，实现收益的最大化

（对偶）货物转运问题

在例6 中，我们已将问题约化为：

$\begin{equation} \begin{array}{ c l c } \ minimize\ \ & \sum\limits _{ij} c_{ij} x_{ij} & \\ subject\ to & \sum\limits _{j=1}^{n} x_{ij} =a_{i} \quad i=1,\dotsc ,m & \\ & \sum\limits _{i=1}^{\ m} x_{ij} =b_{j} \quad j=1,\dotsc ,n & \\ & x_{ij} \geq 0\quad \forall i,j & \end{array} \end{equation}$

这里 $\displaystyle \boldsymbol{c}$ 为各转运方式的开销， $\displaystyle \boldsymbol{a}$ 为各地点储存的货物量， $\displaystyle \boldsymbol{b}$ 为各仓库应当接收的货物量，由反对称形式的对偶关系知其对偶问题为：

$\begin{equation} \begin{array}{ c l c } \ maximize\ \ & \sum _{i=1}^{m} a_{i} u_{i} +\sum _{j=1}^{n} b_{j} v_{j} & \\ subject\ to & u_{i} +v_{j} \leq c_{ij} ,\ \ \forall i,j & \end{array} \end{equation}$

可将此对偶问题解释成：你经营着一家运输公司，你只根据运输的起点与终点收费，并且二者相互独立，作为上面开价 $\displaystyle c_{ij}$ 的竞争对手，你需要思考如何对起点和终点定价，才能使在看起来比前者更有性价比的情况下实现最大收益

（对偶）赌马比赛

在例9 中，我们已将问题约化为：

$\begin{equation} \begin{array}{ c l c } \ maximize\ \ & \boldsymbol{r}^{T}\boldsymbol{x} -s & \\ subject\ to & \boldsymbol{Ax} -\boldsymbol{1} s\leq \boldsymbol{0} & \\ & \boldsymbol{x} \leqslant \boldsymbol{q} & \\ & \boldsymbol{x} \geq \boldsymbol{0} & \end{array} \end{equation}$

这里 $\displaystyle \boldsymbol{r}$ 为各合同的价格， $\displaystyle \boldsymbol{A}$ 为各参赛者所押注的队伍， $\displaystyle \boldsymbol{q}$ 为各参赛者所接受的最大合同数量，由构造规则知此问题的对偶问题为：

$\begin{equation*} \begin{array}{ c l } \ maximize\ \ & \boldsymbol{q}^{T}\boldsymbol{y}\\ subject\ to & \boldsymbol{A^{T} p} +\boldsymbol{y} \geq \boldsymbol{r}\\ & -\boldsymbol{1}^{T}\boldsymbol{p} =-1\\ & (\boldsymbol{p} ,\boldsymbol{y}) \geq \boldsymbol{0} \end{array} \quad \quad \Longrightarrow \quad \quad \begin{array}{ c l } \ minnize\ \ & \boldsymbol{q}^{T}\max\left\{\boldsymbol{0} ,\boldsymbol{r} -\boldsymbol{A}^{T}\boldsymbol{p}\right\}\\ subject\ to & \boldsymbol{1}^{T}\boldsymbol{p} =1\\ & \boldsymbol{p} \geq \boldsymbol{0} \end{array} \end{equation*}$

可将此对偶问题解释成：你是一名统计学家，你要寻找马赛结果的概率分布，使得那些能从这次赌马比赛中获利的参赛者的期望获利之和最小

（对偶）马尔可夫决策过程

在例10 中，我们已将问题约化为：

这里 $\displaystyle y_{i}$ 为从状态 $\displaystyle i$ 开始最低开销的期望值，$\displaystyle \gamma $ 为优化函数的衰减常数， $\displaystyle \boldsymbol{p}_{j}$ 为执行操作 $\displaystyle j\in \mathcal{A}_{i}$ 的状态跃迁函数， $\displaystyle \boldsymbol{c}_{j}$ 为执行操作 $\displaystyle j$ 的开销

由构造规则知此问题的对偶问题为：

$\begin{equation} \begin{array}{ c l c } \ minimize\ \ & \sum\limits _{i=1}^{m}\sum\limits _{j\in \mathcal{A}_{i}} c_{j} x_{j} & \\ subject\ to & \sum\limits _{i=1}^{m}\sum\limits _{j\in \mathcal{A}_{i}}(\boldsymbol{e}_{i} -\gamma \boldsymbol{p}_{j}) x_{j} =\boldsymbol{1} & \\ & x_{j} \geq 0,\ \forall i=1,\dotsc ,m;\ j\in \mathcal{A}_{i} & \end{array} \end{equation}$

对偶定理

这一节我们仅考虑反对称对偶关系：

$\begin{equation} \begin{aligned} & Primal & \ \ \quad \quad & Dual\\ minmize\ \ & \boldsymbol{c}^{T}\boldsymbol{x} & \ \ \ \ \ \ \ \ maximize\ \ \ & \boldsymbol{y}^{T}\boldsymbol{b}\\ subject\ to\ \ & \boldsymbol{Ax} =\boldsymbol{b} ,\ \boldsymbol{x} \geq \boldsymbol{0} & subject\ to\ \ \ & \boldsymbol{y}^{T}\boldsymbol{A} \leq \boldsymbol{c}^{T} \end{aligned} \end{equation}$

若主问题和对偶问题均有可行解，则：

$\begin{equation} \boldsymbol{y}^{T}\boldsymbol{b} =\boldsymbol{y}^{T}\boldsymbol{Ax} \leq \boldsymbol{c}^{T}\boldsymbol{x} \end{equation}$

于是，我们得到了下面的引理：

弱对偶引理

若 $\displaystyle \boldsymbol{x} ,\boldsymbol{y}$ 为（58）的可行解，则 $\displaystyle \boldsymbol{c}^{T}\boldsymbol{x} \geq \boldsymbol{y}^{T}\boldsymbol{b}$

我们可以从中看到，主问题与对偶问题均为对方的优化函数提供了界

线性规划的对偶定理

若主问题和对偶问题中的一个问题存在有限的最优解，那么另外一个问题也存在有限的最优解，并且二者数值相等

不失一般性，设主问题最优解为 $\displaystyle \boldsymbol{x}$ ，若对偶问题不存在可行解，则由定理1.2.4 ，知约束系统：

$\begin{equation} \begin{aligned} \boldsymbol{Ax} ' & =\boldsymbol{0}\\ \boldsymbol{c}^{T}\boldsymbol{x} ' & =-1\\ \boldsymbol{x} ' & \geq \boldsymbol{0} \end{aligned} \end{equation}$

存在可行解 $\displaystyle \Rightarrow \boldsymbol{x} +\alpha \boldsymbol{x} ',\ \alpha >0$ 为主问题的可行解，但 $\displaystyle \boldsymbol{c}^{T}(\boldsymbol{x} +\alpha \boldsymbol{x} ') =\boldsymbol{c}^{T}\boldsymbol{x} -\alpha$ ，与最优性矛盾 $\displaystyle \Rightarrow$ 对偶问题存在可行解

随后由弱对偶引理，此定理的证明等价于证明系统：

$\begin{equation} \begin{aligned} \boldsymbol{Ax} =\boldsymbol{b} ,\ \boldsymbol{x} & \geq \boldsymbol{0}\\ \boldsymbol{A}^{T}\boldsymbol{y} & \leq \boldsymbol{c}\\ \boldsymbol{c}^{T}\boldsymbol{x} -\boldsymbol{b}^{T}\boldsymbol{y} & \leq 0 \end{aligned} \end{equation}$

存在可行解 $\displaystyle (\boldsymbol{x} ,\boldsymbol{y})$

如若不然，则由定理1.2.5 ，知替代系统：

$\begin{equation} \begin{aligned} \boldsymbol{Ax} ' & =\boldsymbol{b} \tau \\ \boldsymbol{A}^{T}\boldsymbol{y} '-\boldsymbol{c} \tau & \leq \boldsymbol{0}\\ \boldsymbol{b}^{T}\boldsymbol{y} '-\boldsymbol{c}^{T}\boldsymbol{x} ' & =1\\ \boldsymbol{x} '\geq 0,\ \tau & \geq 0 \end{aligned} \end{equation}$

存在可行解，随后根据：

$\begin{equation} \begin{aligned} \tau & =\tau \left(\boldsymbol{b}^{T}\boldsymbol{y} '-\boldsymbol{c}^{T}\boldsymbol{x} '\right)\\ & \leq (\boldsymbol{x} ')^{T}\boldsymbol{A}^{T}\boldsymbol{y} '-\tau \boldsymbol{c}^{T}\boldsymbol{x} '\\ & \leq \tau \left((\boldsymbol{x} ')^{T}\boldsymbol{c} -\boldsymbol{c}^{T}\boldsymbol{x} '\right) =0 \end{aligned} \end{equation}$

$\displaystyle \Rightarrow \tau =0,\ \boldsymbol{A}^{T}\boldsymbol{y} '\leq \boldsymbol{0} ,\ \boldsymbol{Ax} '=\boldsymbol{0} \Rightarrow \boldsymbol{x} +\alpha \boldsymbol{x} ',\ \boldsymbol{y} +\alpha \boldsymbol{y} ',\ \alpha >0$ 也分别为主问题与对偶问题的可行解，并且：

$\begin{equation} \boldsymbol{c}^{T}(\boldsymbol{x} +\alpha \boldsymbol{x} ') -\boldsymbol{b}^{T}(\boldsymbol{y} +\alpha \boldsymbol{y} ') =\boldsymbol{c}^{T}\boldsymbol{x} -\boldsymbol{b}^{T}\boldsymbol{y} -\alpha \end{equation}$

与弱对偶引理相矛盾，故而约束系统(61) 存在可行解

无约束优化问题

在这一章中，我们考虑无约束优化问题：

$\begin{equation} \min f( x) \quad \quad x\in \mathbb{R}^{n} \end{equation}$

这里 $\displaystyle f\in C^{2}\left(\mathbb{R}^{n}\right)$

对于这种问题，已经有了许多性能优异的算法。

一般而言，这些算法都是先选定一个起始点 $\displaystyle \boldsymbol{x}_{0}$ ，然后通过一些确定的方法确定之后的迭代点：

$\begin{equation} \boldsymbol{x}_{1} ,\dotsc ,\boldsymbol{x}_{k} ,\dotsc \end{equation}$

使得 $\displaystyle f(\boldsymbol{x}_{k+m}) < f(\boldsymbol{x}_{k})$ ，以此来逼近优化问题的局部最优

而根据 $\displaystyle \boldsymbol{x}_{k}$ 来获得 $\displaystyle \boldsymbol{x}_{k+1}$ 的方法基本上又可以划分为线搜索策略与信任域方法

线搜索策略中，是根据 $\displaystyle \boldsymbol{x}_{k}$ 首先确定一个搜索方向 $\displaystyle \boldsymbol{p}_{k}$ ，而后再通过确定步长 $\displaystyle \alpha_k$ ，使得

$\begin{equation} f(\boldsymbol{x}_{k+1}) =f(\boldsymbol{x}_{k} +\alpha_k \boldsymbol{p}_{k}) <div f(\boldsymbol{x}_{k}) \end{equation}$

在迭代过程中趋于最优解

线搜索策略

最速降线法

由泰勒公式：

$\begin{equation} f(\boldsymbol{x} +\alpha \boldsymbol{p}) =f(\boldsymbol{x}) +\alpha \nabla f(\boldsymbol{x})^{T}\boldsymbol{p} +\frac{1}{2} \alpha ^{2}\boldsymbol{p}^{T} \nabla ^{2} f(\boldsymbol{x} +t\boldsymbol{p})\boldsymbol{p} ,\ t\in ( 0,1) \end{equation}$

可见对于 $\displaystyle \boldsymbol{p}_{k}$ ，一种显然的选择方式为：

$\begin{equation} \boldsymbol{p}_{k} =-\frac{\nabla f_{k}}{\| \nabla f_{k} \| } \end{equation}$

若在搜索过程中的每一步均选择 $\displaystyle \boldsymbol{p}_{k} =-\frac{\nabla f_{k}}{\| \nabla f_{k} \| }$ ，由此得到的搜索策略便是最速降线法

若将精确线搜索的最速下降法应用于强凸二次函数：

$\begin{equation} f(\boldsymbol{x}) =\frac{1}{2}\boldsymbol{x}^{T}\boldsymbol{Qx} -\boldsymbol{b}^{T}\boldsymbol{x} \end{equation}$

则收敛误差满足：

$\begin{equation} \| \boldsymbol{x}_{k+1} -\boldsymbol{x}^{*} \| _{Q}^{2} \leq \left(\frac{\lambda _{n} -\lambda _{1}}{\lambda _{n} +\lambda _{1}}\right)^{2} \| \boldsymbol{x}_{k} -\boldsymbol{x}^{*} \| _{Q}^{2} \end{equation}$

这里 $\displaystyle 0< \lambda _{1} < \cdots < \lambda _{n}$ 为 $\displaystyle Q$ 的特征值， $\displaystyle \| \boldsymbol{x} \| _{Q}^{2} :=\boldsymbol{x}^{T} Q\ \boldsymbol{x}$ ， $\displaystyle \boldsymbol{x}^{*}$ 为最优点

首先由最速降线法：

$\begin{gather} f(\boldsymbol{x}_{k} -\alpha \nabla f_{k}) =\frac{1}{2}(\boldsymbol{x}_{k} -\alpha \nabla f_{k})^{T} Q(\boldsymbol{x}_{k} -\alpha \nabla f_{k}) -\boldsymbol{b}^{T}(\boldsymbol{x}_{k} -\alpha \nabla f_{k})\\ \notag\\ \begin{aligned} \Longrightarrow \frac{\partial }{\partial \alpha } f(\boldsymbol{x}_{k} -\alpha \nabla f_{k}) & =\alpha \nabla f_{k}^{T}\boldsymbol{Q} \nabla f_{k} -\boldsymbol{x_{k}^{T} Q} \nabla f_{k} +\boldsymbol{b}^{T} \nabla f_{k}\\ & =\alpha \nabla f_{k}^{T}\boldsymbol{Q} \nabla f_{k} -\nabla f_{k}^{T} \nabla f_{k} \end{aligned} \end{gather}$

故而通过精确线搜索确定的步长为：

$\begin{equation} \alpha _{k} =\frac{\nabla f_{k}^{T} \nabla f_{k}}{\nabla f_{k}^{T}\boldsymbol{Q} \nabla f_{k}} \quad \Longrightarrow \quad \boldsymbol{x}_{k+1} =\boldsymbol{x}_{k} -\left(\frac{\nabla f_{k}^{T} \nabla f_{k}}{\nabla f_{k}^{T}\boldsymbol{Q} \nabla f_{k}}\right) \nabla f_{k} \end{equation}$

故而：

$\begin{equation} \begin{aligned} & \| \boldsymbol{x}_{k} -\boldsymbol{x}^{*} \| _{Q}^{2} -\| \boldsymbol{x}_{k+1} -\boldsymbol{x}^{*} \| _{Q}^{2}\\ = & \left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*}\right)^{T}\boldsymbol{Q}\left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*}\right) -\left(\boldsymbol{x}_{k+1} -\boldsymbol{x}^{*}\right)^{T}\boldsymbol{Q}\left(\boldsymbol{x}_{k+1} -\boldsymbol{x}^{*}\right)\\ = & \left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*}\right)^{T}\boldsymbol{Q}\left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*}\right) -\left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*} +\boldsymbol{x}_{k+1} -\boldsymbol{x}_{k}\right)^{T}\boldsymbol{Q}\left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*} +\boldsymbol{x}_{k+1} -\boldsymbol{x}_{k}\right)\\ = & 2(\boldsymbol{x}_{k} -\boldsymbol{x}_{k+1})\boldsymbol{Q}\left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*}\right) -(\boldsymbol{x}_{k+1} -\boldsymbol{x}_{k})^{T}\boldsymbol{Q}(\boldsymbol{x}_{k+1} -\boldsymbol{x}_{k})\\ = & 2\alpha _{k} \nabla f_{k}\boldsymbol{Q}\left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*}\right) -\alpha _{k}^{2} \nabla f_{k}^{2}\boldsymbol{Q} \nabla f_{k}\\ = & \frac{\left( \nabla f_{k}^{T} \nabla f_{k}\right)^{2}}{\left( \nabla f_{k}^{T}\boldsymbol{Q} \nabla f_{k}\right)} \end{aligned} \end{equation}$

另一方面：

$\begin{gather} \nabla f_{k} =\boldsymbol{x}_{k}^{T}\boldsymbol{Q} -\boldsymbol{b}^{T} =\boldsymbol{Q}\left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*}\right) \notag\\ \notag\\ \begin{aligned} \Longrightarrow \| \boldsymbol{x}_{k} -\boldsymbol{x}^{*} \| _{Q}^{2} & =\left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*}\right)^{T}\boldsymbol{Q}\left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*}\right)\\ & =\left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*}\right)^{T}\boldsymbol{Q}^{T}\boldsymbol{Q}^{-1}\boldsymbol{Q}\left(\boldsymbol{x}_{k} -\boldsymbol{x}^{*}\right)\\ & =\nabla f_{k}^{T}\boldsymbol{Q}^{-1} \nabla f_{k} \end{aligned}\\ \notag\\ \Longrightarrow \begin{aligned} \| \boldsymbol{x}_{k+1} -\boldsymbol{x}^{*} \| _{Q}^{2} & =\left\{1-\frac{\left( \nabla f_{k}^{T} \nabla f_{k}\right)^{2}}{\left( \nabla f_{k}^{T}\boldsymbol{Q} \nabla f_{k}\right)\left( \nabla f_{k}^{T}\boldsymbol{Q}^{-1} \nabla f_{k}\right)}\right\} \end{aligned} \| \boldsymbol{x}_{k} -\boldsymbol{x}^{*} \| _{Q}^{2} \end{gather}$

最后结合 Kantorovich 不等式，即可证得：

$\begin{equation*} \| \boldsymbol{x}_{k+1} -\boldsymbol{x}^{*} \| _{Q}^{2} \leq \left(\frac{\lambda _{n} -\lambda _{1}}{\lambda _{n} +\lambda _{1}}\right)^{2} \| \boldsymbol{x}_{k} -\boldsymbol{x}^{*} \| _{Q}^{2} \end{equation*}$

这种方法的优点在于不涉及目标函数的二阶导数，但对于复杂的问题往往收敛得很慢

牛顿法

通过定义 $\displaystyle f(\boldsymbol{x} +\boldsymbol{p})$ 的二阶近似表达式：

$\begin{gather} f(\boldsymbol{x} +\boldsymbol{p}) \approx m_{k}(\boldsymbol{p}) =f_{k} +\boldsymbol{p}^{T} \nabla f_{k} +\frac{1}{2}\boldsymbol{p}^{T} \nabla ^{2} f_{k}\boldsymbol{p}\\ \notag\\ \Longrightarrow \frac{\partial }{\partial p_{j}} m_{j}(\boldsymbol{p}) =( \nabla f_{k})_{j} +\left( \nabla ^{2} f_{k}\boldsymbol{p}\right)_{j} \end{gather}$

可以得到当 $\displaystyle \nabla ^{2} f_{k}≻0$ 时：

$\begin{equation} \boldsymbol{p}_{k} =-\left( \nabla ^{2} f_{k}\right)^{-1} \nabla f_{k} \end{equation}$

为搜索方向的另一个自然选择，这样确定的方向被称为牛顿方向

牛顿方法有着自然的步长选择 $\displaystyle \alpha =1$ ，往往能够在局域快速收敛，但依赖于 Hessian 矩阵 $\displaystyle \nabla ^{2} f_{k}$ 的正定性

准牛顿法

根据：

$\begin{gather} \nabla f(\boldsymbol{x} +\boldsymbol{p}) =\nabla f(\boldsymbol{x}) +\int _{0}^{1} \nabla ^{2} f(\boldsymbol{x} +t\boldsymbol{p}) \cdot \boldsymbol{p} dt\\ \notag\\ \Longrightarrow \nabla f(\boldsymbol{x} +\boldsymbol{p}) =\nabla f(\boldsymbol{x}) +\nabla ^{2} f(\boldsymbol{x}) \cdot \boldsymbol{p} +\int _{0}^{1}\left( \nabla ^{2} f(\boldsymbol{x} +t\boldsymbol{p}) -\nabla ^{2} f(\boldsymbol{x})\right) \cdot \boldsymbol{p} dt\notag \end{gather}$

可以得到：

$\begin{equation} \nabla f(\boldsymbol{x}_{k+1}) =\nabla f(\boldsymbol{x}_{k}) +\nabla ^{2} f(\boldsymbol{x}_{k})(\boldsymbol{x}_{k+1} -\boldsymbol{x}_{k}) +o( \| \boldsymbol{x}_{k+1} -\boldsymbol{x}_{k} \| ) \end{equation}$

定义 $\displaystyle \boldsymbol{s}_{k} =\boldsymbol{x}_{k+1} -\boldsymbol{x}_{k} ,\ \boldsymbol{y}_{k} =\nabla f(\boldsymbol{x}_{k+1}) -\nabla f(\boldsymbol{x}_{k})$ ，寻找满足如下正割方程：

$\begin{equation} \boldsymbol{B}_{k+1}\boldsymbol{s}_{k} =\boldsymbol{y}_{k} \end{equation}$

的对称矩阵 $\displaystyle \boldsymbol{B}_{k}$ ，使得 $\displaystyle \boldsymbol{B}_{k+1} -\boldsymbol{B}_{k}$ 为低秩矩阵，再令：

$\begin{equation} \boldsymbol{p}_{k} =-\boldsymbol{B}_{k}^{-1} \nabla f(\boldsymbol{x}_{k}) \end{equation}$

这样的递推策略被称为准牛顿法，这里 $\displaystyle \boldsymbol{B}_{k}$ 实际为对 Hessian 阵 $\displaystyle \nabla ^{2} f_{k}$ 的近似

一种常见的构造为：

$\begin{gather} \boldsymbol{B}_{k+1} =\boldsymbol{B}_{k} +\frac{(\boldsymbol{y}_{k} -\boldsymbol{B}_{k}\boldsymbol{s}_{k})(\boldsymbol{y}_{k} -\boldsymbol{B}_{k}\boldsymbol{s}_{k})^{T}}{(\boldsymbol{y}_{k} -\boldsymbol{B}_{k}\boldsymbol{s}_{k})^{T}\boldsymbol{s}_{k}}\\ \notag\\ \Longrightarrow \boldsymbol{B}_{k+1}\boldsymbol{s}_{k} =\boldsymbol{B}_{k}\boldsymbol{s}_{k} +(\boldsymbol{y}_{k} -\boldsymbol{B}_{k}\boldsymbol{s}_{k}) =\boldsymbol{y}_{k} \end{gather}$

显然 $\displaystyle rank(\boldsymbol{B}_{k+1} -\boldsymbol{B}_{k}) =1$ ，故而这样的构造也称为对称秩一构造 (SR1)

另一种流行的构造为：

$\begin{gather} \boldsymbol{B}_{k+1} =\boldsymbol{B}_{k} -\frac{\boldsymbol{B}_{k}\boldsymbol{s}_{k}\boldsymbol{s}_{k}^{T}\boldsymbol{B}_{k}}{\boldsymbol{s}_{k}^{T}\boldsymbol{B}_{k}\boldsymbol{s}_{k}} +\frac{\boldsymbol{y}_{k}\boldsymbol{y}_{k}^{T}}{\boldsymbol{y}_{k}^{T}\boldsymbol{s}_{k}}\\ \notag\\ \Longrightarrow \boldsymbol{B}_{k+1}\boldsymbol{s}_{k} =\boldsymbol{B}_{k}\boldsymbol{s}_{k} -\boldsymbol{B}_{k}\boldsymbol{s}_{k} +\boldsymbol{y}_{k} =\boldsymbol{y}_{k} \end{gather}$

这里 $\displaystyle rank(\boldsymbol{B}_{k+1} -\boldsymbol{B}_{k}) =2$ ，这样的构造被称为 BFGS 构造

定义 $\displaystyle H_{k} =B_{k}^{-1}$ ，则对于 SR1 构造与 BFGS 构造，分别有：

$\begin{equation} \begin{aligned} H_{k+1} & =H_{k} +\frac{( s_{k} -H_{k} y_{k})( s_{k} -H_{k} y_{k})^{T}}{( s_{k} -H_{k} y_{k})^{T} y_{k}}\\ & \\ H_{k+1} & =\left( I-\rho _{k} s_{k} y_{k}^{T}\right) H_{k}\left( I-\rho _{k} y_{k} s_{k}^{T}\right) +\rho _{k} s_{k} s_{k}^{T} \end{aligned} \end{equation}$

首先由矩阵求逆引理，我们可得：

$\begin{equation} \left( A+u^{T} v\right)^{-1} =A^{-1} +\frac{A^{-1} vu^{T} A^{-1}}{1+u^{T} A^{-1} v} \end{equation}$

于是对于 SR1构造， $\displaystyle B_{k}$ 为对称阵 $\displaystyle \Rightarrow \ :$

$\begin{gather} \begin{aligned} & \left( B_{k} +\frac{( y_{k} -B_{k} s_{k})( y_{k} -B_{k} s_{k})^{T}}{( y_{k} -B_{k} s_{k})^{T} s_{k}}\right)^{-1}\\ = & B_{k}^{-1} -B_{k}^{-1} \cdot \frac{( y_{k} -B_{k} s_{k})( y_{k} -B_{k} s_{k})^{T}}{( y_{k} -B_{k} s_{k})^{T} s_{k} +( y_{k} -B_{k} s_{k})^{T} B_{k}^{-1}( y_{k} -B_{k} s_{k})} \cdot B_{k}^{-1}\\ = & B_{k}^{-1} +\frac{\left( s_{k} -B_{k}^{-1} y_{k}\right)\left( s_{k} -B_{k}^{-1} y_{k}\right)^{T}}{\left( s_{k} -B_{k}^{-1} y_{k}\right)^{T} y_{k}} \end{aligned}\\ \notag\\ \notag\\ \Longrightarrow H_{k+1} =H_{k} +\frac{( s_{k} -H_{k} y_{k})( s_{k} -H_{k} y_{k})^{T}}{( s_{k} -H_{k} y_{k})^{T} y_{k}} \end{gather}$

对于 BFGS构造，我们有：

$\begin{aligned} & \left( B_{k} +\frac{y_{k} y_{k}^{T}}{y_{k}^{T} s_{k}} -\frac{B_{k} s_{k} s_{k}^{T} B_{k}}{s_{k}^{-1} B_{k} s_{k}}\right)^{-1}\\ = & \left( B_{k} +\frac{y_{k} y_{k}^{T}}{y_{k}^{T} s_{k}}\right)^{-1} +\left( B_{k} +\frac{y_{k} y_{k}^{T}}{y_{k}^{T} s_{k}}\right)^{-1}\left(\frac{B_{k} s_{k} s_{k}^{T} B_{k}}{s_{k}^{T} B_{k} s_{k} -s_{k}^{T} B_{k}\left( B_{k} +\frac{y_{k} y_{k}^{T}}{y_{k}^{T} s_{k}}\right)^{-1} B_{k} s_{k}}\right)\left( B_{k} +\frac{y_{k} y_{k}^{T}}{y_{k}^{T} s_{k}}\right)^{-1}\\ = & \left( B_{k}^{-1} -\frac{B_{k}^{-1} y_{k} y_{k}^{T} B_{k}^{-1}}{y_{k}^{T} s_{k} +y_{k}^{T} B_{k}^{-1} y_{k}}\right)\\ + & \left( B_{k}^{-1} -\frac{B_{k}^{-1} y_{k} y_{k}^{T} B_{k}^{-1}}{y_{k}^{T} s_{k} +y_{k}^{T} B_{k}^{-1} y_{k}}\right)\left(\frac{B_{k} s_{k} s_{k}^{T} B_{k}}{s_{k}^{T} B_{k} s_{k} -s_{k}^{T} B_{k}\left( B_{k}^{-1} -\frac{B_{k}^{-1} y_{k} y_{k}^{T} B_{k}^{-1}}{y_{k}^{T} s_{k} +y_{k}^{T} B_{k}^{-1} y_{k}}\right) B_{k} s_{k}}\right)\left( B_{k}^{-1} -\frac{B_{k}^{-1} y_{k} y_{k}^{T} B_{k}^{-1}}{y_{k}^{T} s_{k} +y_{k}^{T} B_{k}^{-1} y_{k}}\right)\\ = & \left( B_{k}^{-1} -\frac{B_{k}^{-1} y_{k} y_{k}^{T} B_{k}^{-1}}{y_{k}^{T} s_{k} +y_{k}^{T} B_{k}^{-1} y_{k}}\right)\\ + & \left( B_{k}^{-1} -\frac{B_{k}^{-1} y_{k} y_{k}^{T} B_{k}^{-1}}{y_{k}^{T} s_{k} +y_{k}^{T} B_{k}^{-1} y_{k}}\right)\left(\frac{B_{k} s_{k} s_{k}^{T} B_{k}}{\frac{s_{k}^{T} y_{k} y_{k}^{T} s_{k}}{y_{k}^{T} s_{k} +y_{k}^{T} B_{k}^{-1} y_{k}}}\right)\left( B_{k}^{-1} -\frac{B_{k}^{-1} y_{k} y_{k}^{T} B_{k}^{-1}}{y_{k}^{T} s_{k} +y_{k}^{T} B_{k}^{-1} y_{k}}\right)\\ = & \left( B_{k}^{-1} -\frac{B_{k}^{-1} y_{k} y_{k}^{T} B_{k}^{-1}}{y_{k}^{T} s_{k} +y_{k}^{T} B_{k}^{-1} y_{k}}\right) +\left(\frac{s_{k} s_{k}^{T}}{\frac{s_{k}^{T} y_{k} y_{k}^{T} s_{k}}{y_{k}^{T} s_{k} +y_{k}^{T} B_{k}^{-1} y_{k}}}\right) -\frac{B_{k}^{-1} y_{k}\left( y_{k}^{T} s_{k}\right) s_{k}^{T}}{s_{k}^{T} y_{k}\left( y_{k}^{T} s_{k}\right)} -\frac{s_{k}\left( s_{k}^{T} y_{k}\right) y_{k}^{T} B_{k}^{-1}}{\left( s_{k}^{T} y_{k}\right) y_{k}^{T} s_{k}}\\ + & \frac{B_{k}^{-1} y_{k}\left( y_{k}^{T} s_{k}\right)\left( s_{k}^{T} y_{k}\right) y_{k}^{T} B_{k}^{-1}}{\left( y_{k}^{T} s_{k} +y_{k}^{T} B_{k}^{-1} y_{k}\right)\left( s_{k}^{T} y_{k}\right)\left( y_{k}^{T} s_{k}\right)}\\ = & B_{k}^{-1} +\frac{s_{k}\left( y_{k}^{T} s_{k} +y_{k}^{T} B_{k}^{-1} y_{k}\right) s_{k}^{T}}{\left( s_{k}^{T} y_{k}\right)^{2}} -B_{k}^{-1}\frac{y_{k} s_{k}^{T}}{s_{k}^{T} y_{k}} -\frac{s_{k} y_{k}^{T}}{y_{k}^{T} s_{k}} B_{k}^{-1}\\ = & \left( I-\frac{s_{k} y_{k}^{T}}{y_{k}^{T} s_{k}}\right) B_{k}^{-1}\left( I-\frac{y_{k} s_{k}^{T}}{s_{k}^{T} y_{k}}\right) +\frac{s_{k} s_{k}^{T}}{s_{k}^{T} y_{k}} \end{aligned}$

定义 $\displaystyle \rho _{k} =\frac{1}{s_{k}^{T} y_{k}}$ ，我们有：

$\begin{equation*} H_{k+1} =\left( I-\rho _{k} s_{k} y_{k}^{T}\right) H_{k}\left( I-\rho _{k} y_{k} s_{k}^{T}\right) +\rho _{k} s_{k} s_{k}^{T} \end{equation*}$

步长选取

综合上面的方法，可见他们实际上具有统一的形式，即：

$\begin{gather} \boldsymbol{x}_{k+1} =\boldsymbol{x}_{k} +\alpha _{k}\boldsymbol{p}_{k}\\ \notag\\ \boldsymbol{p}_{k} =-\boldsymbol{B}_{k} \nabla f_{k} \end{gather}$

不同的方法对应于 $\displaystyle \boldsymbol{B}_{k}$ 不同的选取方式：

$\begin{equation} \begin{cases} \boldsymbol{B}_{k} =\boldsymbol{I} & \text{最速降线法}\\ \boldsymbol{B}_{k} =\left( \nabla ^{2} f_{k}\right)^{-1} & \text{牛顿法}\\ \boldsymbol{B}_{k+1} =\boldsymbol{B}_{k} +\frac{(\boldsymbol{y}_{k} -\boldsymbol{B}_{k}\boldsymbol{s}_{k})(\boldsymbol{y}_{k} -\boldsymbol{B}_{k}\boldsymbol{s}_{k})^{T}}{(\boldsymbol{y}_{k} -\boldsymbol{B}_{k}\boldsymbol{s}_{k})^{T}\boldsymbol{s}_{k}} & SR1\\ \boldsymbol{B}_{k+1} =\boldsymbol{B}_{k} -\frac{\boldsymbol{B}_{k}\boldsymbol{s}_{k}\boldsymbol{s}_{k}^{T}\boldsymbol{B}_{k}}{\boldsymbol{s}_{k}^{T}\boldsymbol{B}_{k}\boldsymbol{s}_{k}} +\frac{\boldsymbol{y}_{k}\boldsymbol{y}_{k}^{T}}{\boldsymbol{y}_{k}^{T}\boldsymbol{s}_{k}} & BFGS \end{cases} \end{equation}$

而对于搜索步长 $\displaystyle \alpha$ 的选取，一种自然的考虑是令：

$\begin{equation*} \alpha =\underset{\beta }{\min\arg} f(\boldsymbol{x}_{k} +\beta \boldsymbol{p}_{k}) \end{equation*}$

虽然这能让步长取得最优，但这样的方法往往由于庞大的计算量使得实际不可行，所以更加常见的做法是采用不精确的线搜索

线搜索过程由两个部分组成：首先根据一些标准划定包含理想步长的区间，而后再通过二分法或插值法在这些区间中确定理想步长

沃尔夫条件

通过启发式方法，我们定义了如下的沃尔夫条件

$\begin{gather} \begin{aligned} f(\boldsymbol{x}_{k} +\alpha _{k}\boldsymbol{p}_{k}) & \leq f(\boldsymbol{x}_{k}) +c_{1} \alpha _{k} \nabla f_{k}^{T}\boldsymbol{p}_{k} \end{aligned}\\ \notag\\ \nabla f(\boldsymbol{x}_{k} +\alpha _{k}\boldsymbol{p}_{k})^{T}\boldsymbol{p}_{k} \geq c_{2} \nabla f_{k}^{T}\boldsymbol{p}_{k} \end{gather}$

以及强沃尔夫条件：

$\begin{gather} \begin{aligned} f(\boldsymbol{x}_{k} +\alpha _{k}\boldsymbol{p}_{k}) & \leq f(\boldsymbol{x}_{k}) +c_{1} \alpha _{k} \nabla f_{k}^{T}\boldsymbol{p}_{k} \end{aligned}\\ \notag\\ |\nabla f(\boldsymbol{x}_{k} +\alpha _{k}\boldsymbol{p}_{k})^{T}\boldsymbol{p}_{k} |\leq c_{2} \nabla f_{k}^{T}\boldsymbol{p}_{k} \end{gather}$

这里 $\displaystyle 0< c_{1} < c_{2} < 1$

条件 (96) 有时被称为 Armijo条件，这保证了在线搜索过程中，目标函数在每次迭代均能充分减少

$\displaystyle \nabla f_{k}^{T} \cdot \boldsymbol{p}_{k} < 0\Rightarrow$ 条件 (97) 保证了下个迭代点的斜率不应过小，否则我们总能在该点附近找到显著更优的迭代点

强沃尔夫条件与沃尔夫条件在于条件 (28) 要求迭代点的斜率不能过大，排除了部分迭代点过于远离最优点的情况

$\displaystyle f\in C^{1}\left(\mathbb{R}^{n}\right)$ ， $\displaystyle \boldsymbol{x}_{k} ,\boldsymbol{p}_{k} \in \mathbb{R}^{n}$ ，并且：

$\begin{equation} \phi ( \alpha ) :=f(\boldsymbol{x}_{k} +\alpha \boldsymbol{p}_{k} |\alpha >0) \end{equation}$

存在下界， $\displaystyle 0< c_{1} < c_{2} < 1$ ， $\displaystyle \nabla f_{k}^{T}\boldsymbol{p}_{k} < 0$ ，则存在满足强沃尔夫条件与沃尔夫条件的步长区间

定义 $\displaystyle l( \alpha ) =f(\boldsymbol{x}_{k}) +\alpha c_{1} \nabla f_{k}^{T}\boldsymbol{p}_{k}$ ， $\displaystyle g( \alpha ) =l( \alpha ) -\phi ( \alpha )$ ，则 $\displaystyle \phi ( \alpha )$ 有下界， $\displaystyle \nabla f_{k}^{T}\boldsymbol{p}_{k}$ $\displaystyle \Rightarrow$ ：

$\begin{gather} g( 0) =0,\ g'( 0) >0,\ g( \alpha )\rightarrow -\infty \\ \notag\\ \Longrightarrow \ \exists \ \alpha ' >0\ s.t.\ l( \alpha ') =\phi ( \alpha ') \ ;\quad \ l( \alpha ) >\phi ( \alpha ) ,\ \forall \alpha \in ( 0,\alpha ')\\ \notag\\ \Longrightarrow \begin{aligned} f(\boldsymbol{x}_{k} +\alpha _{k}\boldsymbol{p}_{k}) & \leq f(\boldsymbol{x}_{k}) +c_{1} \alpha _{k} \nabla f_{k}^{T}\boldsymbol{p}_{k} \end{aligned} \quad \quad \forall \alpha _{k} \in ( 0,\alpha ') \end{gather}$

再由中值定理， $\displaystyle \exists \ \alpha ''\in ( 0,\alpha ') \ s.t.$ ：

$\begin{gather} f(\boldsymbol{x}_{k} +\alpha '\boldsymbol{p}_{k}) -f(\boldsymbol{x}_{k}) =\alpha '\nabla f(\boldsymbol{x}_{k} +\alpha ''\boldsymbol{p}_{k})^{T}\boldsymbol{p}_{k}\\ \notag\\ \Longrightarrow \nabla f(\boldsymbol{x}_{k} +\alpha ''\boldsymbol{p}_{k})^{T}\boldsymbol{p}_{k} =\frac{f(\boldsymbol{x}_{k} +\alpha '\boldsymbol{p}_{k}) -f(\boldsymbol{x}_{k})}{\alpha '} =c_{1} \nabla f_{k}^{T}\boldsymbol{p}_{k} >c_{2} \nabla f_{k}^{T}\boldsymbol{p}_{k}\notag \end{gather}$

$\displaystyle f(\boldsymbol{x}_{k} +\alpha '\boldsymbol{p}_{k}) -f(\boldsymbol{x}_{k}) < 0\Rightarrow \ :$

$\begin{equation} |\nabla f(\boldsymbol{x}_{k} +\alpha ''\boldsymbol{p}_{k})^{T}\boldsymbol{p}_{k} |< c_{2} |\nabla f_{k}^{T}\boldsymbol{p}_{k} | \end{equation}$

$\displaystyle \Rightarrow \alpha ''$ 附近的一个邻域即为待求区间

对于由：

$\begin{equation} \boldsymbol{x}_{k+1} =\boldsymbol{x}_{k} +\alpha _{k}\boldsymbol{p}_{k} \end{equation}$

确定的递归方式，若 $\displaystyle \alpha _{k}$ 满足沃尔夫条件， $\displaystyle f$ 存在下界，在一个包含 $\displaystyle \mathcal{L} :=\{x|f( x) \leq f( x_{0})\}$ 的开集内连续可微，并且 $\displaystyle \exists \ L >0\ s.t.$

$\begin{equation} \| \nabla f( x) -\nabla f(\overline{x}) \| \leq L\| x-\overline{x} \| ,\ \forall x,\overline{x} \in \mathcal{L} \end{equation}$

则：

$\begin{equation} \sum _{k\geq 0}\cos^{2} \theta _{k} \| \nabla f_{k} \| ^{2} < \infty ,\quad \quad \text{这里} \ \ \cos \theta _{k} =-\frac{\nabla f_{k}^{T} \cdotp \boldsymbol{p}_{k}}{\| \boldsymbol{p}_{k} \| \| \nabla f_{k} \| } \end{equation}$

由 (97) ，可得：

$\begin{equation} ( \nabla f_{k+1} -\nabla f_{k})^{T}\boldsymbol{p}_{k} \geq ( c_{1} -1) \nabla f_{k}^{T}\boldsymbol{p}_{k} \end{equation}$

再由李氏条件：

$\begin{gather} ( \nabla f_{k+1} -\nabla f_{k})^{T}\boldsymbol{p}_{k} \leq \alpha _{k} L\| \boldsymbol{p}_{k} \| ^{2}\\ \notag\\ \Longrightarrow \alpha _{k} \geq \frac{c_{2} -1}{L}\frac{\nabla f_{k}^{2}\boldsymbol{p}_{k}}{\| \boldsymbol{p}_{k} \| ^{2}} \end{gather}$

代入 Armijo条件，得：

$\begin{gather} f_{k-1} \leq f_{k} -c_{1}\frac{1-c_{2}}{L}\frac{\left( \nabla f_{k}^{T}\boldsymbol{p}_{k}\right)^{2}}{\| \boldsymbol{p}_{k} \| ^{2}} =f_{k} -c\cos^{2} \theta _{k} \| \nabla f_{k} \| ^{2}\\ \notag\\ \Longrightarrow \sum _{k=0}^{\infty }\cos^{2} \theta _{k} \| \nabla f_{k} \| ^{2} < \infty \end{gather}$

这里 $\displaystyle c=c_{1} -\frac{1-c_{2}}{L}$

(108) 也被称为The Zoutendijk condition，若 $\displaystyle \exists \ \delta >0\ s.t.$

$\begin{equation} \cos \theta _{k} \geq \delta >0 \end{equation}$

则：

$\begin{equation} \lim _{k\rightarrow \infty } \| \Delta f_{k} \| \rightarrow 0 \end{equation}$

意味着在此条件下，算法必定能够收敛到局部最优，若优化函数为凸函数，则可收敛到全局最优

$\displaystyle B_{k}$ 为正定对称阵，并且 $\displaystyle \exists \ M\ s.t.$

$\begin{equation} \| \boldsymbol{B}_{k} \| \cdotp \| \boldsymbol{B}_{k}^{-1} \| \leq M \end{equation}$

则：

$\begin{equation} \cos \theta _{k} \geq \frac{1}{\sqrt{M}} \end{equation}$

$\displaystyle \boldsymbol{B}_{k}$ 为对称正定阵 $\displaystyle \Rightarrow \exists$ 对称正定阵 $\displaystyle \boldsymbol{B}_{k}^{1/2} \ s.t.\ \boldsymbol{B}_{k} =\left(\boldsymbol{B}_{k}^{1/2}\right)^{T}\boldsymbol{B}_{k}^{1/2}$ ，随后 $\displaystyle \boldsymbol{p}_{k} =-\boldsymbol{B}_{k}^{-1} \nabla f_{k} \Rightarrow \ :$

$\begin{equation} \begin{aligned} \cos \theta _{k} & =\frac{( \nabla f_{k})^{T}\boldsymbol{B}_{k}^{-1} \nabla f_{k}}{\| \nabla f_{k} \| \cdotp \| \boldsymbol{B}_{k}^{-1} \nabla f_{k} \| }\\ & =\frac{\boldsymbol{p}_{k}^{T}\boldsymbol{B}_{k}\boldsymbol{p}_{k}}{\| \boldsymbol{B}_{k}\boldsymbol{p}_{k} \| \cdotp \| \boldsymbol{p}_{k} \| } =\frac{\tilde{\boldsymbol{p}}_{k}^{T}\tilde{\boldsymbol{p}}_{k}}{\| \boldsymbol{B}_{k}^{1/2}\tilde{\boldsymbol{p}}_{k} \| \cdotp \| \boldsymbol{B}_{k}^{-1/2}\tilde{\boldsymbol{p}}_{k} \| }\\ & \geq \frac{\| \tilde{\boldsymbol{p}}_{k} \| ^{2}}{\| \tilde{\boldsymbol{p}}_{k} \| ^{2} \cdot \| \boldsymbol{B}_{k}^{1/2} \| \cdot \| \boldsymbol{B}_{k}^{-1/2} \| } \geq \frac{1}{\sqrt{M}} \end{aligned} \end{equation}$

运筹学 ​

线性规划 ​

标准形式 ​

应用 ​

食材采购问题 ​

产品生产问题 ​

货物转运问题 ​

网络流量问题 ​

店铺运营问题 ​

赌马比赛 ​

马尔可夫决策过程 ​

规划问题求解 ​

卡拉泰奥多里定理 ​

法卡斯引理与替代系统 ​

几何对应 ​

极点与基本解的等价性 ​

主问题与对偶问题 ​

（对偶）食材采购问题 ​

（对偶）货物转运问题 ​

（对偶）赌马比赛 ​

（对偶）马尔可夫决策过程 ​

对偶定理 ​

无约束优化问题 ​

线搜索策略 ​

最速降线法 ​

牛顿法 ​

准牛顿法 ​

步长选取 ​

沃尔夫条件 ​

运筹学

线性规划

标准形式

应用

食材采购问题

产品生产问题

货物转运问题

网络流量问题

店铺运营问题

赌马比赛

马尔可夫决策过程

规划问题求解

卡拉泰奥多里定理

法卡斯引理与替代系统

几何对应

极点与基本解的等价性

主问题与对偶问题

（对偶）食材采购问题

（对偶）货物转运问题

（对偶）赌马比赛

（对偶）马尔可夫决策过程

对偶定理

无约束优化问题

线搜索策略

最速降线法

牛顿法

准牛顿法

步长选取

沃尔夫条件