University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

283

Pages:

6
Author:

Parker Adams

1 Outline Slide 1 The Lagrangean dual The strength of the Lagrangean dual Solution of the Lagrangean dual 2 The Lagrangean dual Consider Slide 2 cx s t Ax b Dx d x integer IP = min Z 0 : : = fx integer j Dx dg Optimizing over can be done eciently X X 2.1 Formulation Consider Slide 3 ( ) = min c x + (b ; Ax) ( ) st x2 For xed , problem can be solved eciently ; ( ) = mini=1 ::: m c xi + (b ; Axi ) ( ) is concave and piecewise linear 0 0 Z : : 0 0 Z D X : Z 2.2 Weak Duality If problem ( ) has an optimal solution and if Proof: x an optimal solution to ( ). Then b ; Ax 0 and, therefore, 0, D then ( ) IP Z Z D c x + (b ; Ax ) c x = 0 Since x 2 X, Z 0 0 IP Z ( ) c x + (b ; Ax ) and thus, ( ) IP 0 0 1 Z Z Slide 4 ZD Z(p) p* p 2.3 Key problem Slide 5 Consider the Lagrangean dual: D = max Z Z st : : ( ) 0 D ZIP Z We need to maximize a piecewise linear concave function Slide 6 3 Strength of LD 3.1 Main Theorem X = fx integer j Dx dg Note that CH( ) is a polyhedron. Then : Slide 7 X cx s t Ax b x 2 CH( ) D = min Z 0 : : X 3.2 Example min 3x1 ; x2 s:t: x1 ; x2 ;x1 + 2x2 3x1 + 2x2 6x1 + x2 x1 ,x2 0 2 Slide 8 ;1 5 3 15 integer x2 CH(X) 3 2 . x IP xD xL P 1 0 . . . . . . . . 1 c x1 2 Relax x1 ; x2 ;1, X involves the remaining constraints X = (1 0) (2 0) (1 1) (2 1) (0 2) (1 2) (2 2) (1 3) (2 3) For p 0, : we have ; ( ) = (x min 3 ; 2 + (;1 ; 1 + 2 ) 1 1 x2 ) X Z p x x p x Slide 9 Slide 10 x 2 8 > < ;2 + ( )=> 3 ; 2 : 6;3 = 5 3, and D = (5 3) = ;1 3 xD = ;1 3 4 3, D = ;1 3 xLP = ;1 5 6 5, LP = ;9 5 xIP = (1 2), IP = 1 0 5 3 5 3 3 3 p p p Z p = p p = Z Z = = = = p : Slide 11 Slide 12 = Z = = p = Z = Z LP < ZD < ZIP Z Slide 13 In general, LP D IP For c x = 3 1 ; 2, we have LP D IP . For c x = ; 1 + 2 , we have LP D = IP . For c x = ; 1 ; 2 , we have LP = D = IP . It is also possible: LP = D IP but not on this example. Z 0 0 0 x Z Z x Z < Z < Z x x Z < Z Z x x Z Z Z Z Z < Z 3 Z(p) 4 2 0 p 3.3 LP and LD Slide 14 IP = D for all cost vectors c, if and only if Z Z CH X \ x j Ax b = CH( ) \ x j Ax b X We have LP = D for all cost vectors c, if CH( ) = x j D x d Z Z X If x j D x d , has integer extreme points, then CH( ) = x j Dx d, and therefore D = LP X Z Z 4 Solution of LD Z ; Slide 15 ( ) = mini=1 ::: m c xi + (b ; Axi ) i.e., 0 Z 0 ; ( ) = i=1min + fi ::: m i 0 h : Motivation: classical steepest ascent method for maximizing ( ) Z t+1 = t + rZ ( t ) t Problem: ( ) is not dierentiable Z 4 t =1 2 ::: f (x *) +s' (x -x *) f (x) x x* Z (p) f2 s f1 p* p 4.1 Subgradients A function :