Topic 14. Optimization

1. The statement of the optimization problem

Optimization takes place in any field of human activity: in economic planning, management, production processes, designing complex processes, etc. - where the search for the best option is sought. Only mathematically it is possible to give definition of optimization - when instead of words "better", "bad" are quantitative characteristics in the form of a function.

Most optimization tasks are reduced to finding the smallest or largest - the extreme value of some function, which is called a target function or a quality criterion .

Most simply from a mathematical point of view, when the target function is given by a derivative formula. In this case, when looking for an extremum, you can use the derivative function.

Example 1. Find the sizes of cans with the largest volume V and the smallest length of L joints and area.

                                           V = pr ² h, S = 2pr ² + 2prh, L = 4pr + h .

Let's express the height of the jar through its radius: h = V / pr2. Then we get: S = 2pr2 + (2V) / h, L = 4pr + V / pr2, where ¥ <r <¥. Thus, one should find r, at which min S i L.

To do this, find the derivative of these functions by:

                                                           S '(r) = .... = 0

i

L '(r) = .... = 0.

With different optimization criteria, we get different answers.

The problem of one-dimensional optimization can be formulated as follows: find among elements from a given set X such x'ÎX, which gives the extremum of the function f (x ').

To reduce the practical task to mathematics it is necessary:

1. choose the f (x) indicator that is optimized;
2. to construct a mathematical model of the dependence of the minimized index on the initial parameters.

In practice there are three classes of optimization tasks:

• unconditional optimization (without limitations) - no restrictions will be imposed on the value;
• conditional optimization (with restrictions) - the value is in the given interval;
• optimization for incomplete data - values ​​are not defined.

2. Numerical solution of one-dimensional optimization problems

Setting up one-dimensional optimization tasks - find the extremum (least or most) of the target function that is given on the set.

The Weierstrass Theorem. Any function that is continuous on a segment takes on its least and most important in this segment , and therefore there are points such that for any inequality £ £ for any one.

Points in which the derivative of a function equals zero are called critical or stationary points of a function). At the critical point, the "speed of the function" equals zero. The function can have the least (highest) value in one of the two boundary points of the segment, or in any of its internal points. In this case, the point must necessarily be critical - the necessary condition for the extremum.

In order to determine the smallest and largest value of the function f (x) on the segment [a, b], it is necessary to find all its critical points on the given segment, connect them to the boundary points of aib for all these points to compare the value of the function. The least and most of them give a solution to the optimization problem.

Example 1. Find the extreme values ​​of the function f (x) = 3x ⁴ -4x ³ -12x ² +2 on the segment [-2,3].

We find the derivative of the function f ¢ (x) = 12x ³ -12x ² -24x. To determine the critical points equate to zero the derivative function and find all the roots of the equation: 12x ³ -12x ² -24x = 0: x ₁ = -1, x ₂ = 0, x ₃ = 0. We compute the value of the function at these points, and also at the boundary points: f (-2) = 34, f (-1) = - 3, f (0) = 2, f (2) = - 30, f (3) = 29 A comparison of these numbers allows us to determine that the largest and smallest values ​​of the function at points respectively: fmin = (- 2) = - 30 i fmax (-2) = 34.

The method of uniformly dividing the points by segment

We take a certain number, and calculate the step and determine the value of the function in points. Among these numbers is the least. The number  can be taken at the smallest value of the function on the segment []. One of the problems is the definition of the number in order not to miss the extremum of the function.

3. Method of golden section

The gold section of the segment is called its division into two parts, that the ratio of the length of the entire segment to the length of most part is equal to the ratio of the length of the greater part to the smaller. So the gold section of the segment [] performs two symmetrically arranged points, where k = 0.6180339. That is, the point x ₁ divides the segment [ a , x ₂ ] in the golden ratio , and the point x ₂ is the gold section of the segment [ x ₁ , b ] .

In the golden section method, the function must be unimodal. The function is unimodal on a segment if it has a single point of the global minimum on this segment and to the left of this point is strictly decreasing, and to the right is strictly increasing. The essence of the golden section method is to determine the point of the global minimum for a segment for a minimum number of steps.

4. Self-checking

1. What are the methods for finding the extremum of a function?
2. Name the optimization methods