Convex Optimization — Boyd & Vandenberghe 3. Convex …

1 Convex Optimization Boyd & Vandenberghe3. Convex functions basic properties and examples operations that preserve convexity the conjugate function quasiconvex functions log-concave and log- Convex functions convexity with respect to generalized inequalities3 1 Definitionf:Rn Ris Convex ifdomfis a Convex set andf( x+ (1 )y) f(x) + (1 )f(y)for allx, y domf,0 1(x, f(x))(y, f(y)) fis concave if fis Convex fis strictly Convex ifdomfis Convex andf( x+ (1 )y)< f(x) + (1 )f(y)forx, y domf,x6=y,0< <1 Convex functions3 2 Examples on Rconvex: affine:ax+bonR, for anya, b R exponential:eax, for anya R powers:x onR++, for 1or 0 powers of absolute value:|x|ponR, forp 1 negative entropy:xlogxonR++concave: affine:ax+bonR, for anya, b R powers:x onR++, for0 1 logarithm:logxonR++ Convex functions3 3 Examples on Rnand Rm naffine functions are Convex and concave.

2 All norms are convexexamples on Rn affine functionf(x) =aTx+b norms:kxkp= ( ni=1|xi|p)1/pforp 1;kxk = maxk|xk|examples on Rm n(m nmatrices) affine functionf(X) =tr(ATX) +b=m i=1n j=1 AijXij+b spectral (maximum singular value) normf(X) =kXk2= max(X) = ( max(XTX))1/2 Convex functions3 4 Restriction of a Convex function to a linef:Rn Ris Convex if and only if the functiong:R R,g(t) =f(x+tv),domg={t|x+tv domf}is Convex (int) for anyx domf,v Rncan check convexity offby checking convexity of functions of one :Sn Rwithf(X) = log detX,domX=Sn++g(t) = log det(X+tV) = log detX+ log det(I+tX 1/2V X 1/2)= log detX+n i=1log(1 +t i)where iare the eigenvalues ofX 1/2V X 1/2gis concave int(for any choice ofX 0,V); hencefis concaveConvex functions3 5 Extended-value extensionextended-value extension foffis f(x) =f(x), x domf, f(x) = , x6 domfoften simplifies notation; for example, the condition0 1 = f( x+ (1 )y) f(x) + (1 ) f(y)(as an inequality inR { }), means the same as the two conditions domfis Convex forx, y domf,0 1 = f( x+ (1 )y) f(x) + (1 )f(y) Convex functions3 6 First-order conditionfisdifferentiableifdomfis open and the gradient f(x) =( f(x) x1, f(x) x2.)

3 , f(x) xn)exists at eachx domf1st-order condition:differentiablefwith Convex domain is Convex ifff(y) f(x) + f(x)T(y x)for allx, y domf(x, f(x))f(y)f(x) + f(x)T(y x)first-order approximation offis global underestimatorConvex functions3 7 Second-order conditionsfistwice differentiableifdomfis open and the Hessian 2f(x) Sn, 2f(x)ij= 2f(x) xi xj, i, j= 1, .. , n,exists at eachx domf2nd-order conditions:for twice differentiablefwith Convex domain fis Convex if and only if 2f(x) 0for allx domf if 2f(x) 0for allx domf, thenfis strictly convexConvex functions3 8 Examplesquadratic function:f(x) = (1/2)xTP x+qTx+r(withP Sn) f(x) =P x+q, 2f(x) =Pconvex ifP 0least-squares objective:f(x) =kAx bk22 f(x) = 2AT(Ax b), 2f(x) = 2 ATAconvex (for anyA)quadratic-over-linear:f(x, y) =x2/y 2f(x, y) =2y3[y x] [y x]T 0convex fory >0xyf(x, y) 202012012 Convex functions3 9log-sum-exp:f(x) = log nk=1expxkis Convex 2f(x) =11 Tzdiag(z) 1(1Tz)2zzT(zk= expxk)to show 2f(x) 0, we must verify thatvT 2f(x)v 0for allv:vT 2f(x)v=( kzkv2k)( kzk) ( kvkzk)2( kzk)2 0since( kvkzk)2 ( kzkv2k)( kzk)(from Cauchy-Schwarz inequality)geometric mean.

