Example: barber

Convex Optimization Theory - Athena Scientific

Convex Optimization Theory A SUMMARY. BY. DIMITRI P. BERTSEKAS. We provide a summary of theoretical concepts and results relating to Convex analysis, Convex Optimization , and duality Theory . In particular, we list the relevant definitions and propositions (without proofs) of the author's book Convex Optimization Theory , Athena Scientific , 2009. For ease of use, the chapter, section, definition, and proposition numbers of the latter book are identical to the ones of this appendix. CHAPTER 1: Basic Concepts of Convex Analysis Section Convex Sets and Functions Definition : A subset C of n is called Convex if x + (1 )y C, x, y C, [0, 1].

Convex Optimization Theory A SUMMARY BY DIMITRI P. BERTSEKAS We provideasummaryoftheoreticalconceptsandresultsrelatingto convex analysis, convex optimization, and ...

Tags:

  Theory, Optimization, Convex, Convex optimization theory

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Convex Optimization Theory - Athena Scientific

1 Convex Optimization Theory A SUMMARY. BY. DIMITRI P. BERTSEKAS. We provide a summary of theoretical concepts and results relating to Convex analysis, Convex Optimization , and duality Theory . In particular, we list the relevant definitions and propositions (without proofs) of the author's book Convex Optimization Theory , Athena Scientific , 2009. For ease of use, the chapter, section, definition, and proposition numbers of the latter book are identical to the ones of this appendix. CHAPTER 1: Basic Concepts of Convex Analysis Section Convex Sets and Functions Definition : A subset C of n is called Convex if x + (1 )y C, x, y C, [0, 1].

2 Proposition : (a) The intersection i I Ci of any collection {Ci | i I} of Convex sets is Convex . (b) The vector sum C1 + C2 of two Convex sets C1 and C2 is Convex . (c) The set C is Convex for any Convex set C and scalar . Fur- thermore, if C is a Convex set and 1 , 2 are positive scalars, 467. 468 Chap. 1. ( 1 + 2 )C = 1 C + 2 C. (d) The closure and the interior of a Convex set are Convex . (e) The image and the inverse image of a Convex set under an affine function are Convex . A hyperplane is a set of the form {x | a x = b}, where a is a nonzero vector and b is a scalar. A halfspace is a set specified by a single linear inequality, , a set of the form {x | a x b}, where a is a nonzero vector and b is a scalar.

3 A set is said to be polyhedral if it is nonempty and it has the form {x | a j x bj , j = 1, .. , r}, where a1 , .. , ar and b1 , .. , br are some vectors in n and scalars, respectively. A set C is said to be a cone if for all x C and > 0, we have x C. Definition : Let C be a Convex subset of n . We say that a function f : C 7 is Convex if . f x + (1 )y f (x) + (1 )f (y), x, y C, [0, 1]. A Convex function f : C 7 is called strictly Convex if . f x + (1 )y < f (x) + (1 )f (y). for all x, y C with x 6= y, and all (0, 1). A function f : C 7 , where C is a Convex set, is called concave if the function ( f ) is Convex .

4 The epigraph of a function f : X 7 [ , ], where X n , is defined to be the subset of n+1 given by epi(f ) = (x, w) | x X, w , f (x) w . The effective domain of f is defined to be the set dom(f ) = x X | f (x) < . We say that f is proper if f (x) < for at least one x X and f (x) > . for all x X, and we say that f improper if it is not proper. Thus f is proper if and only if epi(f ) is nonempty and does not contain a vertical line. Definition : Let C be a Convex subset of n . We say that an extended real-valued function f : C 7 [ , ] is Convex if epi(f ) is a Convex subset of n+1 . Sec. Convex Sets and Functions 469.

5 Definition : Let C and X be subsets of n such that C is nonempty and Convex , and C X. We say that an extended real- valued function f : X 7 [ , ] is Convex over C if f becomes Convex when the domain of f is restricted to C, , if the function f : C 7 [ , ], defined by f (x) = f (x) for all x C, is Convex . We say that a function f : X 7 [ , ] is closed if epi(f ) is a closed set. We say that f is lower semicontinuous at a vector x X if f (x) lim inf k f (xk ) for every sequence {xk } X with xk x. We say that f is lower semicontinuous if it is lower semicontinuous at each point x in its domain X.

6 We say that f is upper semicontinuous if f is lower semicontinuous. Proposition : For a function f : n 7 [ , ], the following are equivalent: (i) The level set V = x | f (x) is closed for every scalar . (ii) f is lower semicontinuous. (iii) epi(f ) is closed. Proposition : Let f : X 7 [ , ] be a function. If dom(f ). is closed and f is lower semicontinuous at each x dom(f ), then f is closed. Proposition : Let f : m 7 ( , ] be a given function, let A be an m n matrix, and let F : n 7 ( , ] be the function F (x) = f (Ax), x n . If f is Convex , then F is also Convex , while if f is closed, then F is also closed.))

7 Proposition : Let fi : n 7 ( , ], i = 1, .. , m, be given functions, let 1 , .. , m be positive scalars, and let F : n 7 ( , ]. 470 Chap. 1. be the function F (x) = 1 f1 (x) + + m fm (x), x n . If f1 , .. , fm are Convex , then F is also Convex , while if f1 , .. , fm are closed, then F is also closed. Proposition : Let fi : n 7 ( , ] be given functions for i I, where I is an arbitrary index set, and let f : n 7 ( , ] be the function given by f (x) = sup fi (x). i I. If fi , i I, are Convex , then f is also Convex , while if fi , i I, are closed, then f is also closed. Proposition : Let C be a nonempty Convex subset of n and let f : n 7 be differentiable over an open set that contains C.))))

8 (a) f is Convex over C if and only if f (z) f (x) + f (x) (z x), x, z C. (b) f is strictly Convex over C if and only if the above inequality is strict whenever x 6= z. Proposition : Let C be a nonempty Convex subset of n and let f : n 7 be Convex and differentiable over an open set that contains C. Then a vector x C minimizes f over C if and only if f (x ) (z x ) 0, z C. When f is not Convex but is differentiable over an open set that contains C, the condition of the above proposition is necessary but not sufficient for optimality of x (see , [Ber99], Section ). Sec. Convex Sets and Functions 471.

9 Proposition : (Projection Theorem) Let C be a nonempty closed Convex subset of n , and let z be a vector in n . There exists a unique vector that minimizes kz xk over x C, called the projection of z on C. Furthermore, a vector x is the projection of z on C if and only if (z x ) (x x ) 0, x C. Proposition : Let C be a nonempty Convex subset of n and let f : n 7 be twice continuously differentiable over an open set that contains C. (a) If 2 f (x) is positive semidefinite for all x C, then f is Convex over C. (b) If 2 f (x) is positive definite for all x C, then f is strictly Convex over C. (c) If C is open and f is Convex over C, then 2 f (x) is positive semidefinite for all x C.

10 Strong Convexity If f : n 7 is a function that is continuous over a closed Convex set C n , and is a positive scalar, we say that f is strongly Convex over C with coefficient if for all x, y C and all [0, 1], we have . f x + (1 )y + (1 )kx yk2 f (x) + (1 )f (y). 2. Then f is strictly Convex over C. Furthermore, there exists a unique x C. that minimizes f over C, and by applying the definition with y = x and letting 0, it can be seen that . f (x) f (x ) + kx x k2 , x C. 2. If int(C), the interior of C, is nonempty, and f is continuously differentiable over int(C), the following are equivalent: (i) f is strongly Convex with coefficient over C.


Related search queries