The method based on the idea of coordinates descent by all initial coordinates and when possible, the descent in the directions conjugated to initial coordinates. Let's recall that two directions   and   are conjugated if   ; , where H - positive definite Hessian matrix:  . If the function f(x1,x2,…xn) is the n-dimensional positive defined quadratic form or n-dimensional paraboloid; its minimum is obtained for n moves in the direction of n various conjugated directions.

Schematically the computing procedure of algorithm implemented in the Descent program consists in the following rules. At the beginning, there is movement in the line of initial coordinates x1,x2,…,xn by turn. The local minimum   obtained on the k-th iteration at movement in the line of   coordinate is maintained. Later, when finding the second minimum   on the (k+m)-th iteration movement in the direction from the first minimum   to the second one   is carried out at once. As both minimums   and   have been obtained at the movement in the line of the same coordinate  , the direction from   to   and direction in the line of coordinate   is conjugate. If n>2 the third conjugate direction connecting two minimums, obtained at moving in the line of two identical previous conjugate directions is constructed. Thus the Descent program approximates function n variables by a sequence of two-dimensional and three-dimensional paraboloids.

If coordinates descent is unsuccessful, the additional evaluation of the objective function value in the point of  the minimum n-dimensional degenerate paraboloid is produced by which the objective function is approximated. This procedure allows considerably increasing reliability of the program.

Except the descent in the line of coordinate axes and conjugate directions in the program Descent the moving on curvilinear direction takes place. Curvilinear direction is obtained by parabolic approximation of three last coordinates of local minimums found at the movement by the last coordinate. Movement in curvilinear direction allows efficient passing narrow curved canyons, as in Rosenbrock function.

In the Powell's method [1] the complete set of n conjugate directions by the following recurrent rule is under construction: the k-th conjugate direction coincides with the direction connecting two local minimums, obtained at movement along previous k-1 identical conjugate directions. If at movement in the k-th conjugate direction the function considerably decreases, the appropriate coordinate axis on this conjugate direction is replaced. Thus, unlike the Descent program, the Powell program approximates function n variables by a sequence of n-dimensional paraboloids during optimization.

The Hooke-Jeeves method [1] is modification of the simplest coordinates descent method. First, k iterations of this method are carried out similarly to those of the coordinates descent method. After finding the local minimum   after the k iteration the search is carried out in the direction connecting initial approximation   and k approximation   (so-called pattern search).

The modification of the Hooke-Jeeves method performed by the mainly consists in the following: variable step of search and quadratic interpolation have been used at linear search on each coordinate. Besides increase of the probability the direction of pattern search coincides with direction conjugated with coordinate axes.

When searching a minimum of n-variables function by the Nelder-Meed method [1] as trial values, the points located in the vertex of simplex (polyhedron) are taken. In each vertex of the simplex objective function values are calculated. Further, initial polyhedron is deformed by one of special procedures (reflection, expansion, compression or reductions) so that the vertex with a maximum function value to be transformed into a vertex with smaller function value. Deforming of the polyhedron proceeds so long as its size does not decrease up to the given tolerance. The barycentre of the final polyhedron are taken as approximation to a point of a minimum.

The search direction of this method is directly opposite to the direction of a gradient vector of the function f(x1,x2,…,xn). As against the gradient method requiring knowledge of the first analytic derivatives of the objective function, derivatives is estimated approximately by meanse of difference derivation.

 Search directions of this method are random and independent of each other. If the direction is chosen unsuccessfully, another random direction gets out.

