Powell's conjugate directions method. Conjugate directions See what “conjugate directions” are in other dictionaries

RELATED DIRECTIONS

A pair of directions emanating from a point P of the surface S and such that the straight lines containing them are the conjugate diameters of the Dupin indicatrix of the surface S at the point R. In order for directions ( du:dv), at the point P of the surface S was S. n., it is necessary and sufficient to satisfy the condition

Where L, M And N- coefficients of the second quadratic form of the surface S, calculated at the point R. Examples: asymptotic directions, principal directions.

Lit.: Pogorelov A.V., Differential, 5th ed., M., 1969.
E. V. Shikin.

Mathematical encyclopedia. - M.: Soviet Encyclopedia. I. M. Vinogradov. 1977-1985.

See what “CONNECTED DIRECTIONS” are in other dictionaries:

Section of geometry, in which geometrics are studied. images, primarily curves and surfaces, using mathematical methods. analysis. Usually in dynamic geometry the properties of curves and surfaces in the small are studied, that is, the properties of arbitrarily small pieces of them. In addition, in… Mathematical Encyclopedia

1) The sum of the squares of the lengths of the conjugate half-diameters of an ellipse is a constant value equal to the sum of the squares of the lengths of its semi-axes. 2) The area of ​​a parallelogram circumscribed around an ellipse, the sides of which have conjugate directions, is constant and equal to ... ... Mathematical Encyclopedia

Direction on a regular surface, in which the curvature of the normal section of the surface is zero. In order for the direction at point P to be A.N., it is necessary and sufficient to fulfill the following condition: where are the internal coordinates on the surface, and L, M and N... ... Mathematical Encyclopedia

Numerical methods is a branch of computational mathematics dedicated to mathematics. description and study of processes of numerical solution of linear algebra problems. Among the tasks of LA. Two are of greatest importance: the solution of a system of linear algebraic. equations... ... Mathematical Encyclopedia

A network of lines on a surface formed by two families of lines such that at each point on the surface the lines of the network of different families have conjugate directions. If the coordinate network is a coordinate system, then the coefficient M of the second quadratic form... ... Mathematical Encyclopedia

SO 34.21.308-2005: Hydraulic engineering. Basic concepts. Terms and definitions- Terminology SO 34.21.308 2005: Hydraulic engineering. Basic concepts. Terms and definitions: 3.10.28 outport: a water area limited by wave protection dams in the upper pool of a hydroelectric complex, equipped with berthing devices and intended to accommodate ... Dictionary-reference book of terms of normative and technical documentation

I I. History of development railways. The railroad, in the form in which it exists now, was not invented immediately. The three elements, its components, the rail track, the means of transportation and the motive power, each went through a separate stage of development,... ... Encyclopedic Dictionary F.A. Brockhaus and I.A. Efron

Wages- (Wages) The most important means of increasing the interest of workers Participation of workers in the share of newly created material and spiritual benefits Contents Contents. > wages- this is the most important means of increasing interest... ... Investor Encyclopedia

Diversification- (Diversification) Diversification is an investment approach aimed at reducing financial markets Concept, main methods and goals of diversification of production, business and financial risks in the currency, stock and commodity markets Contents... ... Investor Encyclopedia

XIII. Internal Affairs (1866-1871). On April 4, 1866, at four o'clock in the afternoon, Emperor Alexander, after a routine walk in the Summer Garden, was sitting in a carriage when an unknown person shot him with a pistol. At that moment, standing in... Large biographical encyclopedia

Similar documents

Consideration of the effectiveness of applying methods of penalties, unconstrained optimization, conjugate directions and steepest gradient descent for solving the problem of finding the extremum (maximum) of a function of several variables in the presence of an equality constraint.

test, added 08/16/2010


Analysis of conjugate functor theorems. Natural transformation as a family of morphisms. Characteristics of the properties of reflective subcategories. Introduction to universal arrows. Consideration of the features of the method for constructing conjugate functors.

course work, added 01/27/2013


Rotation transformation technique and its significance in solving algebraic systems of equations. Obtaining the resulting matrix. Orthogonal transformations by reflection. Iterative methods with residual minimization. Solution by the method of conjugate directions.

