Читать книгу Convex Optimization - Mikhail Moklyachuk - Страница 8

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.