Analytic Center Cutting-Plane MethodS. Boy d, L. Vandenberghe, and J. SkafApril 13, 2008Contents1 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 optimization, prove its convergence, and give so me nu-merical examples. ACCPM was developed by Goffin and Vial [GV93] and analyzed byNesterov [Nes95 ] and Atkinson and Vaidya [AV95].These notes assume a basic f amiliarity with convex optimization (see [BV04]), cutting-plane methods (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 polyhedron P0known to contain X.k := 0.repeatCompute x(k+1), the analytic center of Pk.Query the cutting-plane oracle a t 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 example, at each step we can addmultiple cuts, instead of just one. We can also prune or drop constraints, for example, a ftercomputing the analytic center of Pk. Later we will see a simple but non-heuristic stoppingcriterion.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) obj ective value encountered for a feasibleiterate.22 Computing the analytic centerEach iteration of ACCPM requires computing the analytic center o f a set of linear inequalities(and, possibly, determining whether the set of linear inequalities is feasible),aTix ≤ bi, i = 1, . . . , m,that define the current localization polyhedron P. In this section we describe some methodsthat can be used to do this.We note that the inequalities defined by aiand bi, as well as their number m, can changeat each iteration of ACCPM, as we add new cutting-planes and 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, but the domain of the objective function is the openpolyhedrondom Φ = {x | aTix < bi, i = 1, . . . , m},i.e., the interior of the polyhedron. Part of the challenge of computing the analytic center isthat we are not given a point in the domain. One simple approach 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 method (see [BV04, §10.3]) tosolve (3), starting from a point that is outside dom Φ, as suggested by Goffin and Sharifi-Mokhtarian in [GSM99]. We reformulate the problem asminimize −Pmi=1log yisubject to y = b − Ax,(4)with variables x and 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 choo sey asyi=(bi− aTix if bi− aTix > 01 otherwise.In the basic form of ACCPM xprevstrictly satisfies all of the inequalities except t he 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 gra dient of the objective. We also define r to be (rd, rp).The Newton step at a point (x, y, ν) is defined by the system of linear equations0 0 AT0 H IA I 0∆x∆y∆ν= −"rdrp#,where H = diag(1/y2i) is the 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 compute ∆x from the first equation in several ways. We can, for example, formATHA, then compute its Cholesky factorization, then carry out backward and forwardsubstitution. Another option is to compute ∆x by solving the least-squares problem∆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, t olerance ǫ > 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 polyhedron is empty (or, in practice, very small),in which case the algorithm does not conver ge. To guard against this, we fix a maximumnumber of iterations. 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 the shape of P.This suggests the (ir)relevance measureηi=bi− aTix∗kH−1/2aik=bi− aTix∗qaTiH−1aifor the inequality aTix ≤ bi. This factor is always