abstract, added 08/14/2009


Methods for solving systems of linear algebraic equations, their characteristics and distinctive features, features and areas of application. The structure of the orthogonalization method and the conjugate gradient method, their varieties and conditions, stages of practical implementation.

course work, added 10/01/2009


Numerical methods for searching for an unconditional extremum. Unconstrained minimization problems. Calculation of the minimum of a function using the coordinate descent method. Solving linear programming problems using graphical and simplex methods. Working with the MathCAD program.

course work, added 04/30/2011


Formation of the Lagrange function, Kuhn and Tucker conditions. Numerical optimization methods and flowcharts. Application of methods of penalty functions, external point, coordinate descent, conjugate gradients to reduce conditional optimization problems to unconditional ones.

course work, added 11/27/2012


Mathematical model tasks. Solving the transport problem using the potential method. Objective function value. A system consisting of 7 equations with 8 unknowns. Solving problems graphically. Selecting the half-plane corresponding to the inequality.

test, added 06/12/2011


Methods for finding the minimum of a function of one variable and a function of many variables. Development of software for calculating the local minimum of the Himmelblau function using the coordinate descent method. Finding the minimum of a function using the golden section method.

course work, added 10/12/2009


Solving systems of linear algebraic equations using the simple iteration method. Polynomial interpolation of a function by Newton's method with divided differences. Mean square approximation of a function. Numerical integration of functions using the Gauss method.

course work, added 04/14/2009


Basic information about the simplex method, assessment of its role and significance in linear programming. Geometric interpretation and algebraic meaning. Finding the maximum and minimum of a linear function, special cases. Solving the problem using the matrix simplex method.

Step 1: Set the starting point X(0) and system N linearly independent directions; it is possible that s (i) = e (i) i = 1, 2, 3,..., N.

Step 2: Minimize f(x) with sequential movement along ( N+1) directions; in this case, the previously obtained minimum point is taken as the initial one, and the direction s(N) used in both the first and last searches.

Step 3: Define the new conjugate direction using the generalized parallel subspace property.

Step 4. Replace s(l) on s(2) etc. Replace s (N) conjugate direction. Go to step 2.

In order to apply the presented method in practice, it must be supplemented with procedures for checking the convergence and linear independence of the direction system. Testing linear independence is especially important in cases where the function f(x) is not quadratic.

From the method of constructing the algorithm it follows that in the case when the objective function is quadratic and has a minimum, the minimum point is found as a result of the implementation N cycles including steps 2, 3 and 4, where N- number of variables. If the function is not quadratic, then more than N cycles. At the same time, it is possible to give a rigorous proof that, under some assumptions, Powell’s method converges to a local minimum point with superlinear speed (see definition below).

Convergence speed. The method under consideration allows you to construct a sequence of points x(k) , which converges to a solution x*. The method is called convergent, if inequality

≤ 1, where (3.39)

= x - X*, (3.40)

is executed at every iteration. Since calculations usually operate with finite decimals, even the most efficient algorithm requires an infinite sequence of iterations. Therefore, of primary interest are the asymptotic properties of the convergence of the methods being studied. We will say that the algorithm has convergence of order r(see) if

, (3.41)

Where WITH- constant value. From formula (3.39) it follows that when r= 1, the inequality C ≤ 1 holds. If r= 1or r= 2, then the algorithm is characterized linear or quadratic convergence rate respectively. At r= 1i WITH= 0 algorithm is characterized superlinear speed of convergence.

Example 3.6. Powell's conjugate directions method

Find the minimum point of a function

f(x) = 2x + 4x x – 10x x+ x,

if the starting point is given X(0) = T, in which f(x (0)) = 314.

Step 1. s(1) = T, s(2) = T.

Step 2. (a) Find a value of λ at which

f (x (0) + λ s(2)) → min.

We get: λ* - 0.81, from where

x(l) = T - 0,81 T = T, f(x(l)) = 250.

(b) Let us find a value of λ for which f (x(1) + λ s(1)) → min.

