Convex Optimization — Boyd ... - Stanford University

1 Convex Optimization Boyd & Vandenberghe1. Introduction mathematical Optimization least-squares and linear programming Convex Optimization example course goals and topics nonlinear Optimization brief history of Convex optimization1 1 Mathematical Optimization (mathematical) Optimization problemminimizef0(x)subject tofi(x) bi, i= 1,..,m x= (x1,..,xn): Optimization variables f0:Rn R: objective function fi:Rn R,i= 1,..,m: constraint functionsoptimal solutionx has smallest value off0among all vectors thatsatisfy the constraintsIntroduction1 2 Examplesportfolio Optimization variables: amounts invested in different assets constraints: budget, investment per asset, minimum return objective: overall risk or return variancedevice sizing in electronic circuits variables: device widths and lengths constraints: manufacturing limits, timing requirements,maximum area objective: power consumptiondata fitting variables: model parameters constraints: prior information, parameter limits objective: measure of misfit or prediction errorIntroduction1 3 solving Optimization problemsgeneral Optimization problem very difficult to solve methods involve some compromise, , very long computation time, ornot always finding the solutionexceptions.

2 Certain problem classes can be solved efficiently and reliably least-squares problems linear programming problems Convex Optimization problemsIntroduction1 4 Least-squaresminimizekAx bk22solving least-squares problems analytical solution:x = (ATA) 1 ATb reliable and efficient algorithms and software computation time proportional ton2k(A Rk n); less if structured a mature technologyusing least-squares least-squares problems are easy to recognize a few standard techniques increase flexibility ( , including weights,adding regularization terms)Introduction1 5 Linear programmingminimizecTxsubject toaTix bi, i= 1,..,msolving linear programs no analytical formula for solution reliable and efficient algorithms and software computation time proportional ton2mifm n; less with structure a mature technologyusing linear programming not as easy to recognize as least-squares problems a few standard tricks used to convert problems into linear programs( , problems involving 1- or -norms, piecewise-linear functions)Introduction1 6 Convex Optimization problemminimizef0(x)subject tofi(x) bi, i= 1.

3 ,m objective and constraint functions are Convex :fi( x+ y) fi(x) + fi(y)if + = 1, 0, 0 includes least-squares problems and linear programs as special casesIntroduction1 7solving Convex Optimization problems no analytical solution reliable and efficient algorithms computation time (roughly) proportional tomax{n3,n2m,F}, whereFis cost of evaluatingfi s and their first and second derivatives almost a technologyusing Convex Optimization often difficult to recognize many tricks for transforming problems into Convex form surprisingly many problems can be solved via Convex optimizationIntroduction1 8 Examplemlamps illuminatingn(small, flat) patcheslamp powerpjilluminationIkrkj kjintensityIkat patchkdepends linearly on lamp powerspj:Ik=mXj=1akjpj, akj=r 2kjmax{cos kj,0} problem : achieve desired illuminationIdeswith bounded lamp powersminimizemaxk=1,..,n|logIk logIdes|subject to0 pj pmax, j= 1,..,mIntroduction1 9how to solve?1. use uniform power:pj=p, varyp2.

4 Use least-squares:minimizePnk=1(Ik Ides)2roundpjifpj> pmaxorpj<03. use weighted least-squares:minimizePnk=1(Ik Ides)2+Pmj=1wj(pj pmax/2)2iteratively adjust weightswjuntil0 pj pmax4. use linear programming :minimizemaxk=1,..,n|Ik Ides|subject to0 pj pmax, j= 1,..,mwhich can be solved via linear programmingof course these are approximate (suboptimal) solutions Introduction1 105. use Convex Optimization : problem is equivalent tominimizef0(p) = maxk=1,..,nh(Ik/Ides)subject to0 pj pmax, j= 1,..,mwithh(u) = max{u,1/u}01234012345uh(u)f0is Convex because maximum of Convex functions is convexexactsolution obtained with effort modest factor least-squares effortIntroduction1 11additional constraints:does adding 1 or 2 below complicate the problem ?1. no more than half of total power is in any 10 lamps2. no more than half of the lamps are on (pj>0) answer: with (1), still easy to solve; with (2), extremely difficult moral: (untrained) intuition doesn t always work; withoutthe properbackground very easy problems can appear quite similar to very difficultproblemsIntroduction1 12 Course goals and topicsgoals1.

5 Recognize/formulate problems (such as the illuminationproblem) asconvex Optimization problems2. develop code for problems of moderate size (1000 lamps, 5000 patches)3. characterize optimal solution (optimal power distribution), give limits ofperformance, Convex sets, functions, Optimization problems2. examples and applications3. algorithmsIntroduction1 13 Nonlinear optimizationtraditional techniques for general nonconvex problems involve compromiseslocal Optimization methods(nonlinear programming ) find a point that minimizesf0among feasible points near it fast, can handle large problems require initial guess provide no information about distance to (global) optimumglobal Optimization methods find the (global) solution worst-case complexity grows exponentially with problem sizethese algorithms are often based on solving Convex subproblemsIntroduction1 14 Brief history of Convex optimizationtheory ( Convex analysis): ca1900 1970algorithms 1947: simplex algorithm for linear programming (Dantzig) 1960s: early interior-point methods (Fiacco & McCormick, Dikin.)

6 1970s: ellipsoid method and other subgradient methods 1980s: polynomial-time interior-point methods for linearprogramming(Karmarkar 1984) late 1980s now: polynomial-time interior-point methods for nonlinearconvex Optimization (Nesterov & Nemirovski 1994)applications before 1990: mostly in operations research; few in engineering since 1990: many new applications in engineering (control,signalprocessing, communications, circuit design, .. ); new problem classes(semidefinite and second-order cone programming , robust Optimization )Introduction1 15 Convex Optimization Boyd & Vandenberghe2. Convex sets affine and Convex sets some important examples operations that preserve convexity generalized inequalities separating and supporting hyperplanes dual cones and generalized inequalities2 1 Affine setlinethroughx1,x2: all pointsx= x1+ (1 )x2( R)x1x2 = = 1 = = 0 = set: contains the line through any two distinct points in the setexample: solution set of linear equations{x|Ax=b}(conversely, every affine set can be expressed as solution setof system oflinear equations) Convex sets2 2 Convex setline segmentbetweenx1andx2: all pointsx= x1+ (1 )x2with0 1convex set: contains line segment between any two points in the setx1,x2 C,0 1 = x1+ (1 )x2 Cexamples(one Convex , two nonconvex sets) Convex sets2 3 Convex combination and Convex hullconvex combinationofx1.

7 ,xk: any pointxof the formx= 1x1+ 2x2+ + kxkwith 1+ + k= 1, i 0convex hullconvS: set of all Convex combinations of points inSConvex sets2 4 Convex coneconic (nonnegative) combinationofx1andx2: any point of the formx= 1x1+ 2x2with 1 0, 2 00x1x2convex cone: set that contains all conic combinations of points in the setConvex sets2 5 Hyperplanes and halfspaceshyperplane: set of the form{x|aTx=b}(a6= 0)axaTx=bx0halfspace:set of the form{x|aTx b}(a6= 0)aaTx baTx bx0 ais the normal vector hyperplanes are affine and Convex ; halfspaces are convexConvex sets2 6 Euclidean balls and ellipsoids(Euclidean) ballwith centerxcand radiusr:B(xc,r) ={x|kx xck2 r}={xc+ru|kuk2 1}ellipsoid:set of the form{x|(x xc)TP 1(x xc) 1}withP Sn++( ,Psymmetric positive definite)xcother representation:{xc+Au|kuk2 1}withAsquare and nonsingularConvex sets2 7 Norm balls and norm conesnorm:a functionk kthat satisfies kxk 0;kxk= 0if and only ifx= 0 ktxk=|t|kxkfort R kx+yk kxk+kyknotation:k kis general (unspecified) norm;k ksymbis particular normnorm ballwith centerxcand radiusr:{x|kx xck r}norm cone:{(x,t)|kxk t}Euclidean norm cone is called second-order conex1x2t 101 balls and cones are convexConvex sets2 8 Polyhedrasolution set of finitely many linear inequalities and equalitiesAx b, Cx=d(A Rm n,C Rp n, is componentwise inequality)a1a2a3a4a5 Ppolyhedron is intersection of finite number of halfspaces and hyperplanesConvex sets2 9 Positive semidefinite conenotation: Snis set of symmetricn nmatrices Sn+={X Sn|X 0}: positive semidefiniten nmatricesX Sn+ zTXz 0for allzSn+is a Convex cone Sn++={X Sn|X 0}: positive definiten nmatricesexample: x yy z S2+ sets2 10 Operations that preserve convexitypractical methods for establishing convexity of a setC1.

8 Apply definitionx1,x2 C,0 1 = x1+ (1 )x2 C2. show thatCis obtained from simple Convex sets (hyperplanes,halfspaces, norm balls, .. ) by operations that preserve convexity intersection affine functions perspective function linear-fractional functionsConvex sets2 11 Intersectionthe intersection of (any number of) Convex sets is convexexample:S={x Rm||p(t)| 1for|t| /3}wherep(t) =x1cost+x2cos 2t+ +xmcosmtform= 2:0 /32 /3 101tp(t)x1x2S 2 1012 2 1012 Convex sets2 12 Affine functionsupposef:Rn Rmis affine (f(x) =Ax+bwithA Rm n,b Rm) the image of a Convex set underfis convexS Rnconvex= f(S) ={f(x)|x S} Convex the inverse imagef 1(C)of a Convex set underfis convexC Rmconvex= f 1(C) ={x Rn|f(x) C}convexexamples scaling, translation, projection solution set of linear matrix inequality{x|x1A1+ +xmAm B}(withAi,B Sp) hyperbolic cone{x|xTPx (cTx)2, cTx 0}(withP Sn+) Convex sets2 13 Perspective and linear-fractional functionperspective functionP:Rn+1 Rn.

9 P(x,t) =x/t,domP={(x,t)|t >0}images and inverse images of Convex sets under perspective are convexlinear-fractional functionf:Rn Rm:f(x) =Ax+bcTx+d,domf={x|cTx+d >0}images and inverse images of Convex sets under linear-fractional functionsare convexConvex sets2 14exampleof a linear-fractional functionf(x) =1x1+x2+ 1xx1x2C 101 101x1x2f(C) 101 101 Convex sets2 15 Generalized inequalitiesa Convex coneK Rnis aproper coneif Kis closed (contains its boundary) Kis solid (has nonempty interior) Kis pointed (contains no line)examples nonnegative orthantK=Rn+={x Rn|xi 0, i= 1,..,n} positive semidefinite coneK=Sn+ nonnegative polynomials on[0,1]:K={x Rn|x1+x2t+x3t2+ +xntn 1 0fort [0,1]} Convex sets2 16generalized inequalitydefined by a proper coneK:x Ky y x K,x Ky y x intKexamples componentwise inequality (K=Rn+)x Rn+y xi yi, i= 1,..,n matrix inequality (K=Sn+)X Sn+Y Y Xpositive semidefinitethese two types are so common that we drop the subscript in Kproperties:many properties of Kare similar to onR, ,x Ky, u Kv= x+u Ky+vConvex sets2 17 Minimum and minimal elements Kis not in general alinear ordering: we can havex6 Kyandy6 Kxx Sisthe minimum elementofSwith respect to Kify S= x Kyx Sisa minimal elementofSwith respect to Kify S, y Kx= y=xexample(K=R2+)x1is the minimum element ofS1x2is a minimal element ofS2x1x2S1S2 Convex sets2 18 Separating hyperplane theoremifCandDare nonempty disjoint Convex sets, there exista6= 0, bforx C, aTx bforx DDCaaTx baTx bthe hyperplane{x|aTx=b}separatesCandDstrict separation requires additional assumptions ( ,Cis closed,Dis asingleton) Convex sets2 19 Supporting hyperplane theoremsupporting hyperplaneto setCat boundary pointx0:{x|aTx=aTx0}wherea6= 0andaTx aTx0for allx CCax0supporting hyperplane theorem.

10 IfCis Convex , then there exists asupporting hyperplane at every boundary point ofCConvex sets2 20 Dual cones and generalized inequalitiesdual coneof a coneK:K ={y|yTx 0for allx K}examples K=Rn+:K =Rn+ K=Sn+:K =Sn+ K={(x,t)|kxk2 t}:K ={(x,t)|kxk2 t} K={(x,t)|kxk1 t}:K ={(x,t)|kxk t}first three examples areself-dualconesdual cones of proper cones are proper, hence define generalized inequalities:y K 0 yTx 0for allx K0 Convex sets2 21 Minimum and minimal elements via dual inequalitiesminimum Kxis minimum element ofSiff for all K 0,xis the unique minimizerof TzoverSxSminimal K ifxminimizes TzoverSfor some K 0, thenxis minimalSx1x2 1 2 ifxis a minimal element of aconvexsetS, then there exists a nonzero K 0such thatxminimizes TzoverSConvex sets2 22optimal production frontier different production methods use different amounts of resourcesx Rn production setP: resource vectorsxfor all possible production methods efficient (Pareto optimal) methods correspond to resource vectorsxthat are minimal +example(n= 2)x1,x2,x3are efficient;x4,x5are notx4x2x1x5x3 PlaborfuelConvex sets2 23 Convex Optimization Boyd & Vandenberghe3.