Обобщенный метод эллипсоидов
Приведен алгоритм с растяжением пространства, который при определенном выборе коэффициента растяжения является методом описанных эллипсоидов. Частным его случаем является метод эллипсоидов Юдина Немировского Шора. Описано применение алгоритма для решения задачи выпуклого программирования и задачи по...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2018 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/161370 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Обобщенный метод эллипсоидов / П.И. Стецюк, А.В. Фесюк, О.Н. Хомяк // Кибернетика и системный анализ. — 2018. — Т. 54, № 4. — С. 70–80. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-161370 |
|---|---|
| record_format |
dspace |
| spelling |
Стецюк, П.И. Фесюк, А.В. Хомяк, О.Н. 2019-12-07T15:38:10Z 2019-12-07T15:38:10Z 2018 Обобщенный метод эллипсоидов / П.И. Стецюк, А.В. Фесюк, О.Н. Хомяк // Кибернетика и системный анализ. — 2018. — Т. 54, № 4. — С. 70–80. — Бібліогр.: 12 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/161370 519.85 Приведен алгоритм с растяжением пространства, который при определенном выборе коэффициента растяжения является методом описанных эллипсоидов. Частным его случаем является метод эллипсоидов Юдина Немировского Шора. Описано применение алгоритма для решения задачи выпуклого программирования и задачи поиска седловой точки выпукло-вогнутой функции. Наведено алгоритм з розтягом простору, який за певного вибору коефіцієнта розтягу є методом описаних еліпсоїдів. Його частковим випадком є метод еліпсоїдів Юдіна Немировського Шора. Описано застосування алгоритму для розв язання задачі опуклого програмування і задачі пошуку сідлової точки опукло увігнутої функції. An algorithm with space dilation is presented, which is the circumscribed ellipsoid method under a certain choice of tensile coefficient. It is shown that its partial case is the Yudin–Nemirovsky–Shor ellipsoid method. The application of the algorithm for solving a convex programming problem and the problem of finding a saddle point of a convex-concave function are described. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Обобщенный метод эллипсоидов Узагальнений метод еліпсоїдів Generalized ellipsoid method Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Обобщенный метод эллипсоидов |
| spellingShingle |
Обобщенный метод эллипсоидов Стецюк, П.И. Фесюк, А.В. Хомяк, О.Н. Системний аналіз |
| title_short |
Обобщенный метод эллипсоидов |
| title_full |
Обобщенный метод эллипсоидов |
| title_fullStr |
Обобщенный метод эллипсоидов |
| title_full_unstemmed |
Обобщенный метод эллипсоидов |
| title_sort |
обобщенный метод эллипсоидов |
| author |
Стецюк, П.И. Фесюк, А.В. Хомяк, О.Н. |
| author_facet |
Стецюк, П.И. Фесюк, А.В. Хомяк, О.Н. |
| topic |
Системний аналіз |
| topic_facet |
Системний аналіз |
| publishDate |
2018 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Узагальнений метод еліпсоїдів Generalized ellipsoid method |
| description |
Приведен алгоритм с растяжением пространства, который при определенном выборе коэффициента растяжения является методом описанных эллипсоидов. Частным его случаем является метод эллипсоидов Юдина Немировского Шора. Описано применение алгоритма для решения задачи выпуклого программирования и задачи поиска седловой точки выпукло-вогнутой функции.
Наведено алгоритм з розтягом простору, який за певного вибору коефіцієнта розтягу є методом описаних еліпсоїдів. Його частковим випадком є метод еліпсоїдів Юдіна Немировського Шора. Описано застосування алгоритму для розв язання задачі опуклого програмування і задачі пошуку сідлової точки опукло увігнутої функції.
An algorithm with space dilation is presented, which is the circumscribed ellipsoid method under a certain choice of tensile coefficient. It is shown that its partial case is the Yudin–Nemirovsky–Shor ellipsoid method. The application of the algorithm for solving a convex programming problem and the problem of finding a saddle point of a convex-concave function are described.
|
| issn |
1019-5262 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/161370 |
| citation_txt |
Обобщенный метод эллипсоидов / П.И. Стецюк, А.В. Фесюк, О.Н. Хомяк // Кибернетика и системный анализ. — 2018. — Т. 54, № 4. — С. 70–80. — Бібліогр.: 12 назв. — рос. |
| work_keys_str_mv |
AT stecûkpi obobŝennyimetodéllipsoidov AT fesûkav obobŝennyimetodéllipsoidov AT homâkon obobŝennyimetodéllipsoidov AT stecûkpi uzagalʹneniimetodelípsoídív AT fesûkav uzagalʹneniimetodelípsoídív AT homâkon uzagalʹneniimetodelípsoídív AT stecûkpi generalizedellipsoidmethod AT fesûkav generalizedellipsoidmethod AT homâkon generalizedellipsoidmethod |
| first_indexed |
2025-11-25T21:04:15Z |
| last_indexed |
2025-11-25T21:04:15Z |
| _version_ |
1850546002996494336 |
| fulltext |
Ï.È. ÑÒÅÖÞÊ, À.Â. ÔÅÑÞÊ, Î.Í. ÕÎÌßÊ
ÓÄÊ 519.85 ÎÁÎÁÙÅÍÍÛÉ ÌÅÒÎÄ ÝËËÈÏÑÎÈÄÎÂ1
Àííîòàöèÿ. Ïðèâåäåí àëãîðèòì ñ ðàñòÿæåíèåì ïðîñòðàíñòâà, êîòîðûé ïðè
îïðåäåëåííîì âûáîðå êîýôôèöèåíòà ðàñòÿæåíèÿ ÿâëÿåòñÿ ìåòîäîì îïèñàí-
íûõ ýëëèïñîèäîâ. Åãî ÷àñòíûì ñëó÷àåì ÿâëÿåòñÿ ìåòîä ýëëèïñîèäîâ
Þäèíà–Íåìèðîâñêîãî–Øîðà. Îïèñàíî ïðèìåíåíèå àëãîðèòìà äëÿ ðåøåíèÿ
çàäà÷è âûïóêëîãî ïðîãðàììèðîâàíèÿ è çàäà÷è ïîèñêà ñåäëîâîé òî÷êè âû-
ïóêëî-âîãíóòîé ôóíêöèè.
Êëþ÷åâûå ñëîâà: ìåòîä ýëëèïñîèäîâ, îïåðàòîð ðàñòÿæåíèÿ ïðîñòðàíñòâà,
ëîêàëèçóþùèé ýëëèïñîèä, çàäà÷à âûïóêëîãî ïðîãðàììèðîâàíèÿ, ñåäëîâàÿ
òî÷êà âûïóêëî-âîãíóòîé ôóíêöèè.
ÂÂÅÄÅÍÈÅ
Êëàññè÷åñêèé ìåòîä ýëëèïñîèäîâ âïåðâûå ïðåäëîæåí â 1976 ã. Ä.Á. Þäèíûì
è À.Ñ. Íåìèðîâñêèì [1]. Â îñíîâó áûëè ïîëîæåíû ñõåìû ïîñëåäîâàòåëüíûõ
îòñå÷åíèé. Ýòîò ìåòîä ýëëèïñîèäîâ áûë íàçâàí ìîäèôèöèðîâàííûì ìåòîäîì
öåíòðèðîâàííûõ ñå÷åíèé (ÌÌÖÑ). Íåçàâèñèìî ìåòîä ýëëèïñîèäîâ áûë îò-
êðûò çàíîâî â 1977 ã. Í.Ç. Øîðîì [2] è ïðåäñòàâëåí êàê ÷àñòíûé ñëó÷àé
ñóáãðàäèåíòíûõ ìåòîäîâ ñ ðàñòÿæåíèåì ïðîñòðàíñòâà â íàïðàâëåíèè ñóáãðàäè-
åíòà, èññëåäîâàíèÿ êîòîðûõ áûëè íà÷àòû â 1969–1970 ãã. Í.Ç. Øîð óêàçàë êî-
ýôôèöèåíò ðàñòÿæåíèÿ ïðîñòðàíñòâà è ïàðàìåòðû ðåãóëèðîâêè øàãà â íàïðàâ-
ëåíèè íîðìèðîâàííîãî àíòèñóáãðàäèåíòà òàêèìè, ÷òî ñóáãðàäèåíòíûé ìåòîä
ñ ðàñòÿæåíèåì ïðîñòðàíñòâà ñòàë ñõîäèòüñÿ ñ ãåîìåòðè÷åñêîé ñêîðîñòüþ óáû-
âàíèÿ îáúåìà ýëëèïñîèäà, â êîòîðîì ëîêàëèçîâàíà òî÷êà ìèíèìóìà âûïóêëîé
ôóíêöèè, è òåì ñàìûì ïîëó÷èë âåñüìà ïðîçðà÷íîå îáîñíîâàíèå (äîêàçà-
òåëüñòâî) ñõîäèìîñòè ìåòîäà ýëëèïñîèäîâ.
 íàñòîÿùåé ñòàòüå ðàññìîòðåíî ñåìåéñòâî ìåòîäîâ ýëëèïñîèäîâ, êîòîðîå
