最优化理论与算法第2章：线性规划的基本性质

本文的内容主要来自陈宝林的《最优化理论与算法（第2版）》第2章《线性规划的基本性质》。

标准形式及图解法

标准形式

一般线性规划问题，可以写成下列标准形式：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T\vec{x} \\ \text{s. t.} \;\;\;\;& \mathbf{A}\vec{x}=\vec{b} \\ \;\;\;\;& \vec{x}\geq\vec{0} \end{aligned}$$

其中$\vec{c},\vec{x}\in\mathbb{R}^n$，$\mathbf{A}\in\mathbb{R}^{m\times n}$，$\vec{b}\in\mathbb{R}^m$。同时一般假定$\vec{b}\geq\vec{0}$。

极大化转换：若优化目标为$\max$，则另$\vec{c}’=-\vec{c}$。

约束方程常量为负：若$b_i<0$，另$b_i=-b_i’,a_{ij}=-a_{ij}’$。

决策变量无非负限制：若$x_j$无非负限制，可以另$x_j=x_j’-x_j’’$，其中$x_j’,x_j’’\geq 0$。

决策变量有上下界：若$x_j\geq l_j$，另$x_j’=x_j-l_j$；若$x_j\leq u_j$，另$x_j’=u_j-x_j$。注：此方法与约束方程为不等式类似，如果同时存在上下界，就引入松弛变量。

约束方程为不等式：若给定的问题为：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T\vec{x} \\ \text{s. t.} \;\;\;\;& \mathbf{A}\vec{x}\leq\vec{b} \\ \;\;\;\;& \vec{x}\geq\vec{0} \end{aligned}$$

可以引入松弛变量$\vec{x}’\in\mathbb{R}^m$，化为下列标准式：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T\vec{x} \\ \text{s. t.} \;\;\;\;& \mathbf{A}\vec{x}+\vec{x}’=\vec{b} \\ \;\;\;\;& \begin{bmatrix}\vec{x}\\\vec{x}’\end{bmatrix}\geq\vec{0} \end{aligned}$$

类似地，对于$\mathbf{A}\vec{x}\geq\vec{b}$，可以引入剩余变量。

含有绝对值：若给定的问题为（这里使用$|\cdot|$表示逐个元素的绝对值）：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T|\vec{x}| \\ \text{s. t.} \;\;\;\;& \mathbf{A}\vec{x}=\vec{b} \end{aligned}$$

可以引入$\vec{u}=\frac{|\vec{x}|+\vec{x}}{2},\vec{v}=\frac{|\vec{x}|-\vec{x}}{2}$，于是我们有$\vec{u},\vec{v}>\vec{0},\vec{x}=\vec{u}-\vec{v},|\vec{x}|=\vec{u}+\vec{v}$，化为下列标准式：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T(\vec{u}+\vec{v}) \\ \text{s. t.} \;\;\;\;& \mathbf{A}(\vec{u}-\vec{v})=\vec{b} \\ \;\;\;\;& \begin{bmatrix}\vec{u}\\\vec{v}\end{bmatrix}\geq\vec{0} \end{aligned}$$

TODO: 写个程序演示一下？

图解法

线性不等式的几何意义是半平面，因此对于两变量线性规划，可以使用图解法：

作出线性规划问题的可行域；
作出目标函数的等值线；
移动等值线到可行域边界得到最优点。

注意，目标函数的梯度指向目标函数增大的方向。

线性规划可能存在无穷多个最优解，这些解组成了可行域的一条边；线性规划可行域为空集，则线性规划无解。若可行域无界，则该线性规划可能无界，即不存在有限最优值（这种情况也是无最优解）。

$$\text{线性规划问题} \begin{cases} \text{有可行解} \begin{cases} \text{有最优解} \begin{cases} \text{唯一解} \\ \text{无穷多解} \end{cases} \\ \text{无界（必要条件是可行域无界）} \end{cases} \\ \text{有可行解} \end{cases}$$

基本性质

可行域

定理2.2.1 约束条件为线性等式或者不等式的线性规划的可行域是凸集。

注：由凸集的有限交是凸集即可得证。

最优极点

考虑标准形式的可行域，其极点为$\vec{x}_1,\cdots,\vec{x}_k$，极方向为$\vec{d}_1,\cdots,\vec{d}_l$，由表示定理可以知道，可行点$\vec{x}$可以表示为：

