О точности двойственных оценок для квадратичных экстремальных задач
Дано короткий огляд відомих часткових результатів про точність двоїстих оцінок, запропонованих Н.З. Шором, для квадратичних екстремальних задач. Наведено необхідну та достатню умову точності двоїстої оцінки для квадратичної задачі у загальному випадку. The paper briefly reviews the well-known partia...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2012 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84014 |
| 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: | О точности двойственных оценок для квадратичных экстремальных задач / О.А. Березовский // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 33-39. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860110216832483328 |
|---|---|
| author | Березовский, О.А. |
| author_facet | Березовский, О.А. |
| citation_txt | О точности двойственных оценок для квадратичных экстремальных задач / О.А. Березовский // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 33-39. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Дано короткий огляд відомих часткових результатів про точність двоїстих оцінок, запропонованих Н.З. Шором, для квадратичних екстремальних задач. Наведено необхідну та достатню умову точності двоїстої оцінки для квадратичної задачі у загальному випадку.
The paper briefly reviews the well-known partial results on the accuracy of dual bounds proposed by N. Z. Shor for quadratic extremal problems. The necessary and sufficient condition for the accuracy of the dual bound for a quadratic problem of general form is presented.
|
| first_indexed | 2025-12-07T17:33:36Z |
| format | Article |
| fulltext |
ÓÄÊ 519.8
Î.À. ÁÅÐÅÇÎÂÑÊÈÉ
Î ÒÎ×ÍÎÑÒÈ ÄÂÎÉÑÒÂÅÍÍÛÕ ÎÖÅÍÎÊ ÄËß ÊÂÀÄÐÀÒÈ×ÍÛÕ
ÝÊÑÒÐÅÌÀËÜÍÛÕ ÇÀÄÀ×1
Êëþ÷åâûå ñëîâà: êâàäðàòè÷íàÿ çàäà÷à, äâîéñòâåííàÿ ëàãðàíæåâàÿ îöåíêà,
ïîëîæèòåëüíî-îïðåäåëåííàÿ ìàòðèöà, ôóíêöèîíàëüíî èçáûòî÷íûå îãðàíè÷åíèÿ.
ÄÂÎÉÑÒÂÅÍÍÛÅ ÎÖÅÍÊÈ. ÎÁÙÈÉ ÏÎÄÕÎÄ
Ðàññìîòðèì êâàäðàòè÷íóþ çàäà÷ó
f f x
x T n
* ( )�
� �
inf
�
0 , (1)
ãäå äîïóñòèìîå ìíîæåñòâî çíà÷åíèé T x f x i I f x i J xi i� � � � � �{ : ( ) , , ( ) , ;0 0
� �( , , ..., )x x xn
T n
1 2 � }, f x x K x b x ci
T
i i
T
i( ) � � � , i I J� � �{ }0 , — êâàäðàòè÷-
íûå ôóíêöèè, îïðåäåëåííûå â n-ìåðíîì ïðîñòðàíñòâå, ñ ñèììåòðè÷íîé
n n� -ìàòðèöåé Ki , âåêòîðîì bi
n�� è êîíñòàíòîé ci ��
1; m I J� �| | | | — îá-
ùåå êîëè÷åñòâî îãðàíè÷åíèé. Î âàæíîñòè äàíîãî êëàñà çàäà÷ ñâèäåòåëüñòâóåò
òîò ôàêò, ÷òî ê íèì îòíîñÿòñÿ èëè ñâîäÿòcÿ âûïóêëûå è íåâûïóêëûå çàäà÷è
êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ, çàäà÷à ëèíåéíîé äîïîëíèòåëüíîñòè, ïîëè-
íîìèàëüíûå ýêñòðåìàëüíûå çàäà÷è (â êîòîðûõ öåëåâàÿ ôóíêöèÿ è âñå ôóíêöèè
îãðàíè÷åíèé ïðåäñòàâëÿþò ñîáîé ïîëèíîìû), ðåøåíèå ñèñòåì ïîëèíîìèàëü-
íûõ óðàâíåíèé ñ âåùåñòâåííûìè è êîìïëåêñíûìè ïåðåìåííûìè, ýêñòðåìàëü-
íûå çàäà÷è íà ãðàôàõ è ò.ä. Îáîáùàÿ, ìîæíî ñêàçàòü, ÷òî ê âèäó êâàäðàòè÷-
íîé çàäà÷è ñâîäÿòñÿ âñå çàäà÷è, ïðåäñòàâèìûå êàê ðàöèîíàëüíûå ýêñòðåìàëü-
íûå çàäà÷è (â êîòîðûõ öåëåâàÿ ôóíêöèÿ è âñå ôóíêöèè îãðàíè÷åíèé
ðàöèîíàëüíûå, ò.å. ïðåäñòàâëÿþò ñîáîé äðîáè, â ÷èñëèòåëå è çíàìåíàòåëå êî-
òîðûõ ñòîÿò ïîëèíîìû).
 îáùåì ñëó÷àå çàäà÷à (1) — ìíîãîýêñòðåìàëüíà è îòíîñèòñÿ ê êëàññó