ïðåäñòàâëåíî êàê ìåòîä ñ ðàñòÿæåíèåì ïðîñòðàíñòâà è îïðåäåëåííûì ñïîñîáîì
ðåãóëèðîâêè øàãà, ñâÿçàííûì ñ ïåðåõîäîì â öåíòð î÷åðåäíîãî ëîêàëèçóþùåãî
ýëëèïñîèäà, îáúåì êîòîðîãî ìåíüøå, ÷åì îáúåì ïðåäûäóùåãî ýëëèïñîèäà. Óñëî-
âèìñÿ íàçûâàòü åãî îáîáùåííûì ìåòîäîì ýëëèïñîèäîâ. Ðàññìîòðåíî åãî ïðèìå-
íåíèå è äîêàçàíà ñõîäèìîñòü ýòîãî ìåòîäà ñ ãåîìåòðè÷åñêîé ñêîðîñòüþ óáûâà-
íèÿ îáúåìà ëîêàëèçóþùåãî ýëëèïñîèäà, à òàêæå óêàçàíû êîýôôèöèåíòû äëÿ
äâóõ ÷àñòíûõ ñëó÷àåâ îáîáùåííîãî ìåòîäà ýëëèïñîèäîâ.
Ñòàòüÿ âêëþ÷àåò òðè ðàçäåëà.  ðàçä. 1 ïðèâåäåíî îïèñàíèå îáîáùåííîãî
ìåòîäà ýëëèïñîèäîâ è äîêàçàíà òåîðåìà î åãî ñõîäèìîñòè [3, 4]. Â ðàçä. 2 ïðèâå-
äåíà H-ôîðìà îáîáùåííîãî ìåòîäà ýëëèïñîèäîâ, ãäå, êàê è â ÌÌÖÑ, êîððåêòè-
ðóåòñÿ ïîëîæèòåëüíî-îïðåäåëåííàÿ ñèììåòðè÷íàÿ ìàòðèöà H . Çäåñü ïîêàçàíî,
70 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4
1 Ðàáîòà âûïîëíåíà ïðè ïîääåðæêå ÍÀÍ Óêðàèíû (ïðîåêòû ¹ 0117U000327, ¹ 0116U004558)
è Volkswagen Foundation (ãðàíò Nî 90 306).
© Ï.È. Ñòåöþê, À.Â. Ôåñþê, Î.Í. Õîìÿê, 2018
÷òî èçâåñòíûé ìåòîä ýëëèïñîèäîâ Þäèíà–Íåìèðîâñêîãî–Øîðà ÿâëÿåòñÿ ÷àñò-
íûì ñëó÷àåì îáîáùåííîãî ìåòîäà ýëëèïñîèäîâ.  ðàçä. 3 îïèñàíû ïðàâèëà ïî-
ñòðîåíèÿ îòñåêàþùèõ âåêòîðîâ è êðèòåðèåâ îñòàíîâà äëÿ çàäà÷è ìèíèìèçàöèè
âûïóêëîé ôóíêöèè, çàäà÷è âûïóêëîãî ïðîãðàììèðîâàíèÿ è çàäà÷è ïîèñêà
ñåäëîâîé òî÷êè âûïóêëî-âîãíóòîé ôóíêöèè.
1. ÎÁÙÀß ÑÕÅÌÀ ÌÅÒÎÄÀ ÝËËÈÏÑÎÈÄÎÂ
Ïóñòü E n – åâêëèäîâî ïðîñòðàíñòâî ðàçìåðíîñòè n ñî ñêàëÿðíûì ïðîèçâåäå-
íèåì ( , )x y .
Çàäà÷à. Íà E nn ( )� 2 çàäàíî âåêòîðíîå ïîëå g x E n( )� . Òðåáóåòñÿ íàéòè òî÷êó
x* òàêóþ, ÷òî ( ( ), )*g x x x� � 0 äëÿ âñåõ x E n� . Ïðåäïîëàãàåòñÿ, ÷òî x* ñóùåñòâóåò
è g x( ) � 0 äëÿ x x� * .
Ýòó çàäà÷ó ìîæíî ðåøèòü îáîáùåííûì ìåòîäîì ýëëèïñîèäîâ, êîòîðûé ÿâ-
ëÿåòñÿ àëãîðèòìîì ñ ðàñòÿæåíèåì ïðîñòðàíñòâà, ãäå êîýôôèöèåíò ðàñòÿæåíèÿ �
óäîâëåòâîðÿåò íåðàâåíñòâó �
�
�� �
1
2 n . Ïðåäñòàâèì îáùóþ ñõåìó ìåòîäà
ýëëèïñîèäîâ.
Èíèöèàëèçàöèÿ. Âûáèðàåì òî÷êó x E n
0 � è ðàäèóñ r0 òàêèìè, ÷òîáû
|| ( ) ||*B x x r0
1
0 0
� � � , ãäå B0 – n n -ìàòðèöà. Ïåðåéäåì ê î÷åðåäíîé èòåðàöèè ñî
çíà÷åíèÿìè x0 , r0 , B0 .
Èòåðàöèîííûé ïðîöåññ. Ïóñòü íà k-é èòåðàöèè íàéäåíû x Ek
n� , rk è
n n -ìàòðèöà Bk . Äëÿ ïåðåõîäà ê ( )k �1 -é èòåðàöèè âûïîëíèì òàêèå äåéñòâèÿ.
Øàã 1. Âû÷èñëèì g g xk k
( ) . Åñëè gk
0 , òî ÎÑÒÀÍÎÂ (x xk
*
).
Øàã 2. Âû÷èñëèì î÷åðåäíóþ òî÷êó
x x h Bk k k k k�
�1: � , ãäå h rk k
�
�
�
�
�
��
1
2
1
1
2�
, �k
k k
k k
B g
B g
T
T|| ||
.
Øàã 3. Ïåðåñ÷èòàåì ìàòðèöó Bk�1 è ðàäèóñ rk�1 :
B B Bk k k k k�
� �
�
�
�
�
�1
1
1: ( )
�
� �T , r rk k�
�
�
�
�
�
�1
1
2
1
: �
�
. (1)
Øàã 4. Ïåðåõîäèì ê ( )k �1 -é èòåðàöèè ñ èñïîëüçîâàíèåì xk�1, rk�1 è Bk�1.
Òåîðåìà 1. Ãåíåðèðóåìàÿ îáîáùåííûì ìåòîäîì ýëëèïñîèäîâ ïîñëåäîâà-
òåëüíîñòü òî÷åê { }xk k
�
0 óäîâëåòâîðÿåò íåðàâåíñòâàì
|| ( ) || , , , ,*A x x r kk k k� �
0 1 2 � , (2)
ãäå A Bk k
�1 . Îòíîøåíèå îáúåìîâ ýëëèïñîèäîâ E x A x x rk k k k
� �{ : || ( ) || } è
E x A x x rk k k k� � � �
� �1 1 1 1{ : || ( ) || } , ëîêàëèçóþùèõ òî÷êó x * , åñòü âåëè÷èíà
ïîñòîÿííàÿ è îïðåäåëÿåòñÿ âûðàæåíèåì
q
E
E
kn
k
k
n
( )
( )
( )
,�
�
�
�
�
�
�
�
�
�
�
�
�
�
�� ��vol
vol
1 1 1
2
1
1
0 1 2, , ,� (3)
Ðàññìîòðèì äîêàçàòåëüñòâî òåîðåìû 1, àíàëîãè÷íîå ïðèâåäåííîìó äëÿ ìå-
òîäà ýëëèïñîèäîâ Í.Ç. Øîðîì [2]. Ïðè äîêàçàòåëüñòâå äëÿ îïåðàòîðà ðàñòÿæåíèÿ
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4 71
ïðîñòðàíñòâà
R I En
n
� � � �� � �( ) ( ) , , || ||
� � �
1 1T , (4)
èñïîëüçîâàíû òàêèå ñîîòíîøåíèÿ:
R R R� � �
� � �T ( ) ( ) ( )
2 , (5)
detR� � �( )
.
Îíè ñëåäóþò èç ñâîéñòâ îïåðàòîðà ðàñòÿæåíèÿ ïðîñòðàíñòâà (4) [5, ñ. 68–69].
Êðîìå òîãî, èñïîëüçóåì ñîîòíîøåíèå
A R Ak k k�
1 � �( ) , (6)
êîòîðîå ñ ó÷åòîì � �
1/ ñëåäóåò èç öåïî÷êè ðàâåíñòâ
A B B R R B R A Rk k k k k k k k� �
� � � �
1 1
1 1 1 1
1( ( )) ( ) ( )/� � �� � � � �( )k kA .
Äîêàçàòåëüñòâî. Äîêàæåì òåîðåìó 1 ìåòîäîì èíäóêöèè ïî k . Äëÿ k
0 íåðà-
âåíñòâî (2) ïåðåõîäèò â || ( ) ||*A x x r0 0 0� � , ãäå A B0 0
1
� , è âûïîëíÿåòñÿ ïî
ïðåäïîëîæåíèþ. Äîïóñòèì, ÷òî íåðàâåíñòâî (2) âûïîëíÿåòñÿ äëÿ k k
. Äîêà-
æåì åãî âûïîëíåíèå äëÿ k k
�1.
Ó÷èòûâàÿ ñîîòíîøåíèå (5) è òî, ÷òî èç (6) ñëåäóåò A R Ak k k�
1 � �( ) , èìååì
öåïî÷êó ðàâåíñòâ:
|| ( ) || ( ( ), ( ))* * *A x x A x x A x xk k k k k k� � � � � ��
� �
1 1
2
1 1 1 1
� �
� �( ( ) ( ), ( ) ( ))* *R A x x R A x xk k k k k k� �� �1 1
� �
� �( ( ), ( ) ( ) ( ))* *A x x R R A x xk k k k k k1 1� �� �T
� �
� �( ( ), ( ) ( ))* *A x x R A x xk k k k k1 12�
�
� � � �
� �( ( ), ( ( ) ) ( ))* *A x x I A x xk k k k k k1
2
11� � �T
� � � � �� � �( ( ), ( )) ( )( , ( ))* * *A x x A x x A x xk k k k k k k1 1
2
1
21� �
� � � �� �|| ( ) || ( )( , ( ))* *A x x A x xk k k k k1
2 2
1
21� � ,
êîòîðóþ çàïèøåì â âèäå ñîîòíîøåíèÿ
|| ( ) || || ( ) || ( )( , (* *A x x A x x A xk k k k k k� � ��
� � �1 1
2
1
2 2 1� � k x� �1
2* )) . (7)
Äàëåå, ðàñøèôðóåì îáà ñëàãàåìûõ â ïðàâîé ÷àñòè (7), èñïîëüçóÿ ñîîòíîøåíèå
A x x A x x hk k k k k k( ) ( ) ,* *
� �
� �1 � (8)
êîòîðîå ñ ó÷åòîì A Bk k
�1 è î÷åðåäíîé òî÷êè â îáîáùåííîì ìåòîäå ýëëèïñî-
èäîâ, âû÷èñëÿåìîé ïî ôîðìóëå (1), ñëåäóåò èç öåïî÷êè ðàâåíñòâ
A x x A x h B xk k k k k k k( ) ( )* *
� �
� �
1 �
� �
� �A x x h A B A x x hk k k k k k k k k k( ) ( )* *� � .
72 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4
Ïåðâîå ñëàãàåìîå â ïðàâîé ÷àñòè (7) ìîæíî çàïèñàòü â âèäå ðàâåíñòâà
|| ( ) || || ( ) || ( ( ), )* * *A x x A x x h A x xk k k k k k k k� �
� � � �1
2 2 2 � h
k
2 , (9)
êîòîðîå ñ ó÷åòîì (8) è òîãî, ÷òî || ||�k
1 , ñëåäóåò èç öåïî÷êè ðàâåíñòâ
|| ( ) || || ( ) ||* *A x x A x x hk k k k k k� �
� �
1
2 2�
� � � �
( ( ) , ( ) )* *A x x h A x x hk k k k k k k k� �
� � � � �( ( ), ( )) ( ( ), ) ( ,* * *A x x A x x h A x x hk k k k k k k k k k k2 2� � � )
� � � �
|| ( ) || ( ( ), ) || ||* *A x x h A x x hk k k k k k k k
2 2 22 � �
� � � �|| ( ) || ( ( ), )* *A x x h A x x hk k k k k k k
2 22 � .
Ó÷èòûâàÿ ñîîòíîøåíèå (8), äëÿ êâàäðàòà ñêàëÿðíîãî ïðîèçâåäåíèÿ âî âòîðîì
ñëàãàåìîì ïðàâîé ÷àñòè (7) èìååì ñëåäóþùóþ öåïî÷êó ðàâåíñòâ:
( ( ), ) ( ( ) , )* *A x x A x x hk k k k k k k k� �
� �
1
2 2� � �
� �
� �(( ( ), ) ( , )) (( ( ), ) ||* *A x x h A x x hk k k k k k k k k k� � � � �2
k
|| )2 2
� �
� � �(( ( ), ) ) ( ( ), ) ( (* * *A x x h A x x h A x xk k k k k k k k k k� �2 2 2 ), ) .�k k
h� 2
Ñëåäîâàòåëüíî, êâàäðàò äàííîãî ñêàëÿðíîãî ïðîèçâåäåíèÿ ìîæíî çàïèñàòü â âèäå
( ( ), ) ( ( ), ) ( ( ),* * *A x x A x x h A x xk k k k k k k k k k� �
� � �1
2 2 2� � � ) .� h
k
2 (10)
Ïîäñòàâëÿÿ (9) è (10) â (7), èìååì
|| ( ) ||*A x xk k� � �
1 1
2
� � � �
�� �|| ( ) || ( )( , ( )) || (* *A x x A x x A xk k k k k k k1
2 2
1
21� � x * ) ||2 �
� � � � � � �2 12 2 2h A x x h A x xk k k k k k k k( ( ), ) ( )(( ( ), )* *� � �
� � �
2 2h A x x hk k k k k
( ( ), ) )* �
� � � � � �|| ( ) || ( ( ), ) ( )( (* *A x x h A x x A x xk k k k k k k k
2 2 22 1� � � * ), )� �k k
h2 2 2�
� � � � � �|| ( ) || ( ( ), )( ( )( (* *A x x A x x h A xk k k k k k k k
2 2 22 1� � � x hk k
* ), ))� �� 2 2 ,
îòêóäà ñ ó÷åòîì h rk k
�
1
2
1
1
2
( )
�
ïîëó÷àåì
|| ( ) ||*A x xk k� � �
1 1
2
� � � � � �|| ( ) || ( )( ( ), )( ( ( )* * *A x x A x x r A x xk k k k k k k k
2 2 1� � , ))�k �
�
�( )�
�
2 2
2
21
4
r
k
. (11)
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4 73
Äàëåå, äëÿ îïðåäåëåíèÿ çíàêà ïðîèçâåäåíèÿ
( ( ), )( ( ( ), ))* *A x x r A x xk k k k k k k� � �� � ,
âõîäÿùåãî â ïðàâóþ ÷àñòü ñîîòíîøåíèÿ (11), îöåíèì çíàêè îáîèõ åãî ñîìíî-
æèòåëåé. Ïåðâûé ñîìíîæèòåëü áóäåò íåîòðèöàòåëüíûì. Ó÷èòûâàÿ, ÷òî
( , ( ))*x x g x� � 0 äëÿ âñåõ x E n� , åãî ëåãêî îöåíèòü ñëåäóþùèì îáðàçîì:
( ( ), ) ( ),
( )
|| ( ) ||
* *A x x A x x
B g x
B g x
k k k k k
k k
k k
�
�
�
�
�
T
T
�
�
�
�
�
�
1
|| ( ) ||
( ( ), ( ))*
B g x
A x x B g x
k k
k k k kT
T
�
1 1
|| ( ) ||
( ( ), ( ))
|| ( ) ||
(*
B g x
B A x x g x
B g x
x
k k
k k k k
k k
kT T
� �x g xk
*, ( )) .0
Ó÷èòûâàÿ, ÷òî
0 � � � � �( ( ), ) || ( ) ||* *A x x A x x rk k k k k k� ,
âòîðîé ñîìíîæèòåëü èç (11) îöåíèâàåòñÿ ñëåäóþùèì îáðàçîì:
r A x xk k k k� � �( ( ), ) .* � 0
Èç íåîòðèöàòåëüíîñòè îáîèõ ñîìíîæèòåëåé ñëåäóåò, ÷òî
( )( ( ), )( ( ( ), )) .* *� � �2 1 0� � � � �A x x r A x xk k k k k k k
(12)
Äàëåå, ó÷èòûâàÿ (12) è íåðàâåíñòâî || ( ) ||*A x x rk k k� � , ñîîòíîøåíèå (11)
ïåðåïèøåì â âèäå
|| ( ) || || ( ) ||
( )* *A x x A x x rk k k k k� � � � � �
�
�1 1
2 2
2 2
2
21
4
�
�
� �
�
� ��
�
�
�
�
�
r r r
k k k
2
2 2
2
2
4 2
2
21
4
2 1
4
( )�
�
� �
�
.
Îòñþäà èìååì íåðàâåíñòâî
|| ( ) || ,*A x x r rk k k k� � �
� � �
�
�
�
�
�
�
�
�
�
��
1 1
2 2
2
1
21
2
1
�
�
èç êîòîðîãî ñëåäóåò ñïðàâåäëèâîñòü íåðàâåíñòâà (2) ïðè k k
�1.
Ìíîæåñòâî òî÷åê x, óäîâëåòâîðÿþùèõ íåðàâåíñòâó || ( ) ||A x x rk k k� � , ÿâëÿ-
åòñÿ ýëëèïñîèäîì Ek , ñîäåðæàùèì òî÷êó x * . Ýëëèïñîèä Ek èìååò îáúåì
vol
det
( )E
r
A
k
k
n
k
� 0
, (13)
ãäå � 0 — îáúåì åäèíè÷íîãî n-ìåðíîãî øàðà, det Ak — îïðåäåëèòåëü ìàòðèöû Ak .
Ñëåäîâàòåëüíî, ñêîðîñòü ñõîäèìîñòè îáîáùåííîãî ìåòîäà ýëëèïñîèäîâ áó-
äåò îïðåäåëÿòüñÿ îòíîøåíèåì îáúåìà ýëëèïñîèäà Ek�1, ëîêàëèçóþùåãî x * íà
( )k �1 -é èòåðàöèè, ê îáúåìó ýëëèïñîèäà Ek , ëîêàëèçóþùåãî x * íà k-é èòåðàöèè.
74 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4
Ñîãëàñíî (6) èìååì A R Ak k k�
1 � �( ) . Ñëåäîâàòåëüíî, äëÿ îïðåäåëèòåëåé
ýòèõ ìàòðèö ñ ó÷åòîì èõ íåâûðîæäåííîñòè ñïðàâåäëèâî ðàâåíñòâî
det det detA R Ak k k� �
1 1� �( ) . Ó÷èòûâàÿ ôîðìóëû (13) è (6), íàõîäèì êîýôôèöè-
åíò óìåíüøåíèÿ îáúåìà
q
E
E
r A
r A
n
k
k
k
n
k
k
n
k
( )
( )
( )
�
�
�
� �
�
vol
vol
det
det
1 0 1
0 1
�
�
�
�
��
�
�
�
�
��
� �r
r
A
R A
r
r
k
k
n
k
k k
k
k
1 1det
det det� �( )
n n
1 1 1
2
1
� �
�
�
�
�
�
�
�
�
�
�
�
�
�� .
Îòñþäà, åñëè êîýôôèöèåíò ðàñòÿæåíèÿ � óäîâëåòâîðÿåò íåðàâåíñòâó
�
�
�� �
1
2 n , èìååì qn
n
( )�
�
�
�
�
�
�
�
�
�
�
�
�
�
�� �
1 1
2
1
1. Òåîðåìà 1 äîêàçàíà.
2. H -ÔÎÐÌÀ ÎÁÎÁÙÅÍÍÎÃÎ ÌÅÒÎÄÀ ÝËËÈÏÑÎÈÄÎÂ
Îáîáùåííûé ìåòîä ýëëèïñîèäîâ ìîæíî çàïèñàòü â H-ôîðìå (êàê ÌÌÖÑ
Þäèíà–Íåìèðîâñêîãî) ñ ïîìîùüþ ïîëîæèòåëüíî-îïðåäåëåííîé ñèììåòðè÷íîé
ìàòðèöû H B Bk k k
T . Äëÿ êîýôôèöèåíòà ðàñòÿæåíèÿ �, êîòîðûé óäîâëåòâîðÿ-
åò íåðàâåíñòâó �
�
�� �
1
2 n , H-ôîðìà îáùåãî ìåòîäà ýëëèïñîèäîâ èìååò ñëå-
äóþùèé âèä.
Èíèöèàëèçàöèÿ. Âûáèðàåì òî÷êó x E n
0 � è ðàäèóñ r0 òàêèìè, ÷òîáû
( ) ( )* *x x H x x r0 0
1
0 0
2� � ��T , ãäå H 0 – ïîëîæèòåëüíî-îïðåäåëåííàÿ ñèììåòðè÷-
íàÿ n n -ìàòðèöà. Ïåðåéäåì ê î÷åðåäíîé èòåðàöèè ñî çíà÷åíèÿìè x0 , r 0 , B0 .
Èòåðàöèîííûé ïðîöåññ. Ïóñòü íà k-é èòåðàöèè íàéäåíû x Ek
n� , rk è
n n -ìàòðèöà H k . Äëÿ ïåðåõîäà ê ( )k �1 -é èòåðàöèè âûïîëíÿåì òàêèå äåéñòâèÿ.
Øàã 1. Âû÷èñëèì g g xk k
( ) . Åñëè gk
0 , òî ÎÑÒÀÍÎÂ (x xk
*
).
Øàã 2. Âû÷èñëèì î÷åðåäíóþ òî÷êó
x x h
H g
g H g
k k k
k k
k k k
�
�1:
T
, ãäå h rk k
�
�
�
�
�
��
1
2
1
1
2�
.
Øàã 3. Ïåðåñ÷èòàåì ìàòðèöó
H H
H g g H
g H g
k k
k k k k
k k k
�
� �
�
�
�
�
��1 2
1
1:
�
T
T
è ðàäèóñ r rk k�
�
�
�
�
�
�1
1
2
1
: �
�
.
Øàã 4. Ïåðåõîäèì ê ( )k �1 -é èòåðàöèè ñî çíà÷åíèÿìè xk�1, rk�1 è H k�1.
 H-ôîðìå îáîáùåííîãî ìåòîäà ýëëèïñîèäîâ ôîðìóëà äëÿ ïåðåñ÷åòà î÷å-