$$\begin{aligned} &\vec{x}=\sum_{j=1}^k\lambda_j\vec{x}_{j}+\sum_{j=1}^l\mu_j\vec{d}_j\\ &\sum_{j=1}^k\lambda_j=1,\\ &\lambda_j\geq 0, j=1,\cdots,k,\\ &\mu_j\geq 0, j=1,\cdots,l. \end{aligned}$$

代入标准形式：

$$\begin{aligned} \min \;\;\;\;&\sum_{j=1}^k\lambda_j\vec{c}^T\vec{x}_j+\sum_{j=1}^l\mu_j\vec{c}^T\vec{d}_j \\ \text{s. t.} \;\;\;\;&\sum_{j=1}^k\lambda_j=1, \\ \;\;\;\;&\lambda_j\geq 0, j=1,\cdots,k,\\ \;\;\;\;&\mu_j\geq 0, j=1,\cdots,l. \end{aligned}$$

若某个$\vec{c}^T\vec{d}_j<0$，则$\mu_j$可以取很大，问题成为了无界。所以有界的充要条件是所有$\vec{c}^T\vec{d}_j\geq 0$。有界的最优解一定有$\mu_j=0$。所以对于有界的问题，简化成了：

$$\begin{aligned} \min \;\;\;\;&\sum_{j=1}^k\lambda_j\vec{c}^T\vec{x}_j \\ \text{s. t.} \;\;\;\;&\sum_{j=1}^k\lambda_j=1, \\ \;\;\;\;&\lambda_j\geq 0, j=1,\cdots. \end{aligned}$$

这时，令：

$$\vec{x}_p=\underset{\vec{x}_j,j=1,\cdots,k}{\operatorname{arg,min}}\;\vec{c}^T\vec{x}_j$$

则：

$$\min\sum_{j=1}^k\lambda_j\vec{c}^T\vec{x}_j=\vec{c}^T\vec{x}_p\;\;\;\;\text{此时}\lambda _j=\begin{cases} 1, &j=p \\ 0, &j\neq p \end{cases}$$

定理2.2.2 设标准形式的线性规划可行域非空，则有下列结论：

存在最优解（这里的存在是指有限的）的充要条件是$\vec{c}\vec{d}_j\geq 0$，其中$\vec{d}_j$为可行域极方向；
若存在最优解，则最优解可在某个极点上达到。

最优基本可行解

对标准形式的线性规划，若$r(\mathbf{A})=m$，可将$\mathbf{A}$列调换后，得到矩阵$\mathbf{A}=[\mathbf{B},\mathbf{N}]$，其中$\mathbf{B}\in\mathbb{R}^{m\times m}$为满秩方阵。$\vec{x}$进行对应的行变换，可以得到$\vec{x}=\begin{bmatrix}\vec{x}_B\\\vec{x}_N\end{bmatrix}$，于是约束条件可以写为：

$$\begin{aligned} & [\mathbf{B},\mathbf{N}]\begin{bmatrix}\vec{x}_B\\\vec{x}_N\end{bmatrix}=\vec{b} \\ \Rightarrow&\mathbf{B}\vec{x}_B+\mathbf{N}\vec{x}_N=\vec{b}\\ \Rightarrow&\vec{x}_B=\mathbf{B}^{-1}\vec{b}-\mathbf{B}^{-1}\mathbf{N}\vec{x}_N \end{aligned}$$

其中$\vec{x}_N$的分量是自由分量，令$\vec{x}_N=\vec{0}$，可得到一个解：

$$\vec{x}=\begin{bmatrix}\vec{x}_B\\\vec{x}_N\end{bmatrix}=\begin{bmatrix}\mathbf{B}^{-1}\vec{b}\\\vec{0}\end{bmatrix}$$

定义2.2.1 对于：...

本文的内容主要来自陈宝林的《最优化理论与算法（第2版）》第2章《线性规划的基本性质》。

标准形式及图解法

标准形式

一般线性规划问题，可以写成下列标准形式：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T\vec{x} \\ \text{s. t.} \;\;\;\;& \mathbf{A}\vec{x}=\vec{b} \\ \;\;\;\;& \vec{x}\geq\vec{0} \end{aligned}$$

其中$\vec{c},\vec{x}\in\mathbb{R}^n$，$\mathbf{A}\in\mathbb{R}^{m\times n}$，$\vec{b}\in\mathbb{R}^m$。同时一般假定$\vec{b}\geq\vec{0}$。

极大化转换：若优化目标为$\max$，则另$\vec{c}’=-\vec{c}$。

