Convex Optimization — Boyd & Vandenberghe 4. Convex ...

1 Convex Optimization Boyd & Vandenberghe4. Convex Optimization problems Optimization problem in standard form Convex Optimization problems quasiconvex Optimization linear Optimization quadratic Optimization geometric programming generalized inequality constraints semidefinite programming vector optimization4 1 Optimization problem in standard formminimizef0(x)subject tofi(x) 0, i= 1, .. , mhi(x) = 0, i= 1, .. , p x Rnis the Optimization variable f0:Rn Ris the objective or cost function fi:Rn R,i= 1, .. , m, are the inequality constraint functions hi:Rn Rare the equality constraint functionsoptimal value:p = inf{f0(x)|fi(x) 0, i= 1.}

2 , m, hi(x) = 0, i= 1, .. , p} p = if problem is infeasible (noxsatisfies the constraints) p = if problem is unbounded belowConvex Optimization problems4 2 Optimal and locally optimal pointsxisfeasibleifx domf0and it satisfies the constraintsa feasiblexisoptimaliff0(x) =p ;Xoptis the set of optimal pointsxislocally optimalif there is anR >0such thatxis optimal forminimize (overz)f0(z)subject tofi(z) 0, i= 1, .. , m, hi(z) = 0, i= 1, .. , pkz xk2 Rexamples(withn= 1,m=p= 0) f0(x) = 1/x,domf0=R++:p = 0, no optimal point f0(x) = logx,domf0=R++:p = f0(x) =xlogx,domf0=R++:p = 1/e,x= 1/eis optimal f0(x) =x3 3x,p = , local optimum atx= 1 Convex Optimization problems4 3 Implicit constraintsthe standard form Optimization problem has animplicit constraintx D=m i=0domfi p i=1domhi, we callDthedomainof the problem the constraintsfi(x) 0,hi(x) = 0are the explicit constraints a problem isunconstrainedif it has no explicit constraints (m=p= 0)example.

3 Minimizef0(x) = ki=1log(bi aTix)is an unconstrained problem with implicit constraintsaTix < biConvex Optimization problems4 4 Feasibility problemfindxsubject tofi(x) 0, i= 1, .. , mhi(x) = 0, i= 1, .. , pcan be considered a special case of the general problem withf0(x) = 0:minimize0subject tofi(x) 0, i= 1, .. , mhi(x) = 0, i= 1, .. , p p = 0if constraints are feasible; any feasiblexis optimal p = if constraints are infeasibleConvex Optimization problems4 5 Convex Optimization problemstandard form Convex Optimization problemminimizef0(x)subject tofi(x) 0, i= 1, .. , maTix=bi, i= 1, .. , p f0,f1, .. ,fmare Convex ; equality constraints are affine problem isquasiconvexiff0is quasiconvex (andf1.)

4 ,fmconvex)often written asminimizef0(x)subject tofi(x) 0, i= 1, .. , mAx=bimportant property: feasible set of a Convex Optimization problem is convexConvex Optimization problems4 6exampleminimizef0(x) =x21+x22subject tof1(x) =x1/(1 +x22) 0h1(x) = (x1+x2)2= 0 f0is Convex ; feasible set{(x1, x2)|x1= x2 0}is Convex not a Convex problem (according to our definition):f1is not Convex ,h1is not affine equivalent (but not identical) to the Convex problemminimizex21+x22subject tox1 0x1+x2= 0 Convex Optimization problems4 7 Local and global optimaany locally optimal point of a Convex problem is (globally) optimalproof: supposexis locally optimal, but there exists a feasibleywithf0(y)< f0(x)xlocally optimal means there is anR >0such thatzfeasible,kz xk2 R= f0(z) f0(x)considerz= y+ (1 )xwith =R/(2ky xk2) ky xk2> R, so0< <1/2 zis a Convex combination of two feasible points, hence also feasible kz xk2=R/2andf0(z) f0(y) + (1 )f0(x)< f0(x)which contradicts our assumption thatxis locally optimalConvex Optimization problems4 8 Optimality criterion for differentiablef0xis optimal if and only if it is feasible and f0(x)T(y x) 0for all feasibley f0(x)Xxif nonzero, f0(x)

5 Defines a supporting hyperplane to feasible setXatxConvex Optimization problems4 9 unconstrained problem:xis optimal if and only ifx domf0, f0(x) = 0 equality constrained problemminimizef0(x)subject toAx=bxis optimal if and only if there exists a such thatx domf0,Ax=b, f0(x) +AT = 0 minimization over nonnegative orthantminimizef0(x)subject tox 0xis optimal if and only ifx domf0,x 0,{ f0(x)i 0xi= 0 f0(x)i= 0xi>0 Convex Optimization problems4 10 Equivalent Convex problemstwo problems are (informally)equivalentif the solution of one is readilyobtained from the solution of the other, and vice-versasome common transformations that preserve convexity: eliminating equality constraintsminimizef0(x)subject tofi(x) 0, i= 1.}

