JZTXT

线性规划学习笔记

发布时间 2023-04-12 18:45:49作者: Watware

定义

线性规划是一类最优化问题，例如：

\[\begin{aligned} \min{\ x_1+2x_2}& \\ s.t.\ x_1+x_2\le 3&\\ x_2\le 2&\\ x_1\ge 0&\\ x_2\ge 0 \end{aligned} \]

（s.t. 是 subject to 的缩写）
简单来说，对于一系列变量，我们在一系列线性约束的范围内找到一个线性函数的最值。
下文称 \(x\in\mathbb{R}^n\ge 0\) 为 \(x\) 的各个分量 \(\ge 0\)。

标准形式

注意到对于所有线性规划问题，我们都能把它变换到如下标准形式：

\[\min_{x\in \mathbb{R}^n}{c^Tx}\\ s.t.\ Ax=b,\forall i,x_i\ge 0\\ that\ A\in\mathbb{R}^{m\times n},b\in\mathbb{R}^m,c\in\mathbb{R}^n \]

  • 对于变量 \(x\ge c\)，用 \(x'=x-c\ge 0\) 替代。
  • 对于变量 \(x\le c\)，用 \(x'=c-x\ge 0\) 替代。
  • 对于变量 \(x\) 无约束，考虑两个非负变量 \(x_1,x_2\ge 0\)，令 \(x=x_1-x_2\)。

至此所有变量 \(x\) 都满足非负性，接下来处理不等式：
对于不等式 \(\sum a_ix_i\le c\)，考虑新建一个松弛变量 \(s\ge 0\)，则有 \(\sum a_ix_i+s=c\)。反方向不等式同理。

注意到线性规划中我们一般不会碰到严格不等关系：如果我们将这些关系换成不严格的，那么要么存在满足严格条件的最优解，要么我们可以无穷接近最优解。

单纯形法

TODO.....

对偶问题

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

\[p^*=\min_{x\in \mathbb{R}^n}{c^Tx}\\ s.t.\ Ax=b,x\ge 0\\ \]

引入拉格朗日乘子 \(\lambda\in\mathbb{R}^n\)，相当于要求：

\[f(x,\lambda)=c^Tx+\lambda^T(Ax-b)\\ h^*=\min_{x}\max_{\lambda}\ f(x,\lambda)\\ s.t.\ x\ge 0 \]

证明：

如果 \(Ax\ne b\)，那么在内层的 \(\max\) 中我们可以取 \(\lambda\rightarrow\pm\infin\) 使得内层 \(\max_{\lambda}f(x,\lambda)\) 趋向于正无穷，不会计入答案。
这同时也告诉我们如果 \(D^*\rightarrow +\infin\) 则原问题无解。

考虑对偶问题：以 \(x\) 为主元，我们可以证明，对任意 \(\lambda\)，\(\min_{x}f(x,\lambda)\) 是 \(h^*\) 的一个下界。

证明：

对于一个特定的 \(\lambda_1\) 和任意的 \(x_1\)，我们有

\[\begin{align*} &\min_{x}f(x,\lambda_1)\le f(x_1,\lambda_1)\le \max_{\lambda}f(x_1,\lambda) \\\Rightarrow&\forall \lambda_1,\min_{x}f(x,\lambda_1)\le \min_{x}\max_{\lambda}f(x,\lambda)=h^* \end{align*} \]

取最紧的下界

\[\begin{align*} p^*&=\max_{\lambda}\min_{x}\ f(x,\lambda)\\ &=\max_{\lambda}\min_{x}\ c^Tx+\lambda^T(Ax-b)\\ &=\max_{\lambda}\min_{x}\ (c^T+\lambda^T A)x-\lambda^T b & (x\ge 0) \end{align*} \]

注意到若 \((c^T+\lambda^TA)_i< 0\)，则令 \(x_i\rightarrow +\infin,x_j=0(i\ne j)\)，有 \(f(x,\lambda)\rightarrow -\infin\)，故必然有 \(c^T+\lambda^TA\ge 0\)，此时必然有 \(x=\mathbf{0}\)，故

\[d^*=\max_{\lambda}-\lambda^Tb\\ s.t.\ c^T+\lambda^TA\ge 0 \]

记 \(w=-\lambda\)，有

\[d^*=\max_{w}w^Tb\\ s.t.\ A^T\lambda\le c \]

同样是一个线性规划问题，称为 \(P^*\) 的对偶问题。
总结一下：

\[\begin{gather*} p^*=\min_{x}{c^Tx}\\ s.t.\ Ax=b,x\ge 0\\ \end{gather*} \ \ \stackrel{dual}{\Longleftrightarrow}\ \ \begin{gather*} d^*=\max_{w}b^Tw\\ s.t.\ A^Tw\le c,w\ge 0 \end{gather*} \]

强对偶定理

由上文的论述我们知道必然有 \(d^*\le p^*\) 称为弱对偶定理。事实上，线性规划满足强对偶定理：
对于互为对偶的线性规划问题 \(d^*,p^*\)，必然满足以下三种情况中的一个：

  • \(d^*,p^*\) 都不存在可行解。
  • \(d^*,p^*\) 一个不存在可行解，一个最优解无界。
  • \(d^*,p^*\) 皆有有界最优解，此时必然有两者的解相同。
证明：

情况一和二易见，对于情况三，记 \(x_0\) 是 \(d^*\) 的最优解，