NP-òðóäíûõ çàäà÷, ïîýòîìó àêòóàëüíî íàõîæäåíèå îöåíîê äëÿ äàííîé çàäà÷è çà
«ïðèåìëåìîå» (ïîëèíîìèàëüíîå) âðåìÿ. Äëÿ ïîëó÷åíèÿ íèæíèõ îöåíîê � * îïòè-
ìàëüíîãî çíà÷åíèÿ öåëåâîé ôóíêöèè f * çàäà÷è (1) (� * *� f ) àêàäåìèê
Í.Ç. Øîð ïðåäëîæèë è èññëåäîâàë äâîéñòâåííûé ïîäõîä [1, 2], îñíîâàííûé íà
èñïîëüçîâàíèè ôóíêöèè Ëàãðàíæà:
� �* *( ) ( )� � �
� ��
sup inf
u D U x T
u f x f0 , (2)
ãäå
�( ) ( , )u L x u
x n
�
�
inf
�
; (3)
L u x x K u x b u x c uT T( , ) ( ) ( ) ( )� � � — ôóíêöèÿ Ëàãðàíæà äëÿ çàäà÷è (1), â êîòîðîé
K u K u Ki 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
,
U � — îáëàñòü îïðåäåëåíèÿ âåêòîðà ìíîæèòåëåé Ëàãðàíæà u m�� , ó÷èòûâàþ-
ùàÿ íàëè÷èå îãðàíè÷åíèé â âèäå íåðàâåíñòâ: U u u i Ii
� � � �{ }: ,0 ;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 33
1Ðàáîòà âûïîëíåíà ÷àñòè÷íî â ðàìêàõ ïðîåêòà ¹IZ73ZO_127962 (SNSF, Øâåéöàðèÿ).
� Î.À. Áåðåçîâñêèé, 2012
D — ìíîæåñòâî ïåðåìåííûõ u m�� , ïðè êîòîðûõ ìàòðèöà K u( ) ïîëîæèòåëü-
íî îïðåäåëåíà.
Íåðàâåíñòâî (2) ñëåäóåò èç òîãî, ÷òî ïðè ëþáûõ x T� è u U� � èìååò ìåñòî
L u x f x( , ) ( )� 0 , ñ ó÷åòîì ÷åãî �( ) ( , ) ( , ) ( ) *u L u x L u x f x f
x x T x T
� � � �
� �
inf inf inf 0 ïðè
ëþáîì u U� � , îòêóäà � �* *( )� �
� �
sup
u D U
u f .
Íà âèïóêëîì ìíîæåñòâå D U � ôóíêöèÿ �( )u âîãíóòà è íåïðåðûâíî äèô-
ôåðåíöèðóåìà, ïðè ýòîì åå ãðàäèåíò âû÷èñëÿåòñÿ ïî ôîðìóëå
�� u ii
f x u( ( )),
i m�1, . Çäåñü x u( ) ÿâëÿåòñÿ ðåøåíèåì áåçóñëîâíîé çàäà÷è ìèíèìèçàöèè êâàäðà-
òè÷íîé ôóíêöèè (3), êîòîðîå ïðè u D� îäíîçíà÷íî îïðåäåëÿåòñÿ èç ñèñòåìû
óðàâíåíèé
� � �L u x K u x b ux ( , ) ( ) ( )2 0 — x u K u b u( ) ( ) ( ) /� � �1 2 . Òàêèì îáðàçîì,
íàõîæäåíèå äâîéñòâåííîé îöåíêè � * îòíîñèòñÿ ê «õîðîøèì» çàäà÷àì âûïóêëîãî
ïðîãðàììèðîâàíèÿ, íî îñòàåòñÿ âîïðîñ î åå òî÷íîñòè. Äëÿ óëó÷øåíèÿ äâîéñòâåííûõ
ëàãðàíæåâûõ îöåíîê ïðåäëàãàåòñÿ èñïîëüçîâàòü ðàñøèðåíèå èñõîäíîé êâàäðà-
òè÷íîé ïîñòàíîâêè çàäà÷è ïóòåì äîáàâëåíèÿ ê íåé ôóíêöèîíàëüíî èçáûòî÷íûõ
îãðàíè÷åíèé. Ïîä òàêèìè îãðàíè÷åíèÿìè ïîíèìàþò îãðàíè÷åíèÿ, êîòîðûå âû-
ñòóïàþò ëîãè÷åñêèìè ñëåäñòâèÿìè èìåþùèõñÿ îãðàíè÷åíèé çàäà÷è (êðîìå èõ
ëèíåéíûõ êîìáèíàöèé, êîòîðûå íè÷åãî íå äàþò ïðè ðàáîòå ñ ôóíêöèåé Ëàãðàí-
æà, ìåíÿÿ ëèøü çíà÷åíèÿ äâîéñòâåííûõ ïåðåìåííûõ). Ýòè îãðàíè÷åíèÿ íå íåñóò
íèêàêîé äîïîëíèòåëüíîé èíôîðìàöèè ñ òî÷êè çðåíèÿ èñõîäíîé çàäà÷è, íî
èçìåíÿþò ôóíêöèþ Ëàãðàíæà è ðàñøèðÿþò îáëàñòü îïðåäåëåíèÿ äâîéñòâåííûõ
ïåðåìåííûõ (èìååòñÿ â âèäó, ÷òî åñëè ïðè íàëè÷èè m îãðàíè÷åíèé
( , ..., )u u Dm
T m
1 � � � , òî ïîñëå äîáàâëåíèÿ íîâîãî îãðàíè÷åíèÿ ïåðâûå m êîì-
ïîíåíò ðàñøèðåííîãî âåêòîðà ( , ..., , )
~
u u u Dm m
T m
1 1
1
�
�� � � ïðè îïðåäåëåííûõ
çíà÷åíèÿõ um�1 ìîãóò è íå ïðèíàäëåæàòü ìíîæåñòâó D).  ðåçóëüòàòå â ðÿäå ñëó-
÷àåâ ëàãðàíæåâàÿ äâîéñòâåííàÿ îöåíêà äëÿ íîâîé «ðàñøèðåííîé» êâàäðàòè÷íîé
ïîñòàíîâêè ìîæåò îêàçàòüñÿ áîëåå òî÷íîé, ÷åì äëÿ èñõîäíîé, èëè äàæå ðàâíîé f * .
 80-õ ãîäàõ ïðîøëîãî âåêà Í.Ç. Øîð ïðåäëàãàë ñëåäóþùèé ïóòü ðàñøèðå-
