Introduction

  1. 最优化:在满足一系列约束条件下,获得目标函数或指标获得一个最大值(最小值)

Linear programs(线性规划)

  1. 线性函数 (linear function) f(x)=aTxf(x) = a^T x
  2. 仿射函数 (affine function f(x)=aTx+βf(x) = a^T x + β

所有线性函数都是仿射函数(ifβ==0)(if β==0),反之则不然,

Integer programs (整数规划)

  1. 整数规划指的是,在一个线性规划中,添加了其变量的非空子集必须取整数的限制条件。
  2. 当所有的变量都要求是整数时,叫做纯整数规划(pure integer program)。否则就叫混合整数规划(mixed integer program)。

Solving linear program

  1. 对于一个线性规划问题,如果目标函数是求最大值的线性规划,结果只会有一个最大值,但可能会有多个不同的解,但结果都是相同的最大值,最小值同理。

Possible outcomes

  1. 对于一个线性规划(LP)问题,一定有如下3种可能的结果:

    • 不可解
    • 有一个最优解
    • 无界

    这三种结果,同一个问题最多只能出现一种

Standard equality form

  1. 如果LP是一个标准等式(SEF),它必须满足一下的条件:

    • 它是一个最大值问题
    • 所有的变量必须是非负的
    • 如果非负的限制,所有的限制条件都应该是等式
  2. 我们将会设计一个算法,对于 LPinSEF(标准等式表示的线性规划问题),我们证明这个问题是那种结果,但不是所有LP都是SEF,我们希望能将任意LP转化成LPinSEF,然后在LPinSEF使用这个算法,他们两个需要有相同的回答。更准确的说,需要满足一下条件

    • LP无解,当且仅当LPinSEF也无解
    • LP无界,当且仅当LPinSEF也无界
    • 给定一个LP的最优解,可以构建出一个LPinSEF的最优解,反之亦然。
  3. 将LP转成LPinSEF的步骤

  • 如果目的函数是最小值 minCTXmin C^T X ,改成最大值max(CT)Xmax (-C^T) X
  • 如果 xix_i 没有非负限制,则xi=xi+xi  where  xi+,xi0x_i = x^+_i- x^-_i \ \ where \ \ x^+_i,x^-_i\ge 0,用xi+,xix^+_i,x^-_i代替xix_i
  • 对于 i=1naixiβ\sum^n_{i=1}a_ix_i\ge \beta,则i=1naixi+xn+1=β where xn+10\sum^n_{i=1}a_ix_i + x_{n+1}=\beta \ where\ x_{n+1}\ge 0,在限制条件中添加xn+1x_{n+1}
    这样就可以将线性规划转化成标准的线性规划

A simplex iteration

Bases and canonical forms (基与规范型)

  1. identity matrix :单位矩阵

  2. nonsingular matrix :非奇异矩阵,性质:满秩,行列式不为0,可逆,也可称可逆矩阵就是非奇异矩阵

  3. a basis :列子集中的最大线性无关组,并且是非奇异矩阵

  4. 规范形式(canonical forms) :对于LPinSEF  max{cTx=zˉ:Ax=b,x0}\ max\{c^Tx = \bar{z}:Ax=b,x\ge 0 \},B是basis,规范形式需要满足

    • ABA_B 是单位矩阵
    • CB=0C_B = 0
  • 对于第一个条件,只需要左乘AB1A_B^{-1},得AB1Ax=AB1bA_B^{-1}Ax=A_B^{-1}bAB1AA_B^{-1}A中的ABA_B就是单位矩阵了。
  • 对于第二个条件,
    Ax=bAx=b两边分别乘yTy^T,得yTAx=yTb  yTAxyTb=0y^TAx=y^Tb\ \xRightarrow\ y^TAx-y^Tb=0
    加到z(x)z(x),得到z(x)=yTb+zˉ+(cTyTA)xz(x) = y^Tb + \bar{z} + (c^T- y^TA)x
    cˉT=cTyTA\bar{c}^T = c^T - y^TA,我们需要cˉT=cTyTA=0\bar{c}^T = c^T - y^TA = 0,故 y=ABTcBy = A_B^{-T}c_B
  • 综上,z(x)=yTb+zˉ+(cTyTA)xz(x) = y^Tb + \bar{z} + (c^T- y^TA)x
    AB1Ax=AB1b,x0, where y=ABTcBA_B^{-1}Ax=A_B^{-1}b,x\ge 0,\ where\ y = A_B^{-T}c_B

The simplex algorithm (单纯形法)

步骤

  1. 获取规范的形式后,选择kNk\in N,并且ck>0c_k>0
  2. xBx_BxNx_N中的其他值设为0后代入到Ax=bAx=b中获得xkx_k能得到的最大值,
  3. 再将xkx_k代回Ax=bAx=b得到xBx_B,求得max后
  4. 更新B和N,
  5. 继续迭代,直到cN0c_N\le 0,最终获得一个最优上界

规范化步骤

  1. 规范形式:max  z(x)=zˉ+cNTxN    subject to  xB+ANxN=b,x0max\ \ z(x) = \bar{z} + c_N^T x_N \ \ \ \ subject\ to\ \ x_B +A_Nx_N = b,x\ge 0
    其中 zˉ\bar{z} 是确定的值,并且 b0b\ge 0
  2. 如果cN0c_N\le 0 , xˉ\bar{x}则是一个最优的解
  3. 选择 kNk\in N并且ck>0c_k>0,然后通过tt定义xNx'_N,对于xjxNx'_j\in x'_Nxj={tif j=k0if jN{k}x'_j = \begin{cases} t &\text{if } j=k \\ 0 &\text{if } j\in N \setminus\{k\} \end{cases}
  4. 如果Ak0A_k\le 0,则线性规划无界(因为t是无限制的)
  5. 因为xB+ANxN=bx_B +A_Nx_N = b,得到xB=btAkx'_B = b - tA_k,我们需要找到满足xB0x'_B\ge 0tt,所以tAkbtA_k\le b,得到t=min{biAik:Aik>0}t=min\{ {\frac {b_i} {A_ik}}:A_ik>0\}
  6. 根据上一条,xBx_B'中的第 r 行为0,则 l 表示 B 中第 r 个基 ,选择B=B{k}{l}B' = B\cup \{k\} \setminus \{l\}N=N{l}{k}N' = N\cup \{l\}\setminus \{k\},更新 BB'NN'
  7. 然后返回第一步执行,直到结束

t=0t=0时,对于多次迭代,我们会获得相同的解,这可能永远也无法结束(known as cycling)
解决方法 布兰德规则(bland’rule):

  • 第三步中,选择一个满足条件的最小的kk
  • 第五步中,选择最小的 rB with Ark>0r \in B\ with\ A_{rk} >0,然后brArl=t\frac {b_r} {A_{rl}} = t

Finding feasible solutions

对于LP问题  max{cTx:Ax=b,x0}\ max\{c^Tx :Ax=b,x\ge 0 \} A有m行n列

Phase 1 构造求解 auxiliary LP

  1. 先将b中的所有值转化成非负数,如果是负数,所在行乘-1即可转化成正数
  2. 构造:min w=xn+1+...+xn+mmin\ w=x_{n+1} +...+ x_{n+m}
    subject (AI)(x1...xn+m)=b,(x1,...,xn+m)T0subject\ \begin{pmatrix} A|I \end{pmatrix} \begin{pmatrix} x_1 \\ ...\\ x_{n+m} \end{pmatrix} = b,(x_1,...,x_{n+m})^T\ge0 ,其中I是m阶单位矩阵
  3. 转化成标准式 min w=xn+1+...+xn+m max w=xn+1...xn+mmin\ w=x_{n+1} +...+ x_{n+m}\xRightarrow\ max\ w=-x_{n+1} -...- x_{n+m}
  4. 其中 (x1,...,xn)T=0,(xn+1,...xn+m)T=b(x_1,...,x_n)^T=0, (x_{n+1},...x_{n+m})^T=b是一个可行解
  5. 使用单纯形法求解上述LP问题,
  • 求得 w=0, (x1,...,xn)T(x_1,...,x_n)T原式中的一个可行解,进行阶段2
  • 若w>0,则此问题无解

Phase 2

  1. 根据 phase 1 获得的可行解,用单纯形法求解原问题

Simplex via tableaus

Pivoting(主元)

  1. 对于mxn的矩阵T,让元素Ti,jT_{i,j}做主元得到T’:对T进行行变换,使得矩阵中第j列除第i个元素为1,其他全为0
    Tk={1Ti,jTkif k=jTkTk,jTi,jTiif kjT'_k = \begin{cases} \frac 1 {T_{i,j}} T_k &\text{if}\ k=j \\ T_k - \frac {T_{k,j}} {T_{i,j}} T_i &\text{if}\ k \not= j \end{cases}

Tableaus

  1. max{z=zˉ+cTx,Ax=b,x0}max\{ z = \bar{z} + c^T x , Ax = b,x\ge 0\} 写成矩阵形式 zcTx=zˉz -c^T x = \bar{z}
    T=(1cTzˉ0Ab)T=\begin{pmatrix} 1 & -c^T & \bar{z} \\ \hline 0 & A & b \end{pmatrix}
  2. 在T中选择一列k,ck>0c_k>0,在T中就是 Tk,0<0T_{k,0}<0,计算t,对于bitTi,k=0b_i-tT_{i,k}=0的,进行上节中的主元变换,直到所有的ck<0c_k<0,也就是cT>0-c^T>0,最终的zˉ\bar{z}就是结果
  3. 整个过程原理其实和单纯形法是一样的,这个只是转化成了矩阵的形式进行计算

Geometry

Feasible region of LPs and polyhedr

  1. {H=xn:aTx=β}\{H={x\in n : a^Tx = β\}} is a hyperplane(超平面), {F=xn:aTxβ}\{F={x\in n : a^Tx \le β\}} is a halfspace(半空间)

  2. rank(A) :矩阵A的秩

  3. LP的解的区域是一个多面体,或者有限个版空间的交集

Convexity

  1. Convexity(凸性):对于一个区域内的任意两点形成的线段,如果这个线段上的任意点也都在这个区域内,就称这个区域是凸性的。
  2. 任意个(infinite)凸集的交集还是凸集
  3. Polyhedra are convex 多面体都是凸集

Extreme points

  1. Extreme points 极点:这个点在凸集中,并且这个点不属于任意凸集中的线段,这个点就叫极点,例如三角形的三个顶点、圆形区域边上的每个点
  2. 多面体(apolyhedron)中的极点(extreme point)
    符号表示:对于不等式系统AxβAx \le β,如果αTxˉ=βα^T\bar{x}=\beta,则AxβAx \le \beta中的约束aTxβa^Tx \le βxˉ\bar{x}是严格的,把AxβAx \le \beta中所有对xˉ\bar{x}严格约束记作A=xb=A^=x \le b^=
    定理:P={xRn:Axb}P = \{x\in R^n : Ax \le b\}是一个多面体 xˉP\bar{x} \in PA=xb=A^=x \le b^=是对xˉ\bar{x}严格约束集合,当rank(A=)=nrank(A^=)=n时,xˉ\bar{x}是极点
    定理:P={x:Ax=b,x0}P = \{x : Ax = b, x\ge 0 \}, xˉP\bar{x} \in P,当且仅当xˉ\bar{x}Ax=bAx = b的解时,\bar{x}$是极点

Geometric interpretation of the simplex algorithm

Duality(对偶) through examples

The shortest path problem

  1. 可行性条件:对于E中的每个边e,st-cuts中包含边e的width和应该小于等于e的length,
  2. 最短路径最优化的条件:如果st-cut都是可行的,所有st-cuts的width和是最短路径的下界,也就是说,如果最短路径的长度等于st-cuts的和,那么这个路径就是最短路径

Minimum cost perfect matching in bipartite graphs

  1. 匹配:图G的一个边集M,若M中的任意两条边都没有公共端点,M是一个匹配
  2. 完美匹配:若一个匹配M覆盖了图中的所有节点,则称M为图的完美匹配
  3. 我们想要找到所有的完美匹配中代价和最小的那个
  4. 方法是,先给顶点赋值,然后让边的权重减去它两个点的值得到一个新的权重,新权重需要大于等于0,最后可以从权重为0的边中选择出完美匹配

An intuitive lower bound

  1. 给所有顶点u赋值yuy_u,边uv的代价为cuvc_{uv},削减后,边uv的代价:cuvˉ=cuvyuyv\bar{c_{uv}}=c_{uv}-y_u-y_v
  2. 因为所有的y是定值,如果M的削减代价cˉ\bar{c}是最小的,那个它原始代价也是最小的。因为cˉ=cy\sum\bar{c} = \sum c -\sum y
  3. 如果削减代价cuvˉ=0\bar{c_{uv}}=0,那么边uv是关于y的等价边
  4. 可行性条件:对于任意边eEe \in E,如果cuvˉ0\bar{c_{uv}} \ge 0,那么y是可行的
  5. 如果y是可行的,并且等价与M中所有的边,那么M就是代价最小的完美匹配集

A general argument–weak duality

  • 对于一个最小化问题,下界值越大越接近真实的下界值(最优解)
    1. 对于LP  min{cTx:Ax=b,x0}\ min\{c^Tx : Ax=b,x\ge 0 \}
    2. 首先给约束条件两边乘yTy^T,得到yTAx=yTb  yTbyTAx=0y^TAx=y^Tb\ \xRightarrow\ y^Tb-y^TAx=0
    3. z(x)=cTx+yTbyTAx=yTb+(cTyTA)xz(x)=c^Tx+y^Tb-y^TAx =y^Tb+(c^T-y^TA)x
    4. 假设(cTyTA)x0(c^T-y^TA)x \ge0xˉ\bar{x}为可行解,所以有 z(x)yTbz(x) \ge y^TbyTby^Tb是目标函数的下界值
    5. 可以转化成  max{bTy:ATyc}\ max\{b^Ty : A^Ty \le c\},y为无约束的变量

Weak duality–special form (弱对偶-特殊形式):下面一对LPs
 min{cTx:Ax=b,x0}\ min\{c^Tx : Ax=b,x\ge 0 \} P
 max{bTy:ATyc}\ max\{b^Ty : A^Ty \le c\} D
xˉ,yˉ\bar{x},\bar{y}分别作为P,D的解,cTxˉbTyˉc^T\bar{x} \ge b^T\bar{y},如果等号成立,xˉ\bar{x} 就是最优解
D被定义为P的对偶

Revisiting the intuitive lower bound

  • 最小完美匹配的图问题,我们可以写成整数规划的形式:
    1. E为所有边的集合,cec_e为边e的权重,xex_e是是否选择这条边
    2. min(cexe:eE)min \sum(c_ex_e:e\in E)
    3. subject to (xe:eδ(v)=1,(vV)\sum(x_e:e \in \delta(v)=1,(v \in V) 一个顶点只能有一条边相连
    4. xe0,(eE)x_e \ge 0 , (e \in E)
    5. xex_e integer (eE)(e \in E) 是否选择这条边,0 or 1
  1. LP relaxation:对于一个整数规划,移除变量必须取整数的条件,叫做IP的线性规划松弛(LP relaxation)
  2. 如果D是 IP 的LP relaxation的对偶,那么任意D的可行解都是IP的下界,原因:把 P 作为上面 IP 的 LP relaxation,IP是个最小化问题,所以IP的最优解是大于等于P的最优解的,D作为P的对偶,P的最最优解一定大于等于任意D的解
  3. 给定一个一般的完美匹配问题,我们可以将它的LP relaxation写作
    1. min{cTx:Ax=1,x0}min \{c^Tx:Ax =1,x\ge0\}
    2. 其中c是边的权重,矩阵A是:
      • A的行是图的顶点
      • A的列是图的边
      • 对于每行每列有 A[v,e]={1if v是e的一个端点0 otherwise A[v,e]= \begin{cases} 1 &\text{if v是e的一个端点} \\ 0 &\text{ otherwise } \end{cases}
    3. 上式的对偶为 max{1Ty:ATy<c}max \{1^Ty:A^Ty<c\}
    4. 也可以写成 max(yv:vV)max \sum(y_v:v\in V),subject to yu+yvcuv (uvE)y_u +y_v\le c_{uv}\ (uv\in E)

An algorithmIn

  1. bipartite graph :二分图,图中顶点可以分为两个不相交的顶点集UW,U和W他们内部任意两个顶点没有边相连,任意的边的一个端点在U内,则另一个在W内。
  2. 如果一个二分图有完美匹配,必须满足|U|=|W|,也就是U和W中的顶点数目相同
  3. 一个二分图G=(V,E),有分割UW,把顶点的子集记作S,S的邻居节点集合记作NG(S)N_G(S),如果有S>NG(S)|S|>N_G(S),则G中没有完美匹配,叫做缺陷集(deficient set)
  4. Hall’s theorem: 二分图G=(V,E)有分割UW,|U|=|W|,当且仅当G中没有缺陷集SUS\in U时,G中有完美匹配M,此外存在多项式时间的算法,对于给定G要么求得它的完美匹配,要么求得缺陷集
  5. 算法步骤
    1. 二分图G=(V,E),有分割UW,|U|=|W|,边的权重c,求最优完美匹配或缺陷集
    2. 初始化yˉv=12min{ce:eE}\bar{y}_v= \frac 1 2 min\{c_e:e\in E\}
    3. 构建图H,H中含有V中所有顶点,但只含有的{uvE:cuv=yˉu+yˉv}\{uv \in E :c_{uv} = \bar{y}_u+\bar{y}_v \}的边
    4. 如果H有完美匹配M(匹配了所有节点),结束
    5. 否则,求得SUS\in U为H的缺陷集
    6. 若图G中的所有的边都满足:如果边的一个端点是S,另一个端点在NH(S)N_H(S)中,则S是G的缺陷集
    7. ϵ=min{cuvyˉuyˉv:uvE,uS,vNH(S)}\epsilon = min\{c_{uv} - \bar{y}_u - \bar{y}_v:uv\in E,u\in S,v\notin N_H(S) \}
    8. 更新 yˉv{yˉv+ϵfor vSyˉvϵfor vNH(S)yˉvotherwise \bar{y}_v \begin{cases} \bar{y}_v + \epsilon &\text{for } v \in S \\ \bar{y}_v - \epsilon &\text{for } v \in N_H(S) \\ \bar{y}_v &\text{otherwise } \end{cases}
    9. 返回第三步继续执行

Correctness of the algorithm

Finding perfect matchings in bipartite graphs*

  1. M-alternating:匹配集MEM\in E图G中的一条路径P,若路径P上的边交替的处于匹配集中和非匹配集中,或者P\M是匹配集,则称P是交替路径(M-alternating)
  2. M-covered,M-exposed:顶点v,M中有连接到v的边,称v是被M覆盖的(M-covered),否则v是未被覆盖(M-exposed)
  3. M-augmenting:一个交替路径P,如果路径P的两个端点都是未被M覆盖的,则P是M的扩充(M-augmenting)
  4. 只要给定了个扩充路径,我们都能重新构建一个新的匹配M’,|M’|=|M|+1
  5. ABA\triangle B:元素在ABA\cup B中但并不在ABA\cap B中。AB=(AB)(BA)=ABABA\triangle B = (A-B) \cup (B-A) = A\cup B-A\cap B
  6. maximum matching:最大匹配是有最多的边的匹配

完美匹配和最大匹配之间的关系:一个完美匹配必定是一个最大匹配,但并非所有图都有完美匹配(例如奇数个点的图就没有完美匹配)

  1. 若M是图G的匹配集,P是M的扩充路径,M=MPM' = M \triangle P是一个匹配集并且,|M’|=|M|+1,另外M不是最大匹配集
  2. definition
    • cycle 一个边的序列C=v1v2v3...vk1vk,k4C=v_1 v_2 v_3 ... v_{k-1} v_k,k \ge 4v1v2v3...vk1v_1 v_2 v_3 ... v_{k-1}是不同的顶点,v1=vkv_1 = v_k
    • connection 在图中,任意不同的两点之间存在路径,则这个图是连通图
    • tree 一个图是连通图但图中不含有环
  3. 在一个树中,任意两点之间都存在唯一的一条路径
  4. graph G(V,E),matching M and rVr \in V ,G中的树T,是根节点为r的关于M的交替树(M-alternating tree) 需满足:
    • r是T的一个节点,且未被图G中的匹配M覆盖
    • T中除r以外的所有节点都被M覆盖
    • 对于任意T中顶点u(uru \not = r),唯一的路径ru是关于M的交替路径
  5. 完美匹配算法步骤:
    1. 图H(V,E),有顶点集UW且U=W1|U|=|W| \ge 1,求完美匹配或缺陷集(树T中的顶点分为A(T)和B(T)。B(T)中的顶点到根节点r的路径中含有的边的个数为偶数,A(T)中的顶点到根节点r的路径中含有的边的个数为奇数)
    2. 初始化:完美匹配M={}M=\{\empty\},交替树T=(r,)T=({r},\empty),r是任意未覆盖的顶点
    3. 如果存在边uv,uB(T) and vV(T)u \in B(T)\ and\ v\notin V(T)
      • 如果v是未覆盖的
        • 路径P = 交替树T中的路径Tru{uv}T_{ru} \cup \{uv\}
        • 匹配集M=MPM = M \triangle P
        • 如果M是一个完美匹配,结束算法
        • 交替树T=(r,)T=({r},\empty),r是任意M未覆盖的顶点
      • 否则 让vwM wVvw \in M \ w\in VT=(V(T){v,w},E(T){uv,vw})T= (V(T)\cup\{v,w\},E(T) \cup \{uv,vw\})
      • 继续第三步
    4. 否则B(T)UB(T) \in U是一个缺陷集

Duality theory

归纳概括上一节的内容,提出通用的理论框架

Weak duality

  1. 原始对偶对(primal dual paris)
min ≥ constrain = constrain ≤ constrain variable ≥ 0 variable free  variable ≤ 0
max variable ≥ 0 variable free  variable ≤ 0 ≤ constrain = constrain ≥ constrain
  1. Weak duality theorem : P和D是一对原始对偶对,P是最大化问题,Q是最小化问题,xˉ\bar xyˉ\bar y 分别是P和D的可行解,有
    • cTxˉbTyˉc^T\bar x \le b^T\bar y
    • cTxˉ=bTyˉc^T\bar x = b^T\bar yxˉ,yˉ\bar x,\bar y分别是P和D的最优解

Strong duality

  1. 强对偶(Strong duality):P和D是一个对偶对,如果P和D存在相同的最优解,则是强对偶
  2. 强对偶-可行性 :P和D是一个对偶对,如果P和D都存在可行解,P和D存在目标值相同的最优解

A geometric characterization of optimality

Complementary slackness(互补松弛)

  1. 对于线性规划的原始对偶对max{cTx:Ax<b} Pmax\{c^Tx:Ax<b\}\ Pmin{bTy:ATy=c,y0} Dmin\{b^Ty:A^Ty=c,y\ge 0\}\ D ,P添加松弛变量s后可写为 max{cTx:Ax+s=b,s0} Qmax\{c^Tx:Ax+s=b,s\ge 0\}\ Q
  2. xˉ,yˉ\bar x,\bar y分别为P、D的可行解,那么sˉ=bAxˉ\bar s=b-A\bar x为Q的可行解,所以bTyˉ=yˉTb=yˉT(Axˉ+sˉ)=cTxˉ+yˉTsˉb^T\bar y = \bar y^Tb =\bar y^T(A\bar x + \bar s)=c^T\bar x + \bar y^T\bar s
  3. 当且仅当cTxˉ=bTyˉ or yˉTsˉ=0c^T\bar x = b^T\bar y\ or\ \bar y^T\bar s=0xˉ,yˉ\bar x,\bar y分别时最优解
  4. yTsˉ=i=1msˉiyˉiy^T\bar s = \sum^m_{i=1}\bar s_i \bar y_i ,因为sˉi0,yˉi0\bar s_i\ge 0, \bar y_i\ge 0,所以sˉi=0 or yˉi=0\bar s_i = 0\ or\ \bar y_i = 0,如果si=0s_i=0,原式取 ‘=’,可以称这个约束对 xˉ\bar x 是严格的(tight)。
  5. 互补松弛-特例:对于P、D的可行解,当且仅当任意 i 都有sˉi=0 or yˉi=0\bar s_i = 0\ or\ \bar y_i = 0时,可行解是最优解
  6. 互补松弛条件(complementary slackness CS)
    • every xj of Pmaxevery\ x_j\ of\ P_{max} 需要满足xj=0x_j = 0或者相关的约束条件 j of Pminj\ of\ P_{min} 满足等式
    • every yi of Pminevery\ y_i\ of\ P_{min} 需要满足yi=0y_i = 0或者相关的约束条件 i of Pmaxi\ of\ P_{max} 满足等式
  7. 互补松弛定理(omplementary slackness theorem):P、D是任意原始对偶对,当且仅当满足互补松弛条件时,可行解是最优解

Geometry

  1. a(1),a(2)...a(k)a^{(1)},a^{(2)}...a^{(k)}RnR^n中的向量集合,定义由上述集合产生的锥形C={i=1kλia(i):λi0}C=\{\sum^k_{i=1}\lambda _i a^{(i)}:\lambda _i \ge 0\}

  2. 实例如下图

  3. P={x:Axb}P=\{x:Ax\le b\} 是一个多面体,xˉP\bar x \in PJ(xˉ)J(\bar x) 定义为A中约束条件取等号的行的索引,例如rowi(A)xˉ=bi>iJ(xˉ)row_i(A)\bar x = b_i -> i \in J(\bar x),定义xˉ\bar x的严格约束锥形为A的严格约束行C=cone{rowi(A)T:iJ(xˉ)}C = cone\{row_i(A)^T:i\in J(\bar x)\}

  4. xˉ\bar xmax{cTx:Axb}max\{c^Tx:Ax\le b\}的可行解,当且仅当c在关于xˉ\bar x的严格约束锥形内时,xˉ\bar x是最优解

  5. 例如对于问题 max(32,12)xmax (\frac 3 2,\frac 1 2)x,约束(101101)x(232)\begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{pmatrix} x \le \begin{pmatrix} 2 \\ 3 \\ 2 \end{pmatrix},解xˉ=(2,1)T\bar x = (2,1)^T是一个可行解,严格限制锥形为C=cone{(10),(11)}C=cone \begin{Bmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \end{pmatrix} \end{Bmatrix},可知,c在锥形C内,也就是说c可以由C内的元素表示,如下图所示

Farkas’ lemma

  1. Farkas 引理:A为一个m x n 的矩阵,b是一个m维向量,一下只有一个是正确的
    • Ax=b,x0Ax=b,x \ge 0,有解
    • 存在向量y,使得ATy0 and bTy<0A^Ty \ge 0\ and\ b^Ty < 0

Applications of duality

Approximation algorithm for set-cover