§ 2 Multivariate function extreme value problem solution ( direct method )
This section discusses finding the objective function
Direct methods ( or experimental optimization methods ) for optimal solutions over defined regions , where
( represents the transpose of a vector )
Represents the column vector composed of the independent variables . Since the minimum and maximum are only the difference between the objective functions by one sign, only the dimension column vector is discussed here so that the
At this time, it is called the optimal solution ( optimal point ) .
[ Unimodal function ] If the function has only one extreme point ( maximum point or minimum point ) on the region in question , then this function is called a multivariate unimodal function.
Multivariate unimodal functions can also be defined analytically. For example, let the function be defined on the area , since any route on the area can be used with a parametric equation
is represented, so the function along this route can also be represented with parameters as
if , when
Then the function is said to be unimodal over the region from point to point , where
A function is said to be unimodal over a region if , for any pair of point sums on the region , there exists a route from passing to to over which the function is unimodal .
[ Factor Alternation Method ] This method is to explore the optimal point in turn according to the direction of the coordinate axis . Set it as the unit vector of the i -th coordinate axis, that is
And given the allowable error in advance , the iterative procedure is as follows:
( 1 ) Select the initial point .
( 2 ) Starting from the initial point , firstly optimize along the direction of the first coordinate axis ( using the single factor method of § 1 ) to obtain a good point , namely
is a real parameter in the formula . Then the starting point is optimized along the direction of the second coordinate axis, and a good point is obtained , that is
And so on, until all directions are optimized, get , it satisfies
( 3 ) repeating step ( 2 ) as a new initial point .
( 4 ) The above steps are carried out until starting from a certain initial point, no new point can be obtained after searching in all directions, or the distance from the previous initial point is less than the preset allowable error . This is the approximate solution of the optimal point .
[ Parallel line method ] If one factor is difficult to adjust and another factor is easy to change in the two-factor problem being dealt with, it is inconvenient to use the two-factor alternation method, and the following parallel line method should be used instead:
Put the factors that are difficult to adjust on the vertical axis ( Figure 18.5) , and set the adjustable range as [ 0 , ] . Put the factors that are easy to change on the horizontal axis, and set the adjustable range as [ 0 , ]. The factor is fixed at the point , and on the straight line passing through this point and parallel to the horizontal axis, the factor is preferably on [ 0 , ] , and the good point is ① ; On the straight line , the pair factor is optimized on [ 0 , ] , and the good point is ② ; compare the quality of the two points ① and ② , if ② is better than ① , remove the upper half of the line ( if ① is better than 1)②Okay , just remove the lower half of the line ) , then fix the factor at the adjustable range, and select the factor on [ 0 , ] on the line passing through this point and parallel to the horizontal axis , and the good point is ③ ; Compare the quality of points ② and ③ . If ② is better than ③ , remove the lower half of the straight line and continue to narrow down the optimal range to find the approximate solution of the optimal point.
The selection of factors can also use the fractional method.
[ Blind Mountain Climbing Method ] The iterative process is as follows:
(1) Select the step size of the initial point ( base point ) , command .
(2) Local exploration of the l -th direction ( ie, the axis direction ) of the k -th stage
where is the unit vector of the lth coordinate axis, first explore in the positive direction
If , then the exploration is successful, take this point as the starting point of the next exploration along the l +1th coordinate axis direction, and command ; otherwise, search in the opposite direction
If , the exploration is successful, take this point as the starting point of the next exploration along the l +1th coordinate axis direction, and order ;
and life .
When the local exploration along the directions of each coordinate axis is carried out in turn, the local exploration at this stage is also completed, and the best point of the kth stage is obtained at this time .
(3) Command , consider the new base point, repeat step (2), if a better point cannot be obtained, reduce the step size and then perform local exploration until the step size is reduced to the specified accuracy, then the best point obtained is is the approximate solution of the optimal point.
Although the blind mountain climbing method ( also known as the exploratory mountain climbing method ) is not as fast as the previous methods, it is especially suitable for the situation where the factors cannot be greatly mobilized, or if a waste product is produced in large-scale production, it will cause a lot of losses.
[ Steep method and diagonal method ]
The 1 ° steepness and the steepness method are set at , two points have been tested, and their objective function values are respectively ( Fig. 18.6) , and , then,
is called the steepness from ascent to . There is a similar definition for dimensional space.
The objective function in the direction with large steepness obviously rises faster . The so-called steepness method is to use the obtained test results to calculate the steepness between points, and then take points in the direction with the greatest steepness ( favorable direction ) for testing. .
2 ° Combined method ( the blind mountain climbing method is used in combination with the steepness method ). For example, the blind mountain climbing method is used to start from the point and move the factor along the axis to get the point . The effect is better, and the factor is still moved along the axis.
The pixel gets a point ( Figure 18.7) , the effect is still good, and then along the axis
If the mobilization factor gets some points , the effect is good, and the next step is not necessarily from the
Hair and then along the vertical and horizontal direction to explore. At this time, the objective function can be calculated by
steepness of rise to , steepness of rise to , steepness of rise to
the steepness of , select a direction with the greatest steepness, for example , then
Next time, you can climb up in the direction of
Use the blind climbing method to climb up the extension line along the line section , or you can
The single-factor method is preferred, and a better point can generally be found .
3 ° Diagonal method Above , we compare the steepness of the three directions through the point to pick out a steeper direction, such as yes , but not
It is not necessary to pass the steepest direction of the point, in fact, you only need to use the steepest direction of the two directions of the point.
degree, you can find the steeper direction of the point.
As shown in Figure 18.8 , take a point in the direction perpendicular to the
The length of is equal to the steepness of to, and and are on both sides of the
Take a point in the direction perpendicular to the
The steepness of , and and on both sides respectively , with , as the side
For a parallelogram, the direction of the diagonal is the point where the steepness is greatest
[ Step acceleration method ] The step acceleration method is actually a combination of the blind mountain climbing method and acceleration in a favorable direction . The iterative procedure is as follows:
(1) Select the initial point ( base point ) and step size , and order .
(2) Blind mountain climbing ( see the blind mountain climbing method for the procedure ) .
When the local exploration along the direction of each coordinate axis is carried out in turn, the local exploration at this stage is completed, and the next step can be accelerated in a favorable direction.
(3) Speed up hill climbing. life . If , then move to a new position to test for acceleration,
Two situations may arise:
1 ° If the value is improved, then , apply the method of step ( 2 ) to start a new exploration.
2 ° If the value of 2 ° does not improve, then cancel this acceleration and place the base point at the best point found last time, ie . command , start a new local exploration as in step (2) .
If it is found that the movement cannot be accelerated after a period , then reduce the step size and repeat step ( 2 ) . If successively reducing the step size can not accelerate the movement, this point is the approximate solution of the optimal point.
The step-acceleration method is shown in Figure 18 in two dimensions . 9 shown.
[ Direction acceleration method ( conjugate direction method )] The iterative procedure is as follows:
(1) Starting from the previous best numerical position ( which can be the point determined at the end of the previous iteration or a good point obtained by other methods ) and a set of linearly independent exploration directions ( which can take the direction of the coordinate axis ) . First find the best point on the straight line parallel to the passing point, and then find the best point on the straight line parallel to the passing point , and continue this process until all n exploration directions have been tried, and the final obtained point is .
(2) Find a special point , this point makes the value of the objective function improve the most compared with the previous point, that is, the point gives the maximum change of the movement , where . Also decide the vector .
(4) Remember if
( 1 )
( 2 )
If that is not a good direction in the exploration, you should start the exploration again, starting from the last point and repeating step (1) in the same way, that is, and . If the inequalities (1), (2) are not satisfied, then explore along the direction until the minimum point is found. Define this point as , and the new exploration direction of stage k + 1 is ; ; and again . Then, starting from step (1) , the whole process is repeated until , where is a predetermined allowable error.
Example of applying the directional acceleration method to find the objective function
the minimum point.
It is easy to find the absolute minimum point of the objective function by using the derivative method . Next, the directional acceleration method is used to find this minimum point.
Start exploring from the point , and use the sum to explore the direction .
In the first stage , starting from the base point, one-dimensional exploration is carried out along the direction , and the moving distance is determined by
Reaching a minimum, we get , therefore , while the objective function value is reduced by . Then explore in the same way along the direction , get , at the same time .
In order to decide whether to use the direction in the next stage, inequality (1) should be checked , the point is calculated , and , since , the direction is not used in the next stage .
The second stage The direction of this stage is the same as that of the previous stage ( because it is not adopted ) . One after another to explore , and , and . Recalculate points . Here , since , inequality (1) is not satisfied. Checking inequality (2) again , calculate
where is the maximum change of the objective function in a given direction, ie . The right-hand side of inequality (2) is
Therefore, inequality (2) is not satisfied, that is, the direction can be adopted in the next stage
, explore along the direction to get the base point of the third stage as , and .
The third stage The exploration direction of this stage is sum . Exploring in these two directions will reveal that we cannot go any further, because in fact the absolute minimum has been found in the previous stage. Of course, this is not surprising since the objective function is quadratic.
[ Direction step size double acceleration method ] The iterative procedure is as follows:
Consider the kth stage
(1) Select an initial point ( base point ) , a set of steps and a set of directions , where the upper index represents the first stage, and the lower index represents the first direction. At that time , the exploration direction was generally chosen to be parallel to the coordinate axis direction.
(2) Perform successive explorations parallel to each of the n directions in turn. If the movement is successful, the new point is adopted, and if the movement is unsuccessful, the base point is retained. If the movement in a given direction is successful, the next time you explore in this direction, the step size will be doubled ; if it fails, it will be reduced to double , and the negative sign indicates exploration in the opposite direction. Generally take .
(3) Until there is at least one success and one failure in each direction, the exploration along this direction ends. The last successful point is the new base point after the exploration in parallel to n directions is completed . The exploration direction of the next stage ( ie the first stage ) is calculated by the following equation:
First define the vector
where is the algebraic sum of all successful moves in the direction,
Then the direction is given by
In particular, where the main direction
Its components are
(4) The above steps are carried out until ( for a predetermined allowable error ) , and the final base point obtained is approximately the optimal point.
The directional step double acceleration method in two dimensions is shown in Figure 18.10 .
[ Simplex tuning method ] The iterative procedure is as follows:
(1) Name the n+ 1 vertices of the simplex of the n-dimensional space as , calculate the function value , compare the size, and determine
(2) Find the symmetry point of the worst point
in the formula
(3) If , it will be reduced to , defined by the following formula:
The requirement here is to avoid situations from happening.
If , then , and repeat the above steps.
If , then , and restart the iteration.
(4) If , it will be expanded to , defined by the following formula:
The expanded condition can also be replaced by
If the above conditions are met, and
and repeat the above steps.
The above process continues until
so far, where is a predetermined positive number.
V uses vector notation here
It represents a point in the dimensional space . The superscript k represents the kth stage of the search, and the subscript l represents the lth cycle in the kth stage search . If it represents the sequence of base points in the search , when it is close to the optimal point, there are