λ* = – 3,26, x (2) = T,f(x (2)) = 1.10.

(c) Let us find a value of λ for which f (x(2) + λ s(2)) → min.

λ* = – 0.098, x (3) = T,f(x (3)) = 0.72.

Step 3. Put s (3) = x (3) - x (1) = [-3.26,-0.098]T. After normalization we get

s (3) = = [– 0,99955, – 0,03]T.

Let's put s (1) = s (2) , s (2) = s (3) and move on to step 2 of the algorithm.

Step 4. Find a value of λ at which f (x(3) + λ s(2)) → min.

λ* = – 0.734, x (4) = T,f(x (4)) = – 2,86.

Note. If f(x) was a quadratic function, then the resulting point would be a solution to the problem (if we neglect the rounding error). In this case, iterations should be continued until a solution is obtained.

The search directions obtained during the implementation of the method are shown in Fig. 3.13.

The results of computational experiments suggest that Powell's method (supplemented with a procedure for checking the linear dependence of directions) is at least as highly reliable as other direct search methods, and in some cases is significantly more effective. Therefore, the problem of choosing a direct search algorithm is often (and justifiably) resolved in favor of the Powell method.

This concludes the consideration of methods for direct search for solutions in unconstrained optimization problems. The next section describes methods based on the use of derivatives.

Gradient methods

The previous section discussed methods that make it possible to obtain a solution to the problem based on using only the values ​​of the objective function. The importance of direct methods is undoubted, since in a number of practical engineering problems information about the values ​​of the objective function is the only reliable information that the researcher has.

f(x) = 2x + 4x x – 10x x+ x

Rice. 3.13. Solving the problem from Example 3.6 using Powell's conjugate directions method.

On the other hand, when using even the most effective direct methods, obtaining a solution sometimes requires extremely large number calculations of function values. This circumstance, along with the completely natural desire to realize the possibility of finding stationary points [i.e. i.e. points satisfying the necessary first-order condition (3.15a)] leads to the need to consider methods based on the use of the gradient of the objective function. These methods are iterative in nature since the gradient components turn out to be nonlinear functions of controlled variables.

In what follows it is assumed that f(x), f(x) And f(x) exist and are continuous. Methods using both first and second derivatives are discussed only briefly and mainly in relation to more useful methods. Particular attention is paid to a detailed presentation of methods conjugate gradients, which are based on the concept of conjugacy of directions introduced above, and the so-called quasi-Newton methods, which are similar to Newton’s method, but use only information about the first derivatives. It is assumed that the gradient components can be written in analytical form or calculated with sufficiently high accuracy using numerical methods. In addition, methods for numerical approximation of gradients are considered." All described methods are based on an iterative procedure implemented in accordance with the formula

x = x +α s(x) (3.42)

Where x- current approach to solution X*; α - parameter characterizing step length; s(x) = s - search direction in N-dimensional space of controlled variables x i , i = 1, 2, 3,..., N Method of determination s(x) and α at each iteration is related to the features of the method used. Usually the choice of α carried out by solving the minimization problem f(x) in the direction s(x). Therefore, when implementing the methods under study, it is necessary to use effective one-dimensional minimization algorithms.

3.3.1. Cauchy method

Let us assume that at some point space of controlled variables, it is necessary to determine the direction of the fastest local descent, i.e., the largest local decrease in the objective function. As before, we expand the objective function in the neighborhood of the point Taylor series

f(x) = f()+ f() ∆x+… (3.43)

and discard terms of second order and higher. It is easy to see that the local decrease in the objective function is determined by the second term, since the value f() fixed. Largest reduction f is associated with the choice of such a direction in (3.42), which corresponds to the largest negative the value of the scalar product appearing as the second term of the expansion. From the property of the scalar product it follows that the specified choice is ensured when

s() = – f(),(3.44)

and the second term will take the form

–α f() f().

The considered case corresponds to the steepest local descent. Therefore, basically the simplest gradient method lies the formula

x = x –α f(x), (3.45)