íèÿ çàäà÷è.
À. Äîáàâëåíèå â èñõîäíóþ çàäà÷ó êâàäðàòè÷íûõ îãðàíè÷åíèé, êîòîðûå ââî-
äÿò íîâûå ïåðåìåííûå R R Ri j k( ) ( ) ( )( ) ( ) ( )� � �� , � � �( ) ( ) ( )i j k� � , ãäå íåîòðè-
öàòåëüíûé öåëî÷èñëåííûé âåêòîð � � � � �( ) ( ) ( ) ( )( , , , )r r r
n
r T� �
1 2
� îïðåäåëÿåò
ïåðåìåííóþ R r( )( )� , êîòîðîé â èñõîäíîì ïðîñòðàíñòâå �
n ñîîòâåòñòâóåò ìîíîì
R x x xr
n
r r
n
r
( )( )
( ) ( ) ( )
�
� � ��
1 2
1 2
� . Âåêòîð �, êîòîðûé òåîðåòè÷åñêè ìîæåò âûáèðàòüñÿ
êàêèì óãîäíî, îãðàíè÷èâàåò êîëè÷åñòâî ýòèõ ïåðåìåííûõ. Ñàìî ïî ñåáå òàêîå
äîáàâëåíèå íîâûõ ïåðåìåííûõ íå äàåò äèâèäåíäîâ, íî â ñîâîêóïíîñòè ñ îãðàíè-
÷åíèÿìè âèäà R R R Ri j k l( ) ( ) ( ) ( )( ) ( ) ( ) ( )� � � �� � 0 ïðè � �( ) ( )i j� � � �( ) ( )k l� ,
çàäàþùèìè ðàçëè÷íûå ñâÿçè ìåæäó íèìè (ñ ïîìîùüþ îãðàíè÷åíèé òàêîãî âèäà
ó÷èòûâàåòñÿ íåîäíîçíà÷íîñòü ïðåäñòàâëåíèÿ ìîíîìà x x x
r r
n
r
n1 2
1 2
� � �
( ) ( ) ( )
� ,
� � � � �( ) ( ) ( ) ( ) ( )r i j k l� � � � â íîâûõ ïåðåìåííûõ), ìîæíî ðàññ÷èòûâàòü íà
óòî÷íåíèå äâîéñòâåííîé îöåíêè.
(Â [1, 2] ââåäåíèå íîâûõ ïåðåìåííûõ èñïîëüçîâàëîñü äëÿ ïîíèæåíèÿ ñòåïå-
íè ïîëèíîìà ïðè ñâåäåíèè åãî ê êâàäðàòè÷íîé ôóíêöèè ïðè êâàäðàòè÷íûõ îãðà-
íè÷åíèÿõ. Îäíàêî ïîíÿòíî, ÷òî ëþáóþ êâàäðàòè÷íóþ ôóíêöèþ (ïîëèíîì) ìîæ-
íî ðàññìàòðèâàòü êàê ïîëèíîì áîëåå âûñîêîé ñòåïåíè, êîýôôèöèåíòû êîòîðîãî
ïðè ñòàðøèõ ñòåïåíÿõ ðàâíû íóëþ.)
34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
Á. Äîáàâëåíèå îãðàíè÷åíèé, ïîëó÷åííûõ ïåðåìíîæåíèåì îãðàíè÷åíèé çàäà-
÷è âî âñåõ âîçìîæíûõ ñî÷åòàíèÿõ (ïî äâà, ïî òðè è ò.ä.), ò.å. îãðàíè÷åíèé âèäà
f xi
i L
( )
�
� � 0 (äëÿ ñëó÷àÿ, åñëè � �i L òàêîå, ÷òî i J� ) è � � �
�
� ( ( ))f xi
i L
0 (â ïðî-
òèâíîì ñëó÷àå, ò.å. êîãäà L I� ) äëÿ âñåõ âîçìîæíûõ L I J� � . Îòìåòèì, ÷òî
çäåñü ìíîæåñòâî J âêëþ÷àåò è îãðàíè÷åíèÿ èñõîäíîé çàäà÷è (1), è îãðàíè÷åíèÿ,
îïðåäåëÿþùèå íîâûå ïåðåìåííûå (ñì. ï. À). Ïîëó÷åííûå îãðàíè÷åíèÿ, ñîäåðæà-
ùèå ìîíîìû, ñòåïåíü êîòîðûõ íå ïîçâîëÿåò ïðåäñòàâëÿòü èõ â âèäå êâàäðàòè÷-
íîé ôîðìû (ñ ó÷åòîì íîâûõ ïåðåìåííûõ), èñêëþ÷àþòñÿ. Íî òîãäà âêëþ÷àþòñÿ
èõ ëèíåéíûå êîìáèíàöèè ñòåïåíè íå áîëüøå äâóõ. Íàïðèìåð, åñëè çàäà÷à èìååò
îãðàíè÷åíèÿ x a x b
1
2
1 1� �( , ) , x a x b
2
2
2 2� �( , ) , x x a x b1 2 3 3� �( , ) , òî îãðàíè÷åíèÿ
x x a x b a x b
1
2
2
2
1 1 2 2� � �(( , ) )(( , ) ) è x x a x b
1
2
2
2
3 3
2� �(( , ) ) èãíîðèðóþòñÿ, íî
(( , ) )(( , ) ) (( , ) )a x b a x b a x b1 1 2 2 3 3
2� � � � äîáàâëÿåòñÿ â çàäà÷ó.
Îáîáùàÿ èçëîæåííûé â ïï. À è Á ïðîöåññ ðàñøèðåíèÿ êâàäðàòè÷íîé çàäà-
÷è (1), ïîä÷åðêíåì, ÷òî â êà÷åñòâå ôóíêöèîíàëüíî èçáûòî÷íûõ îãðàíè÷åíèé ìî-
ãóò âûñòóïàòü ëþáûå êâàäðàòè÷íûå îãðàíè÷åíèÿ (êàê ñ èñõîäíûìè ïåðåìåííû-
ìè, òàê è ñ ïðîèçâîëüíûìè íîâûìè), êîòîðûå íå âëèÿþò íà äîïóñòèìóþ îáëàñòü
èñõîäíîé êâàäðàòè÷íîé çàäà÷è (òåîðåòè÷åñêè äîñòàòî÷íî, ÷òîáû ãëîáàëüíûé
ýêñòðåìóì îñòàâàëñÿ â äîïóñòèìîé îáëàñòè, íî àïðèîðè íàì íåèçâåñòíî äîïóñòè-
ìîå ñóæåíèå îáëàñòè, èíà÷å îíî èñïîëüçîâàëîñü áû â èñõîäíîé çàäà÷å). Ýòî ìî-
ãóò áûòü, íàïðèìåð, îãðàíè÷åíèÿ âèäà f x P xi ( )* ( ) � 0 äëÿ ëþáîãî i J� è ïðîèç-
âîëüíîãî ïîëèíîìà P x( ) (ïðè óñëîâèè ââåäåíèÿ äîñòàòî÷íîãî êîëè÷åñòâà íîâûõ
ïåðåìåííûõ äëÿ ïðèâåäåíèÿ îãðàíè÷åíèÿ ê êâàäðàòè÷íîìó âèäó), èëè âèäà
f x P xi ( )* ( ) � 0 äëÿ ëþáîãî i I� è ïðîèçâîëüíîãî ïîëèíîìà P x( ), êîòîðûé ïðèíè-
ìàåò íåîòðèöàòåëüíûå çíà÷åíèÿ íà îáëàñòè T , èëè îãðàíè÷åíèÿ êàêîãî-ëèáî èíî-
ãî òèïà (íàïðèìåð, â [3] äëÿ áèíàðíûõ ïåðåìåííûõ â êà÷åñòâå ôóíêöèîíàëüíî
èçáûòî÷íûõ îãðàíè÷åíèé ïðåäëîæåíû îãðàíè÷åíèÿ âèäà �
�
�
�
�
�
�
�
�
�
�
�
xi
i
k
1
2 1
2
1 è
1 1
1
2
2
� �
�
�
�
�
�
�
�
�
�
�
xi
i
k
). Ãëàâíîå, ÷òîáû îíè âêëþ÷àëè àêòèâíûå îãðàíè÷åíèÿ, ïîçâî-
ëÿþùèå «ïîëåçíî» èçìåíèòü ôóíêöèþ Ëàãðàíæà è ðàñøèðèòü îáëàñòü îïðåäåëå-
íèÿ äâîéñòâåííûõ ïåðåìåííûõ â çàäà÷å (2). Äëÿ èëëþñòðàöèè ñêàçàííîãî ïðèâå-
äåì ñëåäóþùèé (ïðàâäà, íåñêîëüêî èñêóññòâåííûé) ïðèìåð: åñëè â ïðîèçâîëü-
íóþ êâàäðàòè÷íóþ çàäà÷ó äîáàâèòü îãðàíè÷åíèå y K x f2
0 0� � �( ) * , òî
äâîéñòâåííàÿ îöåíêà � * (2) áóäåò òî÷íîé.
ÊÐÈÒÅÐÈÈ ÒÎ×ÍÎÑÒÈ ÄÂÎÉÑÒÂÅÍÍÛÕ ÎÖÅÍÎÊ
Ïðèìåíåíèå òåõíèêè êâàäðàòè÷íûõ äâîéñòâåííûõ îöåíîê Í.Ç. Øîðà ïðè ðåøå-
íèè ðàçëè÷íûõ êëàññîâ çàäà÷ ïîêàçàëî åå ïðàêòè÷åñêóþ ýôôåêòèâíîñòü. Îäíàêî
ïðè ýòîì ïðèîáðåòàåò âàæíîå çíà÷åíèå âîïðîñ èõ òî÷íîñòè, à â ñâÿçè ñ ýòèì è
âîïðîñ âûáîðà äëÿ èñõîäíîé çàäà÷è ñîîòâåòñòâóþùåé êâàäðàòè÷íîé ïîñòàíîâêè,
íà áàçå êîòîðîé ñëåäóåò èñêàòü äâîéñòâåííóþ îöåíêó (â òîì ÷èñëå, êàêèå ñåìå-
éñòâà ôóíêöèîíàëüíî èçáûòî÷íûõ îãðàíè÷åíèé èñïîëüçîâàòü, ÷òîáû íå ââîäèòü
ñëèøêîì ìíîãî äîïîëíèòåëüíûõ êàê ïðÿìûõ, òàê è äâîéñòâåííûõ ïåðåìåííûõ).
Íà ñåãîäíÿøíèé äåíü èçâåñòíû ñëåäóþùèå òåîðåòè÷åñêèå ðåçóëüòàòû äëÿ
÷àñòíûõ ñëó÷àåâ, êîãäà äâîéñòâåííàÿ îöåíêà ñîâïàäàåò ñ òî÷íûì çíà÷åíèåì
ìèíèìóìà öåëåâîé ôóíêöèè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 35
1. Êâàäðàòè÷íàÿ çàäà÷à (1) äëÿ ñëó÷àÿ, êîãäà äâîéñòâåííàÿ îöåíêà äîñ-
òèãàåòñÿ âî âíóòðåííåé òî÷êå îáëàñòè ïîëîæèòåëüíîé îïðåäåëåííîñòè ìàò-
ðèöû K u( ) ôóíêöèè Ëàãðàíæà.
Ëåììà 1 [1, ñ. 90]. Åñëè � �* ( )�
� �
sup
u D U
u äîñòèãàåòñÿ íà ìíîæåñòâå D, òî
� * *� f .
Ñëåäñòâèå 1. Ïðîèçâîëüíàÿ çàäà÷à âûïóêëîãî êâàäðàòè÷íîãî ïðîãðàììèðî-
âàíèÿ îáëàäàåò �-ñâîéñòâîì.
(Ñ÷èòàåòñÿ, ÷òî êâàäðàòè÷íàÿ çàäà÷à îáëàäàåò �-ñâîéñòâîì, åñëè äâîéñòâåí-
íàÿ îöåíêà äëÿ íåå òî÷íàÿ [1].)
Îòìåòèì, ÷òî â ýòîì ñëó÷àå ìû ïîëó÷àåì òàêæå è îäíó èç òî÷åê ìèíèìóìà
çàäà÷è (1).
2. Çàäà÷à íàõîæäåíèÿ ãëîáàëüíîãî ìèíèìóìà îãðàíè÷åííîãî ñíèçó ïî-
ëèíîìà. Îïèñàííàÿ âûøå ñõåìà À–Á ïîñòðîåíèÿ ôóíêöèîíàëüíî èçáûòî÷íûõ
îãðàíè÷åíèé ïðèìåíÿëàñü äëÿ ïîñòðîåíèÿ êâàäðàòè÷íîé çàäà÷è, ñîîòâåòñòâóþ-
ùåé çàäà÷å íàõîæäåíèÿ ãëîáàëüíîãî ìèíèìóìà ïîëèíîìà P x0 ( ) (x n�� , ms —
ìàêñèìàëüíàÿ ñóììàðíàÿ ñòåïåíü ìîíîìà ïîëèíîìà P x0 ( ), s — âåêòîð ñòàðøèõ
ñòåïåíåé ïîëèíîìà P x0 ( )):
1) äëÿ âñåõ � �( ) /i s� � 2 ââîäÿòñÿ ïåðåìåííûå R R Ri j k( ) ( ) ( )( ) ( ) ( )� � �� ,
� � �( ) ( ) ( )i j k� � , � � � � �( ) ( ) ( ) ( )( , , , )r r r
n
r T� �
1 2
� , â ðåçóëüòàòå ïîëó÷àåì ïîëíûé
íàáîð ïåðåìåííûõ, ïîêðûâàþùèõ âñå ìîíîìû ñòåïåíè � �( )i � , à ïîëèíîì P x0 ( )
ïðåäñòàâèì â âèäå êâàäðàòè÷íîé ôóíêöèè f R0 ( ) (îòìåòèì, ÷òî âñå êîìïîíåíòû
âåêòîðà s ÷åòíûå, â ïðîòèâíîì ñëó÷àå ïîëèíîì íå îãðàíè÷åí ñíèçó);
2) ê êâàäðàòè÷íûì îãðàíè÷åíèÿì, îïðåäåëÿþùèì íîâûå ïåðåìåííûå, äîáàâ-
ëÿåòñÿ ïîëíîå ñåìåéñòâî îãðàíè÷åíèé âèäà R R R Ri j k l( ) ( ) ( ) ( )( ) ( ) ( ) ( )� � � �� � 0
äëÿ âñåõ � � � �( ) ( ) ( ) ( )i j k l� � � , ò.å. ñ ïîìîùüþ èõ ëèíåéíîé êîìáèíàöèè ìîæ-
íî ïîëó÷èòü âñå ïðåäñòàâëåíèÿ (ñòåïåíè ìåíüøå èëè ðàâíî äâóõ) ëþáîãî ìîíîìà
x x x
r r
n
r
n1 2
1 2
� � �
( ) ( ) ( )
� ñòåïåíè � ( )r s� , à çíà÷èò, è ïîëèíîìà P x0 ( ), â íîâûõ
ïåðåìåííûõ.
 ðåçóëüòàòå çàäà÷à f P x
