Об одном способе нахождения двойственных квадратичных оценок Шора
Для квадратичної задачі загального вигляду побудовано аналог у вигляді однорідної квадратичної задачі. Доведено рівність оцінок ψ*, побудованих на базі техніки двоїстих квадратичних оцінок Шора для цих задач. У випадку однорідної квадратичної задачі показано, що знаходження ψ* зводиться до розв'...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2008 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/72000 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Об одном способе нахождения двойственных квадратичных оценок Шора / О.А. Березовский, П.И. Стецюк // Кибернетика и системный анализ. — 2008. — № 2. — С. 89-98. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859913050820182016 |
|---|---|
| author | Березовский, О.А. Стецюк, П.И. |
| author_facet | Березовский, О.А. Стецюк, П.И. |
| citation_txt | Об одном способе нахождения двойственных квадратичных оценок Шора / О.А. Березовский, П.И. Стецюк // Кибернетика и системный анализ. — 2008. — № 2. — С. 89-98. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Для квадратичної задачі загального вигляду побудовано аналог у вигляді однорідної квадратичної задачі. Доведено рівність оцінок ψ*, побудованих на базі техніки двоїстих квадратичних оцінок Шора для цих задач. У випадку однорідної квадратичної задачі показано, що знаходження ψ* зводиться до розв'язання безумовної задачі мінімізації випуклої функції.
|
| first_indexed | 2025-12-07T16:03:29Z |
| format | Article |
| fulltext |
ÓÄÊ 519.8
Î.À. ÁÅÐÅÇÎÂÑÊÈÉ, Ï.È. ÑÒÅÖÞÊ
ÎÁ ÎÄÍÎÌ ÑÏÎÑÎÁÅ ÍÀÕÎÆÄÅÍÈß ÄÂÎÉÑÒÂÅÍÍÛÕ
ÊÂÀÄÐÀÒÈ×ÍÛÕ ÎÖÅÍÎÊ ØÎÐÀ1
Êëþ÷åâûå ñëîâà: êâàäðàòè÷íàÿ çàäà÷à, äâîéñòâåííàÿ îöåíêà Øîðà, îòðèöà-
òåëüíàÿ îïðåäåëåííîñòü ìàòðèöû, ñîáñòâåííîå ÷èñëî ìàòðèöû, ìíîæèòåëè
Ëàãðàíæà, íåãëàäêàÿ øòðàôíàÿ ôóíêöèÿ.
ÂÂÅÄÅÍÈÅ
Ïîä êâàäðàòè÷íîé çàäà÷åé ïîíèìàþò çàäà÷ó ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ,
â êîòîðîé öåëåâàÿ ôóíêöèÿ è âñå ôóíêöèè îãðàíè÷åíèé êâàäðàòè÷íû:
f f x x K x b x
x R
T T
n
* ( )� � �
�
max { }0 0
(1)
ïðè îãðàíè÷åíèÿõ
x K x b x c i mT
i i
T
i� � � �0 1 1, , ,
(2)
x K x b x c i m mT
i i
T
i� � � � �0 11, , .
 ñëó÷àå, êîãäà â çàäà÷å (1), (2) � � �i m bi{ }0 1 0, , . . ., (ò.å. âñå ôóíêöèè çàäà-
÷è ïðåäñòàâëÿþò ñîáîé îäíîðîäíûå êâàäðàòè÷íûå ôîðìû), áóäåì ãîâîðèòü îá
îäíîðîäíîé êâàäðàòè÷íîé çàäà÷å.
 âèäå (1), (2) ïðåäñòàâèì ðÿä îáùåèçâåñòíûõ çàäà÷, òàêèõ êàê çàäà÷à ëèíåé-
íîé äîïîëíèòåëüíîñòè, êâàäðàòè÷íàÿ çàäà÷à î íàçíà÷åíèÿõ, çàäà÷è ïðîåêòèðîâà-
íèÿ, ýêñòðåìàëüíûå çàäà÷è íà ãðàôàõ (íàïðèìåð, çàäà÷è ðàñêðàñêè è ðàçðåçàíèÿ
ãðàôîâ, íàõîæäåíèå ìàêñèìàëüíîãî íåçàâèñèìîãî ìíîæåñòâà, ìàêñèìàëüíîãî
âçâåøåííîãî ðàçðåçà, ìàêñèìàëüíîãî k-êëàáà è ò.ï.). Áîëåå òîãî, ê âèäó êâàäðà-
òè÷íûõ çàäà÷ ñâîäèòcÿ áîëåå øèðîêèé êëàññ ïîëèíîìèàëüíûõ çàäà÷ (â êîòîðûõ
öåëåâàÿ ôóíêöèÿ è âñå ôóíêöèè îãðàíè÷åíèé ïîëèíîìèàëüíû) ñ âåùåñòâåííûìè
è áóëåâûìè ïåðåìåííûìè ïóòåì ââåäåíèÿ äîïîëíèòåëüíûõ ïåðåìåííûõ è êâàä-
ðàòè÷íûõ îãðàíè÷åíèé, ñâÿçûâàþùèõ ïåðåìåííûå èñõîäíîé ïîëèíîìèàëüíîé çà-
äà÷è ñ ðàñøèðåííûì ìíîæåñòâîì ïåðåìåííûõ ïîëó÷åííîé êâàäðàòè÷íîé çàäà÷è.
Îòìåòèì, ÷òî òàêîå ñâåäåíèå íåîäíîçíà÷íî, âïðî÷åì, êàê è ïðåäñòàâëåíèå ïðîèç-
âîëüíîé êâàäðàòè÷íîé çàäà÷è, íàïðèìåð, çà ñ÷åò ôóíêöèîíàëüíî èçáûòî÷íûõ
îãðàíè÷åíèé, êîòîðûå íå âëèÿþò íà îáëàñòü äîïóñòèìûõ çíà÷åíèé.  îáùåì ñëó-
÷àå çàäà÷à (1), (2) ìíîãîýêñòðåìàëüíà è îòíîñèòñÿ ê êëàññó NP-òðóäíûõ çàäà÷. Â
ñâÿçè ñ ýòèì âîçíèêàåò îïðåäåëåííûé èíòåðåñ ê ðàçðàáîòêå ýôôåêòèâíûõ
ìåòîäîâ íàõîæäåíèÿ îöåíîê äëÿ äàííîé çàäà÷è êàê ñ ïðàêòè÷åñêîé òî÷êè çðåíèÿ
îöåíêè ðåøåíèÿ çàäà÷è çà «ïðèåìëåìîå» (ïîëèíîìèàëüíîå) âðåìÿ, òàê è èõ
èñïîëüçîâàíèÿ â ñõåìå âåòâåé è ãðàíèö.
 ðàáîòàõ [1, 2] äëÿ ïîëó÷åíèÿ âåðõíèõ îöåíîê � * îïòèìóìà f * çàäà÷è (1),