ðåäíîãî ïðèáëèæåíèÿ xk�1 (øàã 2) ñëåäóåò èç ñïðàâåäëèâîñòè öåïî÷êè
ñîîòíîøåíèé
B
B g
B g
B B g
B g B g
H g
g B B
k
k k
k k
k k k
k k k k
k k
k k k
T
T
T
T T T|| || ( ) ( )
T Tg
H g
g H gk
k k
k k k
( )
.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4 75
Ôîðìóëà äëÿ ïåðåñ÷åòà ïîëîæèòåëüíî-îïðåäåëåííîé ñèììåòðè÷íîé ìàòðèöû
H k�1 (øàã 3) cëåäóåò èç òàêîé öåïî÷êè ñîîòíîøåíèé:
H B B B R B R B R Rk k k k k k k k k k� � �
1 1 1
T T T
� � � �
� � � �( )( ( )) ( ) ( )B
k
T
� �B R R B B R B B Ik k k k k k k k n k k� � �
� � � � � �( ) ( ) ( ) ( ( ) )T T T
2
2 1 B
k
T
� �
� �B B B B H
B B g g B B
k k k k k k k
k k k k k kT T T
T T T
( ) ( )
||
� � � �2 21 1
B g
k k
T ||2
� �
� �H
H g g H
B g B g
H
H g g H
k
k k k k
k k k k
k
k k k( )
( )
( )� �2 21 1
T
T T T
T
k
k k k kg B B gT T
� �H
H g g H
g H g
k
k k k k
k k k
( )� 2 1
T
T
,
ãäå � �
1/ .
Òåîðåìà 2. Ïîñëåäîâàòåëüíîñòü òî÷åê { }xk k
�
0 , ãåíåðèðóåìàÿ H-ôîðìîé
îáîáùåííîãî ìåòîäà ýëëèïñîèäîâ, óäîâëåòâîðÿåò íåðàâåíñòâàì
( ) ( ) , , , ,* *x x H x x r kk k k k
� � �
�T 1 2 0 1 2 � , (14)
à îòíîøåíèå îáúåìîâ ýëëèïñîèäîâ E x x x H x x rk k k k k
� � ��{ :( ) ( ) }T 1 2 è
E x x x H x x rk k k k k� � �
�
� �
� � �1 1 1
1
1 1
2{ : ( ) ( ) }T , ëîêàëèçóþùèõ òî÷êó x * , åñòü âå-
ëè÷èíà ïîñòîÿííàÿ è îïðåäåëÿåòñÿ ôîðìóëîé
q
E
E
kn
k
k
n
( )
( )
( )
,�
�
�
�
�
�
�
�
�
�
�
�
�
�
�� ��vol
vol
1 1 1
2
1
1
0 1 2, , ,� (15)
Èç ñîîòíîøåíèé (3) è (15) ñëåäóåò, ÷òî ìåòîä ýëëèïñîèäîâ ñõîäèòñÿ (ïî îáú-
åìó ëîêàëèçàöèè òî÷êè x *) ñî ñêîðîñòüþ ãåîìåòðè÷åñêîé ïðîãðåññèè ñî çíàìåíà-
òåëåì qn ( )� � 1 . Âåëè÷èíà çíàìåíàòåëÿ çàâèñèò îò âûáðàííîãî çíà÷åíèÿ � , óäîâ-
ëåòâîðÿþùåãî íåðàâåíñòâó �
�
�� �
1
2 n . Íàèìåíüøèé çíàìåíàòåëü ïðîãðåññèè
ðåàëèçóåòñÿ â ìåòîäå ýëëèïñîèäîâ Þäèíà–Íåìèðîâñêîãî–Øîðà. Åìó ñîîòâåò-
ñòâóåò êîýôôèöèåíò ðàñòÿæåíèÿ �1
1
1
�
�
n
n
, êîòîðûé äîñòèãàåòñÿ â òî÷êå ìèíè-
ìóìà ôóíêöèè qn ( )� ïî � . Çíàìåíàòåëü ïðîãðåññèè, áëèçêèé ê íàèìåíüøåìó,
ðåàëèçóåòñÿ â ïðèáëèæåííîì ìåòîäå ýëëèïñîèäîâ [6], è åìó ñîîòâåòñòâóåò êî-
ýôôèöèåíò ðàñòÿæåíèÿ � 2 2
1
1 1
� �
n n
. Îí äîñòèãàåòñÿ â òî÷êå ìèíèìóìà
ôóíêöèè Qn ( )� , êîòîðàÿ àïïðîêñèìèðóåò ñâåðõó ôóíêöèþ qn ( )� ñîãëàñíî ñî-
îòíîøåíèþ
qn
n
( )�
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
��
� � �
�
�
�
�
�
�
�
1 1
2
1 1
1
1
2
1
2
�
�
�� � � �
�
�
�
�
�
�
�
�
�
�
�
n
n
n
Q
1
2
1
2
�
�
�
�exp ( ) .
76 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4
Ïðè áîëüøèõ çíà÷åíèÿ n çíàìåíàòåëè ãåîìåòðè÷åñêîé ïðîãðåññèè â îáîèõ
ìåòîäàõ àïïðîêñèìèðóþòñÿ ñâåðõó áëèçêèìè âåëè÷èíàìè q n
n
* ( )
�1
1
2
è
Q n
n n
*( )
� �1
1
2
1
2 2
.
3. ÇÀÄÀ×È ÄËß ÎÁÎÁÙÅÍÍÎÃÎ ÌÅÒÎÄÀ ÝËËÈÏÑÎÈÄÎÂ
Ðàññìîòðèì îïèñàíèå íåêîòîðûõ çàäà÷ èç [7], äëÿ ðåøåíèÿ êîòîðûõ ìîæíî
èñïîëüçîâàòü îáîáùåííûé ìåòîä ýëëèïñîèäîâ.
Çàäà÷à áåçóñëîâíîé ìèíèìèçàöèè âûïóêëîé ôóíêöèè. Ïóñòü f x( ) — âû-
ïóêëàÿ ôóíêöèÿ, ãäå x E n� . Åå ìèíèìàëüíîå çíà÷åíèå îáîçíà÷èì f f x* *( )
è,
íå îãðàíè÷èâàÿ îáùíîñòè, ïðåäïîëîæèì, ÷òî x * — åäèíñòâåííàÿ òî÷êà ìèíèìó-
ìà. Ïóñòü èìååòñÿ àïðèîðíàÿ èíôîðìàöèÿ, ÷òî òî÷êà x * íàõîäèòñÿ â øape
S x R( , )0 . Òîãäà åñëè âåêòîðíîå ïîëå îïðåäåëåíî ïî ôîðìóëå g x g xf( ) ( )
, ãäå
g xf ( ) — ñóáãðàäèåíò ôóíêöèè f x( ) â òî÷êå x , òî äëÿ íåãî áóäåò âûïîëíÿòüñÿ
íåðàâåíñòâî
( , ( )) ( , ( )) ( ) ( ) ( )* * * *x x g x x x g x f x f x f x f x Ef
n�
� � �
� � � �0 . (16)
Ñëåäîâàòåëüíî, äëÿ íàõîæäåíèÿ òî÷êè x * ìîæíî èñïîëüçîâàòü ìåòîä ýëëèïñî-
èäîâ, óñòàíîâèâ ñòàðòîâóþ òî÷êó x0 , íà÷àëüíûé ðàäèóñ r R0
è ìàòðèöó
B I n0
, ãäå I n – åäèíè÷íàÿ n n -ìàòðèöà.  êà÷åñòâå êðèòåðèÿ îñòàíîâà ìîæ-
íî èñïîëüçîâàòü óñëîâèå r B g xk k f k|| ( ) ||T � �, êîòîðîå ïðè ñêîëü óãîäíî ìàëîì
� ïîçâîëÿåò íàéòè òî÷êó x xk�
*
, äëÿ êîòîðîé f x f( ) .* *
� �� � Ýòî ñëåäóåò èç
ñïðàâåäëèâîñòè íåðàâåíñòâà
r B x x B x x
B g x
B g x
k k k k k
k f k
k f k
� � � �� �|| ( ) || ( ),
( )
|| (
* *1 1
T
T ) ||
�
�
�
�
�
�
�
�
�( , ( ))
|| ( ) ||
( )
|| ( ) ||
* *x x g x
B g x
f x f
B g x
k f k
k f k
k
k f k
T T
,
êîòîðîå èìååò ìåñòî äëÿ âûïóêëîé ôóíêöèè f x( ) ñ ó÷åòîì íåðàâåíñòâà (16).
Îáùàÿ çàäà÷à âûïóêëîãî ïðîãðàììèðîâàíèÿ. Íàéòè
f f x f x
x E n
0 0 0
* *( ) min ( )
�
(17)
ïðè îãðàíè÷åíèÿõ
f x i mi ( ) , , , ,�
0 1 2 � , (18)
ãäå f xi ( ) — âûïóêëûå ôóíêöèè, îïðåäåëåííûå íà E n , i m
0 1, , ,� . Ïóñòü
g xi ( ) — ñîîòâåòñòâóþùèå ñóáãðàäèåíòû, i m
0 1, , ,� . Èçâåñòíî, ÷òî îïòè-
ìàëüíàÿ òî÷êà x * ñóùåñòâóåò è íàõîäèòñÿ â øape S x R( , )0 (ôîðìàëüíî ê ñèñ-
òåìå îãðàíè÷åíèé (18) ìîæíî äîáàâèòü îãðàíè÷åíèå || ||x x R� �0 ), à òàêæå âû-
ïîëíåíî óñëîâèå Ñëåéòåðà äëÿ çàäà÷è (17), (18).
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4 77
Ðàññìîòðèì âåêòîðíîå ïîëå g x( ) , ïîñòðîåííîå ñëåäóþùèì îáðàçîì:
g x( )
g x f x
g x f x
i m
i
i
i m
i
0
1
1
0( ), max ( ) ,
( ), max ( )*
åñëè
åñëè
� �
� �
�
�
�
�
�
��
f xi* ( ) .0
(19)
Ïîêàæåì, ÷òî ( ( ), )*g x x x� � 0 ïðè âñåõ x E n� . Åñëè max ( )
1
0
� �
�
i m
if x , òî
g x g x( ) ( )
0 ,
( ( ), ) ( ( ), ) ( ) ( )* * *g x x x g x x x f x f x�
� � � �0 0 0 0 .
Åñëè max ( )
1
0
� �
�
i m
if x , òî g x g xi( ) ( )*
, ïðè÷åì f xi* ( ) � 0 , f xi*
*( ) � 0 ,
( ( ), ) ( ( ), ) ( ) ( )*
*
*
* *
*g x x x g x x x f x f xi i i�
� � � � 0 .
Òàêèì îáðàçîì, ñïðàâåäëèâî íåðàâåíñòâî ( ( ), )*g x x x� � 0 äëÿ âñåõ x E n� .
Ñëåäîâàòåëüíî, âû÷èñëÿÿ g x( ) ïî ôîðìóëå (19), äëÿ ëîêàëèçàöèè x * â çàäà-
÷å (17), (18) ìîæíî èñïîëüçîâàòü îáîáùåííûé ìåòîä ýëëèïñîèäîâ. Îòìåòèì, ÷òî
ýòîò ðåçóëüòàò íå èçìåíèòñÿ, åñëè âî âòîðîé ôîðìóëå (19) âìåñòî g xi* ( ) áðàòü gi ,
ãäå i – ïðîèçâîëüíûé èíäåêñ, äëÿ êîòîðîãî f xi ( ) � 0. Îñòàíîâ ïî óñëîâèþ
r B g xk k k|| ( ) ||T
0 � � ïîçâîëÿåò íàéòè òî÷êó x xk�
*
, äëÿ êîòîðîé f x f0 0( )* *
� �� � ,
÷òî ñëåäóåò èç ñïðàâåäëèâîñòè íåðàâåíñòâà
r B x x B x x
B g x
B g x
k k k k k
k k
k k
� � � �� �|| ( ) || ( ),
( )
|| (
* *1 1 0
0
T
T ) ||
�
�
�
�
�
�
�
�
�( , ( ))
|| ( ) ||
( )
|| ( )
* *x x g x
B g x
f x f
B g x
k k
k k
k
k k
0
0
0 0
0
T T ||
äëÿ âûïóêëîé ôóíêöèè f x0 ( ) .
Çàäà÷à î ñåäëîâîé òî÷êå. Ïóñòü çàäàíà âûïóêëî-âîãíóòàÿ ôóíêöèÿ f x y( , )
âåêòîðíûõ ïåðåìåííûõ x E n� , y E m� , z x y E E En m n m
� � �{ , } , z * — ñåä-
ëîâàÿ òî÷êà ýòîé ôóíêöèè, z0 — çàäàííîå íà÷àëüíîå ïðèáëèæåíèå, ïðè ýòîì èç-
âåñòíî, ÷òî || ||*z z R0 � � .
Ïðåäñòàâèì ïñåâäîãðàäèåíòíîå ìíîæåñòâî G z G x y G x y
f
x
f
y( ) ( , ) ( ( , ))
� ,
ãäå G x y
f
x ( , ) — ìíîæåñòâî ÷àñòíûõ ñóáãðàäèåíòîâ ôóíêöèè f x y( , ) , ðàññìàòðè-
âàåìîé êàê ôóíêöèÿ îò x ïðè ôèêñèðîâàííîì y ; G x y
f
y ( , ) — ìíîæåñòâî ÷àñòíûõ
ñóïåðãðàäèåíòîâ ôóíêöèè f x y( , ) ïî y ïðè ôèêñèðîâàííîì x. Ïóñòü âåêòîðíîå
ïîëå g z( ) ïîñòðîåíî ñëåäóþùèì îáðàçîì:
g z g z g z g z G z g z G z
f
x
f
y
f
x
f
x
g
y
f
y( ) { ( ), ( )}, ( ) ( ), ( ) ( )
� � � . (20)
Èç îïðåäåëåíèÿ ñåäëîâîé òî÷êè ñëåäóåò, ÷òî f x y f x y f x y( , ) ( , ) ( , )* * * *� � .
Ïîýòîìó
0 � �
� � � �f x y f x y f x y f x y f x y f x y( , ) ( , ) ( , ) ( , ) ( , ) ( , )* * * *
� � � �
�( ( ), ) ( ( ), ) ( ( ), ),* * *g z x x g z y y g z z z
f
x
g
y
78 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4
îòêóäà ñëåäóåò, ÷òî ( ( ), )*g z z z� � 0 äëÿ âñåõ z E n m� � . Òàêèì îáðàçîì, âû-
÷èñëÿÿ g z( ) ïî ôîðìóëå (20), äëÿ ëîêàëèçàöèè ñåäëîâîé òî÷êè z * ìîæíî ïðè-
ìåíÿòü îáîáùåííûé ìåòîä ýëëèïñîèäîâ.
Îáîáùåííûé ìåòîä ýëëèïñîèäîâ èìååò è äðóãèå ïðèìåíåíèÿ, íàïðèìåð ïðè
ðåøåíèè êîîðäèíèðóþùèõ íåãëàäêèõ çàäà÷ íåáîëüøèõ ðàçìåðíîñòåé, êîòîðûå
èìåþò ìåñòî â ñõåìàõ äåêîìïîçèöèè (ïî îãðàíè÷åíèÿì, ïî ïåðåìåííûì), â ñïå-
öèàëüíûõ âûïóêëûõ çàäà÷àõ ñ íåáîëüøèì êîëè÷åñòâîì ïåðåìåííûõ ïðè ïàðà-
ìåòðè÷åñêè çàäàííîì ñåìåéñòâå îãðàíè÷åíèé è äð. Îñíîâíîå òðåáîâàíèå ïðèìå-
íåíèÿ — îïðåäåëèòü ïðàâèëî ïîñòðîåíèÿ îòñåêàþùèõ âåêòîðîâ, êîòîðûå ëîêàëè-
çóþò èñêîìóþ òî÷êó, è óñëîâèÿ îñòàíîâà èòåðàöèîííîãî ïðîöåññà â îáîáùåííîì
ìåòîäå ýëëèïñîèäîâ.
ÇÀÊËÞ×ÅÍÈÅ
 ðàìêàõ ñåìåéñòâà ìåòîäîâ ñ ðàñòÿæåíèåì ïðîñòðàíñòâà îïèñàíà îáùàÿ ñõå-