Simulated annealing [2] is a random-search technique utilizing an analogy between the way in which a metal cools and freezes into a minimum energy crystalline structure (the annealing process). Simulated annealing's major advantage over other methods is an ability to avoid becoming trapped in local minimum. The algorithm employs a random search which not only accepts changes that decrease the objective function f, but also some changes increasing it. The algorithm starts with an initial feasible solution, which is set as the current solution. Randomly, a neighboring solution from the solution space is chosen, and its energy (objective function) f is compared to that of the current solution. If the energy is decreased, this neighbor solution is kept and set as the current solution. Otherwise, this solution is accepted with a probability that is calculated according to the stage the algorithm is in (we designate this stage via a variable T called "temperature"). The probability of accepting a worse solution is P = exp( - df / T ) where df is the difference between energy of the neighbor solution and the current solution. The temperature is managed by the cooling schedule that controls the execution of the algorithm, i.e. the temperature T decreases according to the formula T_new=Cooling*T_old , where 0<Cooling<1 - cooling factor.

f - function or procedure of n-variables (n=nops(Xmin0)).

Xmin0 - list  of  n  initial approximation of the locate minimum.

Step - initial search step.

epsilon<<Step*Shorten - tolerance to stop when ||Xmin-XOld ||<epsilon.

0<Shorten<1 - shortening step coefficient.  Recommended value: Shorten=0.15.

Nmax - maximum permissible number of  function evaluations. If  number of function evaluations exceed Nmax, the search stops.

Return list containing the minimum of the function f estimation, list of n arguments of minimum estimation, number iterations, number of function evaluations.

The arguments Step, epsilon, Shorten, Nmax can be missed. In this case default values are: Step:=1;epsilon:=10.^(-6);Shorten:=0.15;Nmax:=10000.

The global listlist Descent_Search_Path contains the search path coordinates.

f - function or procedure of n-variables (n=nops(Xmin0)).

Xmin0 - list  of  n  initial approximation of the locate minimum.

Step - initial search step.

epsilon<<Step*Shorten - tolerance to stop when ||Xmin-XOld ||<epsilon.

0<Shorten<1 - shortening step coefficient.  Recommended value: Shorten=0.01.

Nmax - maximum permissible number of function evaluations. If  number of function evaluations exceed Nmax, the search stops.

Return list containing the minimum of the function f estimation, list of n arguments of minimum estimation, number iterations, number of function evaluations.

The arguments Step, epsilon, Shorten, Nmax can be missed. In this case default values are: Step:=1;epsilon:=10.^(-6);Shorten:=0.01;Nmax:=10000.

The global listlist Powell_Search_Path contains the search path coordinates.

f - function or procedure of n-variables (n=nops(Xmin0)).

Xmin0 - list  of  n  initial approximation of the locate minimum.

Step - initial search step.

epsilon<<Step*Shorten - tolerance to stop when ||Xmin-XOld ||<epsilon.

0<Shorten<1 - shortening step coefficient.  Recommended value: Shorten=0.15.

Nmax - maximum permissible number of  function evaluations. If  number of function evaluations exceed Nmax, the search stops.

Return list containing the minimum of the function f estimation, list of n arguments of minimum estimation, number iterations, number of function evaluations.

The arguments Step, epsilon, Shorten, Nmax can be missed. In this case default values are: Step:=1;epsilon:=10.^(-6);Shorten:=0.15;Nmax:=10000.

The global listlist Hooke_Search_Path contains the search path coordinates.

f - function or procedure of n-variables (n=nops(Xmin0)).

Xmin0 - list  of  n  initial approximation of the locate minimum.

Side - initial length of simplex rib.

epsilon<<Step*Compression - tolerance to stop when ||Xmin-XOld ||<epsilon.

0<Compression<1 - Compression coefficient.  Recommended value: Compression=0.5.

Reflection - Reflection coefficient.  Recommended value: Reflection=1.

Stretching>1 - Stretching coefficient.  Recommended value: Stretching=2.

Reduction>1 - Reduction coefficient.  Recommended value: Reduction=2.

Nmax - maximum permissible number of function evaluations. If  number of function evaluations exceed Nmax, the search stops.

