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,
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
Then we write
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
In other words, if
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