6 , mAx=bis equivalent tominimize (overz)f0(F z+x0)subject tofi(F z+x0) 0, i= 1, .. , mwhereFandx0are such thatAx=b x=F z+x0for somezConvex Optimization problems4 11 introducing equality constraintsminimizef0(A0x+b0)subject tofi(Aix+bi) 0, i= 1, .. , mis equivalent tominimize (overx,yi)f0(y0)subject tofi(yi) 0, i= 1, .. , myi=Aix+bi, i= 0,1, .. , m introducing slack variables for linear inequalitiesminimizef0(x)subject toaTix bi, i= 1, .. , mis equivalent tominimize (overx,s)f0(x)subject toaTix+si=bi, i= 1, .. , msi 0, i= 1, .. mConvex Optimization problems4 12 epigraph form: standard form Convex problem is equivalent tominimize (overx,t)tsubject tof0(x) t 0fi(x) 0, i= 1.

7 , mAx=b minimizing over some variablesminimizef0(x1, x2)subject tofi(x1) 0, i= 1, .. , mis equivalent tominimize f0(x1)subject tofi(x1) 0, i= 1, .. , mwhere f0(x1) = infx2f0(x1, x2) Convex Optimization problems4 13 Quasiconvex optimizationminimizef0(x)subject tofi(x) 0, i= 1, .. , mAx=bwithf0:Rn Rquasiconvex,f1, .. ,fmconvexcan have locally optimal points that are not (globally) optimal(x, f0(x)) Convex Optimization problems4 14convex representation of sublevel sets off0iff0is quasiconvex, there exists a family of functions tsuch that: t(x)is Convex inxfor fixedt t-sublevel set off0is0-sublevel set of t, ,f0(x) t t(x) 0examplef0(x) =p(x)q(x)withpconvex,qconcave, andp(x) 0,q(x)>0ondomf0can take t(x) =p(x) tq(x): fort 0, tconvex inx p(x)/q(x) tif and only if t(x) 0 Convex Optimization problems4 15quasiconvex Optimization via Convex feasibility problems t(x) 0,fi(x) 0, i= 1.

8 , m,Ax=b(1) for fixedt, a Convex feasibility problem inx if feasible, we can conclude thatt p ; if infeasible,t p Bisection method for quasiconvex optimizationgivenl p ,u p , tolerance > := (l+u) Solve the Convex feasibility problem (1). (1) is feasible,u:=t;elsel:= l .requires exactly log2((u l)/ ) iterations (whereu,lare initial values) Convex Optimization problems4 16 Linear program (LP)minimizecTx+dsubject toGx hAx=b Convex problem with affine objective and constraint functions feasible set is a polyhedronPx cConvex Optimization problems4 17 Examplesdiet problem:choose quantitiesx1, .. ,xnofnfoods one unit of foodjcostscj, contains amountaijof nutrienti healthy diet requires nutrientiin quantity at leastbito find cheapest healthy diet,minimizecTxsubject toAx b, x 0piecewise-linear minimizationminimizemaxi=1.

9 ,m(aTix+bi)equivalent to an LPminimizetsubject toaTix+bi t, i= 1, .. , mConvex Optimization problems4 18 Chebyshev center of a polyhedronChebyshev center ofP={x|aTix bi, i= 1, .. , m}is center of largest inscribed ballB={xc+u|kuk2 r}xchebxcheb aTix bifor allx Bif and only ifsup{aTi(xc+u)|kuk2 r}=aTixc+rkaik2 bi hence,xc,rcan be determined by solving the LPmaximizersubject toaTixc+rkaik2 bi, i= 1, .. , mConvex Optimization problems4 19 Linear-fractional programminimizef0(x)subject toGx hAx=blinear-fractional programf0(x) =cTx+deTx+f,domf0(x) ={x|eTx+f >0} a quasiconvex Optimization problem; can be solved by bisection also equivalent to the LP (variablesy,z)minimizecTy+dzsubject toGy hzAy=bzeTy+f z= 1z 0 Convex Optimization problems4 20generalized linear-fractional programf0(x) = maxi=1.

10 ,rcTix+dieTix+fi,domf0(x) ={x|eTix+fi>0, i= 1, .. , r}a quasiconvex Optimization problem; can be solved by bisectionexample: Von Neumann model of a growing economymaximize (overx,x+)mini=1,..,nx+i/xisubject tox+ 0, Bx+ Ax x, x+ Rn: activity levels ofnsectors, in current and next period (Ax)i,(Bx+)i: produced, resp. consumed, amounts of goodi x+i/xi: growth rate of sectoriallocate activity to maximize growth rate of slowest growing sectorConvex Optimization problems4 21 Quadratic program (QP)minimize(1/2)xTP x+qTx+rsubject toGx hAx=b P Sn+, so objective is Convex quadratic minimize a Convex quadratic function over a polyhedronPx f0(x ) Convex Optimization problems4 22 Examplesleast-squaresminimizekAx bk22 analytical solutionx =A b(A is pseudo-inverse) can add linear constraints, ,l x ulinear program with random costminimize cTx+ xT x=EcTx+ var(cTx)