Return list containing the minimum of the function f estimation, list of n arguments of minimum estimation, number iterations, number of function evaluations.
The arguments Side, epsilon, Compression, Reflection, Stretching, Reduction, Nmax can be missed.

In this case default values are: Side:=1;epsilon:=10.^(-6); Compression:=0.5; Reflection:=1; Stretching:=2; Reduction:=2; Nmax:=10000.

The global listlist Nelder_Search_Path contains the search path coordinates of simplex barycentre.

f - function or procedure of n-variables (n=nops(Xmin0)).

Xmin0 - list  of  n  initial approximation of the locate minimum.

Step - initial search step.

epsilon<<Step*Shorten.  If step searcing<epsilon, the search stops.

0<Shorten<1 - shortening step coefficient.  Recommended value: Shorten=0.7.

Nmax - maximum permissible number of function evaluations. If  number of function evaluations exceed Nmax, the search stops.

Return list containing the minimum of the function f estimation, list of n arguments of minimum estimation, number iterations, number of function evaluations.

The arguments Step, epsilon, Shorten, Nmax can be missed. In this case default values are: Step:=1;epsilon:=10.^(-6);Shorten:=0.7;Nmax:=10000.

The global listlist Qgrad_Search_Path contains the search path coordinates.

f - function or procedure of n-variables (n=nops(Xmin0)).

Xmin0 - list  of  n  initial approximation of the locate minimum.

Nrnd - number of random directions per iteration.

Step - initial search step.

epsilon<<Step*Shorten. If step searching<epsilon, the search stops.

0<Shorten<1 - shortening step coefficient.  Recommended value: Shorten=0.15.

Nmax - maximum permissible number of  function evaluations. If number of function evaluations exceed Nmax, the search stops.

Return list containing the minimum of the function f estimation, list of n arguments of minimum estimation, number iterations, number of function evaluations.

The arguments Nrnd, Step, epsilon, Shorten, Nmax can be missed.

In this case default values are:  Nrnd:=60;Step:=1;epsilon:=10.^(-6);Shorten:=0.15;Nmax:=10000.

The global listlist Random_Search_Path contains the search path coordinates.

f - function or procedure of n-variables (n=nops(Xmin0)).

Xmin0 - list  of  n  initial approximation of the locate minimum (initial solution).

Trnd - number of neighbor random solutions  generated to calculate the initial temperature (T_initial=(fmin-fmax)/ln(0.8)).

0<Cooling<1 - cooling factor (the temperature T decreases according to the formula T_new=Cooling*T_old).

Step - initial  width of uniform distribution which used for selection random search step.

epsilon<<Step*Shorten. If Step<epsilon, the search stops.

0<Shorten<1 - shortening step coefficient.  Recommended value: Shorten=0.85.
Nrnd - number of random solutions that decrease the temperature (T_new=Cooling*T_old) and Step (Step_new=Shorten*Step_old).

Nmax - maximum permissible number of  function evaluations. If  number of  function evaluations exceed Nmax, the search stops.

Return list containing the minimum of the function f estimation, list of n arguments of minimum estimation, number iterations, number of function evaluations.

The arguments Trnd, Nrnd, Cooling, Step, epsilon, Shorten, Nmax can be missed.

In this case default values are:  Trnd:=10; Nrnd:=30; Cooling:=0.15; Step:=1;epsilon:=10.^(-6);Shorten:=0.95;Nmax:=10000.

The global listlist Anneal_Search_Path contains the search path coordinates.

Warning!  To improve reliability one can increase the Shortening step coefficient for nondifferentiable functions and decrease it for differentiable functions.

List of lists of  n search path coordinates: [[x1_0, x2_0,.., xn_0], [x1_1, x2_1,.., xn_1],..., [x1_k, x2_k,.., xn_k]],

n - number of variables, k - number of search directions.

Plots  for  x1, x2  out of  n search path coordinates.  

Repetition_Number is the number of minimization repetitions. The more Repetition_Number the better computation time estimation.