(2) Í.Ç. Øîðîì ïðåäëîæåí è èññëåäîâàí äâîéñòâåííûé ïîäõîä, îñíîâàííûé íà
èñïîëüçîâàíèè ôóíêöèè Ëàãðàíæà:
� �* *( ) ( )� � �
� � �
inf max
u D U x T
u f x f .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 89
1Ðàáîòà âûïîëíåíà ïðè ÷àñòè÷íîé ôèíàíñîâîé ïîääåðæêå ãðàíòà UKM2-2812-KV-06 (CRDF
Cooperative Grants Program).
© Î.À. Áåðåçîâñêèé, Ï.È. Ñòåöþê, 2008
Çäåñü �( ) ( , )u L x u
x R n
�
�
sup ; L x u x K u x b u x c uT T( , ) ( ) ( ) ( )� � � — ôóíêöèÿ Ëàãðàí-
æà äëÿ çàäà÷è (1), (2), â êîòîðîé
K u K u K b u b u b c u u c
i
m
i i
i
m
i i
i
m
i i( ) , ( ) , ( )� � � � �
� � �
0
1
0
1 1
;
U — îáëàñòü îïðåäåëåíèÿ âåêòîðà ìíîæèòåëåé Ëàãðàíæà u R m� :
U u u i m Di
� � �{ }: , , ;0 1 1 — ìíîæåñòâî òî÷åê u, â êîòîðûõ ìàòðèöà K u( )
îòðèöàòåëüíî îïðåäåëåíà.
Òàêîå ñóæåíèå äîïóñòèìîé îáëàñòè ïðè äàííîì ïîäõîäå ê îöåíêå
âïîëíå îïðàâäàíî, ïîñêîëüêó ïðè u D� (ãäå D — çàìûêàíèå ìíîæåñòâà D
è ñîîòâåòñòâóåò íåïîëîæèòåëüíîé îïðåäåëåííîñòè ìàòðèöû K u( )) èìååì òðèâè-
àëüíóþ (íå íåñóùóþ íèêàêîé èíôîðìàöèè) îöåíêó �( )u � � �.  ñëó÷àå, êîã-
äà u D� , âíóòðåííÿÿ çàäà÷à íàõîæäåíèÿ ôóíêöèè �( )u ÿâëÿåòñÿ çàäà÷åé ìàêñè-
ìèçàöèè ñòðîãî âîãíóòîé êâàäðàòè÷íîé ôóíêöèè, äëÿ ðåøåíèÿ êîòîðîé íåîá-
õîäèìî ðåøèòü ñèñòåìó ëèíåéíûõ óðàâíåíèé L x u K u x b ux
� � �( , ) ( ) ( )2 0,
îòêóäà x K u b u� 1 2( ) ( ) / . Òîãäà âíåøíÿÿ çàäà÷à ïðåäñòàâëÿåò ñîáîé çàäà÷ó íà-
õîæäåíèÿ èíôèíóìà âûïóêëîé íåïðåðûâíî äèôôåðåíöèðóåìîé ôóíêöèè
�( ) ( ) ( ) ( ) / ( )u b u K u b u c uT� � 1 4 íà âûïóêëîì ìíîæåñòâå D U� . Îòìåòèì,
÷òî äîïóñòèìàÿ îáëàñòü âíåøíåé çàäà÷è â íåêîòîðûõ ñëó÷àÿõ ìîæåò áûòü ðàñ-
øèðåíà çà ñ÷åò u G D D U� � � ( / ) (íåêîòîðîãî ïîäìíîæåñòâà G çíà÷åíèé ïåðå-
ìåííîé u, ïðè êîòîðûõ K u( ) íåïîëîæèòåëüíî îïðåäåëåíà è âûðîæäåíà). Ýòî âîç-
ìîæíî ïðè òåõ çíà÷åíèÿõ u D D� / , êîãäà ôóíêöèÿ L x u( , ) îãðàíè÷åíà ñâåðõó ïî x, ÷òî
ýêâèâàëåíòíî ìíîæåñòâó ïåðåìåííûõ u, óäîâëåòâîðÿþùèõ õîòÿ áû îäíîé èç n
ñèñòåì âèäà
b u u
u
T
i
i
( ) ( ) ,
( ) ,
�
�
�
�
�
�
�
��
0
0
i n�{ }1, . . ., ,
ãäå � i u( ) — ñîáñòâåííîå ÷èñëî ìàòðèöû K u ui( ), ( )� — ñîáñòâåííûé âåêòîð ìàò-
ðèöû K u( ), ñîîòâåòñòâóþùèé � i u( ). (Äàííûå óñëîâèÿ â âèäå ñèñòåì ëåãêî ïîëó-
÷èòü ïîñëå ïðèâåäåíèÿ êâàäðàòè÷íîé ïî x ôîðìû L x u( , ) ê êàíîíè÷åñêîìó âèäó.)
 [1] äîêàçàí ñëåäóþùèé ôàêò.