约束方程常量为负：若$b_i<0$，另$b_i=-b_i’,a_{ij}=-a_{ij}’$。

决策变量无非负限制：若$x_j$无非负限制，可以另$x_j=x_j’-x_j’’$，其中$x_j’,x_j’’\geq 0$。

约束方程为不等式：若给定的问题为：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T\vec{x} \\ \text{s. t.} \;\;\;\;& \mathbf{A}\vec{x}\leq\vec{b} \\ \;\;\;\;& \vec{x}\geq\vec{0} \end{aligned}$$

可以引入松弛变量$\vec{x}’\in\mathbb{R}^m$，化为下列标准式：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T\vec{x} \\ \text{s. t.} \;\;\;\;& \mathbf{A}\vec{x}+\vec{x}’=\vec{b} \\ \;\;\;\;& \begin{bmatrix}\vec{x}\\\vec{x}’\end{bmatrix}\geq\vec{0} \end{aligned}$$

类似地，对于$\mathbf{A}\vec{x}\geq\vec{b}$，可以引入剩余变量。

含有绝对值：若给定的问题为（这里使用$|\cdot|$表示逐个元素的绝对值）：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T|\vec{x}| \\ \text{s. t.} \;\;\;\;& \mathbf{A}\vec{x}=\vec{b} \end{aligned}$$

TODO: 写个程序演示一下？

图解法

线性不等式的几何意义是半平面，因此对于两变量线性规划，可以使用图解法：

作出线性规划问题的可行域；
作出目标函数的等值线；
移动等值线到可行域边界得到最优点。

注意，目标函数的梯度指向目标函数增大的方向。

基本性质

可行域

定理2.2.1 约束条件为线性等式或者不等式的线性规划的可行域是凸集。

注：由凸集的有限交是凸集即可得证。

最优极点

考虑标准形式的可行域，其极点为$\vec{x}_1,\cdots,\vec{x}_k$，极方向为$\vec{d}_1,\cdots,\vec{d}_l$，由表示定理可以知道，可行点$\vec{x}$可以表示为：

$$\begin{aligned} &\vec{x}=\sum_{j=1}^k\lambda_j\vec{x}_{j}+\sum_{j=1}^l\mu_j\vec{d}_j\\ &\sum_{j=1}^k\lambda_j=1,\\ &\lambda_j\geq 0, j=1,\cdots,k,\\ &\mu_j\geq 0, j=1,\cdots,l. \end{aligned}$$

代入标准形式：

$$\begin{aligned} \min \;\;\;\;&\sum_{j=1}^k\lambda_j\vec{c}^T\vec{x}_j \\ \text{s. t.} \;\;\;\;&\sum_{j=1}^k\lambda_j=1, \\ \;\;\;\;&\lambda_j\geq 0, j=1,\cdots. \end{aligned}$$

这时，令：

$$\vec{x}_p=\underset{\vec{x}_j,j=1,\cdots,k}{\operatorname{arg,min}}\;\vec{c}^T\vec{x}_j$$

则：

$$\min\sum_{j=1}^k\lambda_j\vec{c}^T\vec{x}_j=\vec{c}^T\vec{x}_p\;\;\;\;\text{此时}\lambda _j=\begin{cases} 1, &j=p \\ 0, &j\neq p \end{cases}$$

定理2.2.2 设标准形式的线性规划可行域非空，则有下列结论：

存在最优解（这里的存在是指有限的）的充要条件是$\vec{c}\vec{d}_j\geq 0$，其中$\vec{d}_j$为可行域极方向；
若存在最优解，则最优解可在某个极点上达到。

最优基本可行解

其中$\vec{x}_N$的分量是自由分量，令$\vec{x}_N=\vec{0}$，可得到一个解：

$$\vec{x}=\begin{bmatrix}\vec{x}_B\\\vec{x}_N\end{bmatrix}=\begin{bmatrix}\mathbf{B}^{-1}\vec{b}\\\vec{0}\end{bmatrix}$$

定义2.2.1 对于：...

本文的内容主要来自陈宝林的《最优化理论与算法（第2版）》第2章《线性规划的基本性质》。

标准形式及图解法

标准形式

一般线性规划问题，可以写成下列标准形式：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T\vec{x} \\ \text{s. t.} \;\;\;\;& \mathbf{A}\vec{x}=\vec{b} \\ \;\;\;\;& \vec{x}\geq\vec{0} \end{aligned}$$

