Optimization Methods - The Affine Scaling Algorithm | Massachusetts Institute of Technology

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

2023
Views:

100

Pages:

7
Author:

riulagr

1 Outline Slide 1 History Geometric intuition Algebraic development A ne Scaling Convergence Initialization Practical performance 2 History In 1984, Karmakar at AT&T \invented" interior point method In 1985, A ne scaling \invented" at IBM + AT&T seeking intuitive version of Karmarkar's algorithm In early computational tests, A.S. far outperformed simplex and Karmarkar's algorithm In 1989, it was realised Dikin invented A.S. in 1967 Slide 2 3 Geometric intuition 3.1 Notation min st cx Ax = b x0 max st pb pAc : : and its dual : : = fx j Ax = b x 0g fx 2 j x 0g the interior of 0 0 0 0 P P > P 1 and its elements interior points Slide 3 c . x2 . x1 . x0 3.2 The idea Slide 4 4.1 Theorem Slide 5 4 Algebraic development 2 (0 1), y 2 0, and S= ( X (x n x2< n i �1 i ) ; yi )2 2 : y2 i Then, x > 0 for every x 2 S Proof x2S (xi ; yi )2 2 yi2 < yi2 jxi ; yi j < yi ;xi + yi < yi , and hence xi > 0 x2 Replace original LP: S is equivalent to jY 1 (x ; y)j ; min c x s t Ax =1 b jY (x ; y)j 0 : : ; 2 : Slide 6 d = x;y min c d s t Ad = 0 0 : : Y 1djj jj ; 4.2 Solution If rows of A are linearly independent and c is not a linear combination of the rows of A, then optimal solution d : 2 d = ; jYY ((cc;;AA pp))j p = (AY 2A ) 1AY 2c x=y+d 2 c x = c y ; jY (c ; A p)j c y Slide 7 � 0 � � 0 0 0 ; 0 : P 0 0 < 4.2.1 Proof AY 2 A is invertibleif not, there exists some z = 6 0 such that z AY 2 A z = 0 0 0 0 w = Y A z w w = 0 ) w = 0 Hence A z = 0 contradiction 6 0 and d is well Since c is not a linear combination of the rows of A, c ; A p = de ned d feasible Y 1 d = ; jYY ((cc ;; AA pp))j ) jjY 1 d jj = Ad = 0, since AY 2 (c ; A p) = 0 c d = (c ; p A)d = (c ; p A)Y Y 1 d ;jY (c ; A p)j jjY 1 djj ; jY (c ; A p)j: Slide 8 0 0 0 0 � � ; 0 � ; � 0 � 0 0 0 0 0 0 ; 0 ; 0 c d = (c ; p A)d 2 = ;(c ; p A) Y (c ; A p) jY (c ; A p) j ;Y (c ; A p) ;Y (c ; A p) =; jY (c ; A p)j = ; jY (c ; A p)j: c x = c y + c d = c y ; jY (c ; A p)j 0 � 0 0 0 � 0 0 0 0 0 0 0 0 0 0 0 � 0 0 3 Slide 9 4.3 Interpretation y be a nondegenerate BFS with basis B A = B N ] Y = diag( 1 0) and Y 0 = diag( 1 m 0 B Y 0 0] p = (AY 2A ) 1AY 2c = (B ) 1 Y 0 2 B 1B Y 20cB = (B ) 1 cB Vectors p dual estimates r = c ; A p becomes reduced costs: r = c ; A (B ) 1cB y : : : y : : : Slide 10 m ), y : : : y then AY = 0 ; 0 ; ; ; 0 0 ; 0 ; 0 Under degeneracy? 4.4 Termination y and p be primal and dual feasible solutions with c y;bp y and p be optimal primal and dual solutions. Then, cy cy cy + bp ; bp bp 0 0 � Slide 11 < � 0 0 � � 0 < 0 < 0 � 0 � 4.4.1 Proof cy 0 � Slide 12 cy 0 By weak duality, b p c y Since c y ; b p 0 0 0 < 0 � cy bp+ cy + bp = c y c y bp+ 0 0 � 0 < 0 0 � 4 0 < � 0 5 Ane Scaling 5.1 Inputs Slide 13 (A b c) an initial primal feasible solution x0 the optimality tolerance 0 the parameter 2 (0 1) > 0 > 5.2 The Algorithm 1. 2. (Initialization) Start with some feasible x0 0 let = 0. (Computation of dual estimates and reduced costs) Given some feasible xk 0, let > Slide 14 k > k) X k = diag( k1 n pk = (AX 2k A ) 1AX 2kc rk = c ; A pk (Optimality check) Let e = (1 1 1). If rk 0 and e X k r k , then k stop the current solution x is primal -optimal and pk is dual -optimal. (Unboundedness check) If ;X 2k rk 0 then stop the optimal cost is ;1. x : : : x 0 ; 0 3. : 0 : : : 4. 5. < (Update of primal solution) Let 2 k kr xk+1 = xk ; jjX Xk rk jj 5.3 Variants u = maxi j ij (u) = maxf (u) jjujj jjujj jj jj1 u u i j ui > : Slide 15 0g 1 method. Long-step variants Short-step 2 k xk+1 = xk ; jjXXkkrrk jj 2 k xk+1 = xk ; (XXkkrrk) 1 5 6 Convergence 6.1 Assumptions Assumptions A: (a) The rows of the matrix A are linearly independent. (b) The vector c is not a linear combination of the rows of A. (c) There exists an optimal solution. (d) There exists a positive feasible solution. Assumptions B: (a) Every BFS to the primal problem is nondegenerate. (b) At every BFS to the primal problem, the reduced cost of every nonbasic variable is nonzero. 6.2 Theorem If we apply the long-step a ne scaling algorithm with = 0, the following hold: (a) For the Long-step variant and under Assumptions A and B, and if 0 < < 1, xk and pk converge to the optimal primal and dual solutions (b) For the second Long-step variant, and under Assumption A and if 0 < < 2=3, the sequences xk and pk converge to some primal and dual optimal solutions, respectively 7 Initialization min st ; : : x cx + Ax + (b ; Ae) n+1 xn+1 0 Mx n+1 0 x 8 Example max st x1 x1 : : ;x1 +2 + + x2 x2 x2 x1 x2 0 Slide 18 =b 2 1 Excellent practical performance, simple Major step: invert AX 2k A Imitates the simplex method near the boundary 6 Slide 17 Slide 19 9 Practical Performance 0 Slide 16 Slide 20 x2 2 1 .. ... .. .. 2 7 x1