NLP-программы и r-алгоритм в задаче энтропийно-линейного программирования
Рассматривается задача энтропийно-линейного программирования в прямой и двойственной формулировках. Для обеих задач приводятся результаты вычислительных экспериментов с программами решения задач нелинейного программирования из NEOS-солвера. Обсуждаются вычислительные эксперименты для решения двойств...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2015 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/112401 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | NLP-программы и r-алгоритм в задаче энтропийно-линейного программирования / П.И. Стецюк, А.В. Гасников // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 73-78. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860022936565448704 |
|---|---|
| author | Стецюк, П.И. Гасников, А.В. |
| author_facet | Стецюк, П.И. Гасников, А.В. |
| citation_txt | NLP-программы и r-алгоритм в задаче энтропийно-линейного программирования / П.И. Стецюк, А.В. Гасников // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 73-78. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Рассматривается задача энтропийно-линейного программирования в прямой и двойственной формулировках. Для обеих задач приводятся результаты вычислительных экспериментов с программами решения задач нелинейного программирования из NEOS-солвера. Обсуждаются вычислительные эксперименты для решения двойственной задачи с помощью r-алгоритма Шора с адаптивным шагом.
Розглядається задача ентропійно-лінійного програмування у прямому та двоїстому формулюваннях. Для обох задач наведено результати обчислювальних експериментів з програмами розв'язання задач нелінійного програмування із NEOS-солвера. Обговорюються обчислювальні експерименти для розв'язання двоїстої задачі за допомогою r-алгоритма Шора з адаптивним кроком.
The maximum entropy linear programming problem in primal and dual formulations is considered. The results of computational experiments with the NEOS-solvers for nonlinear programming problems are reported for both formulations. The computational experiments with solving the dual problem using Shor's r-algorithm with an adaptive step are discussed.
|
| first_indexed | 2025-12-07T16:48:18Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2015 73
ТЕОРІЯ
ОПТИМАЛЬНИХ
РІШЕНЬ
Рассматривается задача энтро-
пийно-линейного программирова-
ния в прямой и двойственной фор-
мулировках. Для обеих задач при-
водятся результаты вычисли-
тельных экспериментов с про-
граммами решения задач нели-
нейного программирования из
NEOS-солвера. Обсуждаются вы-
числительные эксперименты для
решения двойственной задачи с
помощью r -алгоритма Шора
с адаптивным шагом.
П.И. Стецюк, А.В. Гасников,
2015
УДК 519.85
П.И. СТЕЦЮК, А.В. ГАСНИКОВ
NLP -ПРОГРАММЫ И r -АЛГОРИТМ
В ЗАДАЧЕ ЭНТРОПИЙНО-ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ
Введение. Одномерная нелинейная функция
( ) lnf x x x cx является вогнутой при
0.x Она достигает своего максимума в
единственной точке * exp 1x c , такой,
что * 0x при любом значении параметра .c
Этот факт позволяет эффективно учитывать
требование на неотрицательность перемен-
ных в задачах энтропийно-линейного про-
граммирования (ЭЛП-задачи), которые име-
ют многочисленные приложения [1]. В этих
задачах максимизируемая целевая функция –
это сепарабельная вогнутая функция, по-
строенная как сумма функций вида ( ),f x а
ограничения заданы так, как в задаче линей-
ного программирования.
Наша цель показать, что указанные осо-
бенности ЭЛП-задач позволяют разрабаты-
вать эффективные алгоритмы для решения
ЭЛП-задач большой размерности. Сделаем
это с помощью численных экспериментов
для современных программ решения задач
нелинейного программирования (NLP-
программ) и r -алгоритма Шора.
Последовательность изложения материала
статьи следующая. В разделе 1 для простей-
шей ЭЛП-задачи приведены формулировки
прямой и двойственной задач и описаны не-
которые их свойства. В разделе 2 даны ре-
зультаты решения прямой и двойственной
задач небольших размеров с помощью
NLP-программ из NEOS-cолвера. В разделе 3
приведены результаты решения двойствен-
ной ЭЛП-задачи больших размеров с помо-
щью r -алгоритма с адаптивным шагом.
П.И. СТЕЦЮК, А.В. ГАСНИКОВ
74 Теорія оптимальних рішень. 2015
1. Прямая и двойственная ЭЛП-задачи. Пусть заданы вектор
1
,
n
i i
c c
матрица
,
, 1
n m
ij i j
A a
и вектор
1
,
m
j j
b b
а неизвестными являются неотрица-
тельные компоненты вектора
1
n
i i
x x
. Задача энтропийно-линейного про-
граммирования в простейшей постановке имеет такой вид:
* *
0
1 1
( ) max ( ) ln
n n
i i i i
x
i i
f f x f x x x c x
(1)
при ограничениях
1
, 1,...,
n
ij i j
i
a x b j m
. (2)
Задачу (1) – (2) условимся называть прямой ЭЛП-задачей c n переменными
и m ограничениями (ограничения на неотрицательность переменных учитывать
не будем). Будем предполагать, что система ограничений Ax b имеет допус-
тимые точки
1
0
n
i i
x x
, т. е. задача (1) – (2) имеет единственное оптималь-
ное решение * *
1
0
n
i i
x x
, все компоненты которого положительны.
Если
1
m
j j
u u
– неизвестные множители Лагранжа, соответствующие
ограничениям (2), то двойственная ЭЛП-задача имеет следующий вид:
* *
1 1 1
( ) min ( ) exp 1 .
n
m n m
i i i ij j
u R
j i j
u u b u c a u
(3)
Она является задачей безусловной минимизации гладкой выпуклой функции
( )u от m переменных. Из теории двойственности следует, что * *.f Если
известны * *
1
m
j j
u u
– оптимальные значения множителей Лагранжа для задачи
(3), то оптимальные значения переменных в задаче (1) – (2) вычисляются по
формуле * *exp ,Tx c A u e где e – вектор, состоящий из n единиц.
Главная особенность ЭЛП-задач – это выполнение условия n m . Поэтому
быстрое решение задачи (1) – (2) кроется в эффективном решении задачи (3),
количество переменных в которой намного меньше, чем количество перемен-
ных в прямой ЭЛП-задаче. Так, если в прямой ЭЛП-задаче количество перемен-
ных n будет порядка сотен тысяч, а количество ограничений m – порядка не-
скольких тысяч, то решение задачи (3) можно осуществить с помощью стан-
дартных NLP-программ. Однако, более эффективными будут специальные двой-
ственные алгоритмы, которые учитывают специфику прямой и двойственной
ЭЛП-задач. Двойственный алгоритм будет определяться выбранным градиент-
ным алгоритмом для минимизации гладкой функции ( ).u Изложенное под-
твердим далее, где задачу (3) будем решать с помощью r -алгоритма.
NLP-ПРОГРАММЫ И r -АЛГОРИТМ В ЗАДАЧЕ ЭНТРОПИЙНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Теорія оптимальних рішень. 2015 75
2. NLP-программы из NEOS-солвера. Как задача (1) – (2), так и задача (3)
являются задачами нелинейного программирования, для решения которых су-
ществуют эффективные NLP-программы. Их можно использовать через
NEOS-солвер [2], который является частью системы NEOS (Network-Enhanced
Optimization System), содержащей библиотеку оптимизационного про-
граммного обеспечения, оптимизационный сервер (http://www-neos.mcs.anl.gov/)
для использования этой библиотеки в сети Интернет, а также необходимую ин-
формацию о программном обеспечении. NLP-программы находятся в секции
«Nonlinearly Constrained Optimization» NEOS-солвера. Девять из них поддержи-
вают работу с описанием задач нелинейного программирования на языке моде-
лирования AMPL [3]. Это известные программы: CONOPT 3.15C, filter,
Ipopt 3.10.3, KNITRO 9.0.0, LANCELOT, LOQO 7.00, MINOS 5.51, MOSEK
и SNOPT 7.2-10.
Для этих программ проведен вычислительный эксперимент, который состо-
ял в одновременном решении десяти прямых и десяти двойственных
ЭЛП-задач при 4000n и 400.m Данные для ЭЛП-задачи генерировались с
помощью AMPL-го датчика Uniform(0,1), который обеспечивает равномерное
распределение случайных чисел на (0,1). Компоненты вектора c выбирались
равными 10 1,i 1,..., ,i n а компоненты матрицы A – равными 5 ,ij
1,..., ,i n 1,..., .j m Вектор b вычислялся по формуле
0,b Ax где компонен-
ты вектора
0x выбирались равными 3 1,i 1,..., .i n
Успешно решили все задачи те пять программ, для которых в табл. 1 приве-
дены pt и
dt – времена (в секундах), затраченные на решение прямой и двойст-
венной ЭЛП-задач. В последней строке даны средние времена для десяти задач.
Четыре программы не справились с решением всех задач. Программа LOQO
не смогла вычислить значения функции и ограничений в начальной точке, а
программы filter, LANCELOT и SNOPT были сняты системой из-за превышения
максимально допустимого времени. При этом filter и SNOPT не решили ни
одной задачи, а LANCELOT успела решить четыре задачи из десяти, затратив на
решение прямых задач 3607, 6759, 6942 и 6790 секунд, а на решение двойствен-
ных задач 85, 86, 34 и 77 секунд соответственно.
Из табл. 1 видим, что наилучшими по времени оказались программы
KNITRO и Ipopt. С их помощью решались ЭЛП-задачи, размеры которых были
увеличены. Если 10000n и 600,m то средние времена для KNITRO оказа-
лись такими: 222.7pt и 91.5.dt Из-за нехватки оперативной памяти про-
грамма Ipopt не решила прямые задачи, а среднее время решения двойственных
задач для нее составило 85.2.dt Если 40000n и 600,m то ни одной из
программ не хватило памяти для решения прямых задач, а среднее время реше-
ния двойственных задач составило 283.7dt для программы KNITRO и
324.6dt для программы Ipopt.
http://www-neos.mcs.anl.gov/
П.И. СТЕЦЮК, А.В. ГАСНИКОВ
76 Теорія оптимальних рішень. 2015
ТАБЛИЦА 1. Результаты для NLP-программ из NEOS-солвера (22.01.2015)
3. r -алгоритм Шора [4]. Для того, чтобы оценить время решения задачи
(2) с помощью r -алгоритма, была реализована программа delp на МАТЛАБ-
подобном некоммерческом языке GNU Octave. В ее основу положен код octave-
программы ralgb5 [5, стр. 384 – 385], для которой значения функции ( )u и ее
градиента ( )g u
вычислялись по такому правилу:
( ) exp , ( ) ( ), ( ) ( ),T T Tx u c A u e u b u e x u g u b Ax u (4)
где e – вектор, состоящий из n единиц. Программа ralgb5 реализует ( )r -алго-
ритм с постоянным коэффициентом растяжения пространства и адаптивным
шагом, который настраивается с помощью параметров
0h ,
1q ,
2q и
hn .
Вычисления проводились на компьютере Pentium 3GHz в системе
Windows7/32 с использованием GNU Octave версии 3.6.4. Тестовые ЭЛП-задачи
были такими же, как и для NLP-программ, но случайные числа с равно-
мерным распределением на (0,1) генерировались октавовским датчиком
rand("seed", 2015). Программа delp показала очень незначительные затраты по
времени (см. табл. 2) для ЭЛП-задач, имеющих размеры, близкие к исполь-
зуемым выше.
В табл. 2 дано время (в секундах)
1 7,...,t t для решения серии из семи
ЭЛП-задач одного размера, в последнем столбце приведено среднее время
решения задач этой серии. Для расчетов параметры r -алгоритма выбирались
такими: = 2,
0 =1.0,h
1 = 0.95,q
2 1.1q и 3.hn Программа останавливалась,
если для точки
ru выполнялось условие
* 710 ,ru u где – эвклидова
норма. Это гарантировало, что норма относительных невязок для ограничений в
форме равенств (2) не превышала 8 710 10 .
№
CONOPT Ipopt KNITRO MINOS MOSEK
pt
dt pt
dt pt
dt pt
dt pt
dt
1 290.2 20.3 45.6 22.9 6.1 22.1 1580.5 290.2 35.1 114.8
2 292.9 13.3 48.0 14.5 8.5 18.5 1732.2 252.0 36.1 153.4
3 301.6 14.7 45.8 14.3 8.7 13.4 1556.5 299.9 50.6 136.8
4 276.9 17.6 48.2 14.3 8.7 13.4 1583.3 289.6 39.4 114.0
5 234.2 16.0 47.7 14.3 8.6 13.4 1483.5 281.5 38.2 119.1
6 204.1 13.3 48.0 14.5 8.3 13.4 1418.7 254.9 29.9 142.2
7 275.3 13.9 47.7 14.3 14.0 15.8 1554.0 257.2 35.3 130.7
8 206.8 13.1 47.8 14.3 9.1 21.5 1545.9 265.8 28.3 132.7
9 242.8 16.2 47.9 14.5 20.1 15.8 1447.0 252.6 38.4 137.5
10 274.6 18.7 47.9 14.3 9.7 21.9 1505.1 305.3 25.5 143.4
t 259.9 15.7 47.5 15.2 10.2 16.9 1540.7 274.9 35.7 132.4
NLP-ПРОГРАММЫ И r -АЛГОРИТМ В ЗАДАЧЕ ЭНТРОПИЙНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Теорія оптимальних рішень. 2015 77
ТАБЛИЦА 2. Времена работы программы delp для небольших ЭЛП-задач
№ n m
1t
2t
3t
4t
5t
6t
7t t
1 4000 400 1.27 1.25 1.23 1.23 1.23 1.22 1.25 1.24
2 10000 400 2.14 2.09 2.10 2.10 2.13 2.12 2.11 2.11
3 40000 400 9.82 9.92 9.92 10.02 9.77 9.79 9.75 9.86
4 4000 600 2.20 2.19 2.20 2.20 2.20 2.23 2.20 2.20
5 10000 600 3.47 3.50 3.45 3.45 3.43 3.48 3.50 3.47
6 40000 600 11.54 10.98 11.25 11.63 11.36 11.42 11.59 11.40
7 4000 800 3.58 3.58 3.58 3.59 3.57 3.57 3.57 3.58
8 10000 800 5.16 5.16 5.18 5.16 5.19 5.17 5.17 5.17
9 40000 800 12.85 13.13 13.00 13.01 13.01 12.97 13.02 13.00
Скорость работы программы delp во многом зависит от настройки трех па-
раметров ( )r -алгоритма: ,
0h и
1q . Их надо выбирать с учетом того, что ми-
нимизируется гладкая выпуклая функция, т. е при заданном [2, 4] эффек-
тивную работу будет обеспечивать такое значение параметра
1 1q (уменьша-
ющее величину шага на итерации), при котором точность спуска по направле-
нию увеличивается по ходу итераций. Это означает, что на одну итерацию ( )r -
алгоритма должно приходиться в среднем около 1.2 1.5 вычислений значений
функции и градиента. Для задач из табл. 2 такой настройки не требовалось, так
как улучшать время решения на несколько секунд особого смысла не имеет.
Однако, если размеры ЭЛП-задачи большие, то согласованная настройка
параметров и
1q позволяет добиться значительного эффекта. Насколько за
счет этого для нашего тестового примера можно ускорить программу delp легко
видеть из табл. 3, где приведены результаты расчета для трех ЭЛП-задач боль-
ших размеров. Их размеры выбирались такими, чтобы количество элементов в
матрице ограничений равнялось 40.000.000. В таблице дано количество итера-
ций (itn) и количество вычислений функции (nfg) в зависимости от параметра
1 0.9,0.95,0.99,1.0 .q Все остальные параметры в расчетах были такими же,
как при решении небольших задач. В табл. 3 приведено также и время решения
задач (в секундах). Минимальные из них получены при 2 и
1 0.9q и соста-
вляют для первой задачи 33 секунды, для второй – 15 секунд, а для третьей – 55
секунд. При
1 1.0q для двух задач было превышено максимальное количество
итераций (maxitn = 5000).
П.И. СТЕЦЮК, А.В. ГАСНИКОВ
78 Теорія оптимальних рішень. 2015
ТАБЛИЦА 3. Работа программы delp для больших задач при разных
1q
№ n m
1q Itn Nfg t
1q Itn nfg t
1 1000000 40 0.90 185 249 33 0.95 313 411 54
0.99 614 774 103 1.00 898 1135 150
2 100000 400 0.90 230 313 15 0.95 537 760 38
0.99 1828 2380 118 1.00 5000 6007 299
3 10000 4000 0.90 247 343 55 0.95 314 320 65
0.99 1567 1572 326 1.00 5000 5003 1040
Заключение. Приведенные вычислительные эксперименты для r -алгоритма
Шора с адаптивной регулировкой шага подтверждают, что для решения задач эн-
тропийно-линейного программирования больших размеров целесообразно разраба-
тывать «быстрые» специализированные алгоритмы. Для задач небольших размеров
они будут эффективнее, чем современные оптимизационные программы общего
назначения. Если количество переменных будет порядка сотен тысяч, а количество
ограничений – порядка нескольких тысяч, то решение ЭЛП-задач можно получить
за несколько минут на современных персональных компьютерах. Если матрица
ограничений разрежена либо имеет блочную структуру, то учет специфики матрицы
только усилит выигрыш по времени для специализированных алгоритмов.
Работа выполнена при поддержке НАНУ (проект № 0114U001055) и РФФИ
(гранты 13-01-12007-офи_м, 14-01-00722-а).
П.І. Стецюк, О.В. Гасніков
NLP-ПРОГРАМИ ТА r -АЛГОРИТМ У ЗАДАЧІ ЕНТРОПІЙНО-ЛІНІЙНОГО ПРОГРАМУВАННЯ
Розглядається задача ентропійно-лінійного програмування у прямому та двоїстому формулю-
ваннях. Для обох задач наведено результати обчислювальних експериментів з програмами
розв'язання задач нелінійного програмування із NEOS-солвера. Обговорюються обчислю-
вальні експерименти для розв'язання двоїстої задачі за допомогою r -алгоритма Шора з адап-
тивним кроком.
P.І. Stetsyuk, A.V. Gasnikov
NLP-PROGRAMS AND r -ALGORITHM FOR ENTROPY LINEAR PROGRAMMING PROBLEM
The maximum entropy linear programming problem in primal and dual formulations is considered.
The results of computational experiments with the NEOS-solvers for nonlinear programming prob-
lems are reported for both formulations. The computational experiments with solving the dual prob-
lem using Shor's r-algorithm with an adaptive step are discussed.
1. Fang S.-C., Rajasekera J.R., Tsao H.-S.J. Entropy optimization and mathematical prog-
ramming. – Kluwer’s International Series, 1997. – 343 p.
2. NEOS Solver [Электронный ресурс]:
http://www.neos-server.org/neos/solvers/ – Режим доступа: свободный.
3. Fourer R., Gay D., Kernighan B. AMPL: A Modeling Language for Mathematical Prog-
ramming. – Belmont: Duxburry Press, 2003. – 517 p.
4. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. –
Киев: Наук. думка, 1979. – 200 с.
5. Стецюк П.И. Методы эллипсоидов и r -алгоритмы. – Кишинэу: Эврика, 2014. – 488 с.
Получено 02.02.2015
http://www.neos-server.org/neos/solvers/
|
| id | nasplib_isofts_kiev_ua-123456789-112401 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T16:48:18Z |
| publishDate | 2015 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стецюк, П.И. Гасников, А.В. 2017-01-20T21:33:30Z 2017-01-20T21:33:30Z 2015 NLP-программы и r-алгоритм в задаче энтропийно-линейного программирования / П.И. Стецюк, А.В. Гасников // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 73-78. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/112401 519.85 Рассматривается задача энтропийно-линейного программирования в прямой и двойственной формулировках. Для обеих задач приводятся результаты вычислительных экспериментов с программами решения задач нелинейного программирования из NEOS-солвера. Обсуждаются вычислительные эксперименты для решения двойственной задачи с помощью r-алгоритма Шора с адаптивным шагом. Розглядається задача ентропійно-лінійного програмування у прямому та двоїстому формулюваннях. Для обох задач наведено результати обчислювальних експериментів з програмами розв'язання задач нелінійного програмування із NEOS-солвера. Обговорюються обчислювальні експерименти для розв'язання двоїстої задачі за допомогою r-алгоритма Шора з адаптивним кроком. The maximum entropy linear programming problem in primal and dual formulations is considered. The results of computational experiments with the NEOS-solvers for nonlinear programming problems are reported for both formulations. The computational experiments with solving the dual problem using Shor's r-algorithm with an adaptive step are discussed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень NLP-программы и r-алгоритм в задаче энтропийно-линейного программирования NLP-програми та r-алгоритм у задачі ентропійно-лінійного програмування NLP-programs and r-algorithm for entropy linear programming problem Article published earlier |
| spellingShingle | NLP-программы и r-алгоритм в задаче энтропийно-линейного программирования Стецюк, П.И. Гасников, А.В. |
| title | NLP-программы и r-алгоритм в задаче энтропийно-линейного программирования |
| title_alt | NLP-програми та r-алгоритм у задачі ентропійно-лінійного програмування NLP-programs and r-algorithm for entropy linear programming problem |
| title_full | NLP-программы и r-алгоритм в задаче энтропийно-линейного программирования |
| title_fullStr | NLP-программы и r-алгоритм в задаче энтропийно-линейного программирования |
| title_full_unstemmed | NLP-программы и r-алгоритм в задаче энтропийно-линейного программирования |
| title_short | NLP-программы и r-алгоритм в задаче энтропийно-линейного программирования |
| title_sort | nlp-программы и r-алгоритм в задаче энтропийно-линейного программирования |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/112401 |
| work_keys_str_mv | AT stecûkpi nlpprogrammyiralgoritmvzadačeéntropiinolineinogoprogrammirovaniâ AT gasnikovav nlpprogrammyiralgoritmvzadačeéntropiinolineinogoprogrammirovaniâ AT stecûkpi nlpprogramitaralgoritmuzadačíentropíinolíníinogoprogramuvannâ AT gasnikovav nlpprogramitaralgoritmuzadačíentropíinolíníinogoprogramuvannâ AT stecûkpi nlpprogramsandralgorithmforentropylinearprogrammingproblem AT gasnikovav nlpprogramsandralgorithmforentropylinearprogrammingproblem |