3. Convex functions

213591

Convex Optimization - Boyd & Vandenberghe

3. 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 inequalities 3-1

Definition

f:Rn→Ris convex ifdomfis a convex set and (x,f(x))(y,f(y))

•fis concave if-fis convex

•fis strictly convex ifdomfis convex and

f(θx+ (1-θ)y)< θf(x) + (1-θ)f(y) forx,y?domf,x?=y,0< θ <1

Convex functions3-2

Examples on R

convex:

•affine:ax+bonR, for anya,b?R

•exponential:eax, for anya?R

•powers of absolute value:|x|ponR, forp≥1

•negative entropy:xlogxonR++

concave:

•affine:ax+bonR, for anya,b?R

•logarithm:logxonR++

Convex functions3-3

Examples on Rnand Rm×n

affine functions are convex and concave; all norms are convex examples on R n

•affine functionf(x) =aTx+b

•norms:?x?p= (?ni=1|xi|p)1/pforp≥1;?x?∞= maxk|xk| examples on R m×n(m×nmatrices)

•affine function

f(X) =tr(ATX) +b=m? i=1n j=1A ijXij+b

•spectral (maximum singular value) norm

f(X) =?X?2=σmax(X) = (λmax(XTX))1/2

Convex functions3-4

Restriction of a convex function to a line

f: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?Rn can check convexity offby checking convexity of functions of one variable example.f:Sn→Rwithf(X) = logdetX,domf=Sn++ g(t) = logdet(X+tV) = logdetX+ logdet(I+tX-1/2V X-1/2) = logdetX+n? i=1log(1 +tλi) whereλiare the eigenvalues ofX-1/2V X-1/2 gis concave int(for any choice ofX?0,V); hencefis concave

Convex functions3-5

Extended-value extension

extended-value extension

˜foffis

f(x) =f(x), x?domf,˜f(x) =∞, x??domf often simplifies notation; for example, the condition (as an inequality inR? {∞}), means the same as the two conditions

•domfis convex

•forx,y?domf,

Convex functions3-6

First-order condition

fisdifferentiableifdomfis open and the gradient ?f(x) =?∂f(x) ∂x1,∂f(x) ∂x2,...,∂f(x) ∂xn? exists at eachx?domf

1st-order condition:differentiablefwith convex domain is convex iff

f(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 underestimator

Convex functions3-7

Second-order conditions

fistwice differentiableifdomfis open and the Hessian?2f(x)?Sn,

2f(x)ij=∂2f(x)

∂xi∂xj, i,j= 1,...,n, exists at eachx?domf

2nd-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 convex

Convex functions3-8

Examples

quadratic function:f(x) = (1/2)xTPx+qTx+r(withP?Sn) ?f(x) =Px+q,?2f(x) =P convex ifP?0 least-squares objective:f(x) =?Ax-b?22 ?f(x) = 2AT(Ax-b),?2f(x) = 2ATA convex (for anyA) quadratic-over-linear:f(x,y) =x2/y

2f(x,y) =2

y3? y -x?? y -x? T ?0 convex fory >0 xy f(x,y) -202 0 12012

Convex functions3-9

log-sum-exp:f(x) = log?nk=1expxkis convex

2f(x) =1

1Tzdiag(z)-1

(1Tz)2zzT(zk= expxk) to show?2f(x)?0, we must verify thatvT?2f(x)v≥0for allv: v

T?2f(x)v=(?

kzkv2k)(? kzk)-(? kvkzk)2(? kzk)2≥0 since(? kzkv2k)(? kzk)(from Cauchy-Schwarz inequality) geometric mean: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 sublevel sets of convex functions are convex (converse is false) epigraphoff:Rn→R: epif f fis convex if and only ifepifis a convex set

Convex functions3-11

Jensen"s inequality

extension:iffis convex, then for any random variablez basic inequality is special case with discrete distribution prob(z=x) =θ,prob(z=y) = 1-θ

Convex functions3-12

Operations that preserve convexity

practical methods for establishing convexity of a function

1. verify definition (often simplified by restricting to a line)

2. for twice differentiable functions, show?2f(x)?0

3. show thatfis obtained from simple convex functions by operations

that preserve convexity

•nonnegative weighted sum

•composition with affine function

•pointwise maximum and supremum

•composition

•minimization

•perspective

Convex functions3-13

Positive weighted sum&composition with affine function nonnegative multiple:αfis convex iffis convex,α≥0 sum:f1+f2convex iff1,f2convex (extends to infinite sums, integrals) composition with affine function:f(Ax+b)is convex iffis convex examples

•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) =?Ax+b?

Convex functions3-14

Pointwise maximum

iff1, . . . ,fmare convex, thenf(x) = max{f1(x),...,fm(x)}is convex examples •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:

Convex functions3-15

Pointwise supremum

iff(x,y)is convex inxfor eachy? A, then g(x) = sup y?Af(x,y) is convex

