Об одной реализации r-алгоритма
Рассматривается одна реализация известного r-алгоритма с подключением к системе моделирования AMPL Приводятся результаты сравнительных численных экспериментов на известных тестовых задачах с входящими в состав системы оптимизационными программами. Розглядається одна реалізація відомого r-алгоритму з...
Gespeichert in:
| 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 |