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

发布于:2024-07-25 ⋅ 阅读:(33) ⋅ 点赞:(0)


MIT教授教学视频,讲得比较泛,需要另外学习很多知识补充

0. 概述

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

1. 线性规划问题

1.1 定义

假设我们的原问题如下:

  • 标准形式:
    ( L P )      min ⁡    c T x s t .      A x = b , x ≥ 0 x = ( x 1 , x 2 , ⋯   , x n ) T ; x i ≥ 0 c = ( c 1 , c 2 , ⋯   , c n ) T ; x i ≥ 0 \begin{equation}\begin{aligned} &(LP)\; \;\min\; c^Tx\\ &st.\;\;Ax=b,x\ge 0\\ &x=(x_1,x_2,\cdots,x_n)^T;x_i\ge0\\ &c=(c_1,c_2,\cdots,c_n)^T;x_i\ge0\\ \end{aligned}\end{equation} (LP)mincTxst.Ax=b,x0x=(x1,x2,,xn)T;xi0c=(c1,c2,,cn)T;xi0
    其中, c ∈ R n , A ∈ R m × n , b ∈ R m c\in R^n,A\in R^{m\times n},b\in R^m cRn,ARm×n,bRm,通常假设系数矩阵A行满秩,即 r ( A ) = m < n r(A)=m<n 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,xi0

  • 根据单纯形法Simplex method,Dantzig
    —理论依据:若LP有最优解,则最优解可在极点取到
    – -基本思想: 找到一个极点 x ˉ \bar{x} xˉ,判断 x ˉ \bar{x} xˉ是否最优;若 x ˉ \bar{x} 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+20+50=3P2=(0,3,0)y2=0+23+50=6P3=(0,0,3)y3=0+20+53=15(3,0,0)min{x1+2x2+5x3}=3

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

  • 给出如下线性规划问题,求其对偶问题:
    min ⁡    c T x s t ; A x = b , x ≥ 0 , 其中, c ∈ R n , A ∈ R m × n , b ∈ R m \begin{equation}\begin{aligned} &\min \;c^Tx\\ &st; Ax=b,x\ge0,其中,c\in R^n,A\in R^{m\times n},b\in R^m \end{aligned}\end{equation} mincTxst;Ax=b,x0,其中,cRn,ARm×n,bRm
  • 根据约束来拉格朗日函数:
    L ( x , μ ) = c T x + μ T ( b − A x ) \begin{equation} L(x,\mu)=c^Tx+\mu^T(b-Ax) \end{equation} L(x,μ)=cTx+μT(bAx)
  • 找出拉格朗日函数的对偶问题,先选定一个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} μmaxx0min{cTx+μT(bAx)}
  • 先求内部最小值:
  • 展开公式可得:
    - 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} x0min{cTx+μT(bAx)}=x0min{(cATμ)Tx+bTμ}
  • 我们知道, x ≥ 0 x\ge0 x0,但凡 { c − A T μ } \{c-A^T\mu\} {cATμ}中有一个负数,那么在求整体最小值的时候,就容易出现 − ∞ -\infty ,所以可得:
    min ⁡ x ≥ 0 { ( c − A T μ ) T x + b T μ } = {        b T μ ,    c − A T μ ≥ 0 − ∞ , o t h e r v i s e \begin{equation}\min\limits_{x\ge0}\{(c-A^T\mu )^Tx+ b^T\mu\}=\left\{\begin{aligned} %\nonumber \;\;\;b^T\mu,\; c-A^T\mu\ge0\\ -\infty,othervise\\ \end{aligned}\right.\end{equation} x0min{(cATμ)Tx+bTμ}={bTμ,cATμ0,othervise
  • 再求最大值,其中负无穷就不用考虑了:
    max ⁡    b T μ s t : A T μ ≤ c \begin{equation}\begin{aligned} &\max \;b^T\mu\\ &st:A^T\mu\le c \end{aligned}\end{equation} maxbTμst:ATμc
  • 为了方便观看,将 μ \mu μ转换成y,整理可得:
  • 线性规划的对偶问题如下:
    max ⁡    b T y s t : A T y ≤ c \begin{equation}\begin{aligned} &\max \;b^Ty\\ &st:A^Ty\le c \end{aligned}\end{equation} maxbTyst:ATyc
  • 弱对偶理论,原问题的最优值大于等于对偶问题的最优值: v ( D ) ≤ v ( P ) v(D)\le v(P) v(D)v(P)
    b T y ≤ c T x , ∀ x , y ∈ S \begin{equation} b^Ty\le c^Tx,\forall x,y \in S \end{equation} bTycTx,x,yS
  • 强对偶理论
    1) 集合X为非空凸集, f ( x ) f(x) f(x) g i ( x ) , i = 1 , 2 , ⋯   , m g_i(x),i=1,2,\cdots,m gi(x),i=1,2,,m是凸函数, h i ( x ) , i = 1 , 2 , ⋯   , l h_i(x),i=1,2,\cdots,l hi(x),i=1,2,,l均为线性函数。
    2) 假设存在 x ^ ∈ X \hat{x}\in X x^X使得 g i ( x ^ ) < 0 , i = 1 , ⋯   , m , h i ( x ^ ) = 0 , i = 1 , ⋯   , l g_i(\hat{x})<0,i=1,\cdots,m,h_i(\hat{x})=0,i=1,\cdots,l gi(x^)<0,i=1,,m,hi(x^)=0,i=1,,l,且
    0 ∈ i n t    h ( X ) 0\in \mathrm{int}\; h(X) 0inth(X),其中 h ( X ) = { [ h 1 ( x ) , h 2 ( x ) , ⋯   , h l ( x ) ] T ∣ x ∈ X } h(X)=\{[h_1(x),h_2(x),\cdots,h_l(x)]^T\big|x\in X\} h(X)={[h1(x),h2(x),,hl(x)]T xX},则强对偶成立,即:
    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)xS}=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. 两人零和博弈


网站公告

今日签到

点亮在社区的每一天
去签到