Convex Optimization - Boyd & Vandenberghe

3. 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 inequalities 3-1

Definition

f:Rn→Ris convex ifdomfis a convex set and (x,f(x))(y,f(y))

•fis concave if-fis convex

•fis strictly convex ifdomfis convex and

f(θx+ (1-θ)y)< θf(x) + (1-θ)f(y) forx,y?domf,x?=y,0< θ <1

Convex functions3-2

Examples on R

convex:

•affine:ax+bonR, for anya,b?R

•exponential:eax, for anya?R

•powers of absolute value:|x|ponR, forp≥1

•negative entropy:xlogxonR++

concave:

•affine:ax+bonR, for anya,b?R

•logarithm:logxonR++

Convex functions3-3

Examples on Rnand Rm×n

affine functions are convex and concave; all norms are convex examples on R n

•affine functionf(x) =aTx+b

•norms:?x?p= (?ni=1|xi|p)1/pforp≥1;?x?∞= maxk|xk| examples on R m×n(m×nmatrices)

•affine function

f(X) =tr(ATX) +b=m? i=1n j=1A ijXij+b

•spectral (maximum singular value) norm

f(X) =?X?2=σmax(X) = (λmax(XTX))1/2

Convex functions3-4

Restriction of a convex function to a line

f: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?Rn can check convexity offby checking convexity of functions of one variable example.f:Sn→Rwithf(X) = logdetX,domf=Sn++ g(t) = logdet(X+tV) = logdetX+ logdet(I+tX-1/2V X-1/2) = logdetX+n? i=1log(1 +tλi) whereλiare the eigenvalues ofX-1/2V X-1/2 gis concave int(for any choice ofX?0,V); hencefis concave

Convex functions3-5

Extended-value extension

extended-value extension

˜foffis

f(x) =f(x), x?domf,˜f(x) =∞, x??domf often simplifies notation; for example, the condition (as an inequality inR? {∞}), means the same as the two conditions

•domfis convex

•forx,y?domf,

Convex functions3-6

First-order condition

fisdifferentiableifdomfis open and the gradient ?f(x) =?∂f(x) ∂x1,∂f(x) ∂x2,...,∂f(x) ∂xn? exists at eachx?domf

1st-order condition:differentiablefwith convex domain is convex iff

f(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 underestimator

Convex functions3-7

Second-order conditions

fistwice differentiableifdomfis open and the Hessian?2f(x)?Sn,

2f(x)ij=∂2f(x)

∂xi∂xj, i,j= 1,...,n, exists at eachx?domf

2nd-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 convex

Convex functions3-8

Examples

quadratic function:f(x) = (1/2)xTPx+qTx+r(withP?Sn) ?f(x) =Px+q,?2f(x) =P convex ifP?0 least-squares objective:f(x) =?Ax-b?22 ?f(x) = 2AT(Ax-b),?2f(x) = 2ATA convex (for anyA) quadratic-over-linear:f(x,y) =x2/y

2f(x,y) =2

y3? y -x?? y -x? T ?0 convex fory >0 xy f(x,y) -202 0 12012

Convex functions3-9

log-sum-exp:f(x) = log?nk=1expxkis convex

2f(x) =1

1Tzdiag(z)-1

(1Tz)2zzT(zk= expxk) to show?2f(x)?0, we must verify thatvT?2f(x)v≥0for allv: v

T?2f(x)v=(?

kzkv2k)(? kzk)-(? kvkzk)2(? kzk)2≥0 since(? kzkv2k)(? kzk)(from Cauchy-Schwarz inequality) geometric mean: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 sublevel sets of convex functions are convex (converse is false) epigraphoff:Rn→R: epif f fis convex if and only ifepifis a convex set

Convex functions3-11

Jensen"s inequality

extension:iffis convex, then for any random variablez basic inequality is special case with discrete distribution prob(z=x) =θ,prob(z=y) = 1-θ

Convex functions3-12

Operations that preserve convexity

practical methods for establishing convexity of a function

1. verify definition (often simplified by restricting to a line)

2. for twice differentiable functions, show?2f(x)?0

3. show thatfis obtained from simple convex functions by operations

that preserve convexity

•nonnegative weighted sum

•composition with affine function

•pointwise maximum and supremum

•composition

•minimization

•perspective

Convex functions3-13

Positive weighted sum&composition with affine function nonnegative multiple:αfis convex iffis convex,α≥0 sum:f1+f2convex iff1,f2convex (extends to infinite sums, integrals) composition with affine function:f(Ax+b)is convex iffis convex examples

•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) =?Ax+b?

Convex functions3-14

Pointwise maximum

iff1, . . . ,fmare convex, thenf(x) = max{f1(x),...,fm(x)}is convex examples •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:

Convex functions3-15

Pointwise supremum

iff(x,y)is convex inxfor eachy? A, then g(x) = sup y?Af(x,y) is convex