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
31
Definition
f : Rn R is convex if dom f is a convex set and
f (x + (1 )y) f (x) + (1 )f (y)
for all x, y dom f , 0 1
(y, f (y))
(x, f (x))
f is concave if f is convex
f is strictly convex if dom f is convex and
f (x + (1 )y) < f (x) + (1 )f (y)
for x, y dom f , x 6= y, 0 < < 1
Convex functions
32
Examples on R
convex:
affine: ax + b on R, for any a, b R
exponential: eax, for any a R
powers: x on R++, for 1 or 0
powers of absolute value: |x|p on R, for p 1
negative entropy: x log x on R++
concave:
affine: ax + b on R, for any a, b R
powers: x on R++, for 0 1
logarithm: log x on R++
Convex functions
33
Examples on Rn and Rmn
affine functions are convex and concave; all norms are convex
examples on Rn
affine function f (x) = aT x + b
Pn
norms: kxkp = ( i=1 |xi|p)1/p for p 1; kxk = maxk |xk |
examples on Rmn (m n matrices)
affine function
f (X) = tr(AT X) + b =
n
m X
X
Aij Xij + b
i=1 j=1
spectral (maximum singular value) norm
f (X) = kXk2 = max(X) = (max(X T X))1/2
Convex functions
34
Restriction of a convex function to a line
f : Rn R is convex if and only if the function g : R R,
g(t) = f (x + tv),
dom g = {t | x + tv dom f }
is convex (in t) for any x dom f , v Rn
can check convexity of f by checking convexity of functions of one variable
example. f : Sn R with f (X) = log det X, dom X = Sn++
g(t) = log det(X + tV ) = log det X + log det(I + tX 1/2V X 1/2)
n
X
log(1 + ti)
= log det X +
i=1
where i are the eigenvalues of X 1/2V X 1/2
g is concave in t (for any choice of X 0, V ); hence f is concave
Convex functions
35
Extended-value extension
extended-value extension f of f is
f(x) = f (x),
x dom f,
f(x) = ,
x 6 dom f
often simplifies notation; for example, the condition
01
f(x + (1 )y) f(x) + (1 )f(y)
(as an inequality in R {}), means the same as the two conditions
dom f is convex
for x, y dom f ,
01
Convex functions
f (x + (1 )y) f (x) + (1 )f (y)
36
First-order condition
f is differentiable if dom f is open and the gradient
f (x) =
f (x) f (x)
f (x)
,
,...,
x1
x2
xn
exists at each x dom f
1st-order condition: differentiable f with convex domain is convex iff
f (y) f (x) + f (x)T (y x)
for all x, y dom f
f (y)
f (x) + f (x)T (y x)
(x, f (x))
first-order approximation of f is global underestimator
Convex functions
37
Second-order conditions
f is twice differentiable if dom f is open and the Hessian 2f (x) Sn,
2f (x)
f (x)ij =
,
xixj
2
i, j = 1, . . . , n,
exists at each x dom f
2nd-order conditions: for twice differentiable f with convex domain
f is convex if and only if
2f (x) 0
for all x dom f
if 2f (x) 0 for all x dom f , then f is strictly convex
Convex functions
38
Examples
quadratic function: f (x) = (1/2)xT P x + q T x + r (with P Sn)
2f (x) = P
f (x) = P x + q,
convex if P 0
least-squares objective: f (x) = kAx bk22
f (x) = 2AT (Ax b),
2f (x) = 2AT A
convex (for any A)
quadratic-over-linear: f (x, y) = x2/y
y
x
y
x
T
0
f (x, y)
2
2f (x, y) = 3
y
2
1
0
2
2
0
convex for y > 0
Convex functions
0 2
x
39
log-sum-exp: f (x) = log
2f (x) =
1
1T z
Pn
k=1 exp xk
diag(z)
is convex
1
T
zz
(1T z)2
(zk = exp xk )
to show 2f (x) 0, we must verify that v T 2f (x)v 0 for all v:
P
P
P
2
( k zk vk )( k zk ) ( k vk zk )2
T 2
P
v f (x)v =
0
( k zk )2
P
P
P
2
2
since ( k vk zk ) ( k zk vk )( k zk ) (from Cauchy-Schwarz inequality)
Qn
geometric mean: f (x) = ( k=1 xk )1/n on Rn++ is concave
(similar proof as for log-sum-exp)
Convex functions
310
Epigraph and sublevel set
-sublevel set of f : Rn R:
C = {x dom f | f (x) }
sublevel sets of convex functions are convex (converse is false)
epigraph of f : Rn R:
epi f = {(x, t) Rn+1 | x dom f, f (x) t}
epi f
f
f is convex if and only if epi f is a convex set
Convex functions
311
Jensens inequality
basic inequality: if f is convex, then for 0 1,
f (x + (1 )y) f (x) + (1 )f (y)
extension: if f is convex, then
f (E z) E f (z)
for any random variable z
basic inequality is special case with discrete distribution
prob(z = x) = ,
Convex functions
prob(z = y) = 1
312
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 that f is 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 functions
313
Positive weighted sum & composition with affine function
nonnegative multiple: f is convex if f is convex, 0
sum: f1 + f2 convex if f1, f2 convex (extends to infinite sums, integrals)
composition with affine function: f (Ax + b) is convex if f is convex
examples
log barrier for linear inequalities
f (x) =
m
X
i=1
log(bi aTi x),
dom f = {x | aTi x < bi, i = 1, . . . , m}
(any) norm of affine function: f (x) = kAx + bk
Convex functions
314
Pointwise maximum
if f1, . . . , fm are convex, then f (x) = max{f1(x), . . . , fm(x)} is convex
examples
piecewise-linear function: f (x) = maxi=1,...,m(aTi x + bi) is convex
sum of r largest components of x Rn:
f (x) = x[1] + x[2] + + x[r]
is convex (x[i] is ith largest component of x)
proof:
f (x) = max{xi1 + xi2 + + xir | 1 i1 < i2 < < ir n}
Convex functions
315
Pointwise supremum
if f (x, y) is convex in x for each y A, then
g(x) = sup f (x, y)
yA
is convex
examples
support function of a set C: SC (x) = supyC y T x is convex
distance to farthest point in a set C:
f (x) = sup kx yk
yC
maximum eigenvalue of symmetric matrix: for X Sn,
max(X) = sup y T Xy
kyk2 =1
Convex functions
316
Composition with scalar functions
composition of g : Rn R and h : R R:
f (x) = h(g(x))
nondecreasing
g convex, h convex, h
f is convex if
nonincreasing
g concave, h convex, h
proof (for n = 1, differentiable g, h)
f (x) = h(g(x))g (x)2 + h(g(x))g (x)
note: monotonicity must hold for extended-value extension h
examples
exp g(x) is convex if g is convex
1/g(x) is convex if g is concave and positive
Convex functions
317
Vector composition
composition of g : Rn Rk and h : Rk R:
f (x) = h(g(x)) = h(g1(x), g2(x), . . . , gk (x))
nondecreasing in each argument
gi convex, h convex, h
f is convex if
nonincreasing in each argument
gi concave, h convex, h
proof (for n = 1, differentiable g, h)
f (x) = g (x)T 2h(g(x))g (x) + h(g(x))T g (x)
examples
Pm
i=1 log gi (x) is concave if gi are concave and positive
Pm
log i=1 exp gi(x) is convex if gi are convex
Convex functions
318
Minimization
if f (x, y) is convex in (x, y) and C is a convex set, then
g(x) = inf f (x, y)
yC
is convex
examples
f (x, y) = xT Ax + 2xT By + y T Cy with
A
BT
B
C
0,
C0
minimizing over y gives g(x) = inf y f (x, y) = xT (A BC 1B T )x
g is convex, hence Schur complement A BC 1B T 0
distance to a set: dist(x, S) = inf yS kx yk is convex if S is convex
Convex functions
319
Perspective
the perspective of a function f : Rn R is the function g : Rn R R,
g(x, t) = tf (x/t),
dom g = {(x, t) | x/t dom f, t > 0}
g is convex if f is convex
examples
f (x) = xT x is convex; hence g(x, t) = xT x/t is convex for t > 0
negative logarithm f (x) = log x is convex; hence relative entropy
g(x, t) = t log t t log x is convex on R2++
if f is convex, then
T
g(x) = (c x + d)f (Ax + b)/(c x + d)
is convex on {x | cT x + d > 0, (Ax + b)/(cT x + d) dom f }
Convex functions
320
The conjugate function
the conjugate of a function f is
f (y) =
sup (y T x f (x))
xdom f
f (x)
xy
x
(0, f (y))
f is convex (even if f is not)
will be useful in chapter 5
Convex functions
321
examples
negative logarithm f (x) = log x
f (y) = sup(xy + log x)
x>0
1 log(y) y < 0
otherwise
strictly convex quadratic f (x) = (1/2)xT Qx with Q Sn++
f (y) = sup(y T x (1/2)xT Qx)
x
Convex functions
1 T 1
y Q y
2
322
Quasiconvex functions
f : Rn R is quasiconvex if dom f is convex and the sublevel sets
S = {x dom f | f (x) }
are convex for all
f is quasiconcave if f is quasiconvex
f is quasilinear if it is quasiconvex and quasiconcave
Convex functions
323
Examples
|x| is quasiconvex on R
ceil(x) = inf{z Z | z x} is quasilinear
log x is quasilinear on R++
f (x1, x2) = x1x2 is quasiconcave on R2++
linear-fractional function
aT x + b
,
f (x) = T
c x+d
dom f = {x | cT x + d > 0}
is quasilinear
distance ratio
kx ak2
f (x) =
,
kx bk2
dom f = {x | kx ak2 kx bk2}
is quasiconvex
Convex functions
324
internal rate of return
cash flow x = (x0, . . . , xn); xi is payment in period i (to us if xi > 0)
we assume x0 < 0 and x0 + x1 + + xn > 0
present value of cash flow x, for interest rate r:
PV(x, r) =
n
X
(1 + r)ixi
i=0
internal rate of return is smallest interest rate for which PV(x, r) = 0:
IRR(x) = inf{r 0 | PV(x, r) = 0}
IRR is quasiconcave: superlevel set is intersection of halfspaces
IRR(x) R
Convex functions
n
X
i=0
(1 + r)ixi 0 for 0 r R
325
Properties
modified Jensen inequality: for quasiconvex f
01
f (x + (1 )y) max{f (x), f (y)}
first-order condition: differentiable f with cvx domain is quasiconvex iff
f (y) f (x)
f (x)T (y x) 0
f (x)
sums of quasiconvex functions are not necessarily quasiconvex
Convex functions
326
Log-concave and log-convex functions
a positive function f is log-concave if log f is concave:
f (x + (1 )y) f (x) f (y)1
for 0 1
f is log-convex if log f is convex
powers: xa on R++ is log-convex for a 0, log-concave for a 0
many common probability densities are log-concave, e.g., normal:
f (x) = p
1
(2)n det
e 2 (xx)
1 (x
x)
cumulative Gaussian distribution function is log-concave
Z x
2
1
eu /2 du
(x) =
2
Convex functions
327
Properties of log-concave functions
twice differentiable f with convex domain is log-concave if and only if
f (x)2f (x) f (x)f (x)T
for all x dom f
product of log-concave functions is log-concave
sum of log-concave functions is not always log-concave
integration: if f : Rn Rm R is log-concave, then
g(x) =
f (x, y) dy
is log-concave (not easy to show)
Convex functions
328
consequences of integration property
convolution f g of log-concave functions f , g is log-concave
(f g)(x) =
f (x y)g(y)dy
if C Rn convex and y is a random variable with log-concave pdf then
f (x) = prob(x + y C)
is log-concave
proof: write f (x) as integral of product of log-concave functions
f (x) =
g(x + y)p(y) dy,
g(u) =
1 uC
0 u
6 C,
p is pdf of y
Convex functions
329
example: yield function
Y (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 values
if S is convex and w has a log-concave pdf, then
Y is log-concave
yield regions {x | Y (x) } are convex
Convex functions
330
Convexity with respect to generalized inequalities
f : Rn Rm is K-convex if dom f is convex and
f (x + (1 )y) K f (x) + (1 )f (y)
for x, y dom f , 0 1
example f : Sm Sm, f (X) = X 2 is Sm
+ -convex
proof: for fixed z Rm, z T X 2z = kXzk22 is convex in X, i.e.,
z T (X + (1 )Y )2z z T X 2z + (1 )z T Y 2z
for X, Y Sm, 0 1
therefore (X + (1 )Y )2 X 2 + (1 )Y 2
Convex functions
331
