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.