Ëåììà 1.Åñëè � �* ( )�
� �
inf
u D U
u äîñòèãàåòñÿ íà ìíîæåñòâå D, òî � * *� f .
Îäíàêî äëÿ áîëüøèíñòâà çàäà÷ îöåíêó � * ïîëó÷àåì ïðè u, ñòðåìÿùåìñÿ ê
ãðàíèöå íåïîëîæèòåëüíîé îïðåäåëåííîñòè D D/ . Ïðè ýòîì âîçíèêàþò ïðîáëåìû
ïðè íàõîæäåíèè îáðàòíîé ìàòðèöû K u K u 1 ( ) ( ( ) ñòðåìèòñÿ ê âûðîæäåííîñòè)
âî âíóòðåííåé çàäà÷å è ïðè ó÷åòå âûïîëíåíèÿ îãðàíè÷åíèÿ u D� äëÿ âíåøíåé çà-
äà÷è (âîçíèêàåò âîïðîñ âûáîðà ñïîñîáà âîçâðàòà â äîïóñòèìóþ îáëàñòü ïî u, ïî-
ñêîëüêó ïðè âûõîäå èç îáëàñòè îòðèöàòåëüíîé îïðåäåëåííîñòè ïðîèñõîäèò ðàç-
ðûâ ôóíêöèè �( )u — îíà ñòàíîâèòñÿ ðàâíîé � �, èëè, äðóãèìè ñëîâàìè, íåîïðå-
äåëåííîé). Íèæå ïðåäñòàâëåí ïîäõîä, ïîçâîëÿþùèé îáîéòè ýòè òðóäíîñòè. Åãî
ñóòü çàêëþ÷àåòñÿ â ñâåäåíèè êâàäðàòè÷íîé çàäà÷è îáùåãî âèäà (1), (2) ê îäíîðîä-
íîé êâàäðàòè÷íîé çàäà÷å (â ðàçä. 5 ïîêàçàíî, ÷òî äâîéñòâåííûå îöåíêè â îáîèõ
ñëó÷àÿõ ðàâíû), äëÿ êîòîðîé ðåøåíèå âíóòðåííåé çàäà÷è òðèâèàëüíî (êîãäà K u( )
îòðèöàòåëüíî îïðåäåëåíà, òî x * � 0, ãäå 0 — íóëåâîé n-ìåðíûé âåêòîð) è óïî-
ìÿíóòûå âûøå ïðîáëåìû íå àêòóàëüíû. Áîëåå òîãî, ïîëó÷åííàÿ îäíîðîäíàÿ
90 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
çàäà÷à ñâîäèìà ê áåçóñëîâíîé çàäà÷å ìèíèìèçàöèè âûïóêëîé ôóíêöèè, äëÿ
ðåøåíèÿ êîòîðîé äîñòàòî÷íî ýôôåêòèâíî ìîæíî èñïîëüçîâàòü ìåòîäû íå-
ãëàäêîé îïòèìèçàöèè (íàïðèìåð, ðàçëè÷íûå ìîäèôèêàöèè r-àëãîðèòìà [1, 2]).
1. ÑÂÅÄÅÍÈÅ ÊÂÀÄÐÀÒÈ×ÍÎÉ ÇÀÄÀ×È ÎÁÙÅÃÎ ÂÈÄÀ Ê ÎÄÍÎÐÎÄÍÎÉ
ÊÂÀÄÐÀÒÈ×ÍÎÉ ÇÀÄÀ×Å
Äëÿ ïðîèçâîëüíîé êâàäðàòè÷íîé çàäà÷è (1), (2) ïóòåì ââåäåíèÿ äîïîëíèòåëü-
íîé ïåðåìåííîé ìîæíî ïîñòðîèòü àíàëîã â âèäå îäíîðîäíîé êâàäðàòè÷íîé
çàäà÷è
max
x R z R
T T
n
x K x b xz
� �
�
,
( )
0
1
0 0 0 (3)
ïðè îãðàíè÷åíèÿõ
x K x b xz c i mT
i i
T
i� � � �0 10 1, , ,
(4)
x K x b xz c i m mT
i i
T
i� � � � �0 10 1, , ,
z
0
2
1� . (5)
Çàäà÷à (3)–(5) ñîîòâåòñòâóåò äâóì ýêâèâàëåíòíûì (â ñìûñëå ðàâåíñòâà îïòè-
ìàëüíûõ çíà÷åíèé öåëåâîé ôóíêöèè) çàäà÷àì: ïðè z0 1� — çàäà÷å (1), (2),
ïðè z0 1� — çàäà÷å, êîòîðàÿ âîçíèêàåò â ðåçóëüòàòå çàìåíû ïåðåìåííûõ
y x� â çàäà÷å (1), (2):
f y K y b y
y R
T T
n
* ( )�
�
max 0 0
ïðè îãðàíè÷åíèÿõ
y K y b y c i mT
i i
T
i � � �0 1 1, , ,
y K y b y c i m mT
i i
T
i � � � �0 11, , .
Ãåîìåòðè÷åñêèé ñìûñë ïðèâåäåííîãî óòâåðæäåíèÿ äîñòàòî÷íî ïðîñòîé — ðàñ-
øèðåíèå èñõîäíîé çàäà÷è ïóòåì äîîïðåäåëåíèÿ åå ñèììåòðè÷íî îñè çíà÷åíèé
ôóíêöèé (äëÿ îáëàñòè îïðåäåëåíèÿ — îòíîñèòåëüíî öåíòðà êîîðäèíàò). Îäíàêî
îòìåòèì, ÷òî ïðè òàêîì ñâåäåíèè êâàäðàòè÷íîé çàäà÷è ê îäíîðîäíîìó âèäó êî-
ëè÷åñòâî òî÷åê ìàêñèìóìà óâåëè÷èâàåòñÿ â äâà ðàçà. Òîãäà åñëè ïðèìåíèòü äëÿ
ðåøåíèÿ çàäà÷è (3)–(5) òåîðèþ äâîéñòâåííûõ êâàäðàòè÷íûõ îöåíîê [1, 2], òî ïî-
ëó÷åííàÿ îöåíêà âñåãäà áóäåò äîñòèãàòüñÿ íà ãðàíèöå îòðèöàòåëüíîé îïðåäåëåí-
íîñòè. Òàêèì îáðàçîì, äàæå â ñëó÷àå «õîðîøåé» èñõîäíîé çàäà÷è, äëÿ êîòîðîé
ìíîæåñòâî ðåøåíèé ñîñòîèò èç îäíîé òî÷êè è äâîéñòâåííàÿ îöåíêà òî÷íàÿ, ðàñ-
ñìîòðåíèå îäíîðîäíîãî àíàëîãà íå ïîçâîëèò ïîëó÷èòü íåïîñðåäñòâåííî çíà÷åíèå
x * . Ïîýòîìó òàêîå ñâåäåíèå èìååò ñìûñë òîëüêî â òåõ ñëó÷àÿõ (ñëåäóåò îòìå-
òèòü, äîñòàòî÷íî ìíîãî÷èñëåííûõ), êîãäà ðåøåíèå íå åäèíñòâåííî èëè îöåíêà íå
òî÷íàÿ è ïåðåõîä ê çàäà÷å áåçóñëîâíîé îïòèìèçàöèè îïðàâäàí.
2. ÄÂÎÉÑÒÂÅÍÍÀß ÎÖÅÍÊÀ ÄËß ÎÄÍÎÐÎÄÍÎÉ ÊÂÀÄÐÀÒÈ×ÍÎÉ ÇÀÄÀ×È
Ðàññìîòðèì îäíîðîäíóþ êâàäðàòè÷íóþ çàäà÷ó
f x K x
x R
T
n
* �
�
max 0
(6)
ïðè îãðàíè÷åíèÿõ
x K x c i mT
i i� � �0 1 1, , ,
(7)
x K x c i m mT
i i� � � �0 11, , ,
è ïðèìåíèì îïèñàííóþ âî ââåäåíèè òåõíèêó Í.Ç. Øîðà äëÿ ïîëó÷åíèÿ äâîé-
ñòâåííîé îöåíêè [1, 2].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 91
Ïîñòðîèì ôóíêöèþ Ëàãðàíæà äëÿ çàäà÷è (6), (7)
L x u x K x u x K x cT
i
i
m
T
i
T
i( , ) ( )� � �
�
0
1
è ðàññìîòðèì ìàðãèíàëüíóþ ôóíêöèþ �( ) ( , )u L x u
x
� sup , êîòîðàÿ èìååò âèä
�
�
�
( )
, ( ( )) ,
, ( ( ))
max
max
u
K u
u c K u
i
m
i i
�
� � �
�
åcëè
åcëè
0
1
�
�
�
��
�
�
�
0,
ãäå � max ( ( ))K u — ìàêñèìàëüíîå ñîáñòâåííîå ÷èñëî ìàòðèöû
K u K K
i
m
i( ) � �
�
0
1
(äîïóñòèìàÿ îáëàñòü âíåøíåé çàäà÷è â äàííîì ñëó÷àå ìî-
æåò áûòü ðàñøèðåíà äî D , ïîñêîëüêó �( ) ( , )u L x u
x R n
�
�
sup ïðè u D� ðàâíà
max
x R n
L x u L u
�
�( , ) ( , )0 ïðè u D� ).
Òàêèì îáðàçîì, âåðõíÿÿ äâîéñòâåííàÿ êâàäðàòè÷íàÿ îöåíêà � * [2] äëÿ çàäà-
÷è (6), (7) ìîæåò áûòü ïîëó÷åíà ïóòåì ðåøåíèÿ çàäà÷è âûïóêëîãî
ïðîãðàììèðîâàíèÿ
f u c
u R i
m
i i
m
* *� �
�
�
�
�
�
�
�
�� �
� min
1
(8)
ïðè îãðàíè÷åíèÿõ
� max ( ( )) ,K u � 0 (9)
u i mi � �0 1 1, , . (10)
3. ÂÑÏÎÌÎÃÀÒÅËÜÍÛÅ ÐÅÇÓËÜÒÀÒÛ
Íàïîìíèì íåñêîëüêî èçâåñòíûõ ðåçóëüòàòîâ, íåîáõîäèìûõ äëÿ ïîñëåäóþùåãî
èçëîæåíèÿ.
Ðàññìîòðèì çàäà÷ó îïòèìèçàöèè
min
y M
f y
�
0 ( ), (11)
f y i k y Mi ( ) , , ,� � �0 1 , (12)
ãäå f y i ki ( ), ,� 0 , — íåïðåðûâíûå ôóíêöèè, M R n� — íåêîòîðîå ìíîæåñ-
òâî. Ââåäåì ñåìåéñòâî çàäà÷, çàâèñÿùåå îò âåêòîðà ïàðàìåòðîâ z R k� ,
V z f y f y z i k y Mi( ) ( ) : ( ) ; , ,� � � �inf { }0 1 1 ,
âëîæåííîé çàäà÷åé êîòîðîãî ÿâëÿåòñÿ èñõîäíàÿ çàäà÷à (ïðè z � 0, ãäå 0 —
k-ìåðíûé íóëåâîé âåêòîð).
Åñëè âîñïîëüçîâàòüñÿ äëÿ ó÷åòà îãðàíè÷åíèé (12) íåãëàäêîé øòðàôíîé
ôóíêöèåé â ôîðìå ôóíêöèè ìàêñèìóìà
�N y f y NF y( ) ( ) ( )� �0 ,
(13)
F y f y f yk( ) max , ( ), . . ., ( )� { }0 1 ,
òî ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà.
92 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
Òåîðåìà 1 [3]. Ïóñòü inf
t
V te V
t
L
�
� � �
0
0( ) ( )
, ãäå e — k-ìåðíûé âåêòîð,
âñå êîìïîíåíòû êîòîðîãî ðàâíû åäèíèöå. Åñëè N L� , òî òî÷êè ìèíèìóìà èñõîäíîé çà-
äà÷èV ( )0 è çàäà÷è inf
y M
N y
�
� ( ), ãäå �N y( ) îïðåäåëÿåòñÿ ïî ôîðìóëå (13), ñîâïàäàþò.
Òàêèì îáðàçîì, òåîðåìà 1 ïîçâîëÿåò óñòàíîâèòü òî÷íîå çíà÷åíèå øòðàôíîãî
ìíîæèòåëÿ ïðè èñïîëüçîâàíèè äëÿ ðåøåíèÿ çàäà÷è (11), (12) íåãëàäêîé øòðàô-
íîé ôóíêöèè â ôîðìå ôóíêöèè ìàêñèìóìà.
 äàëüíåéøåì ïîíàäîáèòñÿ åùå îäèí ðåçóëüòàò.  ñëó÷àå, êîãäà ôóíêöèè