where α is a given positive parameter. The method has two disadvantages: firstly, it becomes necessary to select an appropriate value of α , and, secondly, the method is characterized by slow convergence to the minimum point due to the smallness f in the vicinity of this point.

Thus, it is advisable to determine the value of α at each iteration

x = x –α f(x), (3.46)

The value of α is calculated by solving the minimization problem f (x(k +1)) along the direction f(x) using one or another one-dimensional search method. The gradient method under consideration is called the steepest descent method, or Cauchy method, since Cauchy was the first to use a similar algorithm to solve systems of linear equations.

Searching along a straight line in accordance with formula (3.46) provides higher reliability of the Cauchy method compared to the simplest gradient method, however, the speed of its convergence when solving the series practical problems remains unacceptably low. This is quite understandable, since changes in variables directly depend on the gradient value, which tends to zero in the vicinity of the minimum point, and there is no mechanism for accelerating movement towards the minimum point in the last iterations. One of the main advantages of the Cauchy method is related to its stability. The method has important property, which lies in the fact that with a sufficiently small step length, iterations ensure the fulfillment of the inequality

f (x) ≤ f (x). (3.47)

Taking this property into account, we note that the Cauchy method, as a rule, allows one to significantly reduce the value of the objective function when moving from points located at significant distances from the minimum point, and therefore is often used when implementing gradient methods as an initial procedure. Finally, using the Cauchy method as an example, we can demonstrate individual techniques that are used when implementing various gradient algorithms.

Example 3.7. Cauchy method

Consider the function

f(x) = 8x + 4x x + 5x

and use the Cauchy method to solve the problem of its minimization.

Solution. First of all, let's calculate the gradient components

= 16x + 4x , = 10x + 4x .

In order to apply the steepest descent method, we set the initial approximation

x (0) = T

and using formula (3.46) we construct a new approximation

x = x-α f(x)

f(x) = 8x + 4x x + 5x

Rice. 3.14. Iterations using the Cauchy method using the quadratic interpolation method.

Table 3.1.Calculation results using the Cauchy method

Let us choose α in such a way that f (x(1)) → min.; α = 0.056. Hence, x (1) = [– 1,20, 2.16]T Next we will find the point

x = x –α f(x),

calculating the gradient at a point x and searching along a straight line.

Table 3.1 presents the data obtained during iterations based on a one-dimensional search using the quadratic interpolation method. The sequence of obtained points is shown in Fig. 3.14.

Although the Cauchy method has little practical value, it implements the most important steps of most gradient methods. The block diagram of the Cauchy algorithm is shown in Fig. 3.15. Note that the algorithm ends when the gradient module or vector module ∆x becomes quite small.

Rice. 3.15. Flowchart of the Cauchy method.

3.3.2. Newton's method

It is easy to see that the Cauchy method uses the "best" local search strategy using a gradient. However* movement in the direction opposite to the gradient leads to the minimum point only in the case when the function level lines f represent circles. Thus, the direction opposite to the gradient is, generally speaking, Not may serve as an acceptable global direction of searching for optimal points of nonlinear functions. The Cauchy method is based on a sequential linear approximation of the objective function and requires the calculation of the values ​​of the function and its first derivatives at each iteration. In order to build a more general search strategy, information about the second derivatives of the target function should be used.

Let us again expand the objective function into a Taylor series

f(x)=f(x)+ f(x) ∆x+½∆x f(x)∆x+O(∆x³).

Discarding all terms of the expansion of the third order and higher, we obtain a quadratic approximation f(x):

(x; x) = f(x) + f(x) T ∆x + ½∆x f(x)∆x,(3.48)

Where (x;x)- approximating function variable X, built at a point x. Based on the quadratic approximation of the function f(x) Let us form a sequence of iterations in such a way that at the newly obtained point x gradient approximating function turned to zero. We have

(x;x) = + f(x)+ f(x) = 0, (3.49)

The method is focused on solving problems with quadratic objective functions and is based on fundamental theoretical results. Although real-world algorithms that are efficient for quadratic objective functions may perform poorly for more complex objective functions, this approach still seems reasonable.

