Точные двойственные оценки для некоторых невыпуклых минимаксных квадратичных оптимизационных задач
Исследована невыпуклая сепарабельная минимаксная квадратичная оптимизационная задача. Изложено 2 подхода к ее решению: с помощью SOCP-релаксации и лагранжевой релаксации квадратичной экстремальной задачи-аналога. Получено условие, выполнение которого гарантирует нахождение значения и точки глобально...
Gespeichert in:
| Datum: | 2021 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2021
|
| Schriftenreihe: | Кібернетика та системний аналіз |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/190589 |
| 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: | Точные двойственные оценки для некоторых невыпуклых минимаксных квадратичных оптимизационных задач / О.А. Березовский // Кібернетика та системний аналіз. — 2021. — Т. 57, № 1. — С. 115–122. — Бібліогр.: 30 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-190589 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1905892023-06-14T14:20:27Z Точные двойственные оценки для некоторых невыпуклых минимаксных квадратичных оптимизационных задач Березовский, О.А. Системний аналіз Исследована невыпуклая сепарабельная минимаксная квадратичная оптимизационная задача. Изложено 2 подхода к ее решению: с помощью SOCP-релаксации и лагранжевой релаксации квадратичной экстремальной задачи-аналога. Получено условие, выполнение которого гарантирует нахождение значения и точки глобального экстремума задачи рассматриваемого класса вычислением двойственной оценки эквивалентной квадратичной экстремальной задачи. Досліджено неопуклу сепарабельну мінімаксну квадратичну оптимізаційну задачу. Наведено два підходи до її розв'язання: за допомогою SOCP-релаксації і лагранжевої релаксації квадратичної екстремальної задачі-аналога. Отримано умову, виконання якої гарантує знаходження значення і точки глобального екстремуму задачі розглянутого класу обчисленням двоїстої оцінки еквівалентної квадратичної екстремальної задачі. Nonconvex separable minimax quadratic optimization problem is analyzed. Two approaches to solve the problem are described, namely, by using SOCP-relaxation and by using Lagrangian relaxation of a quadratic extremum analog problem. A condition is obtained whose fulfillment guarantees finding the value and the global extremum point of the problem of the considered class by calculating the dual bound of the equivalent quadratic extremum problem. 2021 Article Точные двойственные оценки для некоторых невыпуклых минимаксных квадратичных оптимизационных задач / О.А. Березовский // Кібернетика та системний аналіз. — 2021. — Т. 57, № 1. — С. 115–122. — Бібліогр.: 30 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/190589 519.8 ru Кібернетика та системний аналіз Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системний аналіз Системний аналіз |
| spellingShingle |
Системний аналіз Системний аналіз Березовский, О.А. Точные двойственные оценки для некоторых невыпуклых минимаксных квадратичных оптимизационных задач Кібернетика та системний аналіз |
| description |
Исследована невыпуклая сепарабельная минимаксная квадратичная оптимизационная задача. Изложено 2 подхода к ее решению: с помощью SOCP-релаксации и лагранжевой релаксации квадратичной экстремальной задачи-аналога. Получено условие, выполнение которого гарантирует нахождение значения и точки глобального экстремума задачи рассматриваемого класса вычислением двойственной оценки эквивалентной квадратичной экстремальной задачи. |
| format |
Article |
| author |
Березовский, О.А. |
| author_facet |
Березовский, О.А. |
| author_sort |
Березовский, О.А. |
| title |
Точные двойственные оценки для некоторых невыпуклых минимаксных квадратичных оптимизационных задач |
| title_short |
Точные двойственные оценки для некоторых невыпуклых минимаксных квадратичных оптимизационных задач |
| title_full |
Точные двойственные оценки для некоторых невыпуклых минимаксных квадратичных оптимизационных задач |
| title_fullStr |
Точные двойственные оценки для некоторых невыпуклых минимаксных квадратичных оптимизационных задач |
| title_full_unstemmed |
Точные двойственные оценки для некоторых невыпуклых минимаксных квадратичных оптимизационных задач |
| title_sort |
точные двойственные оценки для некоторых невыпуклых минимаксных квадратичных оптимизационных задач |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2021 |
| topic_facet |
Системний аналіз |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/190589 |
| citation_txt |
Точные двойственные оценки для некоторых невыпуклых минимаксных квадратичных оптимизационных задач / О.А. Березовский // Кібернетика та системний аналіз. — 2021. — Т. 57, № 1. — С. 115–122. — Бібліогр.: 30 назв. — рос. |
| series |
Кібернетика та системний аналіз |
| work_keys_str_mv |
AT berezovskijoa točnyedvojstvennyeocenkidlânekotoryhnevypuklyhminimaksnyhkvadratičnyhoptimizacionnyhzadač |
| first_indexed |
2025-07-16T13:32:20Z |
| last_indexed |
2025-07-16T13:32:20Z |
| _version_ |
1837810572663455744 |
| fulltext |
ÓÄÊ 519.8
Î.À. ÁÅÐÅÇÎÂÑÊÈÉ
ÒÎ×ÍÛÅ ÄÂÎÉÑÒÂÅÍÍÛÅ ÎÖÅÍÊÈ ÄËß ÍÅÊÎÒÎÐÛÕ
ÍÅÂÛÏÓÊËÛÕ ÌÈÍÈÌÀÊÑÍÛÕ ÊÂÀÄÐÀÒÈ×ÍÛÕ
ÎÏÒÈÌÈÇÀÖÈÎÍÍÛÕ ÇÀÄÀ×
Àííîòàöèÿ. Èññëåäîâàíà íåâûïóêëàÿ ñåïàðàáåëüíàÿ ìèíèìàêñíàÿ êâàäðà-
òè÷íàÿ îïòèìèçàöèîííàÿ çàäà÷à. Èçëîæåíî äâà ïîäõîäà ê åå ðåøåíèþ: ñ ïî-
ìîùüþ SOCP-ðåëàêñàöèè è ëàãðàíæåâîé ðåëàêñàöèè êâàäðàòè÷íîé ýêñòðå-
ìàëüíîé çàäà÷è-àíàëîãà. Ïîëó÷åíî óñëîâèå, âûïîëíåíèå êîòîðîãî ãàðàíòè-
ðóåò íàõîæäåíèå çíà÷åíèÿ è òî÷êè ãëîáàëüíîãî ýêñòðåìóìà çàäà÷è
ðàññìàòðèâàåìîãî êëàññà âû÷èñëåíèåì äâîéñòâåííîé îöåíêè ýêâèâàëåíòíîé
êâàäðàòè÷íîé ýêñòðåìàëüíîé çàäà÷è.
Êëþ÷åâûå ñëîâà: ìèíèìàêñíàÿ êâàäðàòè÷íàÿ îïòèìèçàöèîííàÿ çàäà÷à,
SOCP-ðåëàêñàöèÿ, ëàãðàíæåâà ðåëàêñàöèÿ, òî÷íàÿ äâîéñòâåííàÿ îöåíêà, ïî-
ëîæèòåëüíî-îïðåäåëåííàÿ ìàòðèöà.
ÂÂÅÄÅÍÈÅ
Ìíîãèå çàäà÷è, ñâÿçàííûå ñ îïòèìàëüíûì óïðàâëåíèåì, ïëàíèðîâàíèåì, ïðîåê-
òèðîâàíèåì, ìîäåëèðîâàíèåì, àíàëèçîì ñåòåâûõ ñòðóêòóð è äðóãèìè íàïðàâëå-
íèÿìè, äîïóñêàþò ïðåäñòàâëåíèå â âèäå êâàäðàòè÷íûõ îïòèìèçàöèîííûõ çà-
äà÷ [1–11]. Çíà÷èìîñòü êëàññà êâàäðàòè÷íûõ çàäà÷ ïîäòâåðæäàåò è òîò ôàêò,
÷òî ê íèì îòíîñèòñÿ øèðîêèé êðóã çàäà÷ ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ:
âûïóêëûå è íåâûïóêëûå çàäà÷è ìèíèìèçàöèè êâàäðàòè÷íîé ôóíêöèè íà ëèíåé-
íûõ îãðàíè÷åíèÿõ, çàäà÷è ìèíèìèçàöèè êâàäðàòè÷íîé ôóíêöèè ñ áèíàðíûìè
ïåðåìåííûìè, ëèíåéíàÿ çàäà÷à êîìïëåìåíòàðíîñòè, êâàäðàòè÷íàÿ çàäà÷à î íà-
çíà÷åíèè, ýêñòðåìàëüíûå çàäà÷è íà ãðàôàõ (íàïðèìåð, çàäà÷è ðàñêðàøèâàíèÿ
è ðàçáèåíèÿ ãðàôîâ, íàõîæäåíèå ìàêñèìàëüíîãî íåçàâèñèìîãî ìíîæåñòâà, ìàê-
ñèìàëüíîãî k-êëàáà) è ò.ä. Áîëåå òîãî, ê âèäó êâàäðàòè÷íûõ îïòèìèçàöèîííûõ
çàäà÷ ñâîäèòñÿ áîëåå øèðîêèé êëàññ ïîëèíîìèàëüíûõ îïòèìèçàöèîííûõ çàäà÷
(â êîòîðûõ öåëåâàÿ ôóíêöèÿ è âñå ôóíêöèè îãðàíè÷åíèé ïîëèíîìèàëüíû), íà-
õîæäåíèå ðåøåíèÿ ñèñòåì ïîëèíîìèàëüíûõ óðàâíåíèé ñ äåéñòâèòåëüíûìè è áó-
ëåâûìè ïåðåìåííûìè è ò.ä.
 îáùåì ñëó÷àå êâàäðàòè÷íàÿ îïòèìèçàöèîííàÿ çàäà÷à îòíîñèòñÿ ê êëàññó