x R n
* min ( )�
�
0 ñâåäåíà ê êâàäðàòè÷íîé çàäà÷å
f f R
R
* min ( )� 0
(4)
ïðè îãðàíè÷åíèÿõ
R R R Ri j k l( ) ( ) ( ) ( )( ) ( ) ( ) ( )� � � �� � 0, � � � �( ) ( ) ( ) ( )i j k l� � � ,
0 � � �� � � �( ) ( ) ( ) ( )( , , , ) /r r r
n
r T s
1 2
2� . (5)
Òåîðåìà 1 [1, c. 141]. Äëÿ òîãî ÷òîáû êâàäðàòè÷íàÿ çàäà÷à (4), (5) îáëàäàëà
�-ñâîéñòâîì, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ïîëèíîì P x f0 ( ) *� áûë ïðåäñòà-
âèì â âèäå ñóììû êâàäðàòîâ ïîëèíîìîâ.
Ñëåäñòâèå 2. � * *� f , åñëè: 1) ëèáî n � 2, ms — ïðîèçâîëüíîå; 2) ëèáî n —
ïðîèçâîëüíîå; 3) ëèáî ms � 2 ; n � 3, ms � 4.
3. Çàäà÷à ìèíèìèçàöèè êâàäðàòè÷íîé ôóíêöèè íà ïîëîæèòåëüíîì
îðòàíòå. Ðàññìàòðèâàåòñÿ çàäà÷à (1), ãäå f x xi i( ) � � i I n� � { }12, , ,� è J � �{ }.
Ðàñøèðèì åå ñåìåéñòâîì ôóíêöèîíàëüíî èçáûòî÷íûõ îãðàíè÷åíèé âèäà
� �x xi j 0, i j n, ,�1 .
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
Òåîðåìà 2 [1, c. 117]. Åñëè f * � � �, òî � * äëÿ ðàñøèðåííîé êâàäðàòè÷íîé
çàäà÷è ñîâïàäàåò ñ f * òîãäà è òîëüêî òîãäà, êîãäà ìàòðèöà K
K b
b r
r T�
�
�
�
�
�
�
�
�
0 0
0
2
2
/
/
äëÿ íåêîòîðîãî r � 0 ïðåäñòàâèìà â âèäå ñóììû íåîòðèöàòåëüíîé è íåîòðèöàòåëü-
íî-îïðåäåëåííîé ìàòðèöû.
Ñëåäñòâèå 3. Ïðè n � 3 èìååì � * *� f .
4. Çàäà÷à ìèíèìèçàöèè êâàäðàòè÷íîé ôîðìû ïðè îäíîì êâàäðàòè÷íîì
îãðàíè÷åíèè. Ìîæíî ñ÷èòàòü, ÷òî îãðàíè÷åíèå çàäàíî â âèäå ðàâåíñòâà, ïî-
ñêîëüêó ëþáîå îãðàíè÷åíèå-íåðàâåíñòâî f x1 0( ) � ñ ïîìîùüþ ââåäåíèÿ â ôóíê-
öèþ êâàäðàòà äîïîëíèòåëüíîé ïåðåìåííîé ìîæíî çàìåíèòü íà îãðàíè÷åíèå-ðà-
âåíñòâî f x y1
2 0( ) � � , ïðè÷åì ñîãëàñíî äîêàçàííîìó â [4] óòâåðæäåíèþ çíà÷å-
íèÿ äâîéñòâåííûõ îöåíîê ïîëó÷åííîé è èñõîäíîé çàäà÷ ñîâïàäàþò.
Òåîðåìà 3 [5]. Çàäà÷à ìèíèìèçàöèè êâàäðàòè÷íîé ôóíêöèè íà êâàäðàòè÷íîé
ïîâåðõíîñòè, äëÿ êîòîðîé D � �{ }, îáëàäàåò �-ñâîéñòâîì.
5. Çàäà÷à î ìàêñèìàëüíîì âçâåøåííîì óñòîé÷èâîì ìíîæåñòâå ãðàôà. Íàè-
áîëüøåå êîëè÷åñòâî ðåçóëüòàòîâ î òî÷íîñòè äâîéñòâåííûõ îöåíîê ïîëó÷åíî äëÿ
ðàçëè÷íûõ êâàäðàòè÷íûõ ïîñòàíîâîê çàäà÷è íàõîæäåíèÿ âçâåøåííîãî ÷èñëà óñòîé-
÷èâîñòè ãðàôà. Íàïðèìåð, ïðåäëàãàëèñü ðàçíûå êâàäðàòè÷íûå ïîñòàíîâêè (ñ èñïîëü-
çîâàíèåì ðàçíûõ ñåìåéñòâ ôóíêöèîíàëüíî èçáûòî÷íûõ îãðàíè÷åíèé), äëÿ êîòîðûõ
äâîéñòâåííàÿ îöåíêà, êàê áûëî äîêàçàíî, òî÷íàÿ äëÿ ãðàôîâ: ïåðôåêòíûõ
â [2, ñ. 251], [6, 7], h- è t- ïåðôåêòíûõ [2, ñ. 254], [2, 7], w- è wp - ïåðôåêòíûõ [8].
ÍÅÎÁÕÎÄÈÌÎÅ È ÄÎÑÒÀÒÎ×ÍÎÅ ÓÑËÎÂÈÅ
Ñôîðìóëèðóåì è äîêàæåì îáùåå óñëîâèå òî÷íîñòè äâîéñòâåííîé îöåíêè äëÿ
ïðîèçâîëüíîé êâàäðàòè÷íîé çàäà÷è.
Òåîðåìà 4. Äëÿ òîãî ÷òîáû êâàäðàòè÷íàÿ çàäà÷à (1) ñ f * � � � îáëàäàëà
�-ñâîéñòâîì, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ñóùåñòâîâàë òàêîé âåêòîð ìíî-
æèòåëåé Ëàãðàíæà u* , ïðè êîòîðîì ôóíêöèÿ L u x f( , )* *� áûëà ïðåäñòàâèìà
â âèäå ñóììû êâàäðàòîâ ëèíåéíûõ ôîðì:
� � �
�
u L u x f l xi
i
k
* * *: ( , ) ( )2
1
. (6)
Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü. Ïóñòü � * *� f . Ïðè u u� * , ãäå u* �
�
� �
arg ( )sup
u D U
u� , ðåøåíèå âíóòðåííåé çàäà÷è (3) x u K u b u( ) ( ) ( ) /� � �1 2 (K u( ) —
íåâûðîæäåííàÿ ìàòðèöà ïðè u D U� � ) ñòðåìèòñÿ ê íåêîòîðîé òî÷êå x * èç îá-
ëàñòè, çàäàâàåìîé ñèñòåìîé ëèíåéíûõ óðàâíåíèé L u x K u x b ux ( , ) ( ) ( )* * *� � �2 0
(ïðè÷åì x * íåîáÿçàòåëüíî ÿâëÿåòñÿ òî÷êîé ìèíèìóìà èñõîäíîé çàäà÷è). Ïîñêîëüêó
L u x x K u x b u x c uT T( , ) ( ) ( ) ( )� � � �
� � � � �( ( )) ( )( ( )) ( ) ( ) ( ) ( )x x u K u x x u c u x u K u x uT T ,
ïðè u* èìååì
L u x x x K u x x c u x K u xT T
( , ) ( ) ( )( ) ( ) ( )* * * * * * * *� � � � � �
� � � � �( ) ( )( )* * * *x x K u x xT �
� � � � � � �
�
( ) ( )( ) ( , )* * * * * * * *x x K u x x f x x fT
i i
i
n
� �
1
2 ,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 37
ãäå � i
* — ñîáñòâåííûå ÷èñëà, à � i
* — ñîáñòâåííûå âåêòîðû ìàòðèöû K u( )* .
(Îòìåòèì, ÷òî â ñëó÷àå âûðîæäåííîñòè ìàòðèöû K u( )* ëèíåéíûå ÷ëåíû îò-
ñóòñòâóþò, ïîñêîëüêó â ïðîòèâíîì ñëó÷àå �( )*u � � �.) Òàê êàê âñå ñîáñòâåííûå
÷èñëà ìàòðèöû K u( )* íåîòðèöàòåëüíû (u D* � ), èñêîìîå ðàçëîæåíèå ïîëó÷åíî.
Äîñòàòî÷íîñòü. Ïóñòü ñóùåñòâóåò òàêîå ~u U� � , ÷òî L u x f l xi
i
k
(~, ) ( )*� �
�
2
1
,
ãäå l xi ( ) — ëèíåéíûå ôîðìû. Òîãäà �(~ ) min (~, ) min ( ) * *u L u x l x f f
x x
i
i
k
� � � �
�
2
1
.
Íî ïî îïðåäåëåíèþ ôóíêöèÿ �( )u ÿâëÿåòñÿ îöåíêîé ñíèçó f * äëÿ âñåõ
u D U� � , ò.å. �(~ ) *u f� , ïðè÷åì ~ *u u� è l xi ( )* � 0, i k�1, .
Äîêàçàòåëüñòâî äîñòàòî÷íîñòè óñëîâèÿ (6) è òåîðåìû 4 â öåëîì çàâåðøåíî.
Èç òåîðåìû âèäíî, ÷òî ïðèìåð èç ðàçä. 1 ñ ôóíêöèîíàëüíî èçáûòî÷íûì
îãðàíè÷åíèåì y K x f2
0 0� � �( ) * íå ñîâñåì «èñêóññòâåííûé». Ôàêòè÷åñêè,
ñìûñë äâîéñòâåííûõ îöåíîê, ïðåäëîæåííûõ Í.Ç. Øîðîì, çàêëþ÷àåòñÿ â ïîñòðîå-
íèè ñåìåéñòâà îãðàíè÷åííûõ ñíèçó íà �
n êâàäðàòè÷íûõ ôóíêöèé îò ïåðåìåí-
íûõ x (ò.å. îíè âûïóêëû è, áîëåå òîãî, ïðåäñòàâèìû â âèäå ñóììû êâàäðàòîâ ëè-
íåéíûõ ôîðì è çíà÷åíèÿ ìèíèìóìà êâàäðàòè÷íîé ôóíêöèè), êàæäàÿ èç êîòîðûõ
ñîîòâåòñòâóåò íåêîòîðîìó u U� � è åå ìèíèìàëüíîå çíà÷åíèå íå áîëüøå, ÷åì f *
èñõîäíîé çàäà÷è (1). Åñëè ñðåäè íèõ íàéäåòñÿ õîòÿ áû îäíà ôóíêöèÿ ñ ìèíèìó-
ìîì, ðàâíûì f * , òî îöåíêà òî÷íàÿ. Òàêèì îáðàçîì, ìîæíî ãîâîðèòü îá «îâûïóê-
ëåíèè» èñõîäíîé çàäà÷è, òåì áîëåå, ÷òî ïðè x T� ôóíêöèè ýòîãî ñåìåéñòâà «àï-
ïðîêñèìèðóþò» ñíèçó öåëåâóþ ôóíêöèþ f x0 ( ) çàäà÷è (1), à ðîëü ôóíêöèîíàëüíî
èçáûòî÷íûõ îãðàíè÷åíèé â òåõíèêå äâîéñòâåííûõ îöåíîê Í.Ç. Øîðà
çàêëþ÷àåòñÿ â ðàñøèðåíèè ýòîãî ñåìåéñòâà ôóíêöèé.
Çàìåòèì, ÷òî îãðàíè÷åííîñòü ñíèçó êâàäðàòè÷íûõ ôóíêöèé L u x( , ) äîñòèãà-
åòñÿ íå òîëüêî íà îáëàñòè D ïîëîæèòåëüíîé îïðåäåëåííîñòè ìàòðèöû K u( ), íî è
â íåêîòîðîì ïîäìíîæåñòâå ìíîæåñòâà D D\ . Ïðè÷åì åñëè u u D D
u D
� �
�
* \ ïðè
ðåøåíèè çàäà÷è (2), òî L u x( , )* ÿâëÿåòñÿ èìåííî òàêîé ôóíêöèåé, ò.å. ìîæíî
áûëî áû ðàñøèðèòü äîïóñòèìóþ îáëàñòü D äâîéñòâåííûõ ïåðåìåííûõ äî ýôôåê-
òèâíîãî ìíîæåñòâà çàäà÷è (3) (ìíîæåñòâà, ãäå ôóíêöèÿ �( )u íå ðàâíà � �), è ðå-
çóëüòàò ïðè ýòîì íå èçìåíèòñÿ.  ïðèíöèïå ìîæíî äàæå ðàññìàòðèâàòü çàäà÷è
(2) è (3) íà âñåì ïðîñòðàíñòâå �
m äâîéñòâåííûõ ïåðåìåííûõ, íî òîãäà âíóòðåí-
íÿÿ çàäà÷à (3) äàåò òðèâèàëüíóþ îöåíêó � � ïðè x u( ), ñòðåìÿùèõñÿ
ê áåñêîíå÷íîñòè, ÷òî íå äàåò íèêàêîé ïîëåçíîé èíôîðìàöèè.
 çàêëþ÷åíèå îòìåòèì, ÷òî òåîðåìó 4 ìîæíî èñïîëüçîâàòü äëÿ ïîëó÷åíèÿ
