高级优化理论与方法(十二)
- LP
- Duality of LP
- Week LP Duality Theorem
- Strong LP Duality Theorem
- Corollary
- Complementary Slackness Condition
- Remarks
- Example
- Non-Simplex Methods
- Khachiyan (Ellipsoid)
- Karmarkar (Interior point)
- Integer Linear Programming (ILP)
- Unimodular Matrix
- Definition
- Lemma
- Corollary
- Definition
- Property
- Heuristic for Solving ILP
- Branch&Bound
- Gomory Cut
- Example
- 总结
LP
Duality of LP
Week LP Duality Theorem
∀ x , y : c T x ≥ y T b \forall x,y:c^Tx\geq y^Tb ∀x,y:cTx≥yTb
Strong LP Duality Theorem
Thm: Suppose that x ∗ x^* x∗ and y ∗ y^* y∗ are feasible solutions to the primal and dual, respectively. If c T x ∗ = y ∗ T b c^Tx^*={y^*}^Tb cTx∗=y∗Tb, then x ∗ , y ∗ x^*,y^* x∗,y∗ are optimal.
Corollary
If the primal has an optimal solutions, then so does the dual, and the optimal values are equal.
Complementary Slackness Condition
Thm: The feasible solutions x x x and y y y to a duality pair are optimal, if and only if { ( c T − y T A ) x = 0 y T ( A x − b ) = 0 \begin{cases} (c^T-y^TA)x=0\\ y^T(Ax-b)=0 \end{cases} {(cT−yTA)x=0yT(Ax−b)=0
Remarks
( c T − y T A ) x = 0 ⇒ { x i > 0 implies y T a i = c i y T a i < c i implies x i = 0 (c^T-y^TA)x=0\Rightarrow \begin{cases} x_i>0 \,\text{implies}\, y^Ta_i=c_i\\ y^Ta_i<c_i \,\text{implies}\, x_i=0 \end{cases} (cT−yTA)x=0⇒{xi>0impliesyTai=ciyTai<ciimpliesxi=0
Example
26 dollars to purchase gold.
vendor | 1 | 2 | 3 | 4 |
---|---|---|---|---|
dollar/once | 1 2 \frac{1}{2} 21 | 1 | 1 7 \frac{1}{7} 71 | 1 4 \frac{1}{4} 41 |
Define x i = x_i= xi=dollars spent at vendor i i i
max 2 x 1 + x 2 + 7 x 3 + 4 x 4 = Δ min − 2 x 1 − x 2 − 7 x 3 − 4 x 4 2x_1+x_2+7x_3+4x_4\stackrel{\Delta}{=}\text{min} -2x_1-x_2-7x_3-4x_4 2x1+x2+7x3+4x4=Δmin−2x1−x2−7x3−4x4
s.t. x 1 + x 2 + x 3 + x 4 = 26 x_1+x_2+x_3+x_4=26 x1+x2+x3+x4=26
x 1 , ⋯ , x 4 ≥ 0 x_1,\cdots,x_4\geq 0 x1,⋯,x4≥0
max 26 y 26y 26y
s.t. y ≤ − 2 y\leq -2 y≤−2
y ≤ − 1 y\leq -1 y≤−1
y ≤ − 7 y\leq -7 y≤−7
y ≤ − 4 y\leq -4 y≤−4
⇒ y ∗ = − 7 \Rightarrow y^*=-7 ⇒y∗=−7
c T − y T A = [ − 2 , − 1 , − 7 , − 4 ] − ( − 7 ) [ 1 , 1 , 1 , 1 ] = [ 5 , 6 , 0 , 3 ] c^T-y^TA=[-2,-1,-7,-4]-(-7)[1,1,1,1]=[5,6,0,3] cT−yTA=[−2,−1,−7,−4]−(−7)[1,1,1,1]=[5,6,0,3]
⇒ x ∗ = [ 0 , 0 , 26 , 0 ] \Rightarrow x^*=[0,0,26,0] ⇒x∗=[0,0,26,0]
Non-Simplex Methods
1972: Klee-Minty构造了一个例子,使得单纯形法的时间复杂度达到了 O ( n m ) O(n^m) O(nm),使得人们怀疑线性规划问题是否是P问题。
1979: Khachiyan发明了一个新算法,其时间复杂度达到了 O ( n 4 L 1 ) O(n^4L_1) O(n4L1)。 L 1 L_1 L1: accuracy of computation。从而证明了线性规划问题确实属于P问题。
1984: Karmarkar发明了一个新算法,时间复杂度达到了 O ( n 3.5 L ) O(n^{3.5}L) O(n3.5L),不仅算法比Khachiyan的算法效率高,而且算法更为简单。
Khachiyan (Ellipsoid)
min c T x c^Tx cTx
s.t. A x ≥ b Ax\geq b Ax≥b
x ≥ 0 x\geq 0 x≥0
max y T b y^Tb yTb
s.t. y T A ≤ c T y^TA\leq c^T yTA≤cT
y ≥ 0 y\geq 0 y≥0
⇒ [ x , y ] ∈ R n + m \Rightarrow [x,y]\in \mathbb{R}^{n+m} ⇒[x,y]∈Rn+m
s.t. c T x = y T b c^Tx=y^Tb cTx=yTb
A x ≥ b Ax\geq b Ax≥b
y T A ≤ c T y^TA\leq c^T yTA≤cT
x ≥ 0 x\geq 0 x≥0
y ≥ 0 y\geq 0 y≥0
⇒ [ x , y ] ∈ R n + m \Rightarrow [x,y]\in \mathbb{R}^{n+m} ⇒[x,y]∈Rn+m
s.t. c T x − y T b ≥ 0 c^Tx-y^Tb\geq 0 cTx−yTb≥0
y T b − c T x ≥ 0 y^Tb-c^Tx\geq 0 yTb−cTx≥0
A x ≥ b Ax\geq b Ax≥b
x ≥ 0 x\geq 0 x≥0
y ≥ 0 y\geq 0 y≥0
− y T A ≥ − c T -y^TA\geq -c^T −yTA≥−cT
⇒ [ c T − b T − c T b T A 0 I n 0 0 I m 0 − A ] [ x y ] = [ 0 0 b 0 0 − c ] \Rightarrow \begin{bmatrix} c^T&-b^T\\ -c^T&b^T\\ A&0\\ I_n&0\\ 0&I_m\\ 0&-A \end{bmatrix}\begin{bmatrix} x\\ y \end{bmatrix}=\begin{bmatrix} 0\\ 0\\ b\\ 0\\ 0\\ -c \end{bmatrix} ⇒ cT−cTAIn00−bTbT00Im−A [xy]= 00b00−c
⇒ A x ≥ b \Rightarrow Ax\geq b ⇒Ax≥b
⇒ ∀ i : a i T x ≥ b i \Rightarrow \forall i:a_i^Tx\geq b_i ⇒∀i:aiTx≥bi
Basic idea: 为了找到包含满足限制条件的区域,构造椭球,并通过迭代的方式一步步缩小椭球的体积,知道找到目标区域。
Karmarkar (Interior point)
Canonical Form:
min c T x c^Tx cTx
s.t. A x = 0 Ax=0 Ax=0
∑ x i = 1 \sum x_i=1 ∑xi=1
x ≥ 0 x\geq 0 x≥0
该方法也是通过迭代的方式来找到目标区域。由于跟本课程关系不大,所以此处不展开讲。
Integer Linear Programming (ILP)
min c T x c^Tx cTx
s.t. A x ≥ b Ax\geq b Ax≥b
x ≥ 0 x\geq 0 x≥0
x ∈ Z x\in \mathbb{Z} x∈Z
ILP在LP的基础上加上了 x ∈ Z x\in \mathbb{Z} x∈Z的要求,使得求解难度提升了一个档次。一个比较简单的想法是先求出LP问题的解,再通过某种方法四舍五入一下,但很容易举出反例,简单的四舍五入不一定是问题的答案。目前证明了ILP问题是NP-hard问题,没有多项式时间解法,而LP是P问题,这也将ILP和LP划分为了两个完全不同的难度。
Unimodular Matrix
Definition
Def: Minor: determinant of a square submatrix of A ∈ R m × n A\in\mathbb{R}^{m\times n} A∈Rm×n
A p-th order minor: p × p p\times p p×p-submatrix x x x
Def: Unimodular: all its nonzero m-th minors= ± 1 \pm 1 ±1
注:minor意为余子式,unimodular matrix意为幺模矩阵。
Lemma
If a linear equation A x = b Ax=b Ax=b with A ∈ Z m × n , m ≤ n A\in\mathbb{Z}^{m\times n},m\leq n A∈Zm×n,m≤n, and b ∈ Z m b\in \mathbb{Z}^m b∈Zm satisfies A A A being unimodular, then all basic solutions are integer vectors.
Corollary
If { A x = b x ≥ 0 \begin{cases} Ax=b\\ x\geq 0 \end{cases} {Ax=bx≥0 where A A A unimodular, then all basic feasible solutions are integral.
Definition
totally unimodular: if all its nonzero minors= ± 1 \pm 1 ±1. ( A ∈ { 0 , − 1 , 1 } m × n A\in \{0,-1,1\}^{m\times n} A∈{0,−1,1}m×n)
注:totally unimodular matrix意为全幺模矩阵。
Property
A A A totally unimodular ⇒ [ A , I ] \Rightarrow [A,I] ⇒[A,I] unimodular
Heuristic for Solving ILP
Branch&Bound
分支定界法
min c T x c^Tx cTx
s.t. A x ≥ b Ax\geq b Ax≥b
x ≥ 0 x\geq 0 x≥0
x ∈ Z n x\in \mathbb{Z}^n x∈Zn
⟹ relaxtion \stackrel{\text{relaxtion}}{\Longrightarrow} ⟹relaxtionmin c T x c^Tx cTx
s.t. A x = b Ax=b Ax=b
x ≥ 0 x\geq 0 x≥0
⇒ x ∗ \Rightarrow x^* ⇒x∗
∃ i : x i ∗ ∉ Z \exist i:x_i^*\notin \mathbb{Z} ∃i:xi∗∈/Z
⇒ \Rightarrow ⇒min c T x c^Tx cTx
s.t. A x = b Ax=b Ax=b
x ≥ 0 x\geq 0 x≥0
x i ≤ ⌊ x i ∗ ⌋ x_i\leq \lfloor x_i^*\rfloor xi≤⌊xi∗⌋
and
min c T x c^Tx cTx
s.t. A x = b Ax=b Ax=b
x ≥ 0 x\geq 0 x≥0
x i ≥ ⌈ x i ∗ ⌉ x_i\geq \lceil x_i^*\rceil xi≥⌈xi∗⌉
再重复此过程,直到 x ∈ Z n x\in \mathbb{Z}^n x∈Zn
Gomory Cut
切平面法,该方法于1958年提出,通过切割平面的方法,使得非整数解不会出现在切割后的平面中,于是不断切割平面就能得到整数解。
relax: min c T x c^Tx cTx
s.t. A x = b Ax=b Ax=b
x ≥ 0 x\geq 0 x≥0
A ∈ Z m × n , b ∈ Z m A\in\mathbb{Z}^{m\times n},b\in \mathbb{Z}^m A∈Zm×n,b∈Zm
a 1 a_1 a1 | a 2 a_2 a2 | ⋯ \cdots ⋯ | a m a_m am | a m + 1 a_{m+1} am+1 | ⋯ \cdots ⋯ | a n a_n an | b |
---|---|---|---|---|---|---|---|
1 | 0 | ⋯ \cdots ⋯ | 0 | y 1 , m + 1 y_{1,m+1} y1,m+1 | ⋯ \cdots ⋯ | y 1 , n y_{1,n} y1,n | y 1 , 0 y_{1,0} y1,0 |
0 | 1 | ⋯ \cdots ⋯ | 0 | y 2 , m + 1 y_{2,m+1} y2,m+1 | ⋯ \cdots ⋯ | y 2 , n y_{2,n} y2,n | y 2 , 0 y_{2,0} y2,0 |
⋮ \vdots ⋮ | ⋮ \vdots ⋮ | ⋱ \ddots ⋱ | ⋮ \vdots ⋮ | ⋮ \vdots ⋮ | ⋱ \ddots ⋱ | ⋮ \vdots ⋮ | ⋮ \vdots ⋮ |
0 | 0 | ⋯ \cdots ⋯ | 1 | y m , n + 1 y_{m,n+1} ym,n+1 | ⋯ \cdots ⋯ | y m , n y_{m,n} ym,n | y m , 0 y_{m,0} ym,0 |
If y 0 ∈ Z m y_0\in \mathbb{Z}^m y0∈Zm, then done!
If ∃ i : y i , 0 ∉ Z : ∃ \exist i:y_{i,0}\notin\mathbb{Z}:\exist ∃i:yi,0∈/Z:∃ feasible solution x = [ x 1 , ⋯ , x n ] : x i + ∑ j = m + 1 n y i , j x j = y i , 0 x=[x_1,\cdots,x_n]:x_i+\sum_{j=m+1}^n y_{i,j}x_j=y_{i,0} x=[x1,⋯,xn]:xi+∑j=m+1nyi,jxj=yi,0
consider: x i + ∑ j = m + 1 n ⌊ y i , j ⌋ x j ≤ y i , 0 x_i+\sum_{j=m+1}^n \lfloor y_{i,j}\rfloor x_j\leq y_{i,0} xi+∑j=m+1n⌊yi,j⌋xj≤yi,0 valid for all x x x
x i + ∑ j = m + 1 n ⌊ y i , j ⌋ x j ≤ ⌊ y i , 0 ⌋ x_i+\sum_{j=m+1}^n \lfloor y_{i,j}\rfloor x_j\leq \lfloor y_{i,0}\rfloor xi+∑j=m+1n⌊yi,j⌋xj≤⌊yi,0⌋ valid for all x x x
Add ∑ j = m + 1 n ( y i , j − ⌊ y i , j ⌋ ) x i − x n + 1 = y i , 0 − ⌊ y i , 0 ⌋ \sum_{j=m+1}^n (y_{i,j}-\lfloor y_{i,j} \rfloor)x_i-x_{n+1}=y_{i,0}- \lfloor y_{i,0}\rfloor ∑j=m+1n(yi,j−⌊yi,j⌋)xi−xn+1=yi,0−⌊yi,0⌋ to A x = b Ax=b Ax=b. x n + 1 ≥ 0 x_{n+1}\geq 0 xn+1≥0 to x ≥ 0 x\geq 0 x≥0.
Example
max 3 x 1 + 4 x 2 3x_1+4x_2 3x1+4x2
s.t. 3 x 1 − x 2 ≤ 12 3x_1-x_2\leq 12 3x1−x2≤12
3 x 1 + 11 x 2 ≤ 66 3x_1+11x_2\leq 66 3x1+11x2≤66
x 1 , x 2 ≥ 0 x_1,x_2\geq 0 x1,x2≥0
x 1 , x 2 ∈ Z x_1,x_2\in \mathbb{Z} x1,x2∈Z
⇒ \Rightarrow ⇒ min − 3 x 1 − 4 x 2 -3x_1-4x_2 −3x1−4x2
s.t. 3 x 1 − x 2 + x 3 = 12 3x_1-x_2+x_3=12 3x1−x2+x3=12
3 x 1 + 11 x 2 + x 4 = 66 3x_1+11x_2+x_4=66 3x1+11x2+x4=66
x 1 , x 2 , x 3 , x 4 ≥ 0 x_1,x_2,x_3,x_4\geq 0 x1,x2,x3,x4≥0
a 1 a_1 a1 | a 2 a_2 a2 | a 3 a_3 a3 | a 4 a_4 a4 | b b b |
---|---|---|---|---|
3 | -1 | 1 | 0 | 12 |
3 | 11 | 0 | 1 | 66 |
-3 | -4 | 0 | 0 | 0 |
⇒ \Rightarrow ⇒
a 1 a_1 a1 | a 2 a_2 a2 | a 3 a_3 a3 | a 4 a_4 a4 | b b b |
---|---|---|---|---|
1 | 0 | 11 36 \frac{11}{36} 3611 | 1 36 \frac{1}{36} 361 | 11 2 \frac{11}{2} 211 |
0 | 1 | - 1 12 \frac{1}{12} 121 | 1 12 \frac{1}{12} 121 | 9 2 \frac{9}{2} 29 |
0 | 0 | 7 12 \frac{7}{12} 127 | 5 12 \frac{5}{12} 125 | 69 2 \frac{69}{2} 269 |
x 1 ∗ = 11 2 , x 2 ∗ = 9 2 x_1^*=\frac{11}{2},x_2^*=\frac{9}{2} x1∗=211,x2∗=29
∀ x : x 1 + 11 36 x 3 + 1 36 x 4 = 11 2 \forall x:x_1+\frac{11}{36}x_3+\frac{1}{36}x_4=\frac{11}{2} ∀x:x1+3611x3+361x4=211
11 36 x 3 + 1 36 x 4 ≥ 1 2 ⇒ 11 36 x 3 + 1 36 x 4 − x 5 = 1 2 \frac{11}{36}x_3+\frac{1}{36}x_4\geq \frac{1}{2}\Rightarrow \frac{11}{36} x_3+\frac{1}{36}x_4-x_5=\frac{1}{2} 3611x3+361x4≥21⇒3611x3+361x4−x5=21
a 1 a_1 a1 | a 2 a_2 a2 | a 3 a_3 a3 | a 4 a_4 a4 | a 5 a_5 a5 | b b b |
---|---|---|---|---|---|
1 | 0 | 11 36 \frac{11}{36} 3611 | 1 36 \frac{1}{36} 361 | 0 | 11 2 \frac{11}{2} 211 |
0 | 1 | - 1 12 \frac{1}{12} 121 | 1 12 \frac{1}{12} 121 | 0 | 9 2 \frac{9}{2} 29 |
0 | 0 | 11 36 \frac{11}{36} 3611 | 1 36 \frac{1}{36} 361 | -1 | 1 2 \frac{1}{2} 21 |
0 | 0 | 7 12 \frac{7}{12} 127 | 5 12 \frac{5}{12} 125 | -1 | 69 2 \frac{69}{2} 269 |
⟹ simplex \stackrel{\text{simplex}}{\Longrightarrow} ⟹simplex
a 1 a_1 a1 | a 2 a_2 a2 | a 3 a_3 a3 | a 4 a_4 a4 | a 5 a_5 a5 | b b b |
---|---|---|---|---|---|
1 | 0 | 0 | 0 | 1 | 5 |
0 | 1 | 0 | 1 11 \frac{1}{11} 111 | - 3 11 \frac{3}{11} 113 | 51 11 \frac{51}{11} 1151 |
0 | 0 | 1 | 1 11 \frac{1}{11} 111 | - 36 11 \frac{36}{11} 1136 | 18 11 \frac{18}{11} 1118 |
0 | 0 | 0 | 4 11 \frac{4}{11} 114 | 21 11 \frac{21}{11} 1121 | 369 11 \frac{369}{11} 11369 |
x ∗ : x 1 ∗ = 5 , x 2 ∗ = 51 11 , x 3 ∗ = 18 11 x^*:x_1^*=5,x_2^*=\frac{51}{11},x_3^*=\frac{18}{11} x∗:x1∗=5,x2∗=1151,x3∗=1118
1 11 x 4 + 8 11 x 5 − x 6 = 7 11 \frac{1}{11}x_4+\frac{8}{11}x_5-x_6=\frac{7}{11} 111x4+118x5−x6=117
后面还有几步,就是重复切平面的过程,此处省略。
总结
在线性规划的部分,先讲了上节课没讲完的单纯形法的对偶理论,以及互补松弛条件。然后简要介绍了两个非单纯形法的线性规划解法,Khachiyan的椭球法和Karmarkar的内点法,由于与课程关联不大,这里并没有展开讲解。最后重点讲了整数线性规划,介绍了一些定义和理论基础,然后介绍了两个算法,分支定界法和切平面法。