线性代数|机器学习-P25线性规划和两人零和博弈

0. 概述

1. 线性规划[LP]问题
   线性规划是问题为线性求最值，约束也是求线性关系的问题，具体参考
   线性规划学习笔记
2. 最大流-最小割问题
   最大流-最小割问题是一个对偶问题，具体参考最大流最小割学习笔记
3. 两人游戏-对偶问题
4. 拉格朗日乘子法
   拉格朗日乘子法的引入是为了解决约束条件下的最优问题，通过强对偶理论和弱对偶理论来转换目标函数，具体参考强对偶，弱对偶理论学习笔记

1. 线性规划问题

1.1 定义

假设我们的原问题如下：

• 标准形式：
  $$\begin{array}{c}\begin{array}{rl}& (LP)\min c^{T}x\\ & st.Ax=b,x\ge 0\\ & x=(x_1,x_2,\cdots ,x_n{)}^T;x_i\ge 0\\ & c=(c_1,c_2,\cdots ,c_n{)}^T;x_i\ge 0\end{array}\end{array}$$
  其中,$c\in R^n,A\in R^{m\times n},b\in R^m$，通常假设系数矩阵A行满秩，即$r(A)=m<n$

1.2 举例

( L P ) min ⁡ { x 1 + 2 x 2 + 5 x 3 } s t . x 1 + x 2 + x 3 = 3 , x i ≥ 0 \begin{equation}\begin{aligned} &(LP)\; \;\min\; \{x_1+2x_2+5x_3\}\\ &st.\;\;x_1+x_2+x_3=3,x_i\ge 0\\ \end{aligned}\end{equation} ​(LP)min{x1​+2x2​+5x3​}st.x1​+x2​+x3​=3,xi​≥0​​​

• 根据单纯形法Simplex method,Dantzig
  —理论依据：若LP有最优解，则最优解可在极点取到
  – -基本思想： 找到一个极点 $\bar{x}$,判断$\bar{x}$是否最优；若$\bar{x}$不是最优，寻找一个更优(值更小)的极点
• 我们知道最小值只需要在三个极点上找即可，分别算出三个点的值后，取最小值即可是整个线性规划问题的最小值
  P 1 = ( 3 , 0 , 0 ) → y 1 = 3 + 2 ∗ 0 + 5 ∗ 0 = 3 P 2 = ( 0 , 3 , 0 ) → y 2 = 0 + 2 ∗ 3 + 5 ∗ 0 = 6 P 3 = ( 0 , 0 , 3 ) → y 3 = 0 + 2 ∗ 0 + 5 ∗ 3 = 15 min ⁡ ( 3 , 0 , 0 ) { x 1 + 2 x 2 + 5 x 3 } = 3 \begin{equation}\begin{aligned} &P_1=(3,0,0)\to y_1=3+2*0+5*0=3\\ &P_2=(0,3,0)\to y_2=0+2*3+5*0=6\\ &P_3=(0,0,3)\to y_3=0+2*0+5*3=15\\ & \min\limits_{(3,0,0)}\{x_1+2x_2+5x_3\}=3 \end{aligned}\end{equation} ​P1​=(3,0,0)→y1​=3+2∗0+5∗0=3P2​=(0,3,0)→y2​=0+2∗3+5∗0=6P3​=(0,0,3)→y3​=0+2∗0+5∗3=15(3,0,0)min​{x1​+2x2​+5x3​}=3​​​

2. 线性规划中的对偶问题

• 给出如下线性规划问题，求其对偶问题：
  $$\begin{array}{c}\begin{array}{rl}& \min c^{T}x\\ & st;Ax=b,x\ge 0,其中，c\in R^n,A\in R^{m\times n},b\in R^m\end{array}\end{array}$$
• 根据约束来拉格朗日函数：
  $$\begin{array}{c}L(x,\mu )=c^{T}x+{\mu }^T(b-Ax)\end{array}$$
• 找出拉格朗日函数的对偶问题,先选定一个x后，求最小，再求关于$\mu$的最大值：
  - max ⁡ μ min ⁡ x ≥ 0 { c T x + μ T ( b − A x ) } \begin{equation} \max\limits_{\mu}\min\limits_{x\ge0}\{c^Tx+\mu^T(b-Ax)\} \end{equation} μmax​x≥0min​{cTx+μT(b−Ax)}​​
• 先求内部最小值：
• 展开公式可得：
  - min ⁡ x ≥ 0 { c T x + μ T ( b − A x ) } = min ⁡ x ≥ 0 { ( c − A T μ ) T x + b T μ } \begin{equation} \min\limits_{x\ge0}\{c^Tx+\mu^T(b-Ax)\}=\min\limits_{x\ge0}\{(c-A^T\mu )^Tx+ b^T\mu\} \end{equation} x≥0min​{cTx+μT(b−Ax)}=x≥0min​{(c−ATμ)Tx+bTμ}​​
• 我们知道，$x\ge 0$，但凡 { c − A T μ } \{c-A^T\mu\} {c−ATμ}中有一个负数，那么在求整体最小值的时候，就容易出现$-\infty$,所以可得：
  $$\begin{array}{c}\underset{x\ge 0}{\min }\{(c-A^T\mu {)}^{T}x+b^T\mu \}=\{\begin{array}{r}{b}^T\mu ,c-A^T\mu \ge 0\\ -\infty ,othervise\end{array}\end{array}$$
• 再求最大值,其中负无穷就不用考虑了：
  $$\begin{array}{c}\begin{array}{rl}& \max b^T\mu \\ & st:A^T\mu \le c\end{array}\end{array}$$
• 为了方便观看，将 $\mu$转换成y,整理可得：
• 线性规划的对偶问题如下：
  $$\begin{array}{c}\begin{array}{rl}& \max b^{T}y\\ & st:A^{T}y\le c\end{array}\end{array}$$
• 弱对偶理论,原问题的最优值大于等于对偶问题的最优值：$v(D)\le v(P)$
  $$\begin{array}{c}{b}^{T}y\le c^{T}x,\forall x,y\in S\end{array}$$
• 强对偶理论：
  1） 集合X为非空凸集，$f(x)$及$g_i(x),i=1,2,\cdots ,m$是凸函数，$h_i(x),i=1,2,\cdots ,l$均为线性函数。
  2） 假设存在 $\hat{x}\in X$使得$g_i(\hat{x})<0,i=1,\cdots ,m,h_i(\hat{x})=0,i=1,\cdots ,l$,且
  $0\in \mathrm{int}h(X)$,其中$h(X)=\{[h_1(x),h_2(x),\cdots ,h_l(x){]}^T|x\in X\}$,则强对偶成立，即：
  min ⁡ { f ( x ) ∣ x ∈ S } = max ⁡ { d ( λ , μ ) ∣ λ ≥ 0 , μ } \begin{equation} \min \{f(x)|x\in S\}=\max \{d(\lambda,\mu)\big|\lambda \ge 0,\mu\} \end{equation} min{f(x)∣x∈S}=max{d(λ,μ) ​λ≥0,μ}​​

3. 最大流 - 最小割问题

具体参考最大流最小割学习笔记
水流从source开始流向sink，每根线代表管道，上面的数字代表水管的流量能力，我们希望知道最终流到sink上的最大流速是多少？最小割代表的是用刀割断水管，怎样把source和sink 分割成两部分的最小断管数

最大流和最小割是对偶问问题：
min ⁡ { c u t } = max ⁡ { f l o w } = 14 \begin{equation} \min \{\mathrm{cut}\}=\max \{\mathrm{flow}\}=14 \end{equation} min{cut}=max{flow}=14​​

4. 两人零和博弈