§ 3 Unconditional extremum problem solution

This section discusses the objective function

the minimum value problem. Assume

[ Steest descent method ] The   iterative procedure is as follows :

(1)       Select the initial point and discriminate the positive number of convergence .

(2)       life

(3)       Calculation

(4)       Order , if it is , then the iteration stops , which is what is required ; otherwise, proceed to (5) .

(6)       life ; life , carry on (3) .

Although this method is very simple, the speed of convergence of the point sequence to the optimal solution is slow.

[ Newton's method ] The   iterative procedure is as follows:

(1)       Select the initial point and discriminate the positive number of convergence .

(2)       life

(3)       Calculation .

(4)       life

If the iteration stops , it is what is required ; otherwise, go to (5) .

(6)  life ; life , carry on (3) .

Although Newton's method can quickly converge to the optimal solution , it is often difficult to calculate the inverse matrix . In order to avoid this difficulty , a conjugate gradient method with a convergence rate between the steepest descent method and Newton's method is developed.

1 o The   objective function is a quadratic function

The iterative procedure is as follows :

(1) Select the initial point and discriminate the positive number of convergence , if so, stop the iteration ; otherwise, go to (2) .

(2)       life ,

(3)       Calculate

(4)       life

(5)       If , the iteration stops ; otherwise, the command

order , proceed to (3) .

For quadratic functions, the optimal point can be reached with a finite number of steps.

2. When  the objective function is a general function , the iterative procedure is as follows :

(1)   Select the initial point and discriminate the positive number of convergence . If so, the iteration stops ; otherwise, go to (2) .

(2)   Life , .

(3   ) Envoy

(4)  life

(5)   If , the iteration stops ; otherwise , if , then , proceed to (1), if , then calculate

Life

order , proceed to (3) .

The procedure of this method is simpler and the storage capacity is small , but when it is small , the calculation may cause instability due to large rounding errors.

For general ( non-quadratic ) functions , this method is not necessarily a finite number of steps to reach the optimal solution.

[ variable scaling method ]

The 1 ° objective function is a quadratic positive definite function

The iterative procedure is as follows :

(1)        Select the initial point and discriminate the positive number of convergence . If so, the iteration stops ; otherwise, go to (2) .

(2)       Order , ( order identity matrix ), .

(3)       Fate .

(4)       Calculate

(5)       life

(6)       If , the iteration stops ; otherwise , order

figure out

Go to (7) again .

(7)       Order to proceed (3) .

For quadratic functions, the optimal point can be reached with a finite number of steps.

In the case where the 2 ° objective function is a general function , the iterative procedure is as follows :

(1)        Select the initial point and discriminate the positive number of convergence . If so, the iteration stops ; otherwise, go to (2) .

(2)       Order , , ( order identity matrix ) .

(3)       Fate .

(5)       LIFE .

(6)       If , the iteration stops ; otherwise , if , then , proceed to (1), if , then calculate

, ,

order , proceed to (3) .

For general ( non-quadratic ) functions , this method is not necessarily a finite number of steps to reach the optimal solution.

The variable scale method is an improvement of the conjugate gradient method , and its convergence speed is faster.

[ Gauss - Newton Least Squares ]  Assume that the objective function is in the form of a sum of squares

where is the dimension column vector .

This is the most common form of function in data processing.

Obviously , if the minimum point satisfies ( with a predetermined precision ), then it can be considered as a system of equations

solution. So the least squares method can also be used to find solutions to nonlinear equations.

The function is generally nonlinear , assuming continuous first-order partial derivatives :

The iterative procedure is as follows :

(1)       Choose an initial point .

(2)       Calculate

in the formula

is called the correction amount to the initial value ; and

It is assumed that the column vectors of the matrix are linearly independent , so the inverse matrix exists.

(3)       life

is the first approximation of the minimum point of the function .

(4)       To replace the previous , replace , repeat the above calculation process until

or

So far , where sum is a pre-specified two positive numbers representing the accuracy requirement.

[ Improved Gauss - Newton least squares method ]  The above Gaussian - Newton least squares method takes advantage of the fact that the objective function is a sum of squares, and replaces the second derivative matrix in Newton's method with an approximation , which greatly saves the amount of calculation , but it does not affect the initial point. The requirements are more stringent , if the initial point is too far from the minimum point , the algorithm often fails. The reason can be seen from two aspects , one is that the above algorithm is based on linear approximation , but this linear approximation is invalid when it is far away from the minimum point ; the other is that the ratio of the maximum eigenvalue to the minimum eigenvalue is so large that makes the solution meaningless. To this end, the following improved methods are adopted.

After the obtained correction amount , it will not be regarded as the first approximation , but will be regarded as the next search direction .

minimum

then make

instead of repeating the above process until

or

, the minimum point and the minimum value are respectively

,

is called the optimal step size factor for the th step.