Convex Optimization Boyd Vandenberghe 12 Interior point methods inequality constrained minimization logarithmic barrier function and central path barrier method feasibility and phase I methods complexity analysis via self concordance generalized inequalities 12 1 Inequality constrained minimization minimize f0 x subject to fi x 0 Ax b i 1 m 1 fi convex twice continuously di erentiable A Rp n with rank A p we assume p is nite and attained we assume problem is strictly feasible there exists x with x dom f0 fi x 0 i 1 m Ax b hence strong duality holds and dual optimum is attained Interior point methods 12 2 Examples LP QP QCQP GP entropy maximization with linear inequality constraints n minimize i 1 xi log xi subject to F x g Ax b with dom f0 Rn di erentiability may require reformulating the problem e g piecewise linear minimization or norm approximation via LP SDPs and SOCPs are better handled as problems with generalized inequalities see later Interior point methods 12 3 Logarithmic barrier reformulation of 1 via indicator function m minimize f0 x i 1 I fi x subject to Ax b where I u 0 if u 0 I u otherwise indicator function of R approximation via logarithmic barrier minimize f0 x 1 t subject to Ax b m i 1 log fi x 10 an equality constrained problem for t 0 1 t log u is a smooth approximation of I approximation improves as t Interior point methods 5 0 5 3 2 1 u 0 1 12 4 logarithmic barrier function x m log fi x i 1 dom x f1 x 0 fm x 0 convex follows from composition rules twice continuously di erentiable with derivatives x 2 x Interior point methods m 1 fi x f x i i 1 m m 1 1 T 2 f x f x fi x i i 2 f x fi x i 1 i 1 i 12 5 Central path for t 0 de ne x t as the solution of minimize tf0 x x subject to Ax b for now assume x t exists and is unique for each t 0 central path is x t t 0 example central path for an LP minimize cT x subject to aTi x bi T T c i 1 6 x x 10 hyperplane c x c x t is tangent to level curve of through x t Interior point methods 12 6 Dual points on central path x x t if there exists a w such that t f0 x m i 1 1 fi x AT w 0 fi x Ax b therefore x t minimizes the Lagrangian L x t t f0 x m i 1 i t fi x t T Ax b where we de ne i t 1 tfi x t and t w t this con rms the intuitive idea that f0 x t p if t p g t t L x t t t f0 x t m t Interior point methods 12 7 Interpretation via KKT conditions x x t t t satisfy 1 primal constraints fi x 0 i 1 m Ax b 2 dual constraints 0 3 approximate complementary slackness ifi x 1 t i 1 m 4 gradient of Lagrangian with respect to x vanishes f0 x m i 1 i fi x AT 0 di erence with KKT is that condition 3 replaces ifi x 0 Interior point methods 12 8 Force eld interpretation centering problem for problem with no equality constraints minimize tf0 x m i 1 log fi x force eld interpretation tf0 x is potential of force eld F0 x t f0 x log fi x is potential of force eld Fi x 1 fi x fi x the forces balance at x t F0 x t m Fi x t 0 i 1 Interior point methods 12 9 example minimize cT x subject to aTi x bi i 1 m objective force eld is constant F0 x tc constraint force eld decays as inverse distance to constraint hyperplane Fi x ai T bi ai x Fi x 2 1 dist x Hi where Hi x aTi x bi c 3c t 1 Interior point methods t 3 12 10 Barrier method given strictly feasible x t t 0 0 1 tolerance 0 repeat 1 2 3 4 Centering step Compute x t by minimizing tf0 subject to Ax b Update x x t Stopping criterion quit if m t Increase t t t terminates with f0 x p stopping criterion follows from f0 x t p m t centering usually done using Newton s method starting at current x choice of involves a trade o large means fewer outer iterations more inner Newton iterations typical values 10 20 several heuristics for choice of t 0 Interior point methods 12 11 Convergence analysis number of outer centering iterations exactly log m t 0 log plus the initial centering step to compute x t 0 centering problem minimize tf0 x x see convergence analysis of Newton s method tf0 must have closed sublevel sets for t t 0 classical analysis requires strong convexity Lipschitz condition analysis via self concordance requires self concordance of tf0 Interior point methods 12 12 Examples inequality form LP m 100 inequalities n 50 variables 140 10 0 10 2 10 4 50 150 10 6 0 20 40 60 2 Newton iterations duality gap 102 80 120 100 80 60 40 20 0 0 40 80 Newton iterations 120 160 200 starts with x on central path t 0 1 duality gap 100 terminates when t 108 gap 10 6 centering uses Newton s method with backtracking total number of Newton iterations not very sensitive for 10 Interior point methods 12 13 geometric program m 100 inequalities and n 50 variables minimize subject to 5 T log k 1 exp a0k x b0k 5 T log exp a ik x bik k 1 0 i 1 m duality gap 102 100 10 2 10 4 10 6 0 150 20 50 40 60 2 80 100 120 Newton iterations Interior point methods 12 14 family of standard LPs A Rm 2m minimize cT x subject to Ax b x 0 m 10 1000 for each m solve 100 randomly generated instances Newton iterations 35 30 25 20 15 1 10 102 m 103 number of iterations grows very slowly as m ranges over a 100 1 ratio Interior point methods 12 15 Feasibility and phase I methods feasibility problem nd x such that fi x 0 i 1 m Ax b 2 phase I computes strictly feasible starting point for barrier method basic phase I method minimize over x s s subject to fi x s Ax b i 1 m 3 if x s feasible with s 0 then x is strictly feasible for 2 if optimal value p of 3 is positive then problem 2 is infeasible if p 0 and attained then problem 2 is feasible but not strictly if p 0 and not attained then problem 2 is infeasible Interior point methods 12 16 sum …