f y i ki ( ), ,� 0 , è ìíîæåñòâî M âûïóêëû, ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 2 [3]. Ïóñòü V ( )0 — êîíå÷íîå ÷èñëî. Âåêòîð � * ÿâëÿåòñÿ âåêòîðîì
Êóíà–Òàêêåðà òîãäà è òîëüêî òîãäà, êîãäà ��� * ( )V 0 .
4. ÎÄÍÎÐÎÄÍÀß ÊÂÀÄÐÀÒÈ×ÍÀß ÇÀÄÀ×À ÁÅÇ ÎÃÐÀÍÈ×ÅÍÈÉ
 ÂÈÄÅ ÍÅÐÀÂÅÍÑÒÂ
Íà ïðàêòèêå ÷àñòî âñòðå÷àþòñÿ çàäà÷è, êîòîðûå ìîæíî ïðåäñòàâèòü êàê îäíî-
ðîäíûå êâàäðàòè÷íûå çàäà÷è áåç îãðàíè÷åíèé â âèäå íåðàâåíñòâ. Ðàññìîòðèì
ýòîò ÷àñòíûé ñëó÷àé çàäà÷è (6), (7), ïðåäïîëàãàÿ, ÷òî îãðàíè÷åíèÿ (7) ñîñòîÿò
òîëüêî èç m îãðàíè÷åíèé-ðàâåíñòâ (m1 0� ), à çíà÷èò, îãðàíè÷åíèÿ (10) â çàäà-
÷å (8)–(10), îïðåäåëÿþùåé äâîéñòâåííóþ îöåíêó, îòñóòñòâóþò.
Âûïèøåì äëÿ çàäà÷è (8), (9) ñåìåéñòâî çàäà÷, çàâèñÿùåå îò z R� 1:
V z u c K u z u R
u i
m
i i
m( ) : ( ( )) ;max� � �
�
�
�
��
�
�
�
���
inf
1
� . (14)
Òåîðåìà 3. Ïóñòü inf
z
V z V
z
L
( ) ( )
� � �
0
, ãäå V z( ) îïðåäåëÿåòñÿ ïî ôîð-
ìóëå (14). Òîãäà ðåøåíèå îäíîðîäíîé êâàäðàòè÷íîé çàäà÷è (8), (9), êîòîðîå äàåò
âåðõíþþ ëàãðàíæåâó îöåíêó äëÿ çàäà÷è (6), (7) (ïðè m1 0� ), ðàâíî
� �*
max ( ( ))� �
�
�
�
�
�
�
�
�� �
min
u R i
m
i i
m
c u L K u
1
.
(15)
Äîêàçàòåëüñòâî. Ïîñêîëüêó ôóíêöèÿ öåëè è åäèíñòâåííàÿ ôóíêöèÿ îãðàíè-
÷åíèÿ çàäà÷è (8), (9) âûïóêëû è ïðåäïîëàãàåòñÿ, ÷òî V ( )0 — êîíå÷íîå ÷èñëî, ñó-
ùåñòâóåò âîçìîæíîñòü äëÿ äàííîé çàäà÷è àíàëèòè÷åñêè îïðåäåëèòü ìíîæèòåëü
Êóíà–Òàêêåðà � * �R 1.
Ñîãëàñíî òåîðåìå 2 ��� * ( )V 0 . Ïî îïðåäåëåíèþ ñóáäèôôåðåíöèàëà
��� * ( )V 0 òîãäà è òîëüêî òîãäà, êîãäà � � z V z V z( ) ( ) ( , )*0 � , ò.å. êîãäà
� inf
z
V z z V( ) ( , ) ( ) ,*� �� 0 0 inf
z
V z V
z
z� * ( ) ( )
�
�
�
�
�
�
� �
0
0,
÷òî âîçìîæíî òîëüêî â ñëó÷àå � * ( ) ( )
�
�inf
z
V z V
z
L
0
. Ïîäñòàâèâ çíà÷åíèå
� * â ôîðìóëó ôóíêöèè Ëàãðàíæà äëÿ çàäà÷è (8), (9), ïîëó÷èì èñêîìûé ðåçóëüòàò.
Òåîðåìà äîêàçàíà.
Îòäåëüíî îñòàíîâèìñÿ íà íåñêîëüêèõ êîíêðåòíûõ ñëó÷àÿõ.
Ñëåäñòâèå 1. Åñëè â ÷èñëî îãðàíè÷åíèé çàäà÷è (6), (7) (m1 0� ) âõîäÿò óñëîâèÿ áèíàðíîñ-
òè âñåõ ïåðåìåííûõ, òî L n� è ñîîòâåòñòâåííî � �*
max ( ( ))� �
�
�
�
�
�
�
�
�� �
min
u R i
m
i i
m
c u n K u
1
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 93
Äîêàçàòåëüñòâî. Ïðè íàëè÷èè îãðàíè÷åíèé âèäà x i ni
2 1 0 1 � �, , (ïóñòü èõ
èíäåêñû áóäóò ïåðâûìè), ìîæíî çàïèñàòü K u K u( )
~
( )� � diag( , , )u i ni �1 . Òîãäà
ñîãëàñíî (14)
V z u c K u z u R
u i
m
i i
m( ) : ( ( )) ;max� � �
�
�
�
��
�
�
�
��
�
�
inf
1
�
� � �
� � �
inf diag
u i n
m
i i
i
n
i iu c u K u u i
1 1
1: (
~
( ) ( , ,max� n zI u R m) ) ; � �
�
�
�
��
�
�
�
��
�0
� � �
� � �
inf diag
u i n
m
i i
i
n
iu c u z K u
1 1
~ (~ ) : (
~
(~ ) (max� ~ , , )) ; ~u i n u Ri
m� � �
�
�
�
��
�
�
�
��
�1 0
� � �
�
�
�
��
�
�
�
���
inf
i
m
i i i
mu c nz K u u R
1
0~ : ( (~ )) ; ~
max� � V nz( )0 ,
ãäå ~ , ,u u z i ni i� �1 , ~ , ,u u i n mi i� � �1 . Òîãäà
inf inf
z z
V z V
z
V nz V
z
n L
� �
�
� � � �
0 0
0 0 0( ) ( ) ( ) ( )
.
Ñ ó÷åòîì ôîðìóëû (15) äîêàçàòåëüñòâî çàâåðøåíî.
Äàííûé ñëó÷àé èíòåðåñåí êàê äîñòàòî÷íî ÷àñòî âñòðå÷àþùèéñÿ, íàïðèìåð â
òåîðèè ãðàôîâ (çàäà÷è î ìàêñèìàëüíîì ðàçðåçå ãðàôà, ìàêñèìàëüíîì íåçàâèñè-
ìîì ìíîæåñòâå, ìàêñèìàëüíîé k-êëèêå è ò.ä.).
Ñëåäñòâèå 2. Åñëè â ÷èñëî îãðàíè÷åíèé çàäà÷è (6), (7) (m1 0� ) âõîäèò
îãðàíè÷åíèå
i
n
ix
�
�
1
2 1 0, òî L �1 è ñîîòâåòñòâåííî � * �
� �
�
�
�
�
�
�
�
�� �
min
u R i
m
i i
m
c u K u
1
� max ( ( )) .
Äîêàçàòåëüñòâî çäåñü íå ïðèâîäèòñÿ, ïîñêîëüêó îíî èäåíòè÷íî ïðåäûäóùå-
ìó ñëó÷àþ (ïðè îïðåäåëåíèèV z( ) çàìåíÿåòñÿ òîëüêî îäíà äâîéñòâåííàÿ ïåðåìåí-
íàÿ ~u u z1 1� , ñîîòâåòñòâóþùàÿ îãðàíè÷åíèþ
i
n
ix
�
�
1
2 1 0).
Ñëåäñòâèå 2 èíòåðåñíî òåì, ÷òî åñëè îáëàñòü îòðèöàòåëüíîé îïðåäåëåííîñòè
ìàòðèöû K u( ) ôóíêöèè Ëàãðàíæà çàäà÷è (6), (7) (m1 0� ) íå ïóñòà, òî âñåãäà ìîæíî
äîáàâèòü îäíî îãðàíè÷åíèå-ðàâåíñòâî (ëèíåéíàÿ êîìáèíàöèÿ èñõîäíûõ), ôóíêöèÿ
êîòîðîãî ïðåäñòàâëÿåò ñîáîé îäíîðîäíóþ ïîëîæèòåëüíî îïðåäåëåííóþ êâàäðàòè÷-
íóþ ôîðìó, à çíà÷èò, ïóòåì çàìåíû ïåðåìåííûõ ïðèâîäèòñÿ ê âèäó
i
n
ix
�
�
1
2 1 0.
Òàêèì îáðàçîì, äëÿ ëþáîé îäíîðîäíîé êâàäðàòè÷íîé çàäà÷è áåç îãðàíè÷å-
íèé-íåðàâåíñòâ âñåãäà ìîæíî ïîëó÷èòü äâîéñòâåííóþ îöåíêó [1, 4] ïóòåì ðåøåíèÿ
âûïóêëîé çàäà÷è áåçóñëîâíîé îïòèìèçàöèè âèäà (15) áåç äîïîëíèòåëüíûõ çàòðàò (â
õóäøåì ñëó÷àå, äîáàâèâ îäíó äâîéñòâåííóþ ïåðåìåííóþ, åñëè â ïåðâîíà÷àëüíîé
ïîñòàíîâêå îòñóòñòâóåò îãðàíè÷åíèå ñ ïîëîæèòåëüíî îïðåäåëåííîé ìàòðèöåé).
5. ÊÂÀÄÐÀÒÈ×ÍÀß ÇÀÄÀ×À ÎÁÙÅÃÎ ÂÈÄÀ (1), (2)
Áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî âñå îãðàíè÷åíèÿ çàäà÷è (6), (7)
çàäàíû â âèäå ðàâåíñòâ — ëþáîå îãðàíè÷åíèå-íåðàâåíñòâî ïðèâîäèòñÿ ê íåîá-
94 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
õîäèìîìó âèäó ïóòåì ââåäåíèÿ â ôóíêöèþ êâàäðàòà äîïîëíèòåëüíîé
ïåðåìåííîé
f x K x
x R
T
n
* �
�
max 0 (16)
ïðè îãðàíè÷åíèÿõ
x K x c z i mT
i i i� � � �2
10 1, , ,
(17)
x K x c i m mT
i i� � � �0 11, , .
Òàêèì îáðàçîì, ïðîèçâîëüíàÿ êâàäðàòè÷íàÿ çàäà÷à (1), (2) ïóòåì ââîäà ïåðå-
ìåííûõ z i mi , ,� 0 1 (íàïîìíèì, ÷òî ñ ïîìîùüþ z0 èçáàâëÿåìñÿ îò ëèíåéíûõ
÷ëåíîâ â êâàäðàòè÷íûõ ôîðìàõ), ïðåîáðàçóåòñÿ ê ðàññìîòðåííîìó âûøå ñëó÷àþ
êâàäðàòè÷íîé îäíîðîäíîé çàäà÷è áåç îãðàíè÷åíèé-íåðàâåíñòâ. Äàëåå, ïîñòðîèâ,
íàïðèìåð, äîïîëíèòåëüíîå îãðàíè÷åíèå, ôóíêöèÿ êîòîðîãî ïðåäñòàâëÿåò ñîáîé
ïîëîæèòåëüíî îïðåäåëåííóþ êâàäðàòè÷íóþ ôîðìó (åñëè òàêîãî íåò â íàëè÷èè),
è âîñïîëüçîâàâøèñü ñëåäñòâèåì 2, ïîëó÷èì âûïóêëóþ çàäà÷ó áåçóñëîâíîé îïòè-
ìèçàöèè âèäà (15), ðåøåíèå êîòîðîé äàåò äâîéñòâåííóþ îöåíêó èñõîäíîé çàäà-
÷è. Ïðè÷åì íè ââåäåíèå z0 , íè z i mi , ,�1 1 , íå ìåíÿþò çíà÷åíèå ïðåäëîæåííîé
Í.Ç. Øîðîì äâîéñòâåííîé îöåíêè èñõîäíîé çàäà÷è (1), (2). Ïîêàæåì ýòî.
Óòâåðæäåíèå 1. Äâîéñòâåííûå îöåíêè çàäà÷è (1), (2) è çàäà÷è (3)–(5) ñîâïàäàþò.
Äîêàçàòåëüñòâî. Ââåäåì îáîçíà÷åíèÿ u i mi , ,�1 , — äâîéñòâåííûå ïåðåìåííûå
ïðè ñîîòâåòñòâóþùèõ îãðàíè÷åíèÿõ (2) è (4) çàäà÷, u0 — äâîéñòâåííàÿ ïåðåìåííàÿ
ïðè ðàâåíñòâå (5) è âûïèøåì âûðàæåíèÿ äâîéñòâåííûõ êâàäðàòè÷íûõ îöåíîê [1]:
— äëÿ çàäà÷è (1), (2)
f * � ��1
� � �
� � � �
inf
u R i
m
i i
i
m
i i
T
i
m
i i
m
c u b u b K u K
1
0
1
0
1
1
4
( ) ( ) ( )
�
�
�
�
�
�
�
�
�
�
1
0
1
b u b
i
m
i i (18)
ïðè îãðàíè÷åíèÿõ
u i m K u Ki
i
m
i i� � � !
�
0 1 01 0
1
, , ; ( ) ;
— äëÿ çàäà÷è (3)–(5)
f c u u
u R i
m
i i
m
* � �
�
�
�
�
�
�
�
�� �
�
� 2
1
0
1
inf (19)
ïðè îãðàíè÷åíèÿõ
u i mi � �0 1 1, , ;
K u K b u b
b u b u
i
m
i i
i
m
i i
T
i
m
i i
T
0
1
0
1
0
1
0
� �
�
�
�
�
�
�
�
�
�
�
� �
�
�
�
�
�
�
! 0.
Îòìåòèì, ÷òî èñïîëüçîâàíèå ñòðîãîé îòðèöàòåëüíîé îïðåäåëåííîñòè â çà-
äà÷å (19) âïîëíå êîððåêòíî (â ïîñòàíîâêå (8)–(10) ýòîé çàäà÷è òðåáîâàëàñü íåïî-
ëîæèòåëüíàÿ îïðåäåëåííîñòü), ïîñêîëüêó äëÿ îäíîðîäíîé çàäà÷è
� * ( , ) ( , )� �
� � � �
inf sup min max
u D x R u D x Rn n
L x u L x u .
Óñëîâèå îòðèöàòåëüíîé îïðåäåëåííîñòè â çàäà÷å (19) ýêâèâàëåíòíî äâóì
óñëîâèÿì:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 95
K u K
K u K b u b
i
m
i i
i
m
i i
i
m
i i
0
1
0
1
0
1
0� ! " �
� �
�
� �
det
( ) ( )
�
#
#
#
#
#
#
#
#
#
#
#
#
�
�
( )b u b uT
i
m
i i
T
0
1
0
0.
Ðàñïèñàâ äåòåðìèíàíò áëî÷íîé ìàòðèöû ïî ôîðìóëå
A B
C D
#
#
#
#
#
#�
� | | | |A D CA B1 , èìååì
det �
#
#
#
#
#
# � � �
� � �
K u K u b u b K
i
m
i i
i
m
i i
T
i
0
1
0 0
1
0
1
4
( ) (
1
1
0
1
0
m
i i
i
m
i iu K b u b
�
�
#
#
#
#
#
#�) ( )
,
÷òî ïðè ( )K u K
i
m
i i0
1
0� !
�
ýêâèâàëåíòíî
� � � �
� �
�
u b u b K u K b u b
i
m
i i
T
i
m
i i
i
m
i0 0
1
0
1
1
0
1
1
4
( ) ( ) ( i ) .
Çàìåíèâ â ôóíêöèè öåëè u0 íà âûðàæåíèå â ïðàâîé ÷àñòè ïîëó÷åííîãî íå-
ðàâåíñòâà (ïîñêîëüêó ýòî åäèíñòâåííîå óñëîâèå ñ ó÷àñòèåì äàííîé ïåðåìåííîé,
îãðàíè÷èâàþùåå ôóíêöèþ öåëè ñíèçó ïðè ôèêñàöèè îñòàëüíûõ ïåðåìåííûõ),
ïîëó÷èì çàäà÷ó (18), ò.å. � �1 2$ .
Óòâåðæäåíèå 2. Äâîéñòâåííûå îöåíêè çàäà÷è (1), (2) è çàäà÷è (16), (17) ñîâïàäàþò.
Äîêàçàòåëüñòâî. Ââåäåì îáîçíà÷åíèÿ u i mi , ,�1 , — äâîéñòâåííûå ïåðåìåí-
íûå ïðè ñîîòâåòñòâóþùèõ îãðàíè÷åíèÿõ çàäà÷ è âûïèøåì âûðàæåíèÿ äâî-
éñòâåííûõ êâàäðàòè÷íûõ îöåíîê [1]:
— äëÿ çàäà÷è (1), (2)
f * � ��1
� � �
� � � �
inf
u R i
m
i i
i
m
i i
T
i
m
i i
m
c u b u b K u K
1
0
1
0
1
1
4
( ) ( ) ( ) ,
�
�
�
�
�
�
�
�
�
�
1
0
1
b u b
i
m
i i (20)
ïðè îãðàíè÷åíèÿõ
u i mi � �0 1 1, , ; ( )K u K
i
m
i i0
1
0� !
�
;
— äëÿ çàäà÷è (16), (17)
�2 � �
�
�
�
�� � �
inf
u R i
m
i i
i
m
i i
T
mm
Tc u b u b
1
0
1
1
4
0
1
( ) ,
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
K u b u b
i
m
i i
T
m
T
T2
1
0
1
0
1
( ) ( ) , �
�
(21)
ïðè îãðàíè÷åíèè
K u
K u K
u i m
i
m
i i n m
m n
2
0
1
1
0
0 1
1
1
( )
( , , )
�
�
�
�
�
�
�
��
�
�
%
%
diag �
�
�
��
! 0.
Èñïîëüçóÿ ôîðìóëó Ôðîáåíèóñà äëÿ îáðàùåíèÿ áëî÷íîé ìàòðèöû [5], ëåãêî
âèäåòü, ÷òî ôóíêöèè öåëè îáåèõ çàäà÷ ñîâïàäàþò.
Óñëîâèå îòðèöàòåëüíîé îïðåäåëåííîñòè â çàäà÷å (21) ýêâèâàëåíòíî äâóì
óñëîâèÿì:
96 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
( ) , ...,K u K k m
i
m
i i k0
1
10 1� ! " � � �
�
{ }det
�
�
#
#
#
##
#
#
#
##
��
%
%
K u K
u i k
i
m
i i n k
k n
0
1
0
0 1
0
diag( , , )
.
Ðàñïèñàâ äåòåðìèíàíò áëî÷íîé ìàòðèöû ïî ôîðìóëå
A B
C D
#
#
#
#
#
#�
� | | | |A D CA B1 , ïîëó÷èì det k
i
m
i iK u K�
#
#
#
#
#
#
�
0
1
| ( , , )| ,- diag u i k� �1 0 k m�1 1, ,
÷òî ýêâèâàëåíòíî ïðè óñëîâèè ( )K u K
i
m
i i0
1
0� !
�
òîìó, ÷òî u i mi ! �0 1 1, , (ïî-
ñëåäíèå íåðàâåíñòâà ìîæíî çàìåíèòü íà íåñòðîãèå, ïîñêîëüêó îãðàíè÷åííîñòü
ñâåðõó öåëåâîé ôóíêöèè ïî x îò íèõ íå çàâèñèò). Òàêèì îáðàçîì, ïîëó÷èëè îãðàíè-
÷åíèÿ çàäà÷è (20). Äîêàçàòåëüñòâî çàâåðøåíî.
6. ÍÅÊÎÒÎÐÛÅ ÑËÓ×ÀÈ ÊÂÀÄÐÀÒÈ×ÍÎÉ ÇÀÄÀ×È
Ñ ÎÃÐÀÍÈ×ÅÍÈßÌÈ-ÍÅÐÀÂÅÍÑÒÂÀÌÈ
Ïðèâåäåííûé ïîäõîä äëÿ íàõîæäåíèÿ îöåíêè êâàäðàòè÷íîé çàäà÷è (1), (2) ïóòåì
ñâåäåíèÿ ê îäíîðîäíîé êâàäðàòè÷íîé çàäà÷å áåç îãðàíè÷åíèé-íåðàâåíñòâ ìîæåò
íå óäîâëåòâîðÿòü â ñëó÷àå çíà÷èòåëüíîãî óâåëè÷åíèÿ ðàçìåðíîñòè ìàòðèöû K u( )
â çàäà÷å (16), (17) (â êîíå÷íîé çàäà÷å îíà ðàâíà ( ) ( )n m n m� � % � �1 11 1 ). Âîç-
ìîæíî, èíîãäà öåëåñîîáðàçíåå âîñïîëüçîâàòüñÿ ðàññóæäåíèÿìè, ïðåäëîæåííûìè
íèæå, â ðåçóëüòàòå êîòîðûõ, â îòëè÷èå îò ïðåäûäóùåãî ïîäõîäà, íåîáõîäèìî
íàõîäèòü ìàêñèìàëüíîå ñîáñòâåííîå ÷èñëî è ñîáñòâåííûé âåêòîð, ñîîòâåòñòâóþ-
ùèé åìó, ìàòðèöû ìåíüøåé ðàçìåðíîñòè — ( ) ( )n n� % �1 1 .
Äëÿ çàäà÷è (6), (7) äâîéñòâåííàÿ îöåíêà � * îïðåäåëÿåòñÿ çàäà÷åé (8)–(10),
äëÿ êîòîðîé ïîëîæèì
V z u c u z i m K u z
u i
m
i i i i m( ) : , , ; ( ( )) ;max� � � �
�
�
inf
1
1 11
1
� u R m�
�
�
�
��
�
�
�
��
. (22)
Òîãäà ñîãëàñíî òåîðåìå 1 ïðè N L� , ãäå inf
t
V te V
t�
�
0
0( ) ( )
� �L (e —
( )m1 1� -ìåðíûé âåêòîð, âñå êîìïîíåíòû êîòîðîãî ðàâíû åäèíèöå), ïîëó÷àåì
� �*
maxmax ; , , ; ( ( ))� � �
�
� �
min { }
u R i
m
i i i
m
c u N u i m K u
1
10 1
�
�
�
�
�
�
�
.
Òàêèì îáðàçîì, ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 4. Ïóñòü inf
t
V te V
t
L
�
� � �
0
0( ) ( )
. Òîãäà åñëè N L� , òî ðåøåíèå
îäíîðîäíîé êâàäðàòè÷íîé çàäà÷è (6), (7) ìîæíî îöåíèòü ñâåðõó ëàãðàíæåâîé
îöåíêîé � * , êîòîðàÿ ðàâíà
� �*
maxmax ; , , ; ( ( ))� � �
�
� �
min { }
u R i
m
i i i
m
c u N u i m K u
1
10 1
�
�
�
�
�
�
�
. (23)
Âûäåëèì íåñêîëüêî âàæíûõ ÷àñòíûõ ñëó÷àåâ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 97
Ñëåäñòâèå 3. Åñëè ìíîæåñòâî îãðàíè÷åíèé çàäà÷è (6), (7) ñîñòîèò èç ïðîèç-
âîëüíûõ îãðàíè÷åíèé-ðàâåíñòâ, íàáîðà îãðàíè÷åíèé âèäà x ci i
2 0� � ,
i J n� �{ }1 2, , . . ., , è x c i I ni i
2 0 1 2� � � �, , , . . .,{ }, òàêîãî, ÷òî I J n& � { }1 2, , . . ., è
I J� � '{ }, òî L c c
i I
i
i J
i� �
�
�
�
�
�
�
�
�� �
è, ñëåäîâàòåëüíî,
� �*
maxmax ; , , ; ( ( ))� � �
�
�� �
min { }
u R i
m
i i i
m
c u N u i m K u
1
10 1�
�
�
�
�
�
ïðè N L� .
Äîêàçàòåëüñòâî. Ïðè íàëè÷èè çàäàííîãî íàáîðà îãðàíè÷åíèé (ïóñòü èõ èí-
äåêñû áóäóò ïåðâûìè) ìîæíî çàïèñàòü K u K u u i ni( )
~
( ) ( , , )� � �diag 1 . Òîãäà ñî-
ãëàñíî (22)
V te c u K u u i n t
i
m
i i i( ) : (
~
( ) ( , , )) ;max1
1
1� � � �
�
inf diag� u t i Ji � �
�
�
�
��
�
�
�
��
�, , | |1
� � � �
�
inf diag
i
m
i i i ic u K u u i n tI u
1
1 0: (
~
( ) ( , , ) ) ;max� t i J� �
�
�
�
�
�
�
�0 1, , | |
� � � �
� � �
inf diag
i
n
i i
i n
m
i ic u t c u K u
1 1
(~ ) ~ : (
~
(~) (max� ~ , , )) ;u i ni � �
�
�
�
��
1 0
~ , , | | ( )u i J V t c ci
i I
i
i J
� �
�
�
�
��
� � �
�
�
��
�
�
��
� �
0 1 0 ,
ãäå ~ , , , ~ , ,u u t i n u u i n mi i i i� � � � �1 1 . Òîãäà
inf inf
t t
i I
i
i J
i
V t V
t
V t c c
� �
� �
�
� �
�
�
0 0
0
0
( ) ( )
( ) �
�
�
�
�
�
�
V
t
( )0
i I
i
i J
ic c L
� �
�
�
�
�
�
�
�
�
�
� � �.
Ñ ó÷åòîì òåîðåìû 4 äîêàçàòåëüñòâî çàâåðøåíî.
Ñëåäñòâèå 4. Åñëè ìíîæåñòâî îãðàíè÷åíèé çàäà÷è (6), (7) ñîñòîèò èç ïðîèç-
âîëüíûõ îãðàíè÷åíèé-ðàâåíñòâ è îáëàñòü ïåðåìåííûõ îãðàíè÷åíà øàðîì, ò.å.
èìååòñÿ îãðàíè÷åíèå âèäà
i
n
ix r
�
�
1
2 2 , òî L r� 2 è, ñëåäîâàòåëüíî,
� �*
maxmax ; , ( ( ))� �
�
�
�
�
�
�
�
�� �
min { }
u R i
m
i i
m
c u N u K u
1
10 ïðè N L� .
Ñõåìà äîêàçàòåëüñòâà àíàëîãè÷íà.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ø î ð Í . Ç . , Ñ ò å ö å í ê î Ñ . È . Êâàäðàòè÷íûå ýêñòðåìàëüíûå çàäà÷è è
íåäèôôåðåíöèðóåìàÿ îïòèìèçàöèÿ. — Ê.: Íàóê. äóìêà, 1989. — 208 ñ.
2. S h o r N . Z . Nondifferentiable optimization and polynomial problems. — Dordrecht: Kluwer,
1998. — 394 p.
3. Ï ø å í è ÷ í û é Á . Í . Ìåòîä ëèíåàðèçàöèè. — Ì.: Íàóêà, 1983. — 136 ñ.
4. Ð à ç â è ò è å àëãîðèòìîâ íåäèôôåðåíöèðóåìîé îïòèìèçàöèè è èõ ïðèëîæåíèÿ / Í.Ç. Øîð, Í.Ã. Æóðáåíêî,
À.Ï. Ëèõîâèä, Ï.È. Ñòåöþê // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2003. — ¹ 4. — Ñ. 80–94.
5. Ã à í ò ì à õ å ð Ô . Ð . Òåîðèÿ ìàòðèö. — Ì.: Íàóêà, 1988. — 552 ñ.
Ïîñòóïèëà 29.05.2007
98 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
|
| id | nasplib_isofts_kiev_ua-123456789-72000 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| language | Russian |
| last_indexed | 2025-12-07T16:03:29Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Березовский, О.А. Стецюк, П.И. 2014-12-15T22:19:14Z 2014-12-15T22:19:14Z 2008 Об одном способе нахождения двойственных квадратичных оценок Шора / О.А. Березовский, П.И. Стецюк // Кибернетика и системный анализ. — 2008. — № 2. — С. 89-98. — Бібліогр.: 5 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/72000 519.8 Для квадратичної задачі загального вигляду побудовано аналог у вигляді однорідної квадратичної задачі. Доведено рівність оцінок ψ*, побудованих на базі техніки двоїстих квадратичних оцінок Шора для цих задач. У випадку однорідної квадратичної задачі показано, що знаходження ψ* зводиться до розв'язання безумовної задачі мінімізації випуклої функції. Работа выполнена при частичной финансовой поддержке гранта UKM2-2812-KV-06 (CRDFCooperative Grants Program). ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Об одном способе нахождения двойственных квадратичных оценок Шора Article published earlier |
| spellingShingle | Об одном способе нахождения двойственных квадратичных оценок Шора Березовский, О.А. Стецюк, П.И. Системный анализ |
| title | Об одном способе нахождения двойственных квадратичных оценок Шора |
| title_full | Об одном способе нахождения двойственных квадратичных оценок Шора |
| title_fullStr | Об одном способе нахождения двойственных квадратичных оценок Шора |
| title_full_unstemmed | Об одном способе нахождения двойственных квадратичных оценок Шора |
| title_short | Об одном способе нахождения двойственных квадратичных оценок Шора |
| title_sort | об одном способе нахождения двойственных квадратичных оценок шора |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/72000 |
| work_keys_str_mv | AT berezovskiioa obodnomsposobenahoždeniâdvoistvennyhkvadratičnyhocenokšora AT stecûkpi obodnomsposobenahoždeniâdvoistvennyhkvadratičnyhocenokšora |