Zhurbenko N.G. – Institute of Cybernetics of National Academy of Sciences of Ukraine, zhurbnick@yandex.ru,

Likhovid A.P. – Institute of Cybernetics of National Academy of Sciences of Ukraine,  o.lykhovyd@gmail.com

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_iterationsthe maximum number of iterations of r-algorithm;

·                 Argument_accuracystopping 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;

·                 Gradient_accuracystopping 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_intervalthe 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_stepthe initial value for stepsize of the algorithm of approximate search for the minimum along the direction of descent

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

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

·                 Alpha_parameterthe coefficient of space dilation;

·                 Penalty_parametera 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 Gradient_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)