4 F(x) = ( nk=1xk)1/nonRn++is concave(similar proof as for log-sum-exp) Convex functions3 10 Epigraph and sublevel set -sublevel setoff:Rn R:C ={x domf|f(x) }sublevel sets of Convex functions are Convex (converse is false)epigraphoff:Rn R:epif={(x, t) Rn+1|x domf, f(x) t}epifffis Convex if and only ifepifis a Convex setConvex functions3 11 Jensen s inequalitybasic inequality:iffis Convex , then for0 1,f( x+ (1 )y) f(x) + (1 )f(y)extension:iffis Convex , thenf(Ez) Ef(z)for any random variablezbasic inequality is special case with discrete distributionprob(z=x) = ,prob(z=y) = 1 Convex functions3 12 Operations that preserve convexitypractical methods for establishing convexity of a function1. verify definition (often simplified by restricting to a line)2. for twice differentiable functions , show 2f(x) 03. show thatfis obtained from simple Convex functions by operationsthat preserve convexity nonnegative weighted sum composition with affine function pointwise maximum and supremum composition minimization perspectiveConvex functions3 13 Positive weighted sum&composition with affine functionnonnegative multiple: fis Convex iffis Convex , 0sum:f1+f2convex iff1, f2convex (extends to infinite sums, integrals)composition with affine function:f(Ax+b)is Convex iffis convexexamples log barrier for linear inequalitiesf(x) = m i=1log(bi aTix),domf={x|aTix < bi, i= 1.}

5 , m} (any) norm of affine function:f(x) =kAx+bkConvex functions3 14 Pointwise maximumiff1, .. ,fmare Convex , thenf(x) = max{f1(x), .. , fm(x)}is convexexamples piecewise-linear function:f(x) = maxi=1,..,m(aTix+bi)is Convex sum ofrlargest components ofx Rn:f(x) =x[1]+x[2]+ +x[r]is Convex (x[i]isith largest component ofx)proof:f(x) = max{xi1+xi2+ +xir|1 i1< i2< < ir n} Convex functions3 15 Pointwise supremumiff(x, y)is Convex inxfor eachy A, theng(x) = supy Af(x, y)is convexexamples support function of a setC:SC(x) = supy CyTxis Convex distance to farthest point in a setC:f(x) = supy Ckx yk maximum eigenvalue of symmetric matrix: forX Sn, max(X) = supkyk2=1yTXyConvex functions3 16 Composition with scalar functionscomposition ofg:Rn Randh:R R:f(x) =h(g(x))fis Convex ifgconvex,hconvex, hnondecreasinggconcave,hconvex, hnonincreasing proof (forn= 1, differentiableg, h)f (x) =h (g(x))g (x)2+h (g(x))g (x) note.

6 Monotonicity must hold for extended-value extension hexamples expg(x)is Convex ifgis Convex 1/g(x)is Convex ifgis concave and positiveConvex functions3 17 Vector compositioncomposition ofg:Rn Rkandh:Rk R:f(x) =h(g(x)) =h(g1(x), g2(x), .. , gk(x))fis Convex ifgiconvex,hconvex, hnondecreasing in each argumentgiconcave,hconvex, hnonincreasing in each argumentproof (forn= 1, differentiableg, h)f (x) =g (x)T 2h(g(x))g (x) + h(g(x))Tg (x)examples mi=1loggi(x)is concave ifgiare concave and positive log mi=1expgi(x)is Convex ifgiare convexConvex functions3 18 Minimizationiff(x, y)is Convex in(x, y)andCis a Convex set, theng(x) = infy Cf(x, y)is convexexamples f(x, y) =xTAx+ 2xTBy+yTCywith[A BBTC] 0,C 0minimizing overygivesg(x) = infyf(x, y) =xT(A BC 1BT)xgis Convex , hence Schur complementA BC 1BT 0 distance to a set:dist(x, S) = infy Skx ykis Convex ifSis convexConvex functions3 19 Perspectivetheperspectiveof a functionf:Rn Ris the functiong:Rn R R,g(x, t) =tf(x/t),domg={(x, t)|x/t domf, t >0}gis Convex iffis convexexamples f(x) =xTxis Convex .

