Analytic Center Cutting-Plane MethodS. Boyd, L. Vandenberghe, and J. SkafApril 14, 2011Contents1 Analytic center cutting-plane method 22 Computing the analytic center 33 Pruning constraints 54 Lower bound and stopping criterion 55 Convergence proof 76 Numerical examples 106.1 Basic ACCPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106.2 ACCPM with constraint dropping . . . . . . . . . . . . . . . . . . . . . . . . 106.3 Epigraph ACCPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131In these notes we describe in more detail the analytic center cutting-plane method (AC-CPM) for non-differentiable convex optimiz at i on , prove its convergence, and give some nu-merical examples. ACCPM was developed by Goffin and Vial [GV93] and analyzed byNesterov [Nes95] and Atkinson and Vaidya [AV95].These note s assume a basic familiarity with convex optimization (see [BV04]), cut t ing-plane method s (see the EE364b notes Localization and Cutting-Plane Methods), and subgra-dients (see the EE364b notes Subgradients).1 Analytic center cutting-plane methodThe basic ACCPM algorithm is:Analytic center cutting-plane method (ACCPM)given an initial polyhed r on P0known to contain X.k := 0.repeatCompute x(k+1), the analytic center of Pk.Query the cutting-plane oracle at x(k+1).If the oracle determines that x(k+1)∈ X, quit.Else, add the returned cutting-plane inequality to P.Pk+1:= Pk∩ {z | aTz ≤ b}If Pk+1= ∅, quit.k := k + 1.There are several variations on this basic algorithm. For exam p l e, at each step we can addmultipl e cuts, instead of just one. We can also prune or drop constraints, for example, aftercomputing the analytic center of Pk. Later we will see a simple but non-heur i st i c stoppi n gcriterion.We can construct a cutting-plane aTz ≤ b at x(k), for the standard convex problemminimize f0(x)subject to fi(x) ≤ 0, i = 1, . . . , m,as follows. If x(k)violates the ith constraint, i.e., fi(x(k)) > 0, we can takea = gi, b = gTix(k)− fi(x(k)), (1)where gi∈ ∂fi(x(k)). If x(k)is feasible, we can takea = g0, b = gT0x(k)− f0(x(k)) + f(k)best, (2)where g0∈ ∂f0(x(k)), and f(k)bestis the best (lowest) object i ve value encountered for a feasibleiterate.22 Computing the analytic centerEach iteration of ACCPM requires computing the analytic center of a set of linear inequalities(and, possibly, determini n g wheth e r the set of linear ineq u a li t i es is feasib l e) ,aTix ≤ bi, i = 1, . . . , m,that define the current localization polyhedron P. In this sect i on we describe some meth odsthat can be used to do this.We note that the i n eq u al i t i es defined by aiand bi, as well as their number m, can changeat each iteration of ACCPM, as we add new cutting-planes an d possibly prune others. Inaddition, these inequalities can include some of the original inequalities that define P0.To find the analytic center, we must solve the problemminimize Φ(x) = −Pmi=1log(bi− aTix).(3)This is an unconstrained problem, bu t the domain of the objective function is the openpolyhedrondom Φ = {x | aTix < bi, i = 1, . . . , m},i.e., the interior of the polyhedr o n . Part of t he challeng e of computing the analytic center isthat we are not given a point in the domain. One simple ap p r oa ch is to use a phase I optimiza-tion method (see [BV04, §11.4]) to find a point in dom Φ (or determine that dom Φ = ∅).Once we find such a point, we can use a standard Newton method to compute the analyticcenter (see [BV04, §9.5]).A simple alternative is to use an infeasible start Newton met hod (see [BV04, §10.3]) tosolve (3), starting from a point that is outside dom Φ, as suggest ed by G offi n and Sharifi-Mokhtarian in [GSM99]. We reformulate the problem asminimize −Pmi=1log yisubject to y = b − Ax,(4)with variables x an d y. The infeasible start Newton method can be started from any x andany y ≻ 0. We can, for example, take the inital x to be the previous point xprev, and ch oosey asyi=(bi− aTix if bi− aTix > 01 otherwise.In the basic form of ACCPM xprevstrictly sat i sfies all of the inequalities except the last oneadded; in this case, yi= bi− aTix holds for all but one index.We define the primal and dual residuals for (4) asrp= y + Ax − b, rd="ATνg + ν#, (5)3where g = −diag(1/yi)1 is the gradient of th e objective. We also define r to be (rd, rp).The Newton step at a point (x, y, ν) is d efined by the system of linear equations0 0 AT0 H IA I 0∆x∆y∆ν= −"rdrp#,where H = diag(1/y2i) is th e Hessian of the objective. We can solve this system by blockelimination (see [BV04, §10.4]), using the expressions∆x = −(ATHA)−1(ATg − ATHrp),∆y = −A∆x −rp, (6)∆ν = −H∆y − g − ν.We can comput e ∆x from the first equation in several ways. We can, for example, formATHA, then compute its Cholesky factorization, t h en carry out backward and forwardsubstitution. Another option is to compute ∆x by solving the least-squar es pr ob l em∆x = argminzH1/2Az − H1/2rp+ H−1/2g.The infeasible start Newton method is:Infeasible start Newton method.given starting point x, y ≻ 0, tolerance ǫ > 0, α ∈ (0, 1/2), β ∈ (0, 1).ν := 0.Compute residuals from (5).repeat1. Compute Newton step (∆x, ∆y, ∆ν) using (6).2. Backtracking line search on krk2.t := 1.while y + t∆y 6≻ 0, t := βt.while kr(x + t∆x, y + t∆y, ν + t∆ν)k2> (1 − α t ) kr(x, y, ν)k2, t := βt.3. Update. x := x + t∆x, y : = y + t∆y, ν := ν + t∆ν.until y = b − Ax and kr(x, y, ν)k2≤ ǫ.This method works quite well, unless the polyh ed r on is empty (or, in practice, very small),in which case the algorithm does n ot converge. To guar d against this, we fix a maximumnumber of iter a t io n s. Typical parameter values are β = 0.5, α = 0.01, with maximumiterations set to 50.43 Pruning constraintsThere is a simple method for ranking the relevance of the inequalities aTix ≤ bi, i = 1, . . . , mthat define a polyhedron P, once we have computed the analytic center x∗. LetH = ∇2Φ(x∗) =mXi=1(bi− aTix)−2aiaTi.Then the ellipsoidEin= {z | (z − x∗)TH(z − x∗) ≤ 1}lies inside P, and the ellipsoidEout= {z | (z − x∗)TH(z − x∗) ≤ m2},which is Einscaled by a factor m about its center, contains P. Thus the ellipsoid Einat leastgrossly (within a factor m) approximates th e shape of P.This suggests the (ir)relevan ce measureηi=bi−