ìà ìåòîäà ýëëèïñîèäîâ, êîòîðàÿ ïîçâîëÿåò ïîëó÷àòü ñõîäÿùèåñÿ ñî ñêîðîñòüþ
ãåîìåòðè÷åñêîé ïðîãðåññèè àëãîðèòìû îïèñàííûõ ýëëèïñîèäîâ äëÿ íàõîæäå-
íèÿ íåêîòîðûõ ñòàöèîíàðíûõ òî÷åê ãðàäèåíòíûõ ïîëåé. Ïðè ýòîì ïîêàçàòåëü
ãåîìåòðè÷åñêîé ïðîãðåññèè çàâèñèò ëèøü îò ðàçìåðíîñòè ïðîñòðàíñòâà è íå
çàâèñèò îò ñâîéñòâ ãðàäèåíòíîãî ïîëÿ. Èñïîëüçîâàíèå ýòèõ àëãîðèòìîâ öåëå-
ñîîáðàçíî ïðè ïîëó÷åíèè îöåíîê ñëîæíîñòè äëÿ àëãîðèòìîâ ðåøåíèÿ ñïåöè-
àëüíûõ êëàññîâ çàäà÷ ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ, çàäà÷ ïîèñêà òî÷åê
ðàâíîâåñèÿ, âêëþ÷àÿ îáîáùåííûå ðàâíîâåñèÿ Íýøà [8, 9], à òàêæå äëÿ ðåøå-
íèÿ ñèñòåì íåëèíåéíûõ óðàâíåíèé ñ îãðàíè÷åíèÿìè, âàðèàöèîííûõ íåðà-
âåíñòâ è êîìïëåìåíòàðíûõ çàäà÷. Åñëè ýòè àëãîðèòìû èñïîëüçóþòñÿ äëÿ ðå-
øåíèÿ ñëîæíûõ êîîðäèíèðóþùèõ ïîäçàäà÷, â êîòîðûõ ÷èñëî ïåðåìåííûõ íå
áîëåå äåñÿòè, òî îíè áóäóò ýôôåêòèâíûìè è ïðè ïðàêòè÷åñêèõ ïðèìåíåíèÿõ.
Ïîñòðîåííûå ýëëèïñîèäû ëîêàëèçàöèè öåëåñîîáðàçíî òàêæå èñïîëüçîâàòü
â îáùåé ñõåìå ïîñòðîåíèÿ ìåòîäîâ öåíòðîâ òÿæåñòè ïðîñòûõ òåë [10]. Åñëè èõ
ïðèìåíÿòü â ñî÷åòàíèè ñ ýëëèïñîèäàìè, ëîêàëèçóþùèìè ïåðåñå÷åíèå øàðà è
äâóõ ïîëóïðîñòðàíñòâ [11, 12], òî ñêîðîñòü ñõîäèìîñòè àëãîðèòìîâ îïèñàííûõ
ýëëèïñîèäîâ ìîæíî çíà÷èòåëüíî ïîâûñèòü. Òàêèå àëãîðèòìû áóäóò èìåòü òåîðå-
òè÷åñêóþ îöåíêó ñêîðîñòè ñõîäèìîñòè íå õóæå, ÷åì â ìåòîäå ýëëèïñîèäîâ
Þäèíà–Íåìèðîâñêîãî–Øîðà, à ïðàêòè÷åñêóþ — ñìîãóò ïðèáëèçèòü ê
ýôôåêòèâíîñòè r-àëãîðèòìîâ Øîðà.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Þäèí Ä.Á., Íåìèðîâñêèé À.Ñ. Èíôîðìàöèîííàÿ ñëîæíîñòü è ýôôåêòèâíûå ìåòîäû ðåøåíèÿ
âûïóêëûõ ýêñòðåìàëüíûõ çàäà÷. Ýêîíîìèêà è ìàòåìàòè÷åñêèå ìåòîäû. 1976. Âûï. 2.
Ñ. 357–369.
2. Øîð Í.Ç. Ìåòîä îòñå÷åíèÿ ñ ðàñòÿæåíèåì ïðîñòðàíñòâà äëÿ ðåøåíèÿ çàäà÷ âûïóêëîãî ïðî-
ãðàììèðîâàíèÿ. Êèáåðíåòèêà. 1977. ¹ 1. Ñ. 94–95.
3. Ñòåöþê Ï.È. Îáùàÿ ñõåìà ìåòîäà ýëëèïñîèäîâ. Èíôîðìàöèîííûé áþëëåòåíü ÀÌÏ ¹ 13.
Åêàòåðèíáóðã: ÓðÎ ÐÀÍ, 2015. Ñ. 59–60.
4. Ñòåöþê Ï.È. Îá îäíîì îáîáùåíèè êëàññè÷åñêîãî ìåòîäà ýëëèïñîèäîâ. ²íôîðìàòèêà òà ñèñ-
òåìí³ íàóêè (²ÑÍ–2015): Ìàòåð³àëè VI Âñåóêð. íàóê.-ïðàêò. êîíô. çà ì³æíàðîäíîþ ó÷àñòþ
(ì. Ïîëòàâà, 19–21 áåðåçíÿ 2015 ðîêó). Ïîëòàâà: ÏÓÅÒ, 2015. Ñ. 335–337.
5. Øîð Í.Ç. Ìåòîäû ìèíèìèçàöèè íåäèôôåðåíöèðóåìûõ ôóíêöèé è èõ ïðèëîæåíèÿ. Êè¿â: Íàóê.
äóìêà, 1979. 200 ñ. (Ïåð. ñ àíãë.: Shor N.Z. Minimization methods for non-differetiable functions.
Berlin: Springer–Verlag, 1985. 178 p.).
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4 79
6. Ñòåöþê Ï.È. Ïðèáëèæåííûé ìåòîä ýëëèïñîèäîâ. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2003.
¹ 3. Ñ. 141–146.
7. Øîð Í.Ç. Íîâûå íàïðàâëåíèÿ â ðàçâèòèè ìåòîäîâ íåãëàäêîé îïòèìèçàöèè. Êèáåðíåòèêà.
1977. ¹ 6. Ñ. 87–91.
8. Fischer A., Herrich M., Sch��onefeld K. Generalized Nash equilibrium problems — recent advances
and challenges. Pesquisa Operacional. 2014. Vol. 34. P. 521–558.
9. Daryina A.N., Izmailov A.F. Newton-type method for variational equilibrium problem. VIII Ìîñêîâ-
ñêàÿ ìåæäóíàðîä. êîíô. ïî èññëåäîâàíèþ îïåðàöèé (ORM2016). Ìîñêâà, 17–22 îêòÿáðÿ
2016 ãîäà. Òðóäû. Ò. 1. Ìîñêâà: ÌÀÊÑ Ïðåññ, 2016. Ñ. 21–22.
10. Ñòåöþê Ï.È. Ìåòîä öåíòðîâ òÿæåñòè ïðîñòûõ òåë. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 1996.
¹ 5. C. 117–138.
11. Ñòåöþê Ï.È. Ìåòîäû ýëëèïñîèäîâ è r-àëãîðèòìû. Êèøèíýó: Ýâðèêà, 2014. 488 ñ.
12. Ñòåöþê Ï.È. r-àëãîðèòìû è ýëëèïñîèäû. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 1996. ¹ 1.
C. 113–134.
Íàä³éøëà äî ðåäàêö³¿ 21.03.2018
Ï.². Ñòåöþê, Î.Â. Ôåñþê, Î.Ì. Õîì’ÿê
ÓÇÀÃÀËÜÍÅÍÈÉ ÌÅÒÎÄ Å˲ÏÑίIJÂ
Àíîòàö³ÿ. Íàâåäåíî àëãîðèòì ç ðîçòÿãîì ïðîñòîðó, ÿêèé çà ïåâíîãî âèáîðó
êîåô³ö³ºíòà ðîçòÿãó º ìåòîäîì îïèñàíèõ åë³ïñî¿ä³â. Éîãî ÷àñòêîâèì âèïàä-
êîì º ìåòîä åë³ïñî¿ä³â Þä³íà–Íåìèðîâñüêîãî–Øîðà. Îïèñàíî çàñòîñóâàííÿ
àëãîðèòìó äëÿ ðîçâ’ÿçàííÿ çàäà÷³ îïóêëîãî ïðîãðàìóâàííÿ ³ çàäà÷³ ïîøóêó
ñ³äëîâî¿ òî÷êè îïóêëî–óâ³ãíóòî¿ ôóíêö³¿.
Êëþ÷îâ³ ñëîâà: ìåòîä åë³ïñî¿ä³â, îïåðàòîð ðîçòÿãíåííÿ ïðîñòîðó, ëîêàë³çó-
þ÷èé åë³ïñî¿ä, çàäà÷à îïóêëîãî ïðîãðàìóâàííÿ, ñ³äëîâà òî÷êà îïóê-
ëî–óâ³ãíóòî¿ ôóíêö³¿.
P.I. Stetsyuk, O.V. Fesiuk, O.N. Khomyak
GENERALIZED ELLIPSOID METHOD
Abstract. An algorithm with space dilation is presented, which is the
circumscribed ellipsoid method under a certain choice of tensile coefficient. It is
shown that its partial case is the Yudin–Nemirovsky–Shor ellipsoid method. The
application of the algorithm for solving a convex programming problem and the
problem of finding a saddle point of a convex-concave function are described.
Keywords: ellipsoid method, space dilation operator, localizing ellipsoid, convex
programming problem, saddle point of convex-concave function.
Ñòåöþê Ïåòð Èâàíîâè÷,
äîêòîð ôèç.-ìàò. íàóê, çàâåäóþùèé îòäåëîì Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà, Êèåâ,
e-mail: stetsyukp@gmail.com.
Ôåñþê Àëåêñàíäð Âëàäèìèðîâè÷,
âåäóùèé èíæåíåð-ïðîãðàììèñò Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà, Êèåâ,
e-mail: sasha.fesyuk@gmail.com.
Õîìÿê Îëüãà Íèêîëàåâíà,
êàíäèäàò ôèç.-ìàò. íàóê, íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà, Êèåâ,
e-mail: khomiak.olha@gmail.com.
80 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4
|