Introduction to Optimization, and Optimality Conditions for Unconstrained Problems

Introduction to Optimization, and Optimality Conditions for Unconstrained Problems Robert M. Freund February, 2004 2004 Massachusetts Institute of Technology. 1 1 Preliminaries 1.1 Types of optimization problems Unconstrained Optimization Problem: f (x) (P) minx s.t. x ∈ X, where x = (x1 , . . . , xn ) ∈ n , f (x) : n → , and X is an open set (usually X = n ). We say that x is a feasible solution of (P) if x ∈ X. Constrained Optimization Problem: (P) minx s.t. f (x) gi (x) ≤ 0 i = 1, . . . , m hi (x) = 0 i = 1, . . . , l x ∈ X, where g1 (x), . . . , gm (x), h1 (x), . . . , hl (x) : n → . Let g(x) = (g1 (x), . . . , gm (x)) : n → m , h(x) = (h1 (x), . . . , hl (x)) : 2 n → l . Then (P) can be written as (P) minx f (x) g(x) ≤ 0 s.t. h(x) = 0 (1) x ∈ X. We say that x is a feasible solution of (P) if g(x) ≤ 0, h(x) = 0, and x ∈ X. 1.2 Local, Global, and Strict Optima The ball centered at x̄ with radius
is the set: x,
) := {x|x − x ¯ ≤
}. B(¯ Consider the following optimization problem over the set F: P : minx or maxx s.t. f (x) x∈F We have the following definitions of local/global, strict/non-strict minima/maxima. Definition 1.1 x ∈ F is a local minimum of P if there exists
> 0 such that f (x) ≤ f (y) for all y ∈ B(x,
) ∩ F. Definition 1.2 x ∈ F is a global minimum of P if f (x) ≤ f (y) for all y ∈ F. 3 Definition 1.3 x ∈ F is a strict local minimum of P if there exists
> 0 such that f (x) < f (y) for all y ∈ B(x,
) ∩ F, y =  x. Definition 1.4 x ∈ F is a strict global minimum of P if f (x) < f (y) for all y ∈ F, y = x. Definition 1.5 x ∈ F is a local maximum of P if there exists
> 0 such that f (x) ≥ f (y) for all y ∈ B(x,
) ∩ F. Definition 1.6 x ∈ F is a global maximum of P if f (x) ≥ f (y) for all y ∈ F. Definition 1.7 x ∈ F is a strict local maximum of P if there exists
> 0 such that f (x) > f (y) for all y ∈ B(x,
) ∩ F, y =  x. Definition 1.8 x ∈ F is a strict global maximum of P if f (x) > f (y) for all y ∈ F, y = x. 1.3 Gradients and Hessians Let f (x) : X → , where X ⊂ n is open. f (x) is differentiable at x̄ ∈ X if there exists a vector ∇f (¯ x) (the gradient of f (x) at x) ¯ such that for each x∈X f (x) = f (¯ x) + ∇f (¯ x)t (x − x) ¯ x, x − x), ¯ ¯ + x − xα(¯ and limy→0 α(x̄, y) = 0. f (x) is differentiable on X if f (x) is differentiable for all x̄ ∈ X. The gradient vector is the vector of partial derivatives:
∇f (x̄) = ∂f (¯ x) ∂f (¯ x) ,..., ∂xn ∂x1 t . Example 1 Let f (x) = 3(x1 )2 (x2 )3 + (x2 )2 (x3 )3 . Then  ∇f (x) = 6(x1 )(x2 )3 , 9(x1 )2 (x2 )2 + 2(x2 )(x3 )3 , 3(x2 )2 (x3 )2 4 T . The directional derivative of f (x) at x̄ in the direction d is: f (¯ x + λd) − f (¯ x) = ∇f (¯ x)t d λ→0 λ lim The function f (x) is twice differentiable at x̄ ∈ X if there exists a vector ∇f (¯ x) (the Hessian of f (x) at x) ¯ such x) and an n × n symmetric matrix H(¯ that for each x ∈ X 1 ¯ t H(¯ ¯ + (x − x) ¯ 2 α(¯ x, x − x), ¯ x)(x − x) ¯ + x − x f (x) = f (¯ x)t (x − x) x) + ∇f (¯ 2 and limy→0 α(x̄, y) = 0. f (x) is twice differentiable on X if f (x) is twice differentiable for all x ¯ ∈ X. The Hessian is the matrix of second partial derivatives: H(x̄)ij = x) ∂ 2 f (¯ . ∂xi ∂xj Example 2 Continuing Example 1, we have ⎛ 6(x2 )3 H(x) = ⎝ 18(x1 )(x2 )2 0 1.4 18(x1 )(x2 )2 18(x1 )2 (x2 ) + 2(x3 )3 6(x2 )(x3 )2 ⎞ 0 6(x2 )(x3 )2 ⎠ . 6(x2 )2 (x3 ) Positive Semidefinite and Positive Definite Matrices An n × n matrix M is called • positive definite if xt M x > 0 for all x ∈ n , x =  0 • positive semidefinite if xt M x ≥ 0 for all x ∈ n • negative definite if xt M x < 0 for all x ∈ n , x =  0  0 • negative semidefinite if xt M x ≤ 0 for all x ∈ n , x = 5 • indefinite if there exists x, y ∈ n for which xt M x > 0 and y t M y < 0 We say that M is SPD if M is symmetric and positive definite. Similarly, we say that M is SPSD if M is symmetric and positive semi-definite. Example 3
M= 2 0 0 3  is positive definite. Example 4
M= 8 −1 −1 1  is positive definite. To see this, note that for x =  0, xT M x = 8x21 − 2x1 x2 + x22 = 7x21 + (x1 − x2 )2 > 0 . 1.5 Existence of Optimal Solutions Most of the topics of this course are concerned with • existence of optimal solutions, • characterization of optimal solutions, and • algorithms for computing optimal solutions. To illustrate the questions arising in the first topic, consider the following optimization problems: • (P) minx s.t. 6 1+x 2x x≥1. Here there is no optimal solution because the feasible region is unbounded • (P) minx 1 x 1≤x<2. s.t. Here there is no optimal solution because the feasible region is not closed. • (P) minx s.t. f (x) 1≤x≤2, where 1/x, x < 2 1, x=2. f (x) = Here there is no optimal solution because the function f (·) is not sufficiently smooth. Theorem 1 (Weierstrass’ Theorem for sequences) Let {xk }, k → ∞ be an infinite sequence of points in the compact (i.e., closed and bounded) set F . Then some infinite subsequence of points xkj converges to a point contained in F . Theorem 2 (Weierstrass’ Theorem for functions) Let f (x) be a continuous real-valued function on the compact nonempty set F ⊂ n . Then F contains a point that minimizes (maximizes) f (x) on the set F . Proof: Since the set F is bounded, f (x) is bounded below on F . Since F =  ∅, there exists v = inf x∈F f (x). By definition, for any
> 0, the set F = {x ∈ F : v ≤ f (x) ≤ v +
} is non-empty. Let
k → 0 as k → ∞, and let xk ∈ Fk . Since F is bounded, there exists a subsequence of {xk } converging to some x ¯ ∈ F . By continuity of f (x), we have f (¯ x) = limk→∞ f (xk ), and, since v ≤ f (xk ) ≤ v +
k , it follows that f (x̄) = limk→∞ f (xk ) = v. 7 The assumptions of Weierstrass’ Theorem can be somewhat relaxed. For example, for a minimization problem, we can assume that • the set {x ∈ F : f (x) ≤ f (x )} is compact for some x ∈ F , and • f (x) is lower semi-continuous, i.e., for any constant c, the set {x ∈ F : f (x) ≤ c} is closed. The proof is similar to the proof of the Weierstrass’ Theorem. 8 2 Optimality Conditions for Unconstrained Prob­ lems (P) min s.t. f (x) x ∈ X, where x = (x1 , . . . , xn ) ∈ n , f (x) : n → , and X is an open set (usually X = n ). Definition 2.1 The direction d¯ is called a descent direction of f (x) at x = x̄ if f (¯ x +
d¯) < f (¯ x) for all
> 0 and sufficiently small . A necessary condition for local optimality is a statement of the form: “if ¯ is a local minimum of (P), then x x ¯ must satisfy . . . ” Such a condition helps us identify all candidates for local optima. Theorem 3 Suppose that f (x) is differentiable at x̄. If there is a vector d x+λd) < such that ∇f (¯ x)t d < 0, then for all λ > 0 and sufficiently small, f (¯ f (¯ x), and hence d is a descent direction of f (x) at x. ¯ Proof: We have: x, λd), f (¯ x + λd) = f (¯ x) + λ∇f (¯ x)t d + λdα(¯ where α(x̄, λd) → 0 as λ → 0. Rearranging, f (¯ x) x + λd) − f (¯ = ∇f (¯ x)t d + dα(¯ x, λd). λ x + λd) − f (¯ x, λd) → 0 as λ → 0, f (¯ x) < 0 for all Since ∇f (¯ x)t d < 0 and α(¯ λ > 0 sufficiently small. Corollary 4 Suppose f (x) is differentiable at x. ¯ If x ¯ is a local minimum, then ∇f (x̄) = 0. 9 Proof: If it were true that ∇f (¯ x) =  0, then d = −∇f (¯ x) would be a descent direction, whereby x̄ would not be a local minimum. The above corollary is a first order necessary optimality condition for an unconstrained minimization problem. The following theorem is a second order necessary optimality condition Theorem 5 Suppose that f (x) is twice continuously differentiable at x̄ ∈ X. If x ¯ is a local minimum, then ∇f (¯ x) = 0 and H (¯ x) is positive semidefinite. Proof: From the first order necessary condition, ∇f (¯ x) = 0. Suppose H (¯ x) is not positive semi-definite. Then there exists d such that dt H(x̄)d < 0. We have: 1 x)d + λ2 d2 α(¯ x, λd) f (¯ x + λd) = f (¯ x) + λ∇f (¯ x)t d + λ2 dt H (¯ 2 1 x, λd), = f (¯ x) + λ2 dt H(¯ x)d + λ2 d2 α(¯ 2 where α(x̄, λd) → 0 as λ → 0. Rearranging, f (¯ x + λd) − f (¯ x) 1 = dt H(¯ x)d + d2 α(¯ x, λd). 2 λ 2 Since dt H(¯ x)d < 0 and α(¯ x, λd) → 0 as λ → 0, f (¯ x + λd) − f (¯ x) < 0 for all λ > 0 sufficiently small, yielding the desired contradiction. Example 5 Let 1 f (x) = x21 + x1 x2 + 2x22 − 4x1 − 4x2 − x32 . 2 Then  ∇f (x) = x1 + x2 − 4, x1 + 4x2 − 4 − 3x22
and H (x) = 1 1 1 4 − 6x2 T ,  . ∇f (x) = 0 has exactly two solutions: x ¯ = (4, 0) and x ˜ = (3, 1). But
H (x̃) = 1 1 10 1 −2  is indefinite, therefore, the only possible candidate for a local minimum is x̄ = (4, 0). A sufficient condition for local optimality is a statement of the form: “if ¯ satisfies . . . , then x x ¯ is a local minimum of (P).” Such a condition allows us to automatically declare that x̄ is indeed a local minimum. Theorem 6 Suppose that f (x) is twice differentiable at x. ¯ If ∇f (¯ x) = 0 and H (¯ x) is positive definite, then x ¯ is a (strict) local minimum. Proof: 1 f (x) = f (¯ x) + (x − x) ¯ t H(¯ ¯ 2 α(¯ x, x − x). ¯ x)(x − x) ¯ + x − x 2 Suppose that x̄ is not a strict local minimum. Then there exists a sequence x ¯ such that xk = x ¯ and f (xk ) ≤ f (¯ x) for all k. Define dk = xxkk −¯ xk → x −¯ x . Then 2 f (xk ) = f (¯ x) + xk − x ¯ and so
 1 t d H(¯ x)dk + α(¯ x, xk − x) ¯ 2 k , f (xk ) − f (x̄) 1 t dk H (¯ x)dk + α(¯ x, xk − x) ¯ = ≤0. 2 xk − x ¯ 2 Since dk  = 1 for any k, there exists a subsequence of {dk } converging to some point d such that d = 1. Assume without loss of generality that dk → d. Then 1 x)dk + α(¯ x, xk − x) ¯ = dt H(¯ x)d, 0 ≥ lim dtk H (¯ k→∞ 2 which is a contradiction of the positive definiteness of H (x̄). Note: • If ∇f (¯ x) = 0 and H(¯ x) is negative definite, then x ¯ is a local maximum. • If ∇f (¯ x) = 0 and H(¯ x) is positive semidefinite, we cannot be sure if ¯ is a local minimum. x 11 Example 6 Continuing Example 5, we compute
H(x̄) = 1 1 1 4  is positive definite. To see this, note that for any d = (d1 , d2 ), we have x)d = d21 + 2d1 d2 + 4d22 = (d1 + d2 )2 + 3d22 > 0 for all d =  0. dT H(¯ Therefore, x ¯ satisfies the sufficient conditions to be a local minimum, and so x̄ is a local minimum. Example 7 Let f (x) = x31 + x22 . Then  ∇f (x) = 3x21 , 2x2
and 6x1 H(x) = 0 At x ¯ = (0, 0), we have ∇f (¯ x) = 0 and 0 2 0 0 0 2
H(x̄) = T ,  .  ¯ is not a local minimum, since f (−
, 0) = is positive semi-definite, but x −
3 < 0 = f (0, 0) = f (x̄) for all
> 0. Example 8 Let f (x) = x41 + x22 . Then  ∇f (x) = 4x31 , 2x2
and 12x21 0 At x ¯ = (0, 0), we have ∇f (¯ x) = 0 and 0 2 H(x) =
H(x̄) = 0 0 T 0 2 ,  .  is positive semi-definite. Furthermore, x̄ is a local minimum, since for all x we have f (x) ≥ 0 = f (0, 0) = f (x̄). 12 2.1 Convexity and Minimization • Let x, y ∈ n . Points of the form λx + (1 − λ)y for λ ∈ [0, 1] are called convex combinations of x and y . • A set S ⊂ n is called a convex set if for all x, y ∈ S and for all λ ∈ [0, 1] it holds that λx + (1 − λ)y ∈ S. • A function f (x) : S → , where S is a nonempty convex set, is a convex function if f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) for all x, y ∈ S and for all λ ∈ [0, 1]. • A function f (x) as above is called a strictly convex function if the inequality above is strict for all x = y and λ ∈ (0, 1). • A function f (x) : S → , where S is a nonempty convex set, is a concave function if f (λx + (1 − λ)y) ≥ λf (x) + (1 − λ)f (y) for all x, y ∈ S and for all λ ∈ [0, 1]. • A function f (x) as above is called a strictly concave function if the inequality above is strict for all x =  y and λ ∈ (0, 1). Consider the problem: (CP) minx s.t. 13 f (x) x∈S . Theorem 7 Suppose S is a convex set, f (x) : S →  is a convex function, and x ¯ is a local minimum of (CP). Then x ¯ is a global minimum of f (x) over S. Proof: Suppose x̄ is not a global minimum, i.e., there exists y ∈ S for which f (y) < f (¯ x + (1 − λ)y, which is a convex combination of x). Let y(λ) := λ¯ x̄ and y for λ ∈ [0, 1] (and therefore, y(λ) ∈ S for λ ∈ [0, 1]). Note that y(λ) → x̄ as λ → 0. From the convexity of f (x), f (y(λ)) = f (λ¯ x+(1−λ)y) ≤ λf (¯ x)+(1−λ)f (¯ x) x)+(1−λ)f (y) < λf (¯ x) = f (¯ for all λ ∈ (0, 1). Therefore, f (y(λ)) < f (¯ x) for all λ ∈ (0, 1), and so x ¯ is not a local minimum, resulting in a contradiction. Note: • If f (x) is strictly convex, a local minimum is the unique global minimum. • If f (x) is concave, a local maximum is a global maximum. • If f (x) is strictly concave, a local maximum is the unique global maximum. Theorem 8 Suppose S is a non-empty open convex set, and f (x) : S →  is differentiable. Then f (x) is a convex function if and only if f (x) satisfies the following gradient inequality: f (y) ≥ f (x) + ∇f (x)t (y − x) for all x, y ∈ S. Proof: Suppose f (x) is convex. Then for any λ ∈ [0, 1], f (λy + (1 − λ)x) ≤ λf (y) + (1 − λ)f (x) which implies that f (x + λ(y − x)) − f (x) ≤ f (y) − f (x) . λ 14 Letting λ → 0, we obtain: ∇f (x)t (y − x) ≤ f (y) − f (x), establishing the “only if ” part. Now, suppose that the gradient inequality holds for all x, y ∈ S. Let w and z be any two points in S. Let λ ∈ [0, 1], and set x = λw + (1 − λ)z. Then f (w) ≥ f (x) + ∇f (x)t (w − x) and f (z) ≥ f (x) + ∇f (x)t (z − x). Taking a convex combination of the above inequalities, we obtain λf (w) + (1 − λ)f (z) ≥ f (x) + ∇f (x)t (λ(w − x) + (1 − λ)(z − x)) = f (x) + ∇f (x)t 0 = f (λw + (1 − λ)z) , which shows that f (x) is convex. Theorem 9 Suppose S is a non-empty open convex set, and f (x) : S →  is twice differentiable. Let H (x) denote the Hessian of f (x). Then f (x) is convex if and only if H(x) is positive semidefinite for all x ∈ S. Proof: Suppose f (x) is convex. Let x̄ ∈ S and d be any direction. Then for λ > 0 sufficiently small, x̄ + λd ∈ S. We have: 1 x, λd), x)(λd) + λd2 α(¯ f (¯ x + λd) = f (¯ x) + ∇f (¯ x)t (λd) + (λd)t H(¯ 2 where α(x̄, y) → 0 as y → 0. Using the gradient inequality, we obtain λ 2
 1 t d H (¯ x)d + d2 α(¯ x, λd) ≥ 0. 2 Dividing by λ2 > 0 and letting λ → 0, we obtain dt H (x̄)d ≥ 0, proving the “only if ” part. 15 Conversely, suppose that H(z) is positive semidefinite for all z ∈ S. Let x, y ∈ S be arbitrary. Invoking the second-order version of Taylor’s theorem, we have: 1 f (y) = f (x) + ∇f (x)t (y − x) + (y − x)t H(z)(y − x) 2 for some z which is a convex combination of x and y (and hence z ∈ S). Since H(z) is positive semidefinite, this means that f (y) ≥ f (x) + ∇f (x)t (y − x) . Therefore the gradient inequality holds, and hence f (x) is convex. Returning to the optimization problem (P), knowing that the function f (x) is convex allows us to establish a global optimality condition that is both necessary and sufficient: Theorem 10 Suppose f (x) : X →  is convex and differentiable on X. Then x ¯ ∈ X is a global minimum if and only if ∇f (¯ x) = 0. Proof: The necessity of the condition ∇f (x̄) = 0 was established in Corollary 4 regardless of the convexity of the function f (x). Suppose ∇f (x̄) = 0. Then by the gradient inequality we have f (y) ≥ ¯ = f (¯ x) for all y ∈ X, and so x ¯ is a global minimum. f (¯ x)t (y − x) x) + ∇f (¯ Example 9 Continuing Example 5, recall that
H(x) = 1 1 1 4 − 6x2  . Suppose that the domain of of f (·) is X = {(x1 , x2 ) | x2 < 0}. Then f (·) is a convex function on this domain. Example 10 Let f (x) = − ln(1 − x1 − x2 ) − ln x1 − ln x2 . 16 ⎡ Then ⎢ ∇f (x) = ⎣ and ⎡  ⎢ ⎢ ⎣ H(x) = ⎢ 1 1−x1 −x2  2 1 1−x1 −x2 1 1−x1 −x2  + 1 1−x1 −x2 1 x1 2 2 − 1 x1 − 1 x2   ⎤ ⎥ ⎦, 1 1−x1 −x2 1 1−x1 −x2 2 ⎤ 2  + 1 x2 ⎥ ⎥ ⎥. 2 ⎦ It is actually easy to prove that f (x) is a strictly convex function, and hence that H(x) is positive definite  on its domain X = {(x1 , x2 ) | x1 > 0, x2 > 0, x1 + x2 < 1}. At x ¯ = 13 , 31 we have ∇f (¯ x) = 0, and so x ¯ is the unique global minimum of f (x). 3 Exercises on Unconstrained Optimization 1. Find points satisfying necessary conditions for extrema (i.e., local minima or local maxima) of the function f (x) = x1 + x2 . 3 + + x22 + x1 x2 x21 Try to establish the nature of these points by checking sufficient conditions. 2. Find minima of the function f (x) = (x22 − x1 )2 among all the points satisfying necessary conditions for an extremum. 3. Consider the problem to minimize Ax − b2 , where A is an m × n matrix and b is an m vector. a. Give a geometric interpretation of the problem. b. Write a necessary condition for optimality . Is this also a sufficient condition? 17 c. Is the optimal solution unique? Why or why not? d. Can you give a closed form solution of the optimal solution? Specify any assumptions that you may need. e. Solve the problem for A and b given below: ⎛ ⎜ ⎜ ⎝ A=⎜ ⎞ ⎛ 1 −1 0 ⎜ 0 2 1 ⎟ ⎟ ⎜ ⎟, b = ⎜ ⎝ 0 1 0 ⎠ 1 0 1 2 1 1 0 ⎞ ⎟ ⎟ ⎟. ⎠ 4. Let S be a nonempty set in n . Show that S is convex if and only if for each integer k ≥ 2 the following holds true: x1 , . . . , xk ∈ S ⇒ k  λj xj ∈ S j=1 whenever λ1 , . . . , λk satisfy λ1 , . . . , λk ≥ 0 and k  j=1 λj = 1. 5. Bertsekas, Exercise 1.1.1, page 16. (Note: x∗ is called a stationary point of f (·) if ∇f (x∗ ) = 0.) 6. Bertsekas, Exercise 1.1.2, page 16, parts (a), (b), (c), and (d). (Note: x∗ is called a stationary point of f (·) if ∇f (x∗ ) = 0.) 18