NP-òðóäíûõ çàäà÷, â ñâÿçè ñ ÷åì âîçíèêàåò èíòåðåñ ê èññëåäîâàíèþ äàííîãî êëàññà
çàäà÷ ñ èñïîëüçîâàíèåì ðàçëè÷íîãî òèïà âûïóêëûõ ðåëàêñàöèé, â ÷àñòíîñòè
SDP-ðåëàêñàöèé (semidefinite programming relaxations) [1, 2, 12], SOCP-ðåëàêñàöèé
(second-order cone programming relaxations) [2, 13], ëàãðàíæåâûõ ðåëàêñàöèé
(lagrangian relaxations) [1, 14, 15], ëèíåéíûõ ðåëàêñàöèé (linear programming
relaxations) [16]. Îäíèì èç îñíîâíûõ íàïðàâëåíèé ýòèõ èññëåäîâàíèé ÿâëÿåòñÿ âûäå-
ëåíèå ñïåöèàëüíûõ ïîäêëàññîâ êâàäðàòè÷íûõ çàäà÷, äëÿ êîòîðûõ ðåëàêñàöèè ïîçâî-
ëÿþò íàéòè çíà÷åíèå ãëîáàëüíîãî ýêñòðåìóìà, à âîçìîæíî, è òî÷êó ãëîáàëüíîãî ýêñ-
òðåìóìà [1, 17–25]. Äàííàÿ ðàáîòà ïîñâÿùåíà îïðåäåëåíèþ òàêîãî ïîäêëàññà äëÿ íå-
âûïóêëîé ñåïàðàáåëüíîé êâàäðàòè÷íîé îïòèìèçàöèîííîé çàäà÷è ñ öåëåâîé
ôóíêöèåé â âèäå ôóíêöèè ìàêñèìóìà p êâàäðàòè÷íûõ ôóíêöèé ïðè q êâàäðàòè÷-
íûõ îãðàíè÷åíèÿõ-íåðàâåíñòâàõ (âñå êâàäðàòè÷íûå ôóíêöèè çàäà÷è ñåïàðàáåëüíûå):
f f x x A x a x
x R i p
i i i i
n
�
� � �
� � � �
�
�
�
�
inf max ( )
1
1
2
T T � (1)
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 115
© Î.À. Áåðåçîâñêèé, 2021
ïðè îãðàíè÷åíèÿõ
g x x B x b xi j j j( ) � � � �
1
2
0T T � , j q�1, ,� , (2)
ãäå Ai , i p�1, ,� , è B j , j q�1, ,� , — äèàãîíàëüíûå ìàòðèöû ðàçìåðà n n
,
A A A Ai i i in� diag ( , , , )1 2 � , i p�1, ,� ,
B B B Bj j j jn� diag ( , , , )1 2 � , j q�1, ,� ,
ai , i p�1, ,� , è b j , j q�1, ,� , — n-ìåðíûå âåêòîðû, � i , i p�1, ,� , è � j ,
j q�1, ,� , — âåùåñòâåííûå ÷èñëà.
Çàäà÷à âèäà (1), (2) îõâàòûâàåò ðàçëè÷íûå âàæíûå êëàññû ñïåöèàëüíî ñòðóê-
òóðèðîâàííûõ ìèíèìàêñíûõ êâàäðàòè÷íûõ îïòèìèçàöèîííûõ çàäà÷ [17], òàêèõ
êàê íåêîòîðûå ìèíèìàêñíûå îäíîðîäíûå êâàäðàòè÷íûå îïòèìèçàöèîííûå çàäà÷è,
çàäà÷è î ìàêñèìàëüíîé äèñïåðñèè, ìèíèìàêñíûå çàäà÷è ñ äîâåðèòåëüíîé îáëàñ-
òüþ, ðîáàñòíûå êâàäðàòè÷íûå çàäà÷è ïðè óñëîâèè íåêîòîðîé îãðàíè÷åííîñòè íà
íåîïðåäåëåííîñòü äàííûõ. Â îáùåé ïîñòàíîâêå ýòè íåâûïóêëûå ìèíèìàêñíûå
êâàäðàòè÷íûå çàäà÷è ÿâëÿþòñÿ NP-òðóäíûìè (íàïðèìåð, â ðàáîòå [26] äîêàçàíî,
÷òî çàäà÷à î ìàêñèìàëüíîé äèñïåðñèè îòíîñèòñÿ ê NP-òðóäíûì çàäà÷àì).
 êà÷åñòâå ïðîñòåéøåãî èëëþñòðàòèâíîãî ïðèìåðà âîçíèêíîâåíèÿ çàäà÷è
