Analytic Center Cutting-Plane Method• analytic center cutting-plane method• computing the analytic center• pruning constraints• lower bound and stopping criterionProf. S. Boyd, EE364b, Stanford UniversityAnalytic center cutting-plane methodanalytic center of polyhedron P = {z | aTiz  bi, i = 1, . . . , m} isAC(P) = argminz−mXi=1log(bi− aTiz)ACCPM is localiza tion me thod with next que r y point x(k+1)= AC(Pk)(found by Newton’s method)Prof. S. Boyd, EE364b, Stanford University 1ACCPM algorithmgiven an initial polyhedron P0known to contain X.k := 0.repeatCompute x(k+1)= AC(Pk).Query cutting-plane oracle at x(k+1).If x(k+1)∈ X, quit.Else, add returned cutting-plane inequality to P.Pk+1:= Pk∩ {z | aTz ≤ b}If Pk+1= ∅, quit.k := k + 1.Prof. S. Boyd, EE364b, Stanford University 2Constructing cutting-planesminimize f0(x)subject to fi(x) ≤ 0, i = 1, . . . , mf0, . . . , fm: Rn→ R convex; X is se t of optimal points; p⋆is optimal value• if x is not feasible, say fj(x) > 0, we have (deep) feasibility cutfj(x) + gTj(z − x) ≤ 0, gj∈ ∂fj(x)• if x is feasible, we have (dee p) objective cutgT0(z − x) + f0(x) − f(k)best≤ 0, g0∈ ∂f0(x)Prof. S. Boyd, EE364b, Stanford University 3Computing the analytic centerwe must solve the problemminimize Φ(x) = −Pmi=1log(bi− aTix)where dom Φ = {x | aTix < bi, i = 1, . . . , m}• challenge: we are not given a point in dom Φ• some options:– use p ha se I method to find a point in dom Φ ( or determine thatdom Φ = ∅); then use standard Newton method to compute AC– use infeasible start Newton method starting fr om a point outsidedom ΦProf. S. Boyd, EE364b, Stanford University 4Infeasible start Newton methodminimize −Pmi=1log yisubject to y = b − Axwith variables x and y• can be starte d from any x and any y ≻ 0• e.g.: take initial x as previous point xprev, and choose y asyi=bi− aTix bi− aTix > 01 otherwiseProf. S. Boyd, EE364b, Stanford University 5• define prim a l and dual residuals asrp= y + Ax − b, rd=ATνg + νwhere g = − diag(1/yi)1 is gradient of objective and r = (rd, rp)• Newton step a t (x, y, ν) is defined by0 0 AT0 H IA I 0∆x∆y∆ν= −rdrp,where H = diag(1/y2i) is Hessian of the objectiveProf. S. Boyd, EE364b, Stanford University 6• solve this system by block elimination∆x = −(ATHA)−1(ATg − ATHrp)∆y = −A∆x − rp∆ν = −H∆y − g − ν• options f or computing ∆x:– form ATHA, then use dense or spar se Cholesky f actorization– solve (diagonally scaled) least-squares problem∆x = argminzH1/2Az − H1/2rp+ H−1/2g2– use ite r ative method such as conjuga te gradients to (approximately)solve for ∆xProf. S. Boyd, EE364b, Stanford University 7Infeasible start Newton method algorithmgiven starting point x, y ≻ 0, toler a n ce ǫ > 0, α ∈ (0, 1/2), β ∈ (0, 1).ν := 0.repeat1. Compute Newton step (∆x, ∆y, ∆ν) by block elimination.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≤ ǫ.Prof. S. Boyd, EE364b, Stanford University 8Properties• once any equality constraint is satisfied, it rema ins satisfied f or all futureiterates• once a step size t = 1 is taken, a ll equ a lity constraints are satisfied• if dom Φ 6= ∅, t = 1 occurs in finite number of steps• if dom Φ = ∅, algorithm never convergesProf. S. Boyd, EE364b, Stanford University 9Pruning constraints• let x∗be analytic c enter of P = {z | aTiz  bi, i = 1, . . . , m}• let H∗be Hessian of barrie r at x∗,H∗= −∇2mXi=1log(bi− aTiz)z=x∗=mXi=1aiaTi(bi− aTix∗)2• then, P ⊆ E = {z | (z − x∗)TH∗(z − x∗) ≤ m2}define (ir)relevance measure ηi=bi− aTix∗paTiH∗−1aiProf. S. Boyd, EE364b, Stanford University 10• ηi/m is norm alized distance from hyperplane aTix = bito outer ellipsoid• if ηi≥ m, then c onstra int aTix ≤ biis redundantcommon ACCPM constraint dropping schemes:• drop all constraints with ηi≥ m (guarante ed to not change P)• drop constraints in order of irrelevance, keeping constant number,usually 3n – 5nProf. S. Boyd, EE364b, Stanford University 11PWL lower bound on convex function• suppose f is convex, and g(i)∈ ∂f(x(i)), i = 1, . . . , m• then we haveˆf(z) = maxi=1,...,mf(x(i)) + g(i)T(z − x(i))≤ f(z)•ˆf is PWL lower bound on fProf. S. Boyd, EE364b, Stanford University 12Lower bound in ACCPM• in solving convex problemminimize f0(x)subject to f1(x) ≤ 0,Cx  d(by taking max of constraint functions we can assume there is only one)• we ha ve evaluated f0and subgradient g0at x(1), . . . , x(q)• we ha ve evaluated f1and subgradient g1at x(q+1), . . . , x(k)• form piecew ise-linear approximationsˆf0,ˆf1Prof. S. Boyd, EE364b, Stanford University 13• form PWL relaxed problemminimizeˆf0(x)subject toˆf1(x) ≤ 0,Cx  d(can be solved via LP)• optimal value is a lower bound on p⋆• can easily construct a lower bound on the PWL relaxed problem, as aby-product of the a n a lytic centering computation• this, in turn, gives a lower bound on the original pr oblemProf. S. Boyd, EE364b, Stanford University 14• form dual of PWL relaxed problemmaximizePqi=1λi(f0(x(i)) − g(i)T0x(i))+Pki=q+1λi(f1(x(i)) − g(i)T1x(i)) − dTµsubject toPqi=1λig(i)0+Pki=q+1λig(i)1+ CTµ = 0µ  0, λ  0,Pqi=1λi= 1,• optimality condition for x(k+1)qXi=1g(i)0f(i)best− f0(x(i)) − g(i)T0(x(k+1)− x(i))+kXi=q+1g(i)1−f1(x(i)) − g(i)T1(x(k+1)− x(i))+mXi=1cidi− cTix(k+1)= 0.Prof. S. Boyd, EE364b, Stanford University 15• take τi= 1/(f(i)best− f0(x(i)) − g(i)T0(x(k+1)− x(i))) for i = 1, . . . , q.• construct a dual feasible point by takingλi=τi/1Tτ for i = 1, . . . , q1/(−f1(x(i)) − g(i)T1(x(k+1)− x(i)))(1Tτ) for i = q + 1, . . . , k,µi= 1/(di− cTix(k+1))(1Tτ) i = 1, . . . , m.• using these value s of λ and µ, we conclude thatp⋆≥ l(k+1),where l(k+1)=Pqi=1λi(f0(x(i)) − g(i)T0x(i)) +Pki=q+1λi(f1(x(i)) − g(i)T1x(i)) − dTµ.Prof. S. Boyd, EE364b, Stanford University 16Stopping criterionsince ACCPM isn’t a desce n t method, we keep track of best point found,and best lower bound• best function value so f ar: f(k)best=