Журбенко Н.Г. – Институт кибернетики НАН Украины,  zhurbnick@yandex.ru,

Лиховид А.П. .Институт кибернетики НАН Украины,  o.lykhovyd@gmail.com

Программная реализация r-алгоритма.

 

описание алгоритма  |  загрузка программного средства (Windows)  |  загрузка программного средства (Linux)

 

Программная реализация метода обобщенного градиентного спуска с растяжением пространства (r –алгоритм Шора Н.З. [1])  предназначена для решения гладких и негладких задач оптимизации в программной среде AMPL (http://www.ampl.com/index.html). Для решения задач с ограничениями используется метод негладких штрафных функций. Описание математической модели задачи и исходных данных производится в соответствии со стандартными  требованиями AMPL. Подготовленное описание математической модели может использоваться для решения задачи любым солвером, обеспечивающим интерфейс с AMPL. Начальные значения переменных задачи используется в качестве стартовой  точки алгоритма.

Выполнимый модуль AmplRalg.exe должен запускаться на выполнение в программной среде AMPL командами языка AMPL, также как и другие солверы. Для этого на компьютере должна быть установлена студенческая или полная версия программной среды AMPL (http://www.ampl.com/DOWNLOADS/index.html). Модуль AmplRalg.exe должен размещаться в том же директории, где расположены другие солверы AMPL. Пример запуска модуля AmplRalg.exe

 

ampl: reset;

ampl: model mathmod.mod; # описание модели

ampl: data mathmod.dat;  # описание данных

ampl: option solver AmplRalg;

ampl: solve;

 

В этом же директории должен быть расположен файл RALG.OPT параметров r-алгоритма. Файл RALG.OPT содержит следующие данные  (изменять можно только числовые значения)

 

Limit_of_iterations                 10000        (by_default__1000)

Argument_accuracy                   1.e-6        (by_default_1.e-6)

Gradient_accuracy                   1.e-6        (by_default_1.e-6)

Output_interval                       100        (by_default____10)

Initial_step                          1.0        (by_default____1.)

Q1_parameter                         0.95        (by_default__0.95)

Q2_parameter                         1.20        (by_default__1.20)

Alpha_parameter                      2.00        (by_default___2.0)

Penalty_parameter                 1000.00        (by_default_1000.)

 

Перечисленные параметры имеют следующий смысл:

·        Limit_of_iterations максимальное число итераций r-алгоритма;

·        Argument_accuracy критерий остановки  алгоритма по величине текущего шага в пространстве аргументов (переменных задачи) – остановка производится при уменьшении шага до указанной величины;

·        Gradient_accuracy критерий остановки алгоритма по величине нормы градиента целевой функции – остановка производится при уменьшении нормы до указанной величины;

·        Output_intervalчисло итераций алгоритма, после которого выводится на печать информация о состоянии процесса оптимизации – Iter (номер итерации), Obj (текущее значение целевой функции), Shift X (текущий шаг в пространстве аргументов), Fun calls (суммарное число вызовов процедуры вычисления значения функции и градиента);

·          Initial_stepначальный шаг алгоритма при приближенном поиске минимума по направлению спуска;

·          Q1_parameterуправляющий параметр алгоритма одномерного спуска по направлению, Q1_parameter≤1 (соответствует параметру g [1]);

·          Q2_parameterуправляющий параметр алгоритма одномерного спуска по направлению, Q2_parameter≥1 (соответствует параметру m [1]);

·        Alpha_parameter коэффициент растяжения пространства;

·        Penalty_parameter коэффициент штрафной функции при использовании метода негладких штрафов (при малых значениях параметра штрафная функция неограниченна снизу, при слишком больших значениях – замедленная сходимость, возможна остановка программы в неоптимальной точке).

В скобках указаны рекомендуемые значения для решения наиболее типовых задач.

По завершению работы программы выдается значение кода завершения:

 

Требования к программно-технической среде:

 

 

 

1. Шор Н. З., Журбенко Н. Г. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов // Кибернетика. – 1971. – № 3. – C. 51–59.