âèäà (1), (2) ðàññìîòðèì ñëåäóþùóþ íåîïðåäåëåííóþ çàäà÷ó êâàäðàòè÷íîé
îïòèìèçàöèè [17]:
min :
( , )x x R
a x a x x x
1 2
2
1 1
2
2 2
2
1
2
1
2 1
�
� � �{ },
ãäå ïàðàìåòðû ( , )a a1 2 íå îïðåäåëåíû îäíîçíà÷íî, à ïðèíàäëåæàò èíòåðâàëó
M �
�
�
�
�
�
�
�� �
��
�
�
�
�
� �
�
�
�
�
� � �
1
1
1
1
1
0 1( ) : [ , ] .
Òîãäà åå ðîáàñòíûé àíàëîã [24, 27], êîòîðûé íàõîäèò ðåøåíèå íàèõóäøåãî
ñëó÷àÿ íåîïðåäåëåííîé çàäà÷è, ìîæíî ñôîðìóëèðîâàòü ñëåäóþùèì îáðàçîì:
min max :
( , ) ( , )x x R a a M
a x a x x x
1 2
2
1 2
1 1
2
2 2
2
1
2
1
2
� �
�
�
� � �{ } 1
�
�
.
Äàííàÿ çàäà÷à ýêâèâàëåíòíà çàäà÷å
min {max , :
( , )x x R
x x x x x x
1 2
2 1
2
2
2
2
2
1
2
1
2
1
2 1
�
� � � �{ } }.
Òàêèì îáðàçîì, ïîëó÷åíà çàäà÷à, îòíîñÿùàÿñÿ ê êëàññó êâàäðàòè÷íûõ îïòèìèçà-
öèîííûõ çàäà÷ âèäà (1), (2), èññëåäîâàíèþ êîòîðîãî ïîñâÿùåíà íàñòîÿùàÿ ñòàòüÿ.
SOCP-ÐÅËÀÊÑÀÖÈß ÇÀÄÀ×È (1), (2)
 ðàáîòå [17] èññëåäîâàëàñü çàäà÷à, ïîñòàíîâêà êîòîðîé îòëè÷àåòñÿ îò çàäà-
