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–1Definition 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 (x, f(x)) (y, f(y)) • 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 =� y, 0 < θ < 1 Convex functions 3–2Examples 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 o n R++ Convex functions 3–3� � Examples on Rn and Rm×n affine functions are convex and concave; all norms are convex examples on Rn affine function f(x) = aTx + b• • norms: �x�p = ( �n |xi|p)1/p for p ≥ 1; �x�∞ = maxk |xk|i=1 examples on Rm×n (m n matrices) ×affine function • m n f(X) = tr(ATX) + b = AijXij + b i=1 j=1 • spectral (maximum singular value) norm f(X) = �X�2 = σmax(X) = (λmax(XTX))1/2 Convex functions 3–4� 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 f = S++ n →g(t) = log det(X + tV ) = log det X + log det(I + tX−1/2V X−1/2) n = log det X + log(1 + tλi) 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 3–5Extended-value extension extended-value extension f˜of f is f˜(x) = f(x), dom f, f˜(x) = dom fx ∈ ∞, x �∈ often simplifies notation; for example, the condition 0 ≤ θ ≤ 1 = 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, 0 ≤ θ ≤ 1 = ⇒ f(θx + (1 − θ)y) ≤ θf(x) + (1 − θ)f(y) Convex functions 3–6� � 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 (x, f(x)) f(y) f(x) + ∇f(x)T(y − x) first-order approximation of f is global underestimator Convex functions 3–7Second-order conditions f is twice differentiable if dom f is open and the Hessian ∇2f(x) ∈ Sn , 2f(x)ij = ∂2f(x) , i, j = 1, . . . , n, ∇ ∂xi∂xj 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 3–8Examples quadratic function: f(x) = (1/2)xTP x + qTx + r (with P ∈ Sn) ∇f(x) = P x + q, ∇ 2f(x) = P convex if P � 0 least-squares objective: f(x) = �Ax − b�2 2 ∇f(x) = 2AT(Ax − b), ∇ 2f(x) = 2ATA convex (for any A) quadratic-over-linear: f(x, y) = x2/y 2 � �� �T 1 ∇ 2f(x, y) = y2 3 −yx −yx � 0 0 22 10 convex for y > 0 y 0 −2 x f(x, y) Convex functions 3–9log-sum-exp: f(x) = log �kn =1 exp xk is convex ∇ 2f(x) = 1T1 z diag(z) −(1T1 z)2zz T (zk = exp xk) to show ∇2f(x) � 0, we must verify that vT∇2f(x)v ≥ 0 for all v: T ( � k zkvk2)( � k zk) − ( � k vkzk)2 v ∇ 2f(x)v =( � k zk)2 ≥ 0 since ( � k vkzk)2 ≤ ( � k zkvk2)( � k zk) (from Cauchy-Schwarz inequality) geometric mean: f(x) = ( �kn =1 xk)1/n on Rn is concave ++ (similar proof as for log-sum-exp) Convex functions 3–10Epigraph 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 3–11Jensen’s 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) = θ, prob(z = y) = 1 − θ Convex functions 3–12Operations 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 3–13� 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 m f(x) = − log(bi −a Ti x), dom f = {x | aiTx < bi, i = 1, . . . , m}i=1 • (any) norm of affine function: f(x) = �Ax + b� Convex functions 3–14Pointwise maximum if f1, . . . , fm are convex, then f(x) = max{f1(x), .
View Full Document