Definition. Let be a symmetric matrix of order
. Vectors
are called
- conjugate, if they are linearly independent and the condition is satisfied
at
.

Example. Consider the function

As a matrix
you can take the Hessian matrix

.

As one of the directions we will choose
. Then the direction
must satisfy equality

.

It should be noted that the conjugate directions are chosen ambiguously. However, if we add a normalization condition, then they can be determined unambiguously:

Statement. Any quadratic function variables that have a minimum can be minimized in steps, provided that the search is carried out along directions conjugate with respect to the Hessian matrix.

An arbitrary function can be fairly well represented in the neighborhood of the optimal point by its quadratic approximation. Therefore, conjugate directions can be useful for its optimization. However, more than steps. To determine conjugate directions, a method based on the following statement is used.

Statement. Let a quadratic function be given
, two arbitrary points
and directionS..If point is the minimum point of the function
along the directionSfrom point , A - the minimum point of the function along the directionSfrom point
, then the direction
associated with directionS.

Algorithm.

Step 1. Set starting point and system linearly independent directions
(they may initially coincide with the directions of the coordinate axes). Minimize function
with sequential movement along directions; using some kind of one-dimensional search; and take the previously obtained minimum point as the initial one.

Step 2. Perform an additional step
, corresponding to the complete movement in step 1. Calculate the point
(Figure 12). Check the criterion (*) for including a new direction in the system of conjugate directions.

Step 3. Let – the greatest decrease in the objective function in one of the directions
:

And is the direction corresponding .

If the conditions are met

(*)

then continue the search along the original directions
from point
or
(from the point where the function value is smaller).

Step 4. If conditions are not fulfilled, then minimize the function
along the direction
. Take the point of this minimum as the starting point at the next stage. At this stage, use the referral system

those. direction replace with , which should be placed in the last column of the direction matrix.

Step 5. If
, then the minimum is found. IN otherwise complete step 1.

Example. Clicking on the icon will open a Mathcad conjugate direction method document in which you can perform calculations.

Minimizing a function

conjugate directions method

It may seem irrational to throw away the best direction of the current iteration and install a new promising direction last instead of first. However, it is not difficult to see that the most successful direction has most likely exhausted itself, and a new promising direction has just been used for one-dimensional optimization and there is no point in applying it immediately, since there will simply be no progress.

Powell proved that the determinant of the direction matrix takes a maximum value if and only if the directions ,
are conjugate with respect to the Hessian matrix. He concluded that the direction of a complete movement should replace the previous one only if this direction increases the determinant of the direction matrix, since only then will the new set of directions be effective.

It is proven that Powell's procedure converges to a point at which the gradient is zero if the objective function is strictly convex. This point is a local minimum. The method is very sensitive to the way the conjugate directions are constructed and therefore depends on the accuracy of the one-dimensional search used. Powell proposed using a sequence of quadratic interpolations with a special procedure for tuning the parameters of this linear search. However, numerical studies have shown that Powell's conjugate direction method should not be used for dimensions greater than 20.

To conclude the study of approximate methods for searching for the extremum of the FMF without restrictions, let us consider the method of conjugate directions, which is gaining more and more popularity in practice.

First we give the concept of conjugacy. Let us have two directions, which are characterized by vectors and . Directions And are called conjugate with respect to some positive definite matrix H if the relation

, (7)

WITH tension is associated with orthogonality. If H is the identity matrix, then when
we have two mutually perpendicular vectors. Relation (7) can be interpreted as follows: matrix H applied to the vector , changes its length and rotates it by some angle so that the new vector
must be orthogonal to the vector .

Using the method of conjugate directions, we will find the extremum of a separable function with an initial point
.

1) A selection is made and in this direction an extremum is sought.

Let's take a vector with directions And . Vector can be chosen arbitrarily, so let's take ==1. Vector gives the direction L 1.

Let us draw a plane through L 1 perpendicular to the plane (x 1 , x 2 ). The plane will intersect the extremal surface y(x 1, x 2) and highlight an extremal line on it. Let's determine the coordinates of the minimum on this line (parabola), for which we calculate the projections of the gradient at the point x 0:

