Ellipsoid Method• ellipsoid method• convergence proof• inequality constraints• feasibility problemsProf. S. Boyd, EE364b, Stanford UniversityEllipsoid method• developed by Shor, Nemirovsky, Yudin in 1970s• used in 1979 by Khachi an to show polyn omi al solvability of LPs• each step requires cutting-plane or subgradient evaluation• modest storage (O(n2))• modest computation per step (O(n2)), via analytical formula• efficient i n theory; slow but steady in practiceProf. S. Boyd, EE364b, Stanford University 1Motivationin cutting-p l an e methods• serious comp u tati on is needed to find next query point(typically O(n2m), with not small c ons tan t)• localization polyhedron grows in complexity as algorithm pr ogre sses(we can, however, prune constraints to keep m proportional to n, e.g.,m = 4n)ellipsoid method addresses both issues, but retains theoretical efficiencyProf. S. Boyd, EE364b, Stanford University 2Ellipsoid algorithm for minimizing convex functionidea: localize x⋆in an ellipsoid instead of a polyhedron1. at iterati on k we know x⋆∈ E(k)2. set x(k):= center(E(k)); evalua te g(k)∈ ∂f(x(k))(g(k)= ∇f(x(k)) if f is di ffer ent ia bl e)3. hence we knowx⋆∈ E(k)∩ {z | g(k)T(z −x(k)) ≤ 0}(a half- el li p soi d)4. set E(k+1):= minimu m volume ellipsoid coveringE(k)∩ {z | g(k)T(z −x(k)) ≤ 0}Prof. S. Boyd, EE364b, Stanford University 3rx(k)E(k)E(k+1)g(k)compared to cutting-plane methods:• localization set doesn’t grow more compli ca ted• easy to compute query point• but, we add unnecessary points in step 4Prof. S. Boyd, EE364b, Stanford University 4Properties of ellipsoid method• reduces to bisection for n = 1• simple f or mu l a for E(k+1)given E(k), g(k)• E(k+1)can be larger than E(k)in diamete r (max semi-axis length), butis always smaller in volume• vol(E(k+1)) < e−12nvol(E(k))(volume re du cti on factor degrades rapidly with n, compared to CG orMVE cutting-pl an e methods)• log vol E(k+1)≤ log vol E(k)− 1/(2n)(uncertainty in location of x⋆decreases by a fixed n um ber of bits eachiteration)Prof. S. B oyd, EE364b, Stanford University 5Example♣x(0)♣x(1)♣x(2)♣x(3)♣x(4)♣x(5)Prof. S. B oyd, EE364b, Stanford University 6Updating the ellipsoidE(x, P ) =z | (z − x)TP−1(z −x) ≤ 1rxrx+r✠E❅❅❅❘E+gProf. S. B oyd, EE364b, Stanford University 7(for n > 1) minimum volume ellipsoid containing half-ellipsoidE ∩z | gT(z −x) ≤ 0is given byx+= x −1n + 1P ˜gP+=n2n2− 1P −2n + 1P ˜g˜gTPwhere ˜g = (1/pgTP g)gP ˜g is step from x to boundary of EProf. S. B oyd, EE364b, Stanford University 8Ellipsoid update — “Hessian” formpropagate H = P−1instead of Px+= x −1n + 1H−1˜gH+=1 −1n2H +2n − 1˜g˜gTwhere ˜g = (1/pgTH−1g)gH−1˜g is step f rom x to boundary of EProf. S. B oyd, EE364b, Stanford University 9Simple stopping criterionf(x⋆) ≥ f(x(k)) + g(k)T(x⋆− x(k))≥ f(x(k)) + infz∈E(k)g(k)T(z −x(k))= f(x(k)) −pg(k)TP(k)g(k)second ineq ua li ty holds since x⋆∈ Eksimple stop p in g criterion:pg(k)TP(k)g(k)≤ ǫ =⇒ f(x(k)) − f(x⋆) ≤ ǫProf. S. B oyd, EE364b, Stanford University 10Basic ellipsoid algorithmellipsoid described as E(x, P ) = {z | (z − x)TP−1(z −x) ≤ 1}given ellipsoi d E(x, P ) containing x⋆, accuracy ǫ > 0repeat1. evaluate g ∈ ∂f(x)2. ifpgTP g ≤ ǫ, return( x)3. update elli ps oid3a. ˜g :=1√gTP gg3b. x := x −1n+1P ˜g3c. P :=n2n2−1P −2n+1P ˜g˜gTPProf. S. B oyd, EE364b, Stanford University 11Interpretation• change coordin ate s so uncertainty is isotr opi c (same in all direc ti ons) ,i.e., E is unit ball• take sub grad i en t step with fi xed length 1/(n + 1)• Shor call s ellipsoid method ‘gradient method with space dilation indirection of gradient’ (which, strangely enough, didn’t catch on)Prof. S. B oyd, EE364b, Stanford University 12ExamplePWL funct ion f(x) = maxmi=1(aTix + bi), with n = 20, m = 1000 50 100 150 200−8−6−4−2024❇❇▼f(x(k)) −pg(k)TP(k)g(k)✠f(x(k))f⋆kProf. S. B oyd, EE364b, Stanford University 130 500 1000 1500 200010−410−310−210−1100kf(k)best− f⋆Prof. S. B oyd, EE364b, Stanford University 14Improvements• keep trac k of best upper and lower bounds:uk= mini=1,...,kf(x(i)), lk= maxi=1,...,kf(x(i)) −pg(i)TP(i)g(i)stop when uk− lk≤ ǫ• can prop agat e Cholesky factor of P(avoids problem of P 6≻ 0 due to numerical roundoff)Prof. S. B oyd, EE364b, Stanford University 150 500 1000 1500 2000−3−2−10123❅■Lk✠Ukf⋆kProf. S. B oyd, EE364b, Stanford University 16Proof of convergenceassumptions:• f is Lipschitz: |f(y) − f(x)| ≤ Gky − xk• E(0)is ball with radius Rsuppose f(x(i)) > f⋆+ ǫ, i = 0, . . . , kthenf(x) ≤ f⋆+ ǫ =⇒ x ∈ E(k)since at iteration i we only discard points with f ≥ f(x(i))Prof. S. B oyd, EE364b, Stanford University 17from Lipsc hi tz condition,kx − x⋆k ≤ ǫ/G =⇒ f(x) ≤ f⋆+ ǫ =⇒ x ∈ E(k)so B = {x | kx − x⋆k ≤ ǫ/G} ⊆ E(k)hence vol(B) ≤ vol(E(k)), soαn(ǫ/G)n≤ e−k/2nvol(E(0)) = e−k/2nαnRn(αnis volume of unit bal l in Rn)therefore k ≤ 2n2log(RG/ǫ )Prof. S. B oyd, EE364b, Stanford University 18E(0)E(k)x(k)f(x) ≤ f⋆+ ǫB = {x | kx − x⋆k ≤ ǫ/G}x⋆conclusion: for k > 2n2log(RG/ǫ ),mini=0,...,kf(x(i)) ≤ f⋆+ ǫProf. S. B oyd, EE364b, Stanford University 19Interpretation of complexitysince x⋆∈ E0= {x | kx − x(0)k ≤ R}, our prior kn ow le dge of f⋆isf⋆∈ [f(x(0)) − GR, f(x(0))]our prior uncertai nty in f⋆is GRafter k iterations our kn ow l edge of f⋆isf⋆∈mini=0,...,kf(x(i)) − ǫ, mini=0,...,kf(x(i))posterior unce rta in ty in f⋆is ≤ ǫProf. S. B oyd, EE364b, Stanford University 20iterations required:2n2logRGǫ= 2n2logprior u n cer tai ntyposterior unce rta in tyefficiency: 0.72/n2bits per subgradient evaluationProf. S. B oyd, EE364b, Stanford University 21Deep cut ellipsoid methodminimum volume ellips oid containing ellipsoid intersected with halfspaceE ∩z | gT(z − x) + h ≤ 0with h ≥ 0, is given byx+= x −1 + αnn + 1P ˜gP+=n2(1 − α2)n2− 1P −2(1 + αn)(n + 1)(1 + α)P ˜g˜gTPwhere˜g =gpgTP g, α =hpgTP g(if α > 1, in ter sec tion is empty)Prof. S. B oyd, EE364b, Stanford University 22Ellipsoid method with deep objective cuts0 500 1000 1500 200010−410−310−210−1100 f(k)best− f⋆kdeep cutsshallow cutsProf. S. B oyd,