** Zhurbenko N.G. – **Institute of Cybernetics of National
Academy of Sciences of

** Likhovid A.P.** – Institute of Cybernetics of National Academy
of Sciences of

*Software implementation of r-algorithm.*

algorithm description **|** download software tool (Windows) | download
software tool (Linux)

Software implementation of method
of generalized gradient descent with space dilation (Shor's ** r**-algorithm
[1]) is developed to solve smooth and nonsmooth optimization problems in AMPL
environment. (http://www.ampl.com/index.html). The method of nonsmooth penalty functions is used for solving
optimization problems with constraints. Description of the mathematical
model of optimization problem and input data must be in accordance with the
requirements of AMPL. The prepared description of the mathematical model can be
used to solve the problem by any solver, providing an interface with AMPL. The
initial value of problem variables is used as a starting point of the
algorithm.

Executable module AmplRalg.exe must run in AMPL environment by commands of AMPL, as well as other solvers. For this a student or a full version of AMPL software is required on computer (http://www.ampl.com/DOWNLOADS/index.htmll). AmplRalg.exe module must be in the same directory where the other solvers AMPL are located. Below example of run of module AmplRalg.exe is presented.

ampl: *reset;*

ampl: *model
**mathmod**.mod; # **model description*

ampl: *data
**mathmod**.dat; # **data description*

ampl: *option
solver AmplRalg;*

ampl: *solve;*

In the same directory file RALG.OPT
of parameters of r-algorithm should be located. RALG.OPT file contains the
following data (you can change the numeric values only)

Limit_of_iterations |
10000 |
(by_default__1000) |

Argument_accuracy |
1.00E-006 |
(by_default_1.e-6) |

Gradient_accuracy |
1.00E-006 |
(by_default_1.e-6) |

Output_interval |
100 |
(by_default____10) |

Initial_step |
1 |
(by_default____1.) |

Q1_parameter |
0.95 |
(by_default__0.95) |

Q2_parameter |
1.2 |
(by_default__1.20) |

Alpha_parameter |
2 |
(by_default___2.0) |

Penalty_parameter |
1000 |
(by_default_1000.) |

These parameters have the
following meanings:

·
**Limit_of_iterations** – the maximum number
of iterations of r-algorithm;

·
**Argument_accuracy** – stopping criterion of
the algorithm by the value of the current stepsize in the space of variables
(problem variables) – termination is made as the stepsize
value becomes less than a specified value;

·
**G****radient_accuracy** – stopping criterion of the algorithm by the value
of norm of gradient of the objective function – a termination is
made as the norm value becomes less than a specified value;

·
**Output_interval** – the number of
iterations of the algorithm, when information about the status of the
optimization process is
printed – Iter (iteration number), Obj (current value of the objective function), Shift X (current step in the space of arguments), Fun
calls (the total number of calls to the procedure
of computation of function value and gradient);

·
**Initial_step**
– the initial value for
stepsize of the algorithm of approximate search for the minimum along the
direction of descent

·
**Q1_parameter**
– a controlling parameter of the
algorithm of one-dimensional descent direction, **Q1_parameter≤1** ( corresponding to the parameter ** g** [1]);

·
**Q2_parameter**
– a controlling parameter of
the algorithm of one-dimensional descent direction, **Q2_parameter≥1** (corresponding to the parameter ** m** [1]);

·
**Alpha_parameter** – the coefficient of
space dilation;

·
**Penalty_parameter** – a value of the
penalty coefficient for the method of nonsmooth penalty function (for small values of the coefficient penalty
function is unbounded from below, with too large – a
slow convergence, the program may stop in a sub-optimal point).

In parentheses the user can see
the recommended values for the most typical problems.

After completion of the program a
value of termination code is printed :

· Ist = 1 – crash;

·
Ist = 2 – termination is made as the current value of norm of gradient of the objective
function becomes less than the specified value **G****radient****_****accuracy**;

·
Ist = 3 – termination is made as the current
stepsize value becomes less than the specified value **Argument****_****accuracy**;

·
Ist = 4 – termination is made as the current
number of iterations becomes greater than the specified value **Limit_of_iterations**;

·
Ist = 5 – termination is made as the objective
function is unbounded (
usually when a value of
penalty coefficient **Penalty_parameter **is not sufficient).

Requirements
for software and hardware environment:

· PC of standard configuration;

·
32-bit operating system -
Windows XP/ 2003/Vista or later, Linux;

·
Student or full version of
AMPL software environment

1. *N.Z Shor, N.G Zhurbenko *Minimization
method using operation of space dilation in the direction of the difference of
two successive gradients // Kibernetika. - 1971. - № 3. - P. 51-59. (in
Russian)