15 093J Optimization Methods Lecture 22 Barrier Interior Point Algorithms 1 Outline Slide 1 1 Barrier Methods 2 The Central Path 3 Approximating the Central Path 4 The Primal Barrier Algorithm 5 The Primal Dual Barrier Algorithm 6 Computational Aspects of IPMs 2 Barrier methods Slide 2 min f x s t gj x 0 hi x 0 j 1 p i 1 m S x gj x 0 j 1 p hi x 0 i 1 m 2 1 Strategy Slide 3 A barrier function G x is a continous function with the property that is approaches as one of gj x approaches 0 from negative values Examples G x p j 1 log gj x G x p j 1 1 gj x Slide 4 Consider a sequence of k 0 k 1 k and k 0 Consider the problem xk argminx S f x k G x Theorem If Every limit point xk generated by a barrier method is a global minimum of the original constrained problem 1 x c x 0 01 x 0 1 central p a th x 1 x 10 analy t ic center 2 2 Primal path following IPMs for LO Slide 5 P min c x s t Ax b x 0 D max s t Barrier problem min s t B x c x n b p A p s c s 0 log xj j 1 Ax b Minimizer x 3 Central Path Slide 6 As varies minimizers x form the central path lim 0 x exists and is an optimal solution x to the initial LP For x is called the analytic center min s t n log xj j 1 Ax b Slide 7 2 x3 Q 1 2 0 1 2 the analy t ic centerof Q 1 3 1 3 1 3 the analy t ic centerof P P x2 the central p a th x1 Q x x x1 0 x3 x1 x3 1 x 0 set of optimal solutions to original LP The analytic center of Q is 1 2 0 1 2 3 1 Example Slide 8 min x2 s t x1 x2 x3 1 x1 x2 x3 0 min s t x2 log x1 log x2 log x3 x1 x2 x3 1 min x2 log x1 log x2 log 1 x1 x2 1 x2 2 1 3 1 9 2 2 x2 2 1 x2 x3 2 The analytic center 1 3 1 3 1 3 Slide 9 3 2 Slide 10 x1 Solution of Central Path Barrier problem for dual max s t p b n j 1 log sj p A s c 3 Solution KKT Ax x A p s s X S e b 0 c 0 e Slide 11 Theorem If x p and s satisfy optimality conditions then they are optimal solutions to problems primal and dual barrier problems Goal Solve barrier problem min B x c x n log xj j 1 s t Ax b 4 Approximating the central path Slide 12 B x ci xi xi 2 B x 2 x2i xi 2 B x 0 i j xi xj Given a vector x 0 Slide 13 B x d B x n i 1 B x di xi n 1 2 B x di dj 2 i j 1 xi xj 1 B x c e X 1 d d X 2 d 2 X diag x1 xn Approximating problem min s t Slide 14 1 c e X 1 d d X 2 d 2 Ad 0 Solution from Lagrange c X 1 e X 2 d A p 0 Ad 0 4 Slide 15 x c x 0 01 central p a th x 0 1 x 1 x 10 analy t ic center System of m n linear equations with m n unknowns dj j 1 n and pi i 1 m Solution 1 I X 2 A AX 2 A 1 A xe X 2 c 2 1 2 p AX A A X c xe d 4 1 The Newton connection Slide 16 d is the Newton direction process of calculating this direction is called a Newton step Starting with x the new primal solution is x d The corresponding dual solution becomes p s p c A p We then decrease to 0 1 4 2 Geometric Interpretation Slide 17 Take one Newton step so that x would be close to x Measure of closeness 1 XSe e 0 1 X diag x1 xn S diag s1 sn As 0 the complementarity slackness condition will be satis ed 5 Slide 18 5 The Primal Barrier Algorithm Slide 19 Input a A b c A has full row rank b x0 0 s0 0 p0 c optimality tolerance 0 d 0 and where 0 1 1 Initialization Start with some primal and dual feasible x0 0 s0 0 p0 and set k 0 2 Optimality test If sk xk stop else go to Step 3 3 Let Slide 20 X k diag xk1 xkn k 1 k Slide 21 4 Computation of directions Solve the linear system 2 1 k 1 k 1 X X k d A p k e c Ad 0 5 Update of solutions Let xk 1 xk d pk 1 p sk 1 c A p 6 Let k k 1 and go to Step 2 5 1 Correctness 1 x0 s0 p0 x0 0 s0 0 Theorem Given 1 n 1 X 0 S 0 e e 0 Then after K n s0 x0 1 log 1 iterations xK sK pK is found sK xK 6 Slide 22 5 2 Complexity Slide 23 Work per iteration involves solving a linear system with m n equations in m n unknowns Given that m n the work per iteration is O n3 0 s0 x0 initial duality gap Algorithm needs 0 O n log iterations to reduce the duality gap from 0 to with O n3 arithmetic operations per iteration 6 6 1 The Primal Dual Barrier Algorithm Optimality Conditions Slide 24 Ax b x A p s 0 c s sj xj 0 or X S e e X diag x1 xn S diag s1 sn 6 2 Solving Equations Slide 25 Ax b F z A p s c XSe e z x p s r 2n m Solve F z 0 6 2 1 Newton s method Slide 26 F z k d F z k J z k d Here J z k is the r r Jacobian matrix whose i j th element is given by Fi z zj z z k F z k J z k d 0 Set z k 1 z k d d is the Newton direction 7 Slide 27 xk pk sk current primal and dual feasible solution Newton direction d dkx dkp dks 6 2 2 A 0 0 Sk A 0 0 dkx Axk b I dkp A pk sk c Xk X k S k e k e dks Step lengths Slide 28 xk 1 xk Pk dkx k k pk 1 pk D dp k k sk …