÷àñòíûõ ðåçóëüòàòîâ (â òîì ÷èñëå è èçâåñòíûõ). Ïîêàæåì, íàïðèìåð, êàê ñ åå ïî-
ìîùüþ äîêàçàòü òåîðåìó 1 (â îòëè÷èå îò äîêàçàòåëüñòâà â [1] çäåñü íå ïîòðåáóåò-
ñÿ âñïîìîãàòåëüíîé òåîðåìû î ñäâèãå). Äåéñòâèòåëüíî, íåîáõîäèìîå è äîñòàòî÷-
íîå óñëîâèå òî÷íîñòè äâîéñòâåííîé îöåíêè êâàäðàòè÷íîé çàäà÷è (4), (5) ñîãëàñ-
íî òåîðåìå 4 ôîðìóëèðóåòñÿ ñëåäóþùèì îáðàçîì: � � �
�
u L R u f l Ri
i
k
* * *: ( , ) ( )2
1
.
Ïîäñòàâèì âìåñòî ïåðåìåííûõ R ( )� ñîîòâåòñòâóþùèå âûðàæåíèÿ â èñõîäíûõ
ïåðåìåííûõ x. Ïðè ýòîì ëèíåéíûå ôîðìû l Ri ( ) ïðèìóò âèä ïîëèíîìîâ —
l R P xi i( ) ( )� , à âñå ñëàãàåìûå ñ äâîéñòâåííûìè ïåðåìåííûìè îáðàòÿòñÿ
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
â íîëü, ïîñêîëüêó âî âñåõ îãðàíè÷åíèÿõ R R R Ri j k l( ) ( ) ( ) ( )( ) ( ) ( ) ( )� � � �� � 0,
� � � �( ) ( ) ( ) ( )i j k l� � � îáà ÷ëåíà ïðåäñòàâëÿþò ñîáîé îäèí è òîò æå ìîíîì, âû-
ðàæåííûé â ðàçíûõ ïåðåìåííûõ, ò.å. L R u P x( , ) ( )� 0 . Òàêèì îáðàçîì, èç óñëîâèÿ
(6) ñëåäóåò P x f P xi
i
k
0
2
1
( ) ( )*� �
�
, è íåîáõîäèìîñòü óñëîâèÿ òî÷íîñòè äâîéñò-
âåííîé îöåíêè êâàäðàòè÷íîé çàäà÷è (4), (5), ñôîðìóëèðîâàííîãî â òåîðåìå 1, äî-
êàçàíà. Òåïåðü ðàññìîòðèì äîñòàòî÷íîñòü óñëîâèÿ òåîðåìû 1. Ïîäñòàíîâêè ñïðà-
âåäëèâû è â îáðàòíóþ ñòîðîíó, ò.å. åñëè áû ðàçëîæåíèå P x f P xi
i
k
0
2
1
( ) ( )*� �
�
áûëî èçâåñòíî, òî ïðè ïîñòðîåíèè êâàäðàòè÷íîé çàäà÷è (4), (5) äîñòàòî÷íî áûëî
áû çàìåíèòü ìîíîìû ïîëèíîìîâ P xi ( ) íà ñîîòâåòñòâóþùèå ïåðåìåííûå R ( )� ,
÷òîáû ïîëó÷èòü êâàäðàòè÷íóþ çàäà÷ó ñ öåëåâîé ôóíêöèåé f R0 ( ) , äëÿ êîòîðîé
ñïðàâåäëèâî âûðàæåíèå (6) ïðè u* � 0 . Ïîñêîëüêó èçíà÷àëüíî òàêîå ðàçëîæåíèå
íåèçâåñòíî (à ïî ïðåäïîëîæåíèþ îíî ñóùåñòâóåò), èìåííî äëÿ åãî íàõîæäåíèÿ
(òî÷íåå, íàõîæäåíèÿ
~
( )f R0 ) è ââîäÿòñÿ îãðàíè÷åíèÿ âèäà R Ri j( ) ( )( ) ( )� � �
� �R Rk l( ) ( )( ) ( )� � 0, � � � �( ) ( ) ( ) ( )i j k l� � � — ñ ïîìîùüþ ëèíåéíîé êîìáèíà-
öèè ýòèõ îãðàíè÷åíèé â ôóíêöèè Ëàãðàíæà ìîíîìû èçíà÷àëüíî ïðîèçâîëüíî
îïðåäåëåííîé öåëåâîé ôóíêöèè f R0 ( ) (P x0 ( ) â ïåðåìåííûõ R îïðåäåëÿåòñÿ íå-
îäíîçíà÷íî) ïðèâîäÿòñÿ ê íåîáõîäèìîìó äëÿ âûäåëåíèÿ êâàäðàòîâ âèäó èëè,
äðóãèìè ñëîâàìè, ôóíêöèÿ f R0 ( ) ïðèâîäèòñÿ ê âèäó
~
( )f R0 .
Òàêèì îáðàçîì, íåîáõîäèìîå è äîñòàòî÷íîå óñëîâèå òî÷íîñòè äâîéñòâåííîé
îöåíêè èç òåîðåìû 4 äëÿ êâàäðàòè÷íîé çàäà÷è ñïåöèàëüíîãî âèäà (4), (5) ýêâèâà-
ëåíòíî óñëîâèþ P x f P xi
i
k
0
2
1
( ) ( )*� �
�
, ÷òî è òðåáîâàëîñü äîêàçàòü.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ø î ð Í . Ç . , Ñ ò å ö å í ê î Ñ . È . Êâàäðàòè÷íûå ýêñòðåìàëüíûå çàäà÷è è íåäèôôåðåíöèðóåìàÿ
îïòèìèçàöèÿ. — Êèåâ: Íàóê. äóìêà, 1989. — 208 ñ.
2. S h o r N . Z . Nondifferentiable optimization and polynomial problems. — Dordrecht: Kluwer, 1998. —
394 p.
3. Ñ ò å ö þ ê Ï . È . Íîâûå ìîäåëè êâàäðàòè÷íîãî òèïà äëÿ çàäà÷è î ìàêñèìàëüíîì âçâåøåííîì ðàçðåçå
ãðàôà // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 1. — C. 63–75.
4. Á å ð å ç î â ñ ê è é Î . À . , Ñ ò å ö þ ê Ï . È . Îá îäíîì ñïîñîáå íàõîæäåíèÿ äâîéñòâåííûõ
êâàäðàòè÷íûõ îöåíîê Øîðà // Òàì æå. — 2008. — ¹ 2. — Ñ. 89–99.
5. Ø î ð Í . Ç . , Á å ð å ç î â ñ ê è é Î . À . Íàõîæäåíèå ãëîáàëüíîãî ýêñòðåìóìà êâàäðàòè÷íîé ôóíêöèè
íà êâàäðàòè÷íîé ïîâåðõíîñòè // Èíôîðìàöèîííûå òåõíîëîãèè â íàó÷íûõ èññëåäîâàíèÿõ è èñïû-
òàíèÿõ. — Êèåâ: Èí-ò êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, 1991. — Ñ. 30–34.
6. Ñ ò å ö þ ê Ï . È . , Ï à ð ä à ë î ñ Ï . Ì Îá óòî÷íåíèè ëàãðàíæåâûõ äâîéñòâåííûõ îöåíîê â áèíàðíûõ
è áóëåâûõ êâàäðàòè÷íûõ çàäà÷àõ // Òåîðèÿ îïòèìàëüíûõ ðåøåíé. — Êèåâ: Èí-ò êèáåðíåòèêè
èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, 2006. — Ñ. 145–153.
7. Ñ ò å ö þ ê Ï . È . , Ï à ð ä à ë î ñ Ï . Ì . , Ê ð î ø ê î Ä . Ë . Î íîâûõ ëàãðàíæåâûõ äâîéñòâåííûõ
îöåíêàõ äëÿ ÷èñëà óñòîé÷èâîñòè ãðàôà // Êîìïüþòåðíàÿ ìàòåìàòèêà. — 2006. — ¹ 3. — C. 149–158.
8. Ñ ò å ö þ ê Ï . È . Î íîâûõ ñâîéñòâàõ îöåíîê Øîðà äëÿ âçâåøåííîãî ÷èñëà óñòîé÷èâîñòè ãðàôà //
Ïðàö³ ̳æíàð. êîíô. «50 ðîêiâ Iíñòèòóòó êiáåðíåòèêè iì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè». — Êèåâ:
Èí-ò êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, 2008. — Ñ. 164–173.
Ïîñòóïèëà 18.05.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 39
|
| id | nasplib_isofts_kiev_ua-123456789-84014 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:33:36Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Березовский, О.А. 2015-07-02T08:01:38Z 2015-07-02T08:01:38Z 2012 О точности двойственных оценок для квадратичных экстремальных задач / О.А. Березовский // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 33-39. — Бібліогр.: 8 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84014 519.8 Дано короткий огляд відомих часткових результатів про точність двоїстих оцінок, запропонованих Н.З. Шором, для квадратичних екстремальних задач. Наведено необхідну та достатню умову точності двоїстої оцінки для квадратичної задачі у загальному випадку. The paper briefly reviews the well-known partial results on the accuracy of dual bounds proposed by N. Z. Shor for quadratic extremal problems. The necessary and sufficient condition for the accuracy of the dual bound for a quadratic problem of general form is presented. Работа выполнена частично в рамках проекта № IZ73ZO_127962 (SNSF, Швейцария). ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ О точности двойственных оценок для квадратичных экстремальных задач Про точність двоїстих оцінок для квадратичних екстремальних задач On the accuracy of dual bounds for quadratic extremal problems Article published earlier |
| spellingShingle | О точности двойственных оценок для квадратичных экстремальных задач Березовский, О.А. Системный анализ |
| title | О точности двойственных оценок для квадратичных экстремальных задач |
| title_alt | Про точність двоїстих оцінок для квадратичних екстремальних задач On the accuracy of dual bounds for quadratic extremal problems |
| title_full | О точности двойственных оценок для квадратичных экстремальных задач |
| title_fullStr | О точности двойственных оценок для квадратичных экстремальных задач |
| title_full_unstemmed | О точности двойственных оценок для квадратичных экстремальных задач |
| title_short | О точности двойственных оценок для квадратичных экстремальных задач |
| title_sort | о точности двойственных оценок для квадратичных экстремальных задач |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84014 |
| work_keys_str_mv | AT berezovskiioa otočnostidvoistvennyhocenokdlâkvadratičnyhékstremalʹnyhzadač AT berezovskiioa protočnístʹdvoístihocínokdlâkvadratičnihekstremalʹnihzadač AT berezovskiioa ontheaccuracyofdualboundsforquadraticextremalproblems |