Optimization Methods - Recitation 10

Recitation 10 1 Convexity Convex sets A set S ⊂ Rn is convex if λx + (1 − λ)y ∈ S for all x, y ∈ S, λ ∈ [0, 1]. Property Intersection of two convex sets is a convex set. Convex functions A function f : Rn → R is convex if: f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) ∀x, y ∈ Rn , λ ∈ [0, 1] Properties Sum of two convex functions is a convex function. f (x) is a convex function, then g(y) := f (Ax + b) is a convex function. The epigraph of a convex function f , epif = {(x, µ) ∈ Rn+1 |µ ≥ f (x)} is a convex set. How to recognize a convex function? Consider a function f that is twice differentiable, that is the gradient vector ∇f (x) and Hessian � � ∂ 2 f (x) matrix∇2 f (x) exists. We have: [∇f (x)]i = ∂f∂x(x) and ∇2 f (x) ij = ∂x and i i ∂xj 1 x) + ∇f (¯ f (x) = f (¯ x)
(x − x) ¯ + (x − x) ¯ ¯
∇2 f (¯ x)(x − x) ¯ + R(x) x − x 2 2 where R(x) → 0 when x → x̄. The function f (x) is convex if and only if the Hessian matrix ∇2 f (x) is positive semi-definite (PSD) for all x. For symmetric real matrix M , the followings are equivalent: 1. M is PSD 2. x
M x ≥ 0 for all x ∈ Rn 3. All eigenvalues are nonnegative 4. All principal minors of M have nonnegative determinants Characterization ¯ ≤ f (x) − f (¯ x). The function f (x) is convex if only if ∇f (¯ x)
(x − x) Examples 1 1. Linear function f (x) = a
x + b 2. Quadratic function f (x) = 12 x
Qx − c
x, where Q is PSD �m log(bi − ai
x), Ax < b 3. Log function f (x) = − i=1 Convex optimization Convex optimization problem is the problem of minimizing a convex function f (x) over a convex set F . Property If x∗ is a local minimum of a convex optimization problem, then x∗ is the global minimum. 2 Unconstrained Optimization Optimality conditions Consider the unconstrained problem minx∈Rn f (x), where f (x) is twice differentiable, the optimality conditions are: 1. Necessary conditions: If x∗ is a local minimum then ∇f (x∗ ) = 0 and ∇2 f (x∗ ) is PSD. 2. Sufficient conditions: If ∇f (¯ x) = 0 and ∃ > 0: ∇2 f (x) is PSD for all x ∈ B(¯ x, ) then x ¯ is a local optimum. For a continuously differentiable convex function f , the sufficient and necessary for x∗ to be the minimum is ∇f (x∗ ) = 0. Example Find a local minimum of the function f (x1 , x2 ) = − log(1 − x1 − x2 ) − log(x1 ) − log(x2 ) with x1 + x2 < 1, x1 > 0, and x2 > 0. We know that the function f (x1 , x2 ) is a convex function; therefore, the only condition we need to check is ∇f (x) = 0. � � 1 1
1 1 ∇f (x1 , x2 ) = − , − 1 − x1 − x2 x1 1 − x1 − x2 x2 � � Solving the system ∇f (x) = 0, we will obtain the solution (x1 , x2 ) = 13 , 13 and this is the minimum of f. Gradient methods Given a differentiable function f in a high dimensional space, the derivative in a direction d at a point x is calculated as follows: f (x + λd) − f (x) ∇f (x)
d = lim λ→0 λ Descent direction: if we have ∇f (x)
d < 0 then for sufficiently small λ > 0, f (x + λd) < f (x). Generic algorithm elements: 1. Iterative update xk+1 = xk + λk dk 2. Descent direction ∇f (xk )
dk < 0, principal example, dk = −Dk ∇f (xk ), where Dk is SPD. 3. Best step length λk = argminλ>0 f (xk + λdk ). Steepest descent method uses the descent direction with D k = I for all k, or dk = −∇f (xk ). The step length can be calculated using exact or inexact line search or can even follow other rules. 2