÷è (1), (2) ëèøü òåì, ÷òî ìàòðèöû Ai , i p�1, ,� , è B j , j q�1, ,� , íå äèàãî-
íàëüíû, íî èõ ñîáñòâåííûå âåêòîðû îäèíàêîâû, ò.å. îíè ïðåäñòàâèìû â âèäå
A U A A A Ui i i in� diag T( , , , )1 2 � , i p�1, ,� ,
B U B B B Uj j j jn� diag T( , , , )1 2 � , j q�1, ,� ,
ãäå U — ìàòðèöà ñîáñòâåííûõ âåêòîðîâ.  äàëüíåéøåì, áåç îãðàíè÷åíèÿ îá-
ùíîñòè, áóäåì ñ÷èòàòü, ÷òî âñå ìàòðèöû èìåþò äèàãîíàëüíûé âèä (äîñòèãàåò-
ñÿ çàìåíîé ïåðåìåííûõ y U x� T ).
116 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
Äëÿ ïîëó÷åíèÿ íèæíåé îöåíêè çíà÷åíèÿ ãëîáàëüíîãî ýêñòðåìóìà ìèíèìàêñíîé
ñåïàðàáåëüíîé êâàäðàòè÷íîé îïòèìèçàöèîííîé çàäà÷è (1), (2) â [17] ïîñòðîåíà è èñ-
ñëåäîâàíà åå SOCP-ðåëàêñàöèÿ:
� �
� � �
�
�
� � �
� �
� sup
, , ,
,
R
R s R
p j
n n
1 0�
(3)
ïðè îãðàíè÷åíèÿõ
� �k ik
i
p
k jk
j
q
A B
� �
� �� �
1 1
0, k n�1, ,� ,
� � �� �
� �
� �k i
i
p
k j
j
q
a b
1 1
,
2 0
1 1 1
� � � � �i i
i
p
j j
j
q
k
k
n
s
� � �
� � �� �
�
�
�
�
�
�
�
�
� � ,
sk � 0, k n�1, ,� ,
2
1 1 1
� � � �k k i ik
i
p
j jk
j
q
k i ik
i
p
s A B s A, � �
�
�
�
�
�
�
�
�
� �
� � �
� � � �
�
� � j jk
j
q
B
1
, k n�1, ,� ,
ãäå � p i
i
p
px x x x R� � � �
�
�
�
�
�
�
���
�: , ,
1
1 0 .
Ëåììà 1 [17]. Ïóñòü f � — ðåøåíèå çàäà÷è (1), (2), �� — ðåøåíèå çàäà-
÷è (3). Òîãäà f � �� � .
Îñíîâíûì òåîðåòè÷åñêèì ðåçóëüòàòîì îòíîñèòåëüíî èñïîëüçîâàíèÿ äàííîé
SOCP-ðåëàêñàöèè (3) äëÿ ðåøåíèÿ çàäà÷è (1), (2) ÿâëÿåòñÿ äîñòàòî÷íîå óñëîâèå
òîãî, ÷òî îíà áóäåò òî÷íîé (ò.å. �� �� f — çíà÷åíèÿ ãëîáàëüíûõ ýêñòðåìóìîâ
èñõîäíîé çàäà÷è è åå SOCP-ðåëàêñàöèè ñîâïàäàþò). Ýòî óñëîâèå ñôîðìóëèðîâà-
íî â ñëåäóþùåé òåîðåìå.
Òåîðåìà 1 [17, òåîðåìà 2.1]. Åñëè äëÿ çàäà÷è (1), (2) ìíîæåñòâî
E f f f g g gp q( , , , , , , , )1 2 1 2� � �
� �
� �{( , ) :y z R R x Rp q n òàêîå, ÷òî f x y i pi i( ) , , , ,� �1 �
è g x z j qj j( ) , , ,� �1 � }
âûïóêëî è çàìêíóòî, òî �� �� f .
Óñëîâèå, ñôîðìóëèðîâàííîå â òåîðåìå 1, äîñòàòî÷íî æåñòêîå. Îíî òðåáóåò âû-
ïóêëîñòè âñåõ àêòèâíûõ êâàäðàòè÷íûõ ôóíêöèé, ó÷àñòâóþùèõ â ôîðìèðîâàíèè
ìíîæåñòâà E f f f g g gp q( , , , , , , , )1 2 1 2� � . Äàëåå èññëåäóåòñÿ òî÷íîñòü äðóãîãî
ïîäõîäà äëÿ ðåøåíèÿ çàäà÷è (1), (2): ïîñòðîåíèå ýêâèâàëåíòíîé êâàäðàòè÷íîé ïîñòà-
íîâêè äëÿ íåå è íàõîæäåíèå äëÿ ýòîé ïîñòàíîâêè äâîéñòâåííîé îöåíêè �� [1] (ëàã-
ðàíæåâà ðåëàêñàöèÿ ïî âñåì îãðàíè÷åíèÿì). Õîòÿ âû÷èñëèòåëüíàÿ ñëîæíîñòü ïîëó-
÷åíèÿ äâîéñòâåííîé îöåíêè âûøå, ÷åì ðåøåíèÿ SOCP-çàäà÷è, åå çíà÷åíèå, êàê ïðà-
âèëî, áîëåå òî÷íîå ïî îòíîøåíèþ ê f � . Îñîáî îòìåòèì, ÷òî äëÿ äâîéñòâåííîé
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 117
îöåíêè â çàäà÷å (1), (2) ìîæíî ñôîðìóëèðîâàòü äîñòàòî÷íîå óñëîâèå íóëåâîãî ðàç-
ðûâà äâîéñòâåííîñòè (óñëîâèå, ãàðàíòèðóþùåå �� �� f ), íå çàâèñÿùåå îò çíàêîâ
ñîáñòâåííûõ ÷èñåë ìàòðèö Ai , i p�1, ,� , è B j , j q�1, ,� , ñóùåñòâåííî âëèÿþùèõ
íà âûïóêëîñòü ìíîæåñòâà E f f f g g gp q( , , , , , , , )1 2 1 2� � , íà êîòîðîé îñíîâàíà òå-
îðåìà 1.
ÄÂÎÉÑÒÂÅÍÍÀß ÊÂÀÄÐÀÒÈ×ÍÀß ÎÖÅÍÊÀ ÇÀÄÀ×È (1), (2)
Äëÿ ïîëó÷åíèÿ äâîéñòâåííîé êâàäðàòè÷íîé îöåíêè äëÿ èñõîäíîé çàäà÷è (1), (2)
çàìåíèì åå íàèáîëåå î÷åâèäíîé ýêâèâàëåíòíîé êâàäðàòè÷íîé ýêñòðåìàëüíîé çà-
äà÷åé-àíàëîãîì
f t
t R x R n
�
� �
� inf
,1
, (4)
ïðè îãðàíè÷åíèÿõ
1
2
x A x a x ti i i
T T� � �� , i p�1, ,� , (5)
1
2
0x B x b xj j j
T T� � �� , j q�1, ,� , (6)
êîòîðóþ áóäåì èññëåäîâàòü äàëåå.
Äëÿ êâàäðàòè÷íîé ýêñòðåìàëüíîé çàäà÷è îáùåãî âèäà
f f x f x
x T R n
� �
� �
� �0 0( ) inf ( ), (7)
ãäå T x f x i I f x i Ii
LQ
i
EQ� � � � �{ }: ( ) , , ( ) ,0 0 , f x x A x b x ci i i i( ) � � �T T , i� �{ }0
� �I ILQ EQ — êâàäðàòè÷íûå ôóíêöèè â n-ìåðíîì ïðîñòðàíñòâå, äâîéñòâåí-
íàÿ îöåíêà �� îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì [1]:
� ��
� �
�� �
�
� � �
�
� �sup ( ) inf ( , )
u R x Rm n
u L u x f (8)
ïðè îãðàíè÷åíèÿõ
A u( ) �� 0 ,
u U u u i I u Ri
LQ m� � � � �� { }: , ,0 ,
ãäå L u x x A u x b u x c u( , ) ( ) ( ) ( )� � �T T — ôóíêöèÿ Ëàãðàíæà äëÿ çàäà÷è (7), A u( ) �
� �
�
�A u Ai i
i
m
0
1
, b u b u bi i
i
m
( ) � �
�
�0
1
, c u c u ci i
i
m
( ) � �
�
�0
1
, m I ILQ EQ� �| | | | , A � � 0
îáîçíà÷àåò ïîëîæèòåëüíî-ïîëóîïðåäåëåííóþ ìàòðèöó A . Äàëåå áóäåì ïðåäïî-
ëàãàòü, ÷òî îáëàñòü îïðåäåëåíèÿ äâîéñòâåííûõ ïåðåìåííûõ â çàäà÷å (8) èìååò
âíóòðåííèå òî÷êè.
 ðàáîòå [25] äëÿ êâàäðàòè÷íîé ýêñòðåìàëüíîé çàäà÷è îáùåãî âèäà (7) ïîëó-