其中$\vec{c},\vec{x}\in\mathbb{R}^n$，$\mathbf{A}\in\mathbb{R}^{m\times n}$，$\vec{b}\in\mathbb{R}^m$。同时一般假定$\vec{b}\geq\vec{0}$。

极大化转换：若优化目标为$\max$，则另$\vec{c}’=-\vec{c}$。

约束方程常量为负：若$b_i<0$，另$b_i=-b_i’,a_{ij}=-a_{ij}’$。

决策变量无非负限制：若$x_j$无非负限制，可以另$x_j=x_j’-x_j’’$，其中$x_j’,x_j’’\geq 0$。

约束方程为不等式：若给定的问题为：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T\vec{x} \\ \text{s. t.} \;\;\;\;& \mathbf{A}\vec{x}\leq\vec{b} \\ \;\;\;\;& \vec{x}\geq\vec{0} \end{aligned}$$

可以引入松弛变量$\vec{x}’\in\mathbb{R}^m$，化为下列标准式：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T\vec{x} \\ \text{s. t.} \;\;\;\;& \mathbf{A}\vec{x}+\vec{x}’=\vec{b} \\ \;\;\;\;& \begin{bmatrix}\vec{x}\\\vec{x}’\end{bmatrix}\geq\vec{0} \end{aligned}$$

类似地，对于$\mathbf{A}\vec{x}\geq\vec{b}$，可以引入剩余变量。

含有绝对值：若给定的问题为（这里使用$|\cdot|$表示逐个元素的绝对值）：

$$\begin{aligned} \min \;\;\;\;&\vec{c}^T|\vec{x}| \\ \text{s. t.} \;\;\;\;& \mathbf{A}\vec{x}=\vec{b} \end{aligned}$$

TODO: 写个程序演示一下？

图解法

线性不等式的几何意义是半平面，因此对于两变量线性规划，可以使用图解法：

作出线性规划问题的可行域；
作出目标函数的等值线；
移动等值线到可行域边界得到最优点。

注意，目标函数的梯度指向目标函数增大的方向。

基本性质

可行域

定理2.2.1 约束条件为线性等式或者不等式的线性规划的可行域是凸集。

注：由凸集的有限交是凸集即可得证。

最优极点

考虑标准形式的可行域，其极点为$\vec{x}_1,\cdots,\vec{x}_k$，极方向为$\vec{d}_1,\cdots,\vec{d}_l$，由表示定理可以知道，可行点$\vec{x}$可以表示为：

$$\begin{aligned} &\vec{x}=\sum_{j=1}^k\lambda_j\vec{x}_{j}+\sum_{j=1}^l\mu_j\vec{d}_j\\ &\sum_{j=1}^k\lambda_j=1,\\ &\lambda_j\geq 0, j=1,\cdots,k,\\ &\mu_j\geq 0, j=1,\cdots,l. \end{aligned}$$

代入标准形式：

$$\begin{aligned} \min \;\;\;\;&\sum_{j=1}^k\lambda_j\vec{c}^T\vec{x}_j \\ \text{s. t.} \;\;\;\;&\sum_{j=1}^k\lambda_j=1, \\ \;\;\;\;&\lambda_j\geq 0, j=1,\cdots. \end{aligned}$$

这时，令：

$$\vec{x}_p=\underset{\vec{x}_j,j=1,\cdots,k}{\operatorname{arg,min}}\;\vec{c}^T\vec{x}_j$$

则：

$$\min\sum_{j=1}^k\lambda_j\vec{c}^T\vec{x}_j=\vec{c}^T\vec{x}_p\;\;\;\;\text{此时}\lambda _j=\begin{cases} 1, &j=p \\ 0, &j\neq p \end{cases}$$

定理2.2.2 设标准形式的线性规划可行域非空，则有下列结论：

存在最优解（这里的存在是指有限的）的充要条件是$\vec{c}\vec{d}_j\geq 0$，其中$\vec{d}_j$为可行域极方向；
若存在最优解，则最优解可在某个极点上达到。

最优基本可行解

其中$\vec{x}_N$的分量是自由分量，令$\vec{x}_N=\vec{0}$，可得到一个解：

$$\vec{x}=\begin{bmatrix}\vec{x}_B\\\vec{x}_N\end{bmatrix}=\begin{bmatrix}\mathbf{B}^{-1}\vec{b}\\\vec{0}\end{bmatrix}$$

定义2.2.1 对于：...