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; all norms are convexexamples on Rn affine functionf(x) =aTx+b norms:kxkp= ( ni=1|xi|p)1/pforp 1.

2 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,domf=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.

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

7 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 ; 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 open 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.

9 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: 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}