7 Henceg(x, t) =xTx/tis Convex fort >0 negative logarithmf(x) = logxis Convex ; hence relative entropyg(x, t) =tlogt tlogxis Convex onR2++ iffis Convex , theng(x) = (cTx+d)f((Ax+b)/(cTx+d))is Convex on{x|cTx+d >0,(Ax+b)/(cTx+d) domf} Convex functions3 20 The conjugate functiontheconjugateof a functionfisf (y) = supx domf(yTx f(x))f(x)(0, f (y))xyx f is Convex (even iffis not) will be useful in chapter 5 Convex functions3 21examples negative logarithmf(x) = logxf (y) = supx>0(xy+ logx)={ 1 log( y)y <0 otherwise strictly Convex quadraticf(x) = (1/2)xTQxwithQ Sn++f (y) = supx(yTx (1/2)xTQx)=12yTQ 1yConvex functions3 22 Quasiconvex functionsf:Rn Ris quasiconvex ifdomfis Convex and the sublevel setsS ={x domf|f(x) }are Convex for all ab c fis quasiconcave if fis quasiconvex fis quasilinear if it is quasiconvex and quasiconcaveConvex functions3 23 Examples |x|is quasiconvex onR ceil(x) = inf{z Z|z x}is quasilinear logxis quasilinear onR++ f(x1, x2) =x1x2is quasiconcave onR2++ linear-fractional functionf(x) =aTx+bcTx+d,domf={x|cTx+d >0}is quasilinear distance ratiof(x) =kx ak2kx bk2,domf={x|kx ak2 kx bk2}is quasiconvexConvex functions3 24internal rate of return cash flowx= (x0.)}

8 , xn);xiis payment in periodi(to us ifxi>0) we assumex0<0andx0+x1+ +xn>0 present value of cash flowx, for interest rater:PV(x, r) =n i=0(1 +r) ixi internal rate of return is smallest interest rate for whichPV(x, r) = 0:IRR(x) = inf{r 0|PV(x, r) = 0}IRRis quasiconcave: superlevel set is intersection of halfspacesIRR(x) R n i=0(1 +r) ixi 0for0 r RConvex functions3 25 Propertiesmodified Jensen inequality:for quasiconvexf0 1 = f( x+ (1 )y) max{f(x), f(y)}first-order condition:differentiablefwith cvx domain is quasiconvex ifff(y) f(x) = f(x)T(y x) 0x f(x)sumsof quasiconvex functions are not necessarily quasiconvexConvex functions3 26 Log-concave and log- Convex functionsa positive functionfis log-concave iflogfis concave:f( x+ (1 )y) f(x) f(y)1 for0 1fis log- Convex iflogfis Convex powers:xaonR++is log- Convex fora 0, log-concave fora 0 many common probability densities are log-concave, , normal:f(x) =1 (2 )ndet e 12(x x)T 1(x x) cumulative Gaussian distribution function is log-concave (x) =1 2 x e u2/2duConvex functions3 27 Properties of log-concave functions twice differentiablefwith Convex domain is log-concave if and only iff(x) 2f(x) f(x) f(x)Tfor allx domf product of log-concave functions is log-concave sum of log-concave functions is not always log-concave integration: iff:Rn Rm Ris log-concave, theng(x) = f(x, y)dyis log-concave (not easy to show) Convex functions3 28consequences of integration property convolutionf gof log-concave functionsf,gis log-concave(f g)(x) = f(x y)g(y)dy ifC Rnconvex andyis a random variable with log-concave pdf thenf(x) =prob(x+y C)is log-concaveproof.

9 Writef(x)as integral of product of log-concave functionsf(x) = g(x+y)p(y)dy,g(u) ={1u C0u6 C,pis pdf ofyConvex functions3 29example: yield functionY(x) =prob(x+w S) x Rn: nominal parameter values for product w Rn: random variations of parameters in manufactured product S: set of acceptable valuesifSis Convex andwhas a log-concave pdf, then Yis log-concave yield regions{x|Y(x) }are convexConvex functions3 30 Convexity with respect to generalized inequalitiesf:Rn RmisK- Convex ifdomfis Convex andf( x+ (1 )y) K f(x) + (1 )f(y)forx,y domf,0 1examplef:Sm Sm,f(X) =X2isSm+-convexproof: for fixedz Rm,zTX2z=kXzk22is Convex inX, ,zT( X+ (1 )Y)2z zTX2z+ (1 )zTY2zforX, Y Sm,0 1therefore( X+ (1 )Y)2 X2+ (1 )Y2 Convex functions3 31}