§ 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) .
(5) ask , make
(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) .
(5) Ask for an envoy
(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.
[ Conjugate Gradient Method ]
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 .
(4) Ask , make .
(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.