÷åí êðèòåðèé (äîñòàòî÷íîå óñëîâèå) íàõîæäåíèÿ òî÷íîé äâîéñòâåííîé îöåíêè
�� (�� �� f ). Äëÿ òîãî ÷òîáû ñôîðìóëèðîâàòü ýòîò êðèòåðèé, ââåäåì îáîçíà÷å-
íèå �� äëÿ ìíîæåñòâà ãðàíè÷íûõ òî÷åê ìíîæåñòâà { }u A u u R m: ( ) ,� � �0 , óäîâ-
ëåòâîðÿþùèõ óñëîâèþ ui � 0, i I LQ� , è îïðåäåëèì äëÿ êàæäîãî u� ��
ìíîæåñòâî
J u j u j nj( ) : ( ) , , ,� � �{ { }}� 0 1 � ,
ãäå � j u( ), j n�{ }1, ,� , — ñîáñòâåííûå ÷èñëà ìàòðèöû A u( ). Îáîçíà÷èì j u( )
ñîáñòâåííûå âåêòîðû, ñîîòâåòñòâóþùèå ñîáñòâåííûì ÷èñëàì � j u( ).  ýòèõ
îáîçíà÷åíèÿõ èìååò ìåñòî ñëåäóþùàÿ òåîðåìà.
118 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
Òåîðåìà 2 [25]. Åñëè ñóùåñòâóþò òàêîé âåêòîð p è òàêîå ïîëîæèòåëüíîå
÷èñëî ~
� 0, ÷òî äëÿ ëþáîãî
�( , ~ )0
� � �u � � �j J u( ) òàêîå, ÷òî
j i i
i
m
u b u b pT ( ) 0
1
0� �
�
�
�
�
�
�
�
�
�
�
� , (9)
òî äâîéñòâåííàÿ îöåíêà �� (8) äëÿ êâàäðàòè÷íîé ýêñòðåìàëüíîé çàäà÷è (7) ÿâ-
ëÿåòñÿ òî÷íîé (�� �� f ). Ïðè÷åì åñëè óñëîâèå (9) âûïîëíÿåòñÿ ïðè p � 0 , òî
âåêòîð
x x u A u b u� � � � �� � �( ) ( ) ( ) /1 2
ðåøåíèÿ çàäà÷è (8) ÿâëÿåòñÿ è ðåøåíèåì çàäà÷è (7).
Îòìåòèì, ÷òî â ôîðìóëèðîâêå òåîðåìû 2 ïðè âûïîëíåíèè óñëîâèÿ (9) äëÿ
p � 0 ìàòðèöà A u( )� âñåãäà ïîëîæèòåëüíî îïðåäåëåíà.
Âîñïîëüçóåìñÿ òåîðåìîé 2 äëÿ èññëåäîâàíèÿ ñëó÷àåâ, êîãäà äëÿ êâàäðàòè÷-
íîé çàäà÷è (4)–(6) äâîéñòâåííûé ïîäõîä ãàðàíòèðóåò íàõîæäåíèå îïòèìàëüíîãî
çíà÷åíèÿ åå öåëåâîé ôóíêöèè (ïðè �� �� f ).
Ôóíêöèÿ Ëàãðàíæà çàäà÷è (4)–(6) èìååò ñëåäóþùèé âèä:
L x t u t x A x a x t u xi i i i
i
p
j( , , , )� � �� � � � �
�
�
�
�
�
��
�
�
1
2
1
21
T T T B x b xj j j
j
q
� �
�
�
�
�
�
� �
�
� T �
1
� �
�
�
�
�
�
�
�
�
� � �
�
�1
1
� � � �i
i
p
t x A u x b u x c uT T( , ) ( , ) ( , ) ,
ãäå
A u A u B k ni ik
i
p
j jk
j
q
( , ) , , ,� �� �
�
�
�
�
�
�
�
�
�
� �
� �diag
1
2
1
1 1
�
�
�
�
�
�
�
�
�
,
b u a u bi i
i
p
j j
j
q
( , )� �� �
� �
� �
1 1
,
c u ui i
i
p
j j
j
q
( , )� � � �� �
� �
� �
1 1
,
u, � � 0.
Ïîñêîëüêó ïî ïåðåìåííîé t êâàäðàòè÷íûé ÷ëåí îòñóòñòâóåò, òî÷êè ýôôåêòèâ-
íîãî ìíîæåñòâà äâîéñòâåííîé ôóíêöèè äîëæíû óäîâëåòâîðÿòü ñëåäóþùåìó
óñëîâèþ ðàâåíñòâà íóëþ êîýôôèöèåíòà ïðè ëèíåéíîì ÷ëåíå ïî t (èíà÷å ðåøå-
íèå âíóòðåííåé çàäà÷è ðàâíî � ):
� i
i
p
�
� �
1
1.
Ïðè âûïîëíåíèè ýòîãî óñëîâèÿ ïåðåìåííàÿ t èñêëþ÷àåòñÿ èç çàäà÷è íàõîæäå-
íèÿ äâîéñòâåííîé îöåíêè, äàëåå áóäåì «ðàáîòàòü» ñ ôóíêöèåé L x u( , , , )0 � .
Âñå ñîáñòâåííûå âåêòîðû ìàòðèöû A u( , )� íàïðàâëåíû ïî êîîðäèíàòíûì
îñÿì è íå çàâèñÿò îò äâîéñòâåííûõ ïåðåìåííûõ, à ñîáñòâåííûå ÷èñëà îïðåäåëÿ-
þòñÿ òàêèì îáðàçîì:
� � �k i ik
i
p
j ik
j
q
u A u B( , ) � �
�
�
�
�
�
�
�
�
� �
� �
1
2 1 1
, k n�1, .
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 119
Ñëåäîâàòåëüíî, äëÿ çàäà÷è (4)–(6) ìíîæåñòâî ãðàíè÷íûõ òî÷åê ìíîæåñòâà
{ }u A u u R m: ( ) ,� � �0 , óäîâëåòâîðÿþùèõ óñëîâèþ ui � 0, i I LQ� , èìååò âèä
� � �
� �
� ! �
�
�
��
�
�
�� ��( \ ) : min
, ,
D D U
u
A u B
k n
i ik
i
p
j jk
j
�
�
1
1
� � �
� �
�
�
�
�
�
�
�
�
� � �
�
�
�
�
�
�
��1 1
0 1 0
q
i
p
i u; ; ,� � .
Ïîäñòàíîâêîé â óñëîâèå (9) ïðè p � 0 ñîîòâåòñòâóþùèõ çíà÷åíèé ïàðàìåò-
ðîâ çàäà÷è (4)–(6) ïîëó÷àåì
� � �
k k i i
i
p
j j
j
q
u b u e a u bT T( , ) ( , ) � �
�
�
�
�
�
�
�
�
�
� �
� �
1 1
0 ,
ãäå k ku e( ) � , k n�1, , — ñîáñòâåííûå âåêòîðû ìàòðèöû A u( , )� , ek — n-ìåð-
íûé âåêòîð, k-ÿ êîìïîíåíòà êîòîðîãî ðàâíà åäèíèöå, à îñòàëüíûå ðàâíû
íóëþ. Òàêèì îáðàçîì, óñëîâèå (9) äëÿ çàäà÷è (4)–(6) ïðè p � 0 ïðèìåò âèä
�
�
�
�
�
�
��
�
�
�
�
�
� �
� � �
� �
u u
A u B
k n
i ik
i
p
j jk
j
q
� �
�: min
, ,1 1 1�
�
�
�
�
�
�
�
�
� �
�
�
�
�
�
� �
�
�
�
�
�
�
���
�0 1 0
1
; ;�
�
i
i
p
u
� �k J u( , )� òàêîå, ÷òî e a u b
k i i
i
p
j j
j
q
T �
� �
� ��
�
�
�
�
�
�
�
�
�
1 1
0 . (10)
Ïóñòü äëÿ íåêîòîðîãî âåêòîðà
~
~
( \ )
u
D D U
�
�
�
�
�
�
�� ! � ~
k -å ñîáñòâåííîå ÷èñëî
ìàòðèöû A u(~, ~ )� ðàâíî íóëþ, ò.å. min ~ ~ ~
, ,
~
k n
i ik
i
p
j jk
j
q
i ik
i
A u B A
� � �
� ��
�
�
�
�
�
�
�
�
�
1 1 1�
� �
�
� �
1
p
� �
�
� ~ ~u Bj jk
j
q
1
0 . Îäèí èç ñïîñîáîâ óäîâëåòâîðèòü óñëîâèþ (10) — íåîáõîäèìî,
÷òîáû íåðàâåíñòâî e a u b
k
i i
i
p
j j
j
q
~
~ ~T �
� �
� ��
�
�
�
�
�
�
�
�
�
1 1
0 âûïîëíÿëîñü íåçàâèñèìî îò çíà÷å-
íèé âåêòîðà
~
~
u
�
�
�
�
�
�
� , äðóãèìè ñëîâàìè, ÷òîáû
~
k -ÿ êîîðäèíàòà êîíè÷åñêîé êîìáèíà-
öèè âåêòîðîâ { }a i p b j qi j, , ; , ,� �1 1 íèêîãäà íå ïðèíèìàëà çíà÷åíèå íîëü. Ýòî
âîçìîæíî, êîãäà
~
k -å êîîðäèíàòû âñåõ âåêòîðîâ { }a i p b j qi j, , ; , ,� �1 1 èìåþò
îäèíàêîâûé çíàê (ïîñêîëüêó ~, ~u � � 0). Îáîáùàÿ ñêàçàííîå íà âñå ñîáñòâåííûå
÷èñëà ìàòðèöû A u( , )� , ïîëó÷àåì, ÷òî óñëîâèå (10) ïðè p � 0 âûïîëíÿåòñÿ, åñëè
âñå âåêòîðû { }a i p b j qi j, , ; , ,� �1 1 ðàñïîëîæåíû â îäíîì îòêðûòîì îðòàíòå.
Òàêèì îáðàçîì, äîêàçàí ñëåäóþùèé ðåçóëüòàò.
Óòâåðæäåíèå 1. Åñëè {ai , i p�1, ; b j , j q�1, } â çàäà÷å (1), (2) ðàñïîëîæåíû
â îäíîì îòêðûòîì îðòàíòå, òî çíà÷åíèå äâîéñòâåííîé îöåíêè çàäà÷è (4)–(6) ñîâïàäàåò
ñî çíà÷åíèåì åå ãëîáàëüíîãî ìèíèìóìà f � è òî÷êà x A u b u� � � � � �� � 1 2( , ) ( , ) /� �
ÿâëÿåòñÿ åå ðåøåíèåì.
ÇÀÊËÞ×ÅÍÈÅ
 ðàáîòå ïðåäñòàâëåíû äâå âîçìîæíûå ðåëàêñàöèè äëÿ ïîëó÷åíèÿ íèæíèõ