,

and using formula (6) we find :

Naturally, the line L 1 touches at point x (1) the line of equal level of the function y.

2) Searchedfrom the conjugacy condition
.

We get the conjugate vector with projections
And
, using formula (7):

P
We obtained one equation with two unknowns. Because we only need the direction of the vector , and not its length, then one of the unknowns can be specified arbitrarily. Let
=1, then
= –4.

3) From point x (1) in the directionan extremum is sought.

The conjugate vector must pass through x(1). Let's take a step in the conjugate direction:

Step size  (1) in x (1) :

,

So, in two iterations the exact value of the extremum of the function y was found. As the first vector it was possible to select a gradient at the starting point, the search procedure remains the same.

In mathematics, it is proven that the conjugate direction method converges for quadratic functions in no more than n iterations, where n is the number of variables. This circumstance is especially valuable for practice, so this method is increasingly used.

For functions of a more general form, the method of conjugate directions is still being developed. The main difficulty here is that the Hessian matrix turns out to be functional, i.e. contains a variable.

Classical Lagrange conditional extremum problem (equality constraints).

P
Let the objective function be given
and equality constraint (connection equation)
. We need to find the minimum
on a set
. We believe that the functions
And
have continuous first derivatives and are convex or concave.

Let us consider the geometric interpretation of the classical problem. On the plane (x 1 ,x 2 ) we construct a function
, as well as lines of equal function level
with values ​​N 1 , line N 3 has 2 common points with
and they cannot be a solution to the problem, since N 3 >N 2 . What remains is level line N 2, which has a single point of tangency with
. The absolute minimumN 0 may not belong to the constraint
and therefore cannot be a solution to the problem. Hence the name “conditional extremum” is clear, i.e. such an extremum that is achieved only under given restrictions.

At the point of contact
with function
Let's draw a tangent line L. Let's sharpen the function gradients
And
at the point of contact, they will lie on the same line, because both are perpendicular to L and directed in different directions. Let us determine the projections of the gradients on the x1 and x2 axes at the point of tangency:

From the similarity of triangles we can write:

– Lagrange multiplier.

or

Let's now compose the function
as follows:

– Lagrange function.

Let us write down the relations for finding the extremum of the function F.

As can be seen, we obtained the same relationships that were obtained based on the geometric interpretation of the problem. The constant is called the Lagrange multiplier. With the help of this multiplier, the conditional extremum problem is reduced to the unconditional extremum problem.

In the general case, we take the number of variables to be n, and the number of restrictions to be m. Then the Lagrange function will be written as:

or in vector form

To solve the problem, a system of equations is written:

, (8)

those. for n+m variables we will have n+m equations. If the system is consistent, then the Lagrange problem has a unique solution.

Because To determine the extremum, only the first derivatives were used, then the resulting conditions will only be necessary. If the functions
And
convex or concave, then there is only one conditional extremum. If one of the functions is non-convex, then the extremum may not be the only one. In addition, the question remains as to whether what was found is a minimum or a maximum, although in engineering practice this is usually clear from physical considerations.

Example: We will show the technique for solving the problem using the Lagrange method.

D
For the above example with two pumps, the volume of pumped liquid is specified:

With this limitation, it is necessary to find the power consumption of the pumps
. Let the coefficients be  1 = 2 =1, K 1 =1, K 2 =1.5. Then the objective function is to find the minimum under the constraint:.

Solution procedure:

Compiling the Lagrange function

A system of equations (8) is compiled:

Q i are written through  and substituted into the third expression:

,
,
,

Then the coordinates of the extremum are:

,

Example 2:

Let a series connection of compressors be given.
The required compression ratio is set: which must be ensured with a minimum of power consumption:

2.

3.
,
, substitute into the expression for :

,
,
. For physical reasons, we discard the positive root, therefore  = –0.98.

Then the coordinates of the extremum are:

,

As can be seen from the above examples, when solving the Lagrange problem, we generally obtain a system of nonlinear equations, which is sometimes difficult to solve analytically. Therefore, it is advisable to use approximate methods for solving the Lagrange problem.