Вычислительные эксперименты по применению R-алгоритмов для решения одного класса задач нелинейного программирования
The paper investigates the efficiency of r-algorithms used to mathematical programs with equilibrium constraints. The comparative computational results for SNOPT, LOQO, Ralg solvers with AMPL package on test problems from MacMPEC library are given.
Збережено в:
| Дата: | 2006 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Назва видання: | Теорія оптимальних рішень |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84962 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Вычислительные эксперименты по применению R-алгоритмов для решения одного класса задач нелинейного программирования / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 116-121. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84962 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-849622015-07-18T03:02:01Z Вычислительные эксперименты по применению R-алгоритмов для решения одного класса задач нелинейного программирования Лиховид, А.П. The paper investigates the efficiency of r-algorithms used to mathematical programs with equilibrium constraints. The comparative computational results for SNOPT, LOQO, Ralg solvers with AMPL package on test problems from MacMPEC library are given. 2006 Article Вычислительные эксперименты по применению R-алгоритмов для решения одного класса задач нелинейного программирования / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 116-121. — Бібліогр.: 8 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84962 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
The paper investigates the efficiency of r-algorithms used to mathematical programs with equilibrium constraints. The comparative computational results for SNOPT, LOQO, Ralg solvers with AMPL package on test problems from MacMPEC library are given. |
| format |
Article |
| author |
Лиховид, А.П. |
| spellingShingle |
Лиховид, А.П. Вычислительные эксперименты по применению R-алгоритмов для решения одного класса задач нелинейного программирования Теорія оптимальних рішень |
| author_facet |
Лиховид, А.П. |
| author_sort |
Лиховид, А.П. |
| title |
Вычислительные эксперименты по применению R-алгоритмов для решения одного класса задач нелинейного программирования |
| title_short |
Вычислительные эксперименты по применению R-алгоритмов для решения одного класса задач нелинейного программирования |
| title_full |
Вычислительные эксперименты по применению R-алгоритмов для решения одного класса задач нелинейного программирования |
| title_fullStr |
Вычислительные эксперименты по применению R-алгоритмов для решения одного класса задач нелинейного программирования |
| title_full_unstemmed |
Вычислительные эксперименты по применению R-алгоритмов для решения одного класса задач нелинейного программирования |
| title_sort |
вычислительные эксперименты по применению r-алгоритмов для решения одного класса задач нелинейного программирования |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2006 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84962 |
| citation_txt |
Вычислительные эксперименты по применению R-алгоритмов для решения одного класса задач нелинейного программирования / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 116-121. — Бібліогр.: 8 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT lihovidap vyčislitelʹnyeéksperimentypoprimeneniûralgoritmovdlârešeniâodnogoklassazadačnelinejnogoprogrammirovaniâ |
| first_indexed |
2025-07-06T12:05:05Z |
| last_indexed |
2025-07-06T12:05:05Z |
| _version_ |
1836899113063415808 |
| fulltext |
116 Теорія оптимальних рішень. 2006, № 5
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Приведены результаты сравни-
тельных вычислительных экспе-
риментов по применению r-
алгоритмов для нахождения ло-
кальных решений задач с равно-
весными ограничениями (MPEC) с
использованием тестовой биб-
лиотеки MacMPEC.
А.П. Лиховид, 2006
ÓÄÊ 519.8
À.Ï. ËÈÕÎÂÈÄ
ÂÛ×ÈÑËÈÒÅËÜÍÛÅ ÝÊÑÏÅÐÈÌÅÍÒÛ
ÏÎ ÏÐÈÌÅÍÅÍÈÞ R-ÀËÃÎÐÈÒÌÎÂ
ÄËß ÐÅØÅÍÈß ÎÄÍÎÃÎ ÊËÀÑÑÀ
ÇÀÄÀ× ÍÅËÈÍÅÉÍÎÃÎ
ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß
Введение. В настоящее время опубликовано
много работ по нахождению локальных ре-
шению задач с равновесными ограничениями
(mathematical programs with equilibrium
constraints – MPEC), в которых они
рассматриваются как задачи невыпуклого
нелинейного программирования, а для нахо-
ждения локальных решений используются
современные пакеты нелинейного програм-
мирования [1–2]. Показывается, что этот
подход – перспективный, несмотря на
вычислительные трудности, определяемые
сложностью данного класса задач. С этой
точки зрения вызывает интерес проведение
сравнительного анализа эффективности на-
хождение локальных решений этого класса
задач различными известными алгоритмами
нелинейной оптимизации, в том числе и
r-алгоритмом.
Постановка задачи. Рассмотрим поста-
новку задач математического программиро-
вания с равновесными ограничениями
(MPEC) в следующем виде [2]:
( ) minf x →
0 ( ) 0,g x x≤ ⊥ ≥ (1)
где n
x ∈� , : n n
g →� � , а обозначение
0 ( ) 0g x x≤ ⊥ ≥ – краткая запись для
( ) 0T
x g x = .
Задачу (1) можно рассматривать как зада-
чу невыпуклого нелинейного программиро-
вания, например, в следующем виде:
ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ ПО ПРИМЕНЕНИЮ R-АЛГОРИТМОВ …
Теорія оптимальних рішень. 2006, № 5 117
( ) minf x →
( ) 0, 0,g x x≥ ≥
( ) 0, .j jg x x j j≤ ∀ ∈ (2)
Попытаемся применить для нахождения ее локальных минимумов существую-
щие алгоритмы нелинейного программирования. В этой работе будет рассмот-
рен подход к решению задач вида (2) с использованием метода точных штрафов,
а для решения получившейся задачи недифференцируемой оптимизации пред-
лагаетя использовать r-алгоримы [3]. Приведены сравнительные результаты
численных экспериментов для одной реализации r-алгоритма и современных
программ нелинейной оптимизации LOQO [4] и SNOPT [5] на известном наборе
тестовых задач MacMPEC [6].
Метод решения. Рассмотрим задачу (2). Следуя методу точных штрафных
функций [3], заменим исходную задачу следующей задачей безусловной опти-
мизации:
min ( ) max{0, ( ), , ( ) }j jf x g x x g x x+ ρ − − . (3)
Здесь 0ρ > – штрафной множитель. Теория метода точных штрафных
функций гарантирует, что при достаточно большом значении штрафного мно-
жителя решение задачи (3) эквивалентно решению задачи (2), т.е. каждое реше-
ние задачи (2) будет и решением задачи (3). Задача (3) – задача недифференци-
руемой оптимизации. Для ее решения можно использовать алгоритмы оптими-
зации субградиентного типа, например r-алгоритмы. Детальное описание при-
меняемого r-алгоритма приведено в [3]. Далее будут представлены результаты
численных экспериментов и оценки эффективности применения r-алгоритма для
тестового набора задач.
Численные экперименты. Для выполнения численных экспериментов раз-
работана программа на языке программирования C++, реализующая r-алгоритм
с адаптивной регулировкой шага. Данная программа, которую обозначим как
Ralg, была подключена к интерфейсу известной системы моделирования опти-
мизационных задач AMPL [7]. При этом задачи условной оптимизации
автоматически приводятся к виду (3). Преимущества такого подхода состоят в
следующем:
к системе AMPL подключены почти все известные оптимизационные про-
граммы, что позволяет легко проводить сравнительные эксперименты;
на языке моделирования этой системы реализованы многие известные набо-
ры тестовых задач, предлагаемые на различных сайтах сети Интернет, что по-
зволяет провести численные расчеты на большом количестве различных задач;
средства системы моделирования позволяют автоматизировать вычисления
значений функций и производных.
Характеристики компьютера, на котором проводились исследования:
компьютер IBM PC Pentium;
процессор CPU Pentium 750MHz;
А.П. ЛИХОВИД
118 Теорія оптимальних рішень. 2006, № 5
оперативная память 256MB;
операционная система Windows 2000.
Для проведения численных экспериментов была выбрана известная библио-
тека тестовых задач MacMPEC. Все задачи в этой библиотеке написаны на язы-
ке моделирования AMPL и доступны на сайте [6].
Для сравнительного анализа, вместе с r-алгоритмом, были выбраны извест-
ные программы LOQO и SNOPT, одни из лучших для решения задач нелиней-
ной оптимизации. LOQO – одна из реализаций метода внутренних точек, а
SNOPT – одна из реализаций квазиньютоновских методов. Все они подключены
к интерфейсу системы моделирования AMPL. Использовались стандартные
значения управляющих параметров для этих программ. Для r-алгоритма стан-
дартные значения параметров для решения тестовых задач были выбраны сле-
дующими: 2=α – коэффициент растяжения пространства; 8
1 10k kx x
−
+ − ≤ –
точность при завершении по аргументу ( k – номер итерации); 1h = – величина
начального шага; значения параметров 1q , 2q равнялись соответственно
1.1 и 0.95.
Для проведения вычислительных экспериментов из библиотеки MacMPEC
была взята 61 тестовая задача. Максимальное число переменных – 278, а мак-
симальное количество ограничений – 250. О размерности тестовых задач можно
судить по данным табл. 1, где приведено распределение размерностей задач по
заданным интервалам.
Важная характеристика – количество отказов, т.е. когда программа оста-
навливается точке или по превышению заданного количества итераций, или из-
за невозможности дальнейшего продолжения вычислений вследствие возник-
ших численных затруднений. В табл. 2 приведено количество отказов для трех
программ на исследуемом наборе тестовых задач.
ТАБЛИЦА 1
Интервал Распределение
задач по коли-
честву пере-
менных
Распределение
задач по коли-
честву ограни-
чений
1 – 20 45 47
21 – 40 7 7
41 – 60 2 0
61 – 120 2 2
121 – 160 1 1
161 – 180 1 2
181 – 220 2 1
221 – 280 1 1
ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ ПО ПРИМЕНЕНИЮ R-АЛГОРИТМОВ …
Теорія оптимальних рішень. 2006, № 5 119
Из табл. 2 видно, что программа Ralg
только в одном случае выдала сообщение об
отказе, а наибольшее количество отказов
оказалось у программы LOQO.
Далее представлено сравнение эффектив-
ности трех программ, использующее подход,
описанный в [8]. Для сравнения
использовалось время центрального процессо-
ра, требуемое для решения тестовых задач. Предположим, что мы сравниваем
эффективность sn программ на наборе из pn тестовых задач. Пусть ,p st – вре-
мя решения задачи p программой s . Тогда вычислим следующие величины:
,
,
,
, ( , ).
min{ :1 }
p s
p s
p s s
t
p s
t s n
ρ = ∀
≤ ≤
(4)
Если программа s выдала отказ для задачи p , тогда ,p sρ = ∞ .
Для каждой программы s строится график функции
( ) ,
p
s
p
m
n
φ τ = (5)
где pm (1 p pm n≤ ≤ ) – количество тестовых задач, удовлетворяющих ,p sρ ≤ τ .
Функция ( ) : [0,1]sφ τ →� представляет собой функцию распределения для
величин (4) и служит как для оценки эффективности, так и надежности решеня
тестовых задач программой s .
На рисунке показаны графики функций (5) для программ SNOPT, LOQO и
Ralg, из которых видно, что наилучший результат показала программа SNOPT, а
результаты программ LOQO и Ralg близки, при этом Ralg, немного уступая
LOQO по быстродействию, имеет намного меньшее количество отказов.
Необходимо отметить, что все три программы для большинства тестовых
задач нашли решения, совпадающие с представленными на сайте [6]. Для не-
скольких задач найдены допустимые точки, имеющие лучшие значения целевой
функции, чем представленные на этом сайте. Более того, было найдено допус-
тимое решение для задачи, объявленной на сайте как не имеющей допустимых
решений.
ТАБЛИЦА 2
Программа Количество
отказов
SNOPT 3
LOQO 12
Ralg 1
А.П. ЛИХОВИД
120 Теорія оптимальних рішень. 2006, № 5
0
0,2
0,4
0,6
0,8
1
1,2
1 2 3
Ralg
snopt
LOQO
РИСУНОК. Графики функций (5) для программ SNOPT, LOQO и Ralg
Заключение. Из результатов вычислительных экспериментов можно
сделать вывод, что лучшую производительность показала програма SNOPT, а
программа Ralg, использующая метод точных штрафных функций и r-алгоритм,
несколько уступая на данном тестовом наборе по быстродействию программе
SNOPT, сравнима с ней по надежности нахождения решений и вполне работо-
способна для нахождения локальных минимумов для задач данного класса
средней размерности.
О.П. Лиховид
ОБЧИСЛЮВАЛЬНІ ЕКСПЕРИМЕНТИ ПО ВИКОРИСТАННЮ R-АЛГОРИТМІВ ДЛЯ
РІШЕННЯ ОДНОГО КЛАСУ ЗАДАЧ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ
Розглядається дослідження ефективності використання r-алгоритмів для рішення задач нелі-
нійного програмування з рівноважними обмеженнями. Наведені результати порівняльних
обчислювальних експериментів з використанням пакета AMPL та задач з бібліотеки MacPEC
для програм SNOPT, LOQO та Ralg.
O.P. Lykhovyd
ON COMPUTATIONAL EXPERIMENTS WITH R-ALGORITHM TO SOLVE ONE CLASS OF
NONLINEAR PROGRAMMING PROBLEMS
The paper investigates the efficiency of r-algorithms used to mathematical programs with equili-
brium constraints. The comparative computational results for SNOPT, LOQO, Ralg solvers with
AMPL package on test problems from MacMPEC library are given.
ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ ПО ПРИМЕНЕНИЮ R-АЛГОРИТМОВ …
Теорія оптимальних рішень. 2006, № 5 121
1. Fletcher R., Leyffer S. Numerical experience with solving MPECs as NLP. University of
Dundee Technical Report NA-210, August 2002.
2. Benson H.Y., Shanno D.F., Vanderbei R.J. Interior-point methods for nonconvex nonlinear
programming: complementarity constraints. Princeton University, 2002.
3. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – Boston Dordrecht.
– London: Kluwer Academic Publishers, 1998. – 412 p.
4. Vanderbei R.J. LOQO: An interior point code for quadratic programming // Technical Re-
port SOR-94-15, School of Engineering and Applied Science, Department of Civil Engi-
neering and Operations Research, Princeton University. – 1994.
5. Gill P.E., Murray W, and Saunders M.A. SNOPT: An SQP algorithm for large-scale
constrained optimization. SIAM J. on Optimization 12 (2002), 979-1006.
6. Leyffer S. MacMPEC Test Suite. www.maths.dandee.ac.uk/~sleyffer/MacMPEC/.
7. Fourer R., Gay D., Kernighan B. AMPL: A Modeling Language for Mathematical Pro-
gramming. Duxbury Press-Brooks-Cole Publishing Company. – 1993. – 351 p.
8. Dolan E.D., More J.J. Benchmarking optimization software with performance profiles.
Math. Programming, 91:201-214, 2002.
Получено 05.06.2006
|