îöåíîê ãëîáàëüíûõ ýêñòðåìóìîâ íåâûïóêëûõ ñåïàðàáåëüíûõ ìèíèìàêñíûõ çà-
120 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
äà÷ êâàäðàòè÷íîé îïòèìèçàöèè (1), (2). Îñíîâíûì ðåçóëüòàòîì ÿâëÿåòñÿ óòâåð-
æäåíèå 1, â êîòîðîì ñôîðìóëèðîâàíî äîñòàòî÷íîå óñëîâèå íàõîæäåíèÿ çíà÷å-
íèÿ è òî÷êè ãëîáàëüíîãî ýêñòðåìóìà çàäà÷è äàííîãî êëàññà îïðåäåëåíèåì
äâîéñòâåííîé îöåíêè äëÿ ýêâèâàëåíòíîé êâàäðàòè÷íîé ýêñòðåìàëüíîé çàäà-
÷è (4)–(6). Ïðåäñòàâëÿåò èíòåðåñ èññëåäîâàíèå âîçìîæíîñòè îñëàáèòü óñëîâèå
ýòîãî óòâåðæäåíèÿ.
Ïðèâåäåííûå â ðàáîòå ðàññóæäåíèÿ è ðåçóëüòàòû ïî äâîéñòâåííîé îöåí-
êå (8) äëÿ êâàäðàòè÷íîé ýêñòðåìàëüíîé çàäà÷è òàêæå âåðíû è äëÿ åå SDP-ðåëàê-
ñàöèè. Ýòî ñëåäóåò èç òîãî, ÷òî îöåíêè ãëîáàëüíîãî ýêñòðåìóìà, ïîëó÷åííûå
äàííûìè ïîäõîäàìè, äëÿ îäíîé è òîé æå ïîñòàíîâêè êâàäðàòè÷íîé ýêñòðåìàëü-
íîé çàäà÷è ñîâïàäàþò [28–30].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Shor N.Z. Nondifferentiable optimization and polynomial problems. Boston; London; Dordrecht:
Kluwer Academic Publishers, 1998. 394 p.
2. Pardalos P.M., Rosen J.B. Constrained global optimization: Algorithms and applications. In: Lecture
Notes in Computer Science. Vol. 268. Berlin; Heidelberg: Springer-Verlag, 1987. 122 p.
3. Momoh J.A. Electric power system applications of optimization. New York: CRC Press, 2017. 595 p.
4. Arora J.S. Optimization of structural and mechanical systems. Singapore: World Scientific, 2007.
595 p.
5. Øîð Í.Ç., Ñåð㳺íêî ².Â., Øèëî Â.Ï., Ñòåöþê Ï.²., Ïàðàñþê ².Ì., Ëåáºäºâà Ò.Ò., Ëàïò³í Þ.Ï.,
Æóðáåíêî Ì.Ã., Áàðäàäèì Ò.Î., Øàð³ôîâ Ô.À., Ëèõîâèä Î.Ï., Áåðåçîâñüêèé Î.À., ̳ðîøíè-
÷åíêî Â.Ì. Çàäà÷³ îïòèìàëüíîãî ïðîåêòóâàííÿ íàä³éíèõ ìåðåæ. Ê.: Íàóê. äóìêà, 2005. 230 ñ.
6. Ñòåöþê Ï.È., Áîðòèñ Ã., Ýììåíåããåð Æ.-Ô., Êîøëàé Ë.Á., Áåðåçîâñêèé Î.À., Áàðäàäûì Ò.À.,
Ïåðâóõèíà Å.Ë., Ãîëèêîâà Â.Â., Îñèïîâ Ê.Í., Êàðïåö Ý.Ï., Ïèëèïîâñêèé À.Â. Èíñòèòóöèî-
íàëüíûå è òåõíîëîãè÷åñêèå èçìåíåíèÿ â ñòðàíàõ ñ ðûíî÷íîé è ïåðåõîäíîé ýêîíîìèêîé. Ê.:
Âèäàâíè÷èé ä³ì «Êèºâî-Ìîãèëÿíñüêà àêàäåì³ÿ», 2015. 336 c.
7. Guisewite G.M. Network problems. Handbook of Global Optimization. Nonconvex Optimization and Its
Applications. Horst R., Pardalos P.M. (Eds.). Vol 2. Boston, MA: Springer, 1995. P. 609–648.
8. Zhuravlev Yu.I., Laptin Yu.P., Vinogradov A.P., Zhurbenko N.G., Lykhovyd O.P., Berezovskyi O.A.
Linear classifiers and selection of informative features. Pattern Recognition and Image Analysis.
2017. Vol. 27, Iss. 3. P. 426–432.
9. Ìóíò³ÿí Â.²., Ïðîêîïåíêî Î.Â., Ïåòðóøåíêî Ì.Ì., Àâåñêóëîâà Ë.²., Àäàñîâñüêèé Á.². Åêî-
íîì³÷íà áåçïåêà äåðæàâè: ñòðàòåã³ÿ, åíåðãåòèêà, ³íôîðìàö³éí³ òåõíîëî㳿. Çà ðåä. Ëóê’ÿíåí-
êî Ñ.Î., Êàðàºâî¿ Í.Â. Ê.: Âèä-âî ÎÎÎ «Þðêà Ëþá÷åíêà», 2014. 468 ñ.
10. Pankov A.R., Platonov E.N., Semenikhin K.V. Minimax quadratic optimization and its application to
investment planning. Automation and Remote Control. 2001. Vol. 62, Iss. 12. P. 1978–1995.
11. Shor N.Z., Berezovskii O.A. Using the method of dual quadratic solutions to solve systems of
polynomial equations in the complex domain. Cybernetics and Systems Analysis. 1994. Vol. 30, N 5.
P. 686–692.
12. Nesterov Y., Wolkowicz H., Ye Y. Semidefinite programming relaxations of nonconvex quadratic
optimization. Handbook of Semidefinite Programming. New York: Springer US, 2000. P. 361–419.
13. Kim S., Kojima M. Second order cone programming relaxation of nonconvex quadratic optimization
problems. Optimization Methods and Software. 2001. Vol. 15, Iss. 3. P. 201–224.
14. Lemar�chal C. Lagrangian relaxation. Computational Combinatorial Optimization. Lecture Notes in
Computer Science. J��unger M., Naddef D. (Eds.). Vol. 2241. Berlin; Heidelberg: Springer,
2001. P. 112–156. https://doi.org/10.1007/3-540-45586-8_4.
15. Anstreicher K., Wolkowicz H. On Lagrangian relaxation of quadratic matrix constraints. SIAM
Journal on Matrix Analysis and Applications. 2000. Vol. 2, Iss. 1. P. 41–55.
16. Qualizza A., Belotti P., Margot F. Linear programming relaxations of quadratically constrained
quadratic programs. Mixed Integer Nonlinear Programming. The IMA Volumes in Mathematics and its
Applications. Lee J., Leyffer S. (Eds.). Vol 154. New York: Springer, 2012. P. 407–426.
https://doi.org/10.1007/978-1-4614-1927-3_14.
17. Jeyakumar V., Li G. Exact second-order cone programming relaxations for some nonconvex
minimax quadratic optimization problems. SIAM Journal on Optimization. 2018. Vol. 28, Iss. 1.
P. 760–787.
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 121
18. Wolkowicz H., Saigal R., Vandenberghe L. (Eds.). Handbook of semidefinite programming: theory,
algorithms, and applications. New York: Springer Science & Business Media, 2012. 654 p.
19. Lasserre J.B. An explicit exact SDP relaxation for nonlinear 0-1 programs. Intern. Conf. on Integer
Programming and Combinatorial Optimization. Berlin: Springer, 2001. P. 293–303.
20. Burer S., Anstreicher K.M. Second-order-cone constraints for extended trust-region subproblems.
SIAM Journal on Optimization. 2013. Vol. 23, Iss. 1. P. 432–451.
21. Beck A., Eldar Y.C. Strong duality in nonconvex quadratic optimization with two quadratic
constraints. SIAM Journal on Optimization. 2006. Vol. 17, Iss. 3. P. 844–860.
22. Áåðåçîâñêèé Î.À. Î òî÷íîñòè äâîéñòâåííûõ îöåíîê äëÿ êâàäðàòè÷íûõ ýêñòðåìàëüíûõ çàäà÷.
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2012. ¹ 1. Ñ. 33–39.
23. Jeyakumar V., Li G. Trust-region problems with linear inequality constraints: Exact SDP relaxation,
global optimality and robust optimization. Mathematical Programming. 2014. Vol. 147, Iss. 1.
P. 171–206.
24. Jeyakumar V., Li G. Y. Strong duality in robust convex programming: complete characterizations.
SIAM Journal on Optimization. 2010. Vol. 20, Iss. 6. P. 3384–3407.
25. Berezovskyi O.A. On solving of a special optimization problem connected with determination of
invariant sets of dynamical systems. Journal of Automation and Information Sciences. 2015. Vol. 47,
Iss. 5. P. 69–77.
26. Haines S., Loeppky J., Tseng P., Wang X. Convex relaxations of the weighted maxmin dispersion
problem. SIAM Journal on Optimization. 2013. Vol. 23, Iss. 4. P. 2264–2294.
27. Ben-Tal A., Ghaoui L.E., Nemirovski A. Robust optimization. Princeton Ser. Appl. Math. Princeton:
Princeton Univ. Press, 2009. 544 ð.
28. Alizadeh F. Optimization over the positive-definite cone: Interior point methods and combinatorial
applications. In: Advances in Optimization and Parallel Computing. Pardalos P.M. (Ed.).
Amsterdam: Elsevier Science, 1992. P. 1–25.
29. Fujit T., Kojima M. Semidefinite programming relaxation for nonconvex quadratic problems.
Journal of Global Optimization. 1997. Vol. 10, Iss. 4. P. 367–380.
30. Áåðåçîâñêèé Î.À. Êðèòåðèè òî÷íîñòè SDP-ðåëàêñàöèé êâàäðàòè÷íûõ ýêñòðåìàëüíûõ çàäà÷.
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2016. Ò. 52, ¹ 6. Ñ. 95–101.
Íàä³éøëà äî ðåäàêö³¿ 16.06.2020
Î.À. Áåðåçîâñüêèé
ÒÎ×Ͳ ÄÂίÑÒ² ÎÖ²ÍÊÈ ÄËß ÄÅßÊÈÕ ÍÅÎÏÓÊËÈÕ Ì²Í²ÌÀÊÑÍÈÕ ÊÂÀÄÐÀÒÈ×ÍÈÕ
ÎÏÒÈ̲ÇÀÖ²ÉÍÈÕ ÇÀÄÀ×
Àíîòàö³ÿ. Äîñë³äæåíî íåîïóêëó ñåïàðàáåëüíó ì³í³ìàêñíó êâàäðàòè÷íó
îïòèì³çàö³éíó çàäà÷ó. Íàâåäåíî äâà ï³äõîäè äî ¿¿ ðîçâ’ÿçàííÿ: çà äîïîìîãîþ
SOCP-ðåëàêñàö³¿ ³ ëàãðàíæåâî¿ ðåëàêñàö³¿ êâàäðàòè÷íî¿ åêñòðåìàëüíî¿ çà-
äà÷³-àíàëîãà. Îòðèìàíî óìîâó, âèêîíàííÿ ÿêî¿ ãàðàíòóº çíàõîäæåííÿ çíà÷åííÿ
³ òî÷êè ãëîáàëüíîãî åêñòðåìóìó çàäà÷³ ðîçãëÿíóòîãî êëàñó îá÷èñëåííÿì äâî¿-
ñòî¿ îö³íêè åêâ³âàëåíòíî¿ êâàäðàòè÷íî¿ åêñòðåìàëüíî¿ çàäà÷³.
Êëþ÷îâ³ ñëîâà: ì³í³ìàêñíà êâàäðàòè÷íà îïòèì³çàö³éíà çàäà÷à, SOCP-ðåëàê-
ñàö³ÿ, ëàãðàíæåâà ðåëàêñàö³ÿ, òî÷íà äâî¿ñòà îö³íêà, äîäàòíî-âèçíà÷åíà ìàòðèöÿ.
O.A. Berezovskyi
EÕÀÑT DUAL BOUNDS FOR SOME NONCONVEX MINIMAX
QUADRATICOPTIMIZATION PROBLEMS
Abstract. Nonconvex separable minimax quadratic optimization problem is
analyzed. Two approaches to solve the problem are described, namely, by using
SOCP-relaxation and by using Lagrangian relaxation of a quadratic extremum
analog problem. A condition is obtained whose fulfillment guarantees finding the
value and the global extremum point of the problem of the considered class by
calculating the dual bound of the equivalent quadratic extremum problem.
Keywords: minimax quadratic optimization problem, SOCP-relaxation,
Lagrangian relaxation, exact dual bound, positive definite matrix.
Áåðåçîâñêèé Îëåã Àíàòîëüåâè÷,
êàíäèäàò ôèç.-ìàò. íàóê, ñòàðøèé íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èìåíè Â.Ì. Ãëóøêîâà
ÍÀÍ Óêðàèíû, Êèåâ, e-mail: o.a.berezovskyi@gmail.com.
122 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
|