Об одной реализации r-алгоритма

Рассматривается одна реализация известного r-алгоритма с подключением к системе моделирования AMPL Приводятся результаты сравнительных численных экспериментов на известных тестовых задачах с входящими в состав системы оптимизационными программами. Розглядається одна реалізація відомого r-алгоритму з...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Теорія оптимальних рішень
Datum:2011
1. Verfasser: Лиховид, А.П.
Format: Artikel
Sprache:Russisch
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/46778
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Об одной реализации r-алгоритма / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 91-95. — Бібліогр.: 8 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1860245599615451136
author Лиховид, А.П.
author_facet Лиховид, А.П.
citation_txt Об одной реализации r-алгоритма / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 91-95. — Бібліогр.: 8 назв. — рос.
collection DSpace DC
container_title Теорія оптимальних рішень
description Рассматривается одна реализация известного r-алгоритма с подключением к системе моделирования AMPL Приводятся результаты сравнительных численных экспериментов на известных тестовых задачах с входящими в состав системы оптимизационными программами. Розглядається одна реалізація відомого r-алгоритму з підключенням до системи моделювання AMPL. Наводяться результати порівняльних чисельних експериментів на відомих тестових задачах з оптимізаційними програмами, що входять до складу системи. A realization of well-known r-algorithm with interface to AMPL modeling system is considered. The results of comparative numerical experiments on known test problems with optimization software implemented to the system are given.
first_indexed 2025-12-07T18:36:18Z
format Article
fulltext ������ ��� �� � � ����� . 2011, � 10 91 ������ ���� �� �� ���� � ���� ��� ������ ���� ���� ��- � � ��������� r-����� � � c ��������� � � � ��� � ���� - ����� � AMPL. �� ������� ��- ��� ���� ����� ��� ��� � ����- ��� ������ ����� �� �������� �������� ������� � ����� � ������ � ��� � ��� ��� ��- �� ������ � .  �.�. �������, 2011 ��������� ����������� ����������� �� �� �� ������ ��������. �� ����� ����� ������� ���- ���� �� � �� �������� ��� ��� ��������- �� �� �� �������� �� ����� AMPL [1], �� ���� � ��� � � ��� �� ��� ����� �� � �� ����� � ����� � �� � � ����� � ���� �� �� �� ��� � ��� ���� ������� �� (��. NEOS-������ [2]). ��� ��� �� ��� �� ��- ��� �� �����!�� �� � � ������� ��� ��� ���������� �� AMPL ����� ��!��� � �- ��� ��"��� ��� �� ��������. ��������� - �� ���"� ������� ��� �� � �����!���: � ��� ��� AMPL �����!�� � #�� �� � - �� ����� �� �� �������� �� ���"����, � � �������� ��"�� ������� ���� � �� - �� ��������� �; � ����� ���������� �� � �� ��� ��� ��������� � ����� �� �#��� �� ���� ��- ���, ������"����� � ������ �� ��� �� �� � � �� � , � � �������� ����� ���� �� ��� �� ����� �� ��"��� ���; ����� �� ��� ��� ���������� �� �����- ��! �� ��� ������� ������� �� � ��� �� �� ���� � �������� ��. � �� ��#� � ������ ����� �� ���������� ����� �"� r-��"��� �� [3] c �����!�� ��� � ����� AMPL, ������� �� ����� � � ���� �- �� �� ����� �� ��������� �� � ��- ��� �� �� ���� ������� � ��������� � ��� �� ��� ��� �� �������� ��� ���- "�������. �� ��� � �� ��� �� ��������� ����� r- ����� � . �������� ����� �����! � �� �� ���������� ����� r -��"��� �� ��� �� �������� �������� �� ���� ( )f x , �������� �� � nE . �.�. ��$% �& 92 ������ ��� �� � � ����� . 2011, �10 �#����� ���� �� ���#��'� �� 0 nx E∈ . ����'�� 0 nB I= – ���"� �� �� ��� �� �� �� ���� n n× . ������ ��" ��"��� �� ���������� �� ������� 1 0 0 0=x x h− η , "�� 0 0 0 0= ( )T fB B g xη , 0h – ���� �� � ��� �� ��"���"� � �'� ���. ��� � ����� � � ������� �� ����� k ( = 1, 2,...k ) ��"�� �������� ������ � �������� �� � ��� �� n kx E∈ � �� ���� kB �������� n n× . %����� ( 1)k + -� ��" ��������. 1. �������� �����!��� ������ �: ( )f kg x – ��#"����� �� ���� ( )f x � ���� kx ; 1= ( ( ) ( ))T k k f k f kr B g x g x −− – ��� �� ��� �� � ���� ��������� �� - �� ��#"����� �� � ����#������ �� ���� �� � ��. 2. %��������� = /k k kr rξ � � ( kξ – ������� �� ��� �'� �� ���� �� � ��). 3. (����� ������ � kβ , �#�� �! ��������� � ��� �'� �� ���� �� � ��. 4. �������� 1 = ( )k k kk B B R+ β ξ , "�� ( )kk Rβ ξ – ����� �� ��� �'� �� ���� �� � �� 1 ( ) = ( 1) , = < 1T nR Iβ ξ + β − ξξ β α . 5. )������ 1= ( )T k k f kg B g x+� ( kkg� – ��#"����� � ����#������ �� ���� �� � ��. 6. %��������� 1 1= / .k k k k k kx x h B g g+ +− � �� � 7. ��������� � �����!���� ��"� ��� ��������� ��#� � ��"��� �� ��� ����� � �� ������� �� � ���: 1k k xx x+ − ≤ ε ��� ( )f k gg x ≤ ε , "�� xε , gε – ���� �� ����'� �� �� �����. �� �� ���������� ��������� ��� �'� �� ���� �� � �� kα ��#������ ��� �� �� (� �������� 2–3). * �"���� � �'� �� kh ����������� �����!��� ���� �� �� �����#�� ��"��������. (���� �� ��� ���� � ���� �� ����� m (� � �� ���������� 3), ��� �� �� 2 > 1q � 0 0 > 0t (����� k ��"�� � � ������ � #��� �#�� ��� �� ��� �� � �� � 0 kt ). &��"����� �� ���� kx � ������� �� ������ η � ��"�� 0 kt �� �� ���, ���� � #��� ����� � � ������� ������� �� ������ �� ������� �!, ��#� ����� ��"�� � � � � ��� �� m . +������ ������� �� ������ ��� �� � ��, � � � �� �� ���� x ( ( ), ) 0fg x η ≤ . ,��� ������ m ��"��, � ������� ������� �� ������ � ����� � �, � ���� � 0 kt ������ ��� 1 0 2=k kt q t , "�� 2 > 1q , � ������'��� ����� � �� '� ������� �� � #�� ��� ��"��. ,��� ����� ������ �"� ��"� ������� ������� �� ������ � %- %&)%. /,���(�0�� R-��1%/�23� ������ ��� �� � � ����� . 2011, � 10 93 ����� � �, � ���� � 1 kt #���� 2 1=k kt qt � . �. ,��� ����� ���� �"� ����� ��"�� (� � �� ���������� 60 ��"��) � �������� �� ������� �� ������� ������� �� ������ � ����� � ��, � ��������� ��������� ������ � �� � �������� ����� � �� ���"�����. ����� � 0=p pk k k kt q t ( {0,1, 2, })kp ∈ � , �� ���� ����� ������� � ������ �� ��"�, ��� ���� �� � ����� �� ���� �� ��� ������ � ���� ������� �� �� ���� 1kx + , .�. 0 1 = pk k kt t+ . ,��� � �� �� � ������ �'� ����� �����"� ��"� ����� � � ������� ������� �� ������ �� ������� �!, � ��"���� � �'� �� �� �'�� �� � ���� �� ����� 1 1q < (������� 0,8–0,95) ( ���� �����# ��"�������� ��"� ������ �������� ����� ��#� ��� "������ �� ����). 2��'� ����� ���� ����� «���� � ���� ��» �� ���� kB , .�. k nB I= ���� 16 1 ( ) 10T k f kB g x − + ≤ . ����� ��� � �� ��� ��� r- ����� � � ���������� � �� ������� ��� ��� AMPL. �������� �� ����� r-��"��� �� #��� ��������� � � ����� ���"�����- ���� �� C++ � ���� ������. ���"�����, �� ���! #���� ����� amplRalg, #��� �����!�� � � � ������� ��� ��� AMPL � ����� ! ����� �, ��� �� �� � ������� �� ��� � (http://www.ampl.com/DOWNLOADS/index.html). % � ����- �� ��� � ��� ���� �� "������ � �"������ ����� �� ��������. &�� ���� �� ����� � �"�� ��� ���� ����� ��� �� �� �� �"������ � ��� �� �� ���� [4]. &�� ��#� � ���"����� � ���� ! ��� ���' � #� �� � ���� � ��� ��� AMPL. %���� �� �� ��� ������� ������ ������ � ����� �� �� �� �������- �� �� � ��� �� � ��� � ��#��� ���� ����� ���������� �� AMPL, ��� � �� � ��� �� �� ���� � �������� �� #��� ������� �� �� ��� ������ ��� ����. +������!��� ������ �� r-��"��� �� ����! �� � ��� ���� ����� � ���� ��� RALG.OPT. % ����������� �� ������ ���"����� amplRalg ��� ��� �� Windows � Linux � ����� �� �� ����� � �� ��' � �� � � ��� � http://elis.dvo.ru /sites/default/files/OptimiZone/software/ndo-icyb/. &���� ����� ���� � ����� � � ���� � �� �� ����� �� ��������� �� � ��� �� ����� �� �� � ����� � �� ���"����� ��� �#��� �� ���� �����. �� ��� ������ ��������� ��� ������ �. &�� ������� �� ����� �� ��������� �� #��� ��#�� � �� ���� ������, ��� �� �� � ��� � http://orfe.princeton.edu/~rvdb/ampl/nlmodels/. (��� ����� �� � �"�� ����� �� �#��� �� ���� �����, ������� �� CUTEr [5], ����� �� � ����� AMPL. &�� ���� � �� �"� � ����� #��� ��#�� � ����� �� ���"����� LOQO (Version 6.06) � SNOPT (Student SNOPT 7.2-8), �����!�� �� � ��� ��� ���������� �� AMPL. LOQO – �� � �� ���������� �.�. ��$% �& 94 ������ ��� �� � � ����� . 2011, �10 �� ��� � � �� �� ����, ���� �� ��� �� ��� ���� �� ����� ��� �� �"� ���"��������� �� [6], SNOPT – �� � �� ���������� ����� ! � ������ �� ���� [7]. ����� ������� � � ��� �� � ��� �� �������!��� ������ ��� ��� � �� ���"����. &�� amplRalg � ��� �� ������ ��� ��� ���� �� �� ���� ����� #��� ��#�� � �����!����: 2=α – ��������� ��� �'� �� ���� �� � ��; 8 1 10k kx x − + − ≤ – �� �� ��� ������� �� �� ��"��� � ( k – ���� � ������); 1h = – ������ � ���� �"� ��"�; � ��� �� ������ ��� 1 1.2q = , 2 0.95q = , ������ � � ��� �"� ��������� � ��� ���� 1000. $���� ���� ��� ���� ! ���, � �� ���� ���������� ��������� ��: ���- � ! �� IBM PC Pentium; ��������� CPU Pentium 750MHz; ����� �� �� ���� 256MB; �������� �� ��� ��� Windows 2000; ��� ��� ���������� �� AMPL (student version). &�� ������� �� ������� �� �� ��������� �� #��� ��� � 429 ����� �� �� ���"� �#��� CUTEr. 3������� �� ����� ������ �� – 203, �"�� ��� �� – 256. 4 � ������ #��� ��� ��������, �� � ���������. &�� ���� � �� �����- �� �� � � ���' �� � ���"���� ����� ��� �� ������, �� ��� �� � ��- � ��� �� ������ �������� ��������� �� �� � [8]. ������ ��������� �� �- � � ����� ����� ��#�� �� ���! ���������� �� ����� ���� �� ����� � ���- '� ��� ��� ��� �� ����� �� �� �, �� � ���' �� � ����������� ���"�����. )� ���� �� ������ � ������ �� "������ ������ �������� ��������� �� �- � �, �� �� ���� ��� �, � � �������� ����� � �������� ���"����� SNOPT, � ����� � � ��#� � ���"���� LOQO � amplRalg #�����. 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 1 2 3 snopt loqo ralg /�5+)%6. 1������ �������� ��������� �� �� � %- %&)%. /,���(�0�� R-��1%/�23� ������ ��� �� � � ����� . 2011, � 10 95 ��������. �� ����� � �� ������� �� �� ��������� �� ��' � ���- �� �����, � � ���"����� amplRalg, ����� ��!��� �� �� �� �� � ��� �� �� ���� � r-��"��� �, ���� ��� � ���"������ LOQO �� ���' �� � � �����- ���� �� �� � � �� ���� �#��� �� CUTEr. !.�. " ��� � �/% %&)+ /,��7(�078 R-��1%/�23+ /��"����9 �� �� � ����:���:� �:����"� r-��"��� �� � �:���!�� �� �� ��� ��� �����!�� � AMPL. )����� �� ����� � � ���:� �� �� ����� �� ��������� :� � �:����� �� ���� ������� � �� ��:���:� ��� ���"������, �� ����� �� ������ ��� ���. O.P. Lykhovyd ON ONE REALIZATION OF R-ALGORITHM A realization of well-known r-algorithm with interface to AMPL modeling system is considered. The results of comparative numerical experiments on known test problems with optimization soft- ware implemented to the system are given. 1. Fourer R., Gay D., Kernighan B. AMPL: A Modeling Language for Mathematical Pro- gramming. – Duxbury Press-Brooks-Cole Publishing Company, –1993. – 351 p. 2. NEOS Server for Optimization. http://www.neos-server.org/neos/ 3. # �� $.%., &��'���� $.(. 3� �� �� ��������, ����� ��!��� �������! ��� �'� �� ���� �� � �� � ������� �� ��� �� � ���� ��������� �� �� "����� �� // 6�#�� � ���. – 1971. – ; 3. – C. 51–59. 4. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – Boston Dordrecht. – London: Kluwer Academic Publishers, 1998. – 412 p. 5. CUTEr. A Constrained and Unconstrained Testing Environment.. http://www.cuter.rl. ac.uk/ 6. 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. 7. SNOPT 7.2 http://www.sbsi-sol-optimize.com/asp/sol_product_snopt.htm 8. Dolan E.D., More J.J. Benchmarking optimization software with performance profiles. Math. Programming, 91:201-214, 2002. ������ � 05.04.2011
id nasplib_isofts_kiev_ua-123456789-46778
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn XXXX-0013
language Russian
last_indexed 2025-12-07T18:36:18Z
publishDate 2011
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
record_format dspace
spelling Лиховид, А.П.
2013-07-06T17:09:20Z
2013-07-06T17:09:20Z
2011
Об одной реализации r-алгоритма / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 91-95. — Бібліогр.: 8 назв. — рос.
XXXX-0013
https://nasplib.isofts.kiev.ua/handle/123456789/46778
519.8
Рассматривается одна реализация известного r-алгоритма с подключением к системе моделирования AMPL Приводятся результаты сравнительных численных экспериментов на известных тестовых задачах с входящими в состав системы оптимизационными программами.
Розглядається одна реалізація відомого r-алгоритму з підключенням до системи моделювання AMPL. Наводяться результати порівняльних чисельних експериментів на відомих тестових задачах з оптимізаційними програмами, що входять до складу системи.
A realization of well-known r-algorithm with interface to AMPL modeling system is considered. The results of comparative numerical experiments on known test problems with optimization software implemented to the system are given.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Теорія оптимальних рішень
Об одной реализации r-алгоритма
Про одну реалізацію r-алгоритму
On one realization of r-algorithm
Article
published earlier
spellingShingle Об одной реализации r-алгоритма
Лиховид, А.П.
title Об одной реализации r-алгоритма
title_alt Про одну реалізацію r-алгоритму
On one realization of r-algorithm
title_full Об одной реализации r-алгоритма
title_fullStr Об одной реализации r-алгоритма
title_full_unstemmed Об одной реализации r-алгоритма
title_short Об одной реализации r-алгоритма
title_sort об одной реализации r-алгоритма
url https://nasplib.isofts.kiev.ua/handle/123456789/46778
work_keys_str_mv AT lihovidap obodnoirealizaciiralgoritma
AT lihovidap proodnurealízacíûralgoritmu
AT lihovidap ononerealizationofralgorithm