Convex Optimization — Boyd & Vandenberghe 1. Introduction

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.

2 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: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.

3 ,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,..,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)

4 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. 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.

5 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.

6 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.

7 Simplex algorithm for linear programming (Dantzig) 1960s: early interior-point methods (Fiacco & McCormick, Dikin, .. ) 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.

8 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.

9 ,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.

10 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.