Convex Optimization. Mikhail Moklyachuk

give detailed proofs for most of the results presented in the book and also include many figures and exercises for better understanding of the material. Finally, we present solutions and hints to selected exercises at the end of the book. Exercises are given at the end of each chapter while figures and examples are provided throughout the whole text. The list of references contains texts which are closely related to the topics considered in the book and may be helpful to the reader for advanced studies of convex analysis, its applications and further extensions. Since only elementary knowledge in linear algebra and basic calculus is required, this book can be used as a textbook for both undergraduate and graduate level courses in convex optimization and its applications. In fact, the author has used these lecture notes for teaching such classes at Kyiv National University. We hope that the book will make convex optimization methods more accessible to large groups of undergraduate and graduate students, researchers in different disciplines and practitioners. The idea was to prepare materials of lectures in accordance with the suggestion made by Einstein: “Everything should be made as simple as possible, but not simpler.”

      1

      Optimization Problems with Differentiable Objective Functions

      1.1. Basic concepts

      The word “maximum” means the largest, and the word “minimum” means the smallest. These two concepts are combined with the term “extremum”, which means the extreme. Also pertinent is the term “optimal” (from Latin optimus), which means the best. The problems of determining the largest and smallest quantities are called extremum problems. Such problems arise in different areas of activity and therefore different terms are used for the descriptions of the problems. To use the theory of extremum problems, it is necessary to describe problems in the language of mathematics. This process is called the formalization of the problem.

      The formalized problem consists of the following elements:

       – objective function ;

       – domain X of the definition of the objective functional f;

       – constraint: C ⊂ X.

      Here,

is an extended real line, that is, the set of all real numbers, supplemented by the values +∞ and –∞, C is a subset of the domain of definition of the objective functional f. So to formalize an optimization problem means to clearly define and describe elements f, C and X. The formalized problem is written in the form

[1.1]

Points of the set C are called admissible points of the problem [1.1]. If C = X, then all points of the domain of definition of the function are admissible. The problem [1.1] in this case is called a problem without constraints.

      The maximization problem can always be reduced to the minimization problem by replacing the functional f with the functional g = –f. And, on the contrary, the minimization problem in the same way can be reduced to the maximization problem. If the necessary conditions for the extremum in the minimization problem and maximization problem are different, then we write these conditions only for the minimization problem. If it is necessary to investigate both problems, then we write down

      An admissible point is a point of absolute or global minimum (maximum) of the extremum problem if for any x. ∈ C the inequality holds true

      Then we write ∈ absmin (absmax). The point of the absolute minimum (maximum) is called a solution of the problem. The value , where is a solution of the problem, is called a numerical value of the problem. This value is denoted by S_min (S_max).

      In addition to global extremum problems, local extremum problems are also studied. Let X be a normed space. A local minimum (maximum) of the problem is reached at a point that is ∈ locmin (locmax), if ∈ C and there exists a number δ > 0 such that for any admissible point x ∈ C that satisfies condition , the inequality holds true

      In other words, if ∈ locmin (locmax), then there exists a neighborhood of the point such that

      in the problem

      The theory of extremum problems gives general rules for solving extremum problems. The theory of necessary conditions of the extremum is more developed. The necessary conditions of the extremum make it possible to allocate a set of points among which solutions of the problem are situated. Such a set is called a critical set, and the points themselves are called critical points. As a rule, a critical set does not contain many points and a solution of the problem can be found by one or another method.

1.2. Optimization problems with objective functions of one variable

      Let f: ℝ → ℝ be a function of one real variable.

      DEFINITION 1.1.– A function f is said to be lower semicontinuous (upper semicontinuous) at a point if for every ε > 0, there exists a δ > 0 such that the inequality

      holds true for all x ∈ (, ).

      DEFINITION 1.2.– (Equivalent) A function f is said to be lower semicontinuous (upper semicontinuous) at a point if for every a ∈ ℝ,