О нижней оценке для одной квадратичной задачи намногообразии Штифеля
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2008 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/44257 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О нижней оценке для одной квадратичной задачи намногообразии Штифеля / О.А. Березовский // Кибернетика и системный анализ. — 2008. — № 5. — С. 95-103 . — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-44257 |
|---|---|
| record_format |
dspace |
| spelling |
Березовский, О.А. 2013-05-27T14:31:26Z 2013-05-27T14:31:26Z 2008 О нижней оценке для одной квадратичной задачи намногообразии Штифеля / О.А. Березовский // Кибернетика и системный анализ. — 2008. — № 5. — С. 95-103 . — Бібліогр.: 7 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44257 519.8 ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ О нижней оценке для одной квадратичной задачи намногообразии Штифеля 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 |
2008 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/44257 |
| citation_txt |
О нижней оценке для одной квадратичной задачи намногообразии Штифеля / О.А. Березовский // Кибернетика и системный анализ. — 2008. — № 5. — С. 95-103 . — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT berezovskiioa onižneiocenkedlâodnoikvadratičnoizadačinamnogoobraziištifelâ |
| first_indexed |
2025-11-24T19:09:32Z |
| last_indexed |
2025-11-24T19:09:32Z |
| _version_ |
1850490170058473472 |
| fulltext |
ÓÄÊ 519.8
Î.À. ÁÅÐÅÇÎÂÑÊÈÉ
Î ÍÈÆÍÅÉ ÎÖÅÍÊÅ ÄËß ÎÄÍÎÉ ÊÂÀÄÐÀÒÈ×ÍÎÉ
ÇÀÄÀ×È ÍÀ ÌÍÎÃÎÎÁÐÀÇÈÈ ØÒÈÔÅËß
Êëþ÷åâûå ñëîâà: îïòèìèçàöèîííàÿ êâàäðàòè÷íàÿ çàäà÷à, äâîéñòâåííàÿ ëàã-
ðàíæåâàÿ îöåíêà, ôóíêöèîíàëüíî èçáûòî÷íûå îãðàíè÷åíèÿ, äâîéñòâåííûå ïåðå-
ìåííûå, ïîëîæèòåëüíî îïðåäåëåííàÿ ìàòðèöà.
Ðàññìàòðèâàåìàÿ â äàííîé ðàáîòå çàäà÷à, äëÿ êîòîðîé ïðåäëàãàåòñÿ íèæíÿÿ
îöåíêà, ñîñòîèò â íàõîæäåíèè ãëîáàëüíîãî ìèíèìóìà ñóììû êâàäðàòè÷íûõ
ôîðì f x f x x x A xk i
T
i i
i
k
( ) ( , , )� �
�
�
�
�
� � �
1
1
íà ìíîãîîáðàçèè Øòèôåëÿ, ãäå A Ai ijl� { :
j n l n� �1 1, , , ,} i k� 1, , — çàäàííûå n n� âåùåñòâåííûå ñèììåòðè÷íûå ìàòðèöû,
�
�x x x x Ri i i in
n� �( , , , )1 2 , i k� 1, , — âåêòîðû ïåðåìåííûõ, k n� . Ïîä ìíîãîîáðà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 95
� Î.À. Áåðåçîâñêèé, 2008
çèåì Øòèôåëÿ (Stiefel manifolds) ïîíèìàþò ìíîæåñòâî âñåõ îðòîíîðìèðîâàííûõ
ñèñòåì âåêòîðîâ { }
� �
�
�
x x xk1 2, � � â ïðîñòðàíñòâå R n .
 îáùåì ñëó÷àå äàííàÿ çàäà÷à ÿâëÿåòñÿ ìíîãîýêñòðåìàëüíîé çàäà÷åé íåëèíåé-
íîãî ïðîãðàììèðîâàíèÿ è åå ðåøåíèå äîñòàòî÷íî ñëîæíî äàæå ïðè íåáîëüøèõ ðàç-
ìåðíîñòÿõ [1, 2]. Â ñâÿçè ñ ýòèì îïðåäåëåííûé èíòåðåñ ïðåäñòàâëÿåò íàõîæäåíèå
îöåíîê ãëîáàëüíîãî ìèíèìóìà çàäà÷è, êîòîðûå ìîæíî ïîëó÷èòü, íàïðèìåð, èñ-
ïîëüçóÿ òåõíèêó äâîéñòâåííûõ ëàãðàíæåâûõ îöåíîê äëÿ êâàäðàòè÷íûõ çàäà÷ [3].
Êðàòêî ñóòü äàííîãî ïîäõîäà çàêëþ÷àåòñÿ â òîì, ÷òîáû ðàññìàòðèâàòü çàäà÷ó ìàê-
ñèìèçàöèè ïî äâîéñòâåííûì ïåðåìåííûì ôóíêöèè Ëàãðàíæà L x u( , ) , ïîñòðîåííîé
äëÿ èñõîäíîé îïòèìèçàöèîííîé êâàäðàòè÷íîé çàäà÷è, íà áîëåå óçêîé îáëàñòè îïðå-
äåëåíèÿ, íà êîòîðîé êâàäðàòè÷íàÿ ôîðìà L x u( , ) ïî ïðÿìûì ïåðåìåííûì ïîëîæè-
òåëüíî îïðåäåëåíà è âíóòðåííÿÿ çàäà÷à ÿâëÿåòñÿ âûïóêëîé.
 [4] ïðèâåäåíà ïîñòàíîâêà èñõîäíîé çàäà÷è â âèäå îïòèìèçàöèîííîé êâàäðà-
òè÷íîé çàäà÷è
f x A xi
T
i i
i
k
* min�
�
�
� �
1
(1)
ïðè îãðàíè÷åíèÿõ
� �
x xi
T
i � 1, i k� 1, , ,� (2)
� �
� �x x i k j i ki
T
j � � �
0 1 1 1, , , , , , (3)
(çäåñü îãðàíè÷åíèÿ (2) ñîîòâåòñòâóþò óñëîâèþ íîðìèðîâàííîñòè âåêòîðîâ
�
�x i ki , , ,� 1 , à îãðàíè÷åíèÿ (3) — óñëîâèþ èõ îðòîãîíàëüíîñòè).  ðåçóëüòàòå
ïðèìåíåíèÿ òåõíèêè äâîéñòâåííûõ ëàãðàíæåâûõ îöåíîê ïî îòíîøåíèþ ê êâàä-
ðàòè÷íîé ïîñòàíîâêå (1)–(3) (à òàêæå áëàãîäàðÿ åå îäíîðîäíîñòè) â [4] ïîëó÷åíà
íèæíÿÿ îöåíêà
f u u
u K u
* * *
: ( )
( ) max ( )� � �
�
� � �1 1
0
1 , (4)
ãäå ôóíêöèÿ �1
1
( ) ,u uii
i
k
�
�
� à K u( ) � 0 îáîçíà÷àåò íåîòðèöàòåëüíóþ îïðåäåëåí-
íîñòü ñåìåéñòâà ñèììåòðè÷íûõ ( )kn kn� -ìàòðèö âèäà
K u K u K u K Kii ii
i
k
ij ij ji
j i
k
i
k
( ) ( ).�
�
�
�
� ��0
1
1
11
1
2
Çäåñü u — âåêòîð ìíîæèòåëåé Ëàãðàíæà äëÿ çàäà÷è (1)–(3), ïðè÷åì
� { }u i kii , ,� 1 ñîîòâåòñòâóþò îãðàíè÷åíèÿì (2),
� { }u i k j i kij , , , ,� �
1 1 1 — îãðàíè÷åíèÿì (3),
à ìàòðèöû K 0 è K ij ñîñòîÿò èç k 2 áëîêîâ ðàçìåðîì n n� è çàäàþòñÿ ñëåäóþ-
ùèì îáðàçîì:
� K 0 — ìàòðèöa, ïî äèàãîíàëè êîòîðîé ðàçìåùåíû áëîêè, çàäàííûå ñèììåò-
ðè÷íûìè ( )n n� -ìàòðèöàìè A i ki , ,� 1 , à âñå âíåäèàãîíàëüíûå áëîêè ðàâíû íóëå-
âûì ( )n n� -ìàòðèöàì;
� K ij — ìàòðèöà, ( , )i j -é áëîê êîòîðîé ðàâåí åäèíè÷íîé ( )n n� -ìàòðèöå, à âñå
îñòàëüíûå áëîêè ðàâíû íóëåâûì ( )n n� -ìàòðèöàì.
Äàëåå ïðåäëàãàåòñÿ äðóãàÿ íèæíÿÿ îöåíêà �2
* äëÿ èñõîäíîé çàäà÷è, âûâîä êî-
òîðîé áàçèðóåòñÿ íà òîé æå òåõíèêå Í.Ç. Øîðà [3, 5] è èñïîëüçóåò îäíî åå çàìå÷à-
òåëüíîå ñâîéñòâî. Îíî çàêëþ÷àåòñÿ â âîçìîæíîñòè óëó÷øåíèÿ äâîéñòâåííûõ ëàã-
ðàíæåâûõ îöåíîê ïóòåì äîáàâëåíèÿ ê èñõîäíîé êâàäðàòè÷íîé ïîñòàíîâêå çàäà÷è
ôóíêöèîíàëüíî èçáûòî÷íûõ îãðàíè÷åíèé, êîòîðûå ÿâëÿþòñÿ ñëåäñòâèÿìè óæå èìå-
þùèõñÿ îãðàíè÷åíèé. Ýòè îãðàíè÷åíèÿ íå íåñóò íèêàêîé äîïîëíèòåëüíîé èíôîð-
ìàöèè ñ òî÷êè çðåíèÿ èñõîäíîé çàäà÷è, íî èçìåíÿþò ôóíêöèþ Ëàãðàíæà è ðàñøè-
96 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5
ðÿþò îáëàñòü îïðåäåëåíèÿ äâîéñòâåííûõ ïåðåìåííûõ â ìàêñèìèííîé çàäà÷å.  ðå-
çóëüòàòå â ðÿäå ñëó÷àåâ ëàãðàíæåâàÿ äâîéñòâåííàÿ îöåíêà äëÿ íîâîé
«ðàñøèðåííîé» êâàäðàòè÷íîé ïîñòàíîâêè ìîæåò îêàçàòüñÿ áîëåå òî÷íîé, ÷åì äëÿ
èñõîäíîé. Ïðåäëàãàåìàÿ â ñòàòüå îöåíêà �2
* , ïîñòðîåííàÿ ñ èñïîëüçîâàíèåì äîáàâ-
ëåíèÿ ê çàäà÷å (1)–(3) ñåìåéñòâà ôóíêöèîíàëüíî èçáûòî÷íûõ îãðàíè÷åíèé îïðåäå-
ëåííîãî âèäà, ïîêàçûâàåò ýôôåêòèâíîñòü «ðàáîòû» òàêèõ îãðàíè÷åíèé (ïî êðàéíåé
ìåðå, äëÿ âñåõ ïðèìåðîâ èç [1], â òîì ÷èñëå è â ñëó÷àå, êîãäà îöåíêà �1
* [4] îêàçà-
ëàñü íåòî÷íîé, íîâàÿ îöåíêà �2
* äàëà òî÷íûå ðåçóëüòàòû).
Ïåðåéäåì íåïîñðåäñòâåííî ê ôîðìèðîâàíèþ «ðàñøèðåííîé» êâàäðàòè÷íîé
ïîñòàíîâêè èñõîäíîé çàäà÷è, ò.å. ê ïîñòðîåíèþ òåõ êâàäðàòè÷íûõ ðàâåíñòâ (íåòðè-
âèàëüíûõ ñëåäñòâèé ðàâåíñòâ (2), (3)), êîòîðûå ïðåäëàãàåì èñïîëüçîâàòü â êà÷åñòâå
äîïîëíèòåëüíûõ îãðàíè÷åíèé äëÿ çàäà÷è (1)–(3).
Áåç îãðàíè÷åíèÿ îáùíîñòè â äàëüíåéøåì áóäåì ñ÷èòàòü, ÷òî k n� . Ýòîãî âñåãäà
ìîæíî äîáèòüñÿ ïóòåì äîïîëíåíèÿ ìíîæåñòâà âåêòîðîâ { }
� �
�
�
x x xk1 2, � � ïåðåìåííûõ çà-
äà÷è äî ïîëíîãî áàçèñà îðòîíîðìèðîâàííûõ âåêòîðîâ â R n , ò.å. ïóòåì ââåäåíèÿ äîïîë-
íèòåëüíûõ âåêòîðîâ
� �
�
�
x x x Rk k n
n
� � �1 2, , äëÿ êîòîðûõ A i k ni , ,�
1 , — íóëåâûå
n n� -ìàòðèöû, è ðàñøèðåíèÿ ñîîòâåòñòâóþùèì îáðàçîì ìíîæåñòâà îãðàíè÷åíèé
(2), (3) òàê, ÷òîáû îíè îïðåäåëÿëè îðòîíîðìèðîâàííîñòü ïî âñåì n âåêòîðàì. Ñëåäóåò
îòìåòèòü, ÷òî ïðè òàêîì ïåðåõîäå îò k n
ê k n� äâîéñòâåííûå îöåíêè, ïîëó÷åííûå
ñîãëàñíî (4) äëÿ îáîèõ ñëó÷àåâ, ñîâïàäàþò. Ñïðàâåäëèâîñòü ýòîãî óòâåðæäåíèÿ ëåãêî
ñëåäóåò èç ðàññìîòðåíèÿ çàäà÷è (4) äëÿ ïîñëåäíåãî ñëó÷àÿ, èç êîòîðîãî âèäíî, ÷òî
u i n j i nij
* , , , ,� � �
0 1 1 1 (ýòè ïåðåìåííûå íå âëèÿþò íà öåëåâóþ ôóíêöèþ, è ïðè èõ
íóëåâîì çíà÷åíèè îáëàñòü îïðåäåëåíèÿ äðóãèõ ïåðåìåííûõ ìàêñèìàëüíà),
u i k nii
* , ,� �
0 1 (ó÷èòûâàÿ âèä öåëåâîé ôóíêöèè, îíè ñòðåìÿòñÿ ê �, íî îãðàíè÷åíû
óñëîâèåì íåîòðèöàòåëüíîé îïðåäåëåííîñòè ìàòðèöû K u( ) , ÷òî ïî îòíîøåíèþ ê ýòèì
ïåðåìåííûì ýêâèâàëåíòíî îãðàíè÷åíèÿì u i k nii
* , ,� �
0 1 ). Òàêèì îáðàçîì, ïîëó÷àåì
çàäà÷ó (4), ñîîòâåòñòâóþùóþ èñõîäíîìó ñëó÷àþ (êîãäà k n
).
Ïîñêîëüêó èçâåñòíî, ÷òî åñëè ñòðîêè êâàäðàòíîé ìàòðèöû — îðòîíîðìèðîâàí-
íûå âåêòîðû, òî è ñòîëáöû ìàòðèöû — îðòîíîðìèðîâàííûå âåêòîðû, ìîæåì çàïè-
ñàòü:
x j nij
i
n
2
1
1 1
�
� � �, , , ,�
x x i n j i nli
l
n
lj
�
� � � �
1
0 1 1 1, , , , , , .� �
Ðàñøèðèì çà ñ÷åò ýòèõ ôóíêöèîíàëüíî èçáûòî÷íûõ îãðàíè÷åíèé çàäà÷ó
(1)–(3). Ýòî ïðèâåäåò ê ðåøåíèþ çàäà÷è âèäà
f x A xi
T
i i
i
k
* min�
�
�
� �
1
(5)
ïðè îãðàíè÷åíèÿõ
x i nij
j
n
2
1
1 1
�
� � �, , ,� , (6)
x x i n j i nil
l
n
jl
�
� � � �
1
0 1 1 1, , , , , ,� � , (7)
x j nij
i
n
2
1
1 1
�
� � �, , ,� , (8)
x x i n j i nli
l
n
lj
�
� � � �
1
0 1 1 1, , , , , ,� � . (9)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 97
Äàëüíåéøèå äåéñòâèÿ ïî îòíîøåíèþ ê ðàñøèðåííîé çàäà÷å (5)–(9) èäåíòè÷íû
ïðîâåäåííûì â [4] äëÿ êâàäðàòè÷íîé ïîñòàíîâêè (1)–(3) — ñîãëàñíî [3] «íîâîé» çà-
äà÷å ñîîòâåòñòâóåò äâîéñòâåííàÿ ëàãðàíæåâàÿ îöåíêà
� � � �
� �
2 2
0
* * *
( , ): ( , )
( , ) ( , , )� � �
�
u L x u
u K u x
sup inf
� �
� �
sup
( , ): ( , ) ( , ): ( , )
( , , ) max ( ,
u K u u K u
L u u
� � � �
� � �
0 0
20 ) , (10)
ãäå ôóíêöèÿ Ëàãðàíæà L x u x K u x uT
ii ii
i
n
( , , ) ( , ) ( )� � ��
�
�
1
, ôóíêöèÿ � �2 ( , )u �
�
�
� ( )uii ii
i
n
�
1
, à K u( , )� � 0 îáîçíà÷àåò íåîòðèöàòåëüíóþ îïðåäåëåííîñòü ñåìå-
éñòâà ñèììåòðè÷íûõ ( )n n2 2� -ìàòðèö âèäà
K u K u K u K Kii
i
n
ii
i
n
ij
j i
n
ij ji( , ) ( )� �
� �
�
� � �0
1 1
1
1
1
2
V;
x x x x x x xn n n nn� ( , , , , , , , , , )11 1 21 2 1� � � � — âåêòîð ïðÿìûõ ïåðåìåííûõ çàäà÷è
ðàçìåðíîñòè n2 , 0 — íóëåâîé n2 -ìåðíûé âåêòîð.
Çäåñü ( , )u � — âåêòîð ìíîæèòåëåé Ëàãðàíæà, ïðè÷åì
� { }u i nii , ,� 1 ñîîòâåòñòâóþò îãðàíè÷åíèÿì (6),
� { , , , ,u i n j i nij � �
1 1 1 } — îãðàíè÷åíèÿì (7),
� { }� ii i n, ,� 1 — îãðàíè÷åíèÿì (8),
� { }� ij i n j i n, , , ,� �
1 1 1 — îãðàíè÷åíèÿì (9);
ìàòðèöû K 0 è K ij çàäàþòñÿ òàê æå, êàê ïðè îïðåäåëåíèè îöåíêè �1
* , à ìàòðèöà
V ÿâëÿåòñÿ ñèììåòðè÷íîé ìàòðèöåé èç n2 áëîêîâ ðàçìåðîì n n n� , äèàãîíàëüíûõ
áëîêîâ êîòîðîé ñîâïàäàþò è ïðåäñòàâëÿþò ñîáîé ìàòðèöó äâîéñòâåííûõ ïåðå-
ìåííûõ � ij ñ êîýôôèöèåíòîì 1, åñëè i j� , è
1
2
, åñëè i j� (âñå âíåäèàãîíàëüíûå
áëîêè ìàòðèöû V ðàâíû íóëåâûì ( )n n� -ìàòðèöàì). Òàêèì îáðàçîì, äèàãîíàëü-
íûé ii-áëîê (i n� 1, ) ñèììåòðè÷íîé ìàòðèöû K u( , )� èìååò âèä
A u A A A
A
i ii i i j
j
i n
n
i
11 11 12
12
1
1
1
1
12
2 2 2
�
� � �
... ...
�
�
� �12
22 22 2
2
2
2
2 2 2
A u A Ai ii i j
j
i n
n
... ...
... ... ...� ... ...
... ...A A A u Ai j
j
i j
j
ijj ii jj inj
nj
1
1
2
2
2 2
� �
�
�
2
2 2 2
1
1
2
2
... ... ... ... ...
... ...
�
A A Ai n
n
i n
n
inj
nj
� � �
A uinn ii nn
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
,
à âíåäèàãîíàëüíûå ij- è ji-áëîêè (i n j i n� �
1 1 1, , , ) ðàâíû
u
I
ij
n
2
, ãäå I n —
åäèíè÷íàÿ ìàòðèöà.
Ïîñêîëüêó â çàäà÷å (10) ïåðåìåííûå { }u i n j i nij , , , ,� �
1 1 1 íå âõîäÿò â öåëå-
âóþ ôóíêöèþ è ïðè èõ íóëåâîì çíà÷åíèè îáëàñòü íåîòðèöàòåëüíîé îïðåäåëåííîñ-
òè ìàòðèöû K u( , )� îòíîñèòåëüíî äðóãèõ ïåðåìåííûõ ìàêñèìàëüíà (äëÿ òîãî ÷òîáû
ìàòðèöà áûëà íåîòðèöàòåëüíî îïðåäåëåíà, äèàãîíàëüíûå áëîêè äîëæíû áûòü òàê-
98 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5
æå íåîòðèöàòåëüíî îïðåäåëåíû), èõ ìîæíî ñðàçó îáíóëèòü. Ýòî îçíà÷àåò, ÷òî îãðà-
íè÷åíèÿ (7) íå âëèÿþò íà âåëè÷èíó äâîéñòâåííîé îöåíêè �2
* , èõ ìîæíî èñêëþ÷èòü
èç êâàäðàòè÷íîé ïîñòàíîâêè è ðàññìàòðèâàòü çàäà÷ó (5), (6), (8), (9) (îòìåòèì, ÷òî ñ
òî÷êè çðåíèÿ èñõîäíîé çàäà÷è îãðàíè÷åíèÿ (7) òàêæå íå íóæíû äëÿ çàäàíèÿ ìíîãî-
îáðàçèÿ Øòèôåëÿ, òàê êàê îíè ÿâëÿþòñÿ ñëåäñòâèåì îãðàíè÷åíèé (8), (9)).
Òàêèì îáðàçîì, ïðåäëàãàåìàÿ â äàííîé ðàáîòå íèæíÿÿ îöåíêà äëÿ çàäà÷è ìè-
íèìèçàöèè êâàäðàòè÷íîé ôóíêöèè ñïåöèàëüíîãî âèäà (1) íà ìíîãîîáðàçèè Øòèôå-
ëÿ ïðèìåò îêîí÷àòåëüíûé âèä
� � �
� �
2
0
2
*
( ( , ))
max ( , )
min
�
�K u
u . (11)
Çäåñü ôóíêöèÿ � � �2
1
( , ) ( )u uii ii
i
n
�
�
� , à óñëîâèå íåîòðèöàòåëüíîé îïðåäåëåí-
íîñòè ìàòðèöû K u K u K Vii ii
i
n
( , )� �
�
�0
1
çàïèñàíî â âèäå íåîòðèöàòåëüíîñòè åå
ìèíèìàëüíîãî ñîáñòâåííîãî ÷èñëà; ðàçìåðíîñòü çàäà÷è (11) ðàâíà
n n( )
3
2
(âåê-
òîð ïåðåìåííûõ { }u i n i n j i nii ij, , ; , , , ,� � �1 1� ).
Óòâåðæäåíèå 1. Äëÿ çàäà÷è (1) íà ìíîãîîáðàçèè Øòèôåëÿ îöåíêà �2
* (11)
âñåãäà íå õóæå îöåíêè �1
* (4) — f * * *� �� �2 1 .
Ýòî óòâåðæäåíèå î÷åâèäíî ñëåäóåò èç ïîñòðîåíèÿ îöåíêè �2
* :
� � � �
� � �
2
0
2
0
2
*
( ( , )) ( ( , ))
max ( , ) max (
min min
� �
� �K u K u
u u
0
, ) *0 � �1 .
Çäåñü 0 — íóëåâîé
n n( )
1
2
-ìåðíûé âåêòîð.
Óòâåðæäåíèå 2. Íàõîæäåíèå îöåíêè �2
* (11) ñâîäèòñÿ ê ðåøåíèþ áåçóñëîâíîé
çàäà÷è ìàêñèìèçàöèè âîãíóòîé ôóíêöèè
� � � �
�
2
1
*
,
minmax ( ) ( ( , ))�
�
�
�
�
�
�
�
�
�
�
u
ii ii
i
n
u n K u .
Äîêàçàòåëüñòâî. Äëÿ çàäà÷è âèäà
�* min�
�
�
�
�
�
�
�
�� �
�
y R
i i
i
m
m
c y
1
(12)
ïðè îãðàíè÷åíèè
� max ( ( ))K y � 0 (13)
â [6] ïðèâîäèòñÿ ñëåäóþùàÿ òåîðåìà.
Òåîðåìà. Ïóñòü inf
t
V t V
t
L
( ) ( )
� � �
0
, ãäå V t c y
y
i i
i
m
( ) :�
�
�
�
�� �
�inf
1
� max ( ( )) ;K y t y R m� �
�
�
�
��
, t R� 1. Òîãäà ðåøåíèå çàäà÷è (12), (13) èìååò âèä
� �*
maxmin ( ( ))�
�
�
�
�
�
�
�
�� �
�
y R
i i
i
m
m
c y L K y
1
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 99
Âîñïîëüçóåìñÿ äàííûì ðåçóëüòàòîì. Ïåðåïèøåì çàäà÷ó (11), ñîîòâåòñòâóþ-
ùóþ íàõîæäåíèþ �2
* , â âèäå çàäà÷è ìèíèìèçàöèè
� �
� � �
2
0
1
*
( ( , ))
max ( ) min
min
�
�
�
�
�
�
�
�
�
�
� �
�
K u
ii ii
i
n
u
max ( ( , ))
( )
� �
�
K u
ii ii
i
n
u
�
�
0
1
.
Òîãäà èìååì
V t u K u t
u
ii ii
i
n
( ) ( ) : ( ( , ))
,
max�
�
�
�
�
��
�
�
�
��
�inf
�
� � �
1 �
�
�
�
� �
� �inf
u
ii ii
i
n
ii ii
i
n
u K u K V tI
,
max( ) : ( )
�
� �
1
0
1
0
�
�
�
��
�
�
�
��
�
�
� �
� �inf
~,
max((~ ) ) : ( ~
u
ii ii
i
n
ii ii
i
n
u t K u K
�
� �
1
0
1
V ) �
�
�
�
��
�
�
�
��
�0
�
�
�
�
�
��
�
�
�
�inf
~,
max(~ ) : ( (~, ))
u
ii ii
i
n
u nt K u
�
� � �
1
0
�
��
� V nt( )0 ,
ãäå ~ , ,u u t i nii ii�
� 1 , I — åäèíè÷íàÿ ìàòðèöà ðàçìåðíîñòè n n2 2� .
Ïîäñòàâëÿÿ âûðàæåíèåV t( ) â ôîðìóëó äëÿ îïðåäåëåíèÿ ìíîæèòåëÿ L èç ïðèâå-
äåííîé òåîðåìû, ïîëó÷àåì
inf inf
t t
V t V
t
V nt V
t
n L
� �
�
� � � �
0 0
0 0 0( ) ( ) ( ) ( )
.
Òàêèì îáðàçîì, â ñîîòâåòñòâèè ñ òåîðåìîé
� �
� � �
2
0
1
*
( ( , )) ,
min ( ) min (
max
�
�
� �
�
K u
ii ii
i
n
u
iiu u � � �ii
i
n
n K u) ( ( , ))max
�
�
�
�
�
�
�
�
�
�
�
1
�
�
�
�
�
�
�
�
�
�
�max ( ) ( ( , ))
,
min
u
ii ii
i
n
u n K u
�
� � �
1
.
Äîêàçàòåëüñòâî óòâåðæäåíèÿ 2 çàâåðøåíî.
Ðàññìîòðåíà ìèíèìèçàöèÿ êâàäðàòè÷íîé ôóíêöèè (1) íà ìíîãîîáðàçèè Øòè-
ôåëÿ, êîãäà êîìïîíåíòû âåêòîðîâ
�
xi , i k� 1, , ïðèíàäëåæàò ìíîæåñòâó äåéñòâèòåëü-
íûõ ÷èñåë. Âñòðå÷àþòñÿ âàðèàíòû ýòîé çàäà÷è (íàïðèìåð, â [1, 4]), êîãäà êîìïîíåí-
òû âåêòîðîâ
�
xi , i k� 1, , ïðèíàäëåæàò ìíîæåñòâó öåëûõ ÷èñåë (÷òî ñ ó÷åòîì íîðìè-
ðîâàííîñòè âåêòîðîâ ñîîòâåòñòâóåò xij � { 10 1, , }) èëè ìíîæåñòâó öåëûõ
íåîòðèöàòåëüíûõ ÷èñåë (ýêâèâàëåíòíî óñëîâèþ áóëåâîñòè ïåðåìåííûõ xij ). Îíè
èíòåðåñíû â ïåðâóþ î÷åðåäü òåì, ÷òî ñ ïîìîùüþ èñïîëüçîâàíèÿ òåõíèêè äâîé-
ñòâåííûõ êâàäðàòè÷íûõ îöåíîê äëÿ íèõ, êàê áóäåò ïîêàçàíî äàëåå, ìîæíî ïîëó÷èòü
òî÷íûå îöåíêè (ýòè çàäà÷è ïîëèíîìèàëüíî ðàçðåøèìû). Îáà ñëó÷àÿ ýêâèâàëåíòíû:
îïòèìàëüíîå çíà÷åíèå îäíî è òî æå, îòëè÷àåòñÿ ëèøü ìíîæåñòâî òî÷åê ãëîáàëüíî-
ãî ýêñòðåìóìà — åñëè äëÿ íåêîòîðîé êîíêðåòíîé çàäà÷è íà ìíîæåñòâå öåëûõ íåîò-
ðèöàòåëüíûõ ÷èñåë èõ êîëè÷åñòâî ñîñòàâëÿåò L, òî äëÿ òîé æå çàäà÷è íà ìíîæåñòâå
öåëûõ ÷èñåë — 2k L (çà ñ÷åò âñåõ âîçìîæíûõ âàðèàíòîâ çàìåí 1 íà –1), è íàîáîðîò
(çàìåíèâ âñå –1 íà 1). Ïîýòîìó äîñòàòî÷íî èññëåäîâàòü âòîðóþ èç íèõ.
100 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5
Ðàññìîòðèì êâàäðàòè÷íóþ ïîñòàíîâêó äëÿ èñõîäíîé çàäà÷è íà ìíîæåñòâå öå-
ëûõ íåîòðèöàòåëüíûõ ÷èñåë (êàê è ðàíåå, áåç îãðàíè÷åíèÿ îáùíîñòè ñ÷èòàåì k n� )
f A xB ijj ij
j
n
i
n
* min�
��
�� 2
11
(14)
ïðè îãðàíè÷åíèÿõ
x i nij
j
n
2
1
1 1
�
� � �, , ,� , (15)
x j nij
i
n
2
1
1 1
�
� � �, , ,� , (16)
x x i n j nij ij
2 0 1 1 � � �, , , , , ,� � , (17)
ãäå Aijj — j-é äèàãîíàëüíûé ýëåìåíò ìàòðèöû Ai (îò íåäèàãîíàëüíûõ ÷ëåíîâ
çàäà÷à íå çàâèñèò, ïîñêîëüêó â ñèëó îðòîíîðìèðîâàííîñòè êàæäûé âåêòîð
�
x i ni , ,� 1 , ñîäåðæèò îäíó, è òîëüêî îäíó êîìïîíåíòó, îòëè÷íóþ îò íóëÿ). Çàäà÷à
(14)–(17) ïîëó÷àåòñÿ â ðåçóëüòàòå äîáàâëåíèÿ ê çàäà÷å (5), (6), (8), (9) óñëîâèÿ
áóëåâîñòè ïåðåìåííûõ è èñêëþ÷åíèÿ îãðàíè÷åíèé (9), êîòîðûå íå íóæíû êàê ñ
òî÷êè çðåíèÿ èñõîäíîé çàäà÷è (ÿâëÿþòñÿ ñëåäñòâèåì îãðàíè÷åíèé (15)–(17)), òàê
è êâàäðàòè÷íîé îöåíêè (íå âëèÿþò íà åå ðåøåíèå).
 îòëè÷èå îò ïðåäûäóùåãî ñëó÷àÿ êâàäðàòè÷íàÿ çàäà÷à (14)–(17) íå îäíî-
ðîäíà, â ñèëó ÷åãî íàõîæäåíèå äâîéñòâåííîé ëàãðàíæåâîé îöåíêè ïîòðåáóåò áîëü-
øèõ óñèëèé — ðåøåíèå âíóòðåííåé çàäà÷è óæå íå áóäåò òðèâèàëüíûì (ðàâíûì íó-
ëåâîìó âåêòîðó) è äëÿ åãî íàõîæäåíèÿ ïðè ôèêñèðîâàííûõ äâîéñòâåííûõ ïåðåìåí-
íûõ ïîòðåáóåòñÿ ðåøåíèå ñèñòåìû ëèíåéíûõ óðàâíåíèé.  äàííîì ñëó÷àå
äâîéñòâåííàÿ ëàãðàíæåâàÿ îöåíêà èìååò îáùèé âèä
� � � � �
� �
B B
u w K u w
Bu w u w* * * *
( , , ): ( , , )
( , , ) ( , , )� �
�
sup
0
, (18)
ãäå ( , , )u w� — âåêòîð ìíîæèòåëåé Ëàãðàíæà (u u i ni� �{ }, ,1 ñîîòâåòñòâóþò îãðà-
íè÷åíèÿì (15), � �� �{ }i i n, ,1 — îãðàíè÷åíèÿì (16), w w i n j nij� � �{ }, , , ,1 1 —
îãðàíè÷åíèÿì (17));
� � �B
x
T
ij ij
j i
n
i
n
i
i
n
u w x K u w x w x u( , , ) ( , , ) (�
�� �
��inf
1 1
�
�
�
�
�
�
�
�
�
� i )
ïðè K u w( , , )� � 0 ;
K u w K u K V Wi ii
i
n
ii ii( , , ) ( )� �
�
�0
1
(çàäàíèå ìàòðèö K 0 è K ii îïðåäåëåíî ðàíåå, Vii — ìàòðèöà èç n2 áëîêîâ ðàçìåðîì
n n� , âñå âíåäèàãîíàëüíûå áëîêè êîòîðîé ðàâíû íóëåâûì ( )n n� -ìàòðèöàì, à i-é äèà-
ãîíàëüíûé áëîê ïðåäñòàâëÿåò ñîáîé äèàãîíàëüíóþ ìàòðèöó diag( , , )� j j n� 1 , Wii —
ìàòðèöà, ïîñòðîåííàÿ àíàëîãè÷íî ìàòðèöå Vii , ñ òåì îòëè÷èåì, ÷òî i-é äèàãî-
íàëüíûé áëîê çàäàåòñÿ ìàòðèöåé diag ( , , )w j nij � 1 ).
Ñ ïîìîùüþ ðàâåíñòâ (17) çàäà÷à (14)–(17) ñâîäèòñÿ ê çàäà÷å ëèíåéíîãî ïðî-
ãðàììèðîâàíèÿ íà áóëåâûõ ïåðåìåííûõ, êîòîðàÿ èçâåñòíà êàê êëàññè÷åñêàÿ çàäà÷à
î íàçíà÷åíèÿõ:
min A xijj ij
j
n
i
n
��
��
11
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 101
ïðè îãðàíè÷åíèÿõ
x i nij
j
n
�
� � �
1
1 1, , , ,� x j nij
i
n
�
� � �
1
1 1, , ,� ,
x x i n j nij ij
2 0 1 1 � � �, , , , , ,� � .
Ïðè ýòîì äâîéñòâåííàÿ îöåíêà íå ìåíÿåòñÿ, ïîñêîëüêó èñêëþ÷åíèå êâàäðàòè÷-
íûõ ÷ëåíîâ ðàâíîñèëüíî çàìåíå w w A uij ij ijj i j� ~ � â ôóíêöèè Ëàãðàíæà.  ñè-
ëó óíèìîäàëüíîñòè ìàòðèöû îãðàíè÷åíèé óñëîâèÿ x x i nij ij
2 0 1 � �, , , ,� j n� 1, ,� ,
ìîæíî çàìåíèòü íåðàâåíñòâàìè x xij ij
2 0 � , â ðåçóëüòàòå ÷åãî ïîëó÷àåì çàäà÷ó âû-
ïóêëîãî êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ, äëÿ êîòîðîé äâîéñòâåííàÿ ëàãðàíæåâàÿ
îöåíêà âñåãäà òî÷íà [3]. Òàêèì îáðàçîì, äîêàçàíà ñïðàâåäëèâîñòü ñëåäóþùåãî
óòâåðæäåíèÿ.
Óòâåðæäåíèå 3. Îöåíêà �B
* (18) äëÿ çàäà÷è (14)–(17) òî÷íàÿ — fB B
* *� � .
Ýôôåêòèâíîñòü äâîéñòâåííûõ îöåíîê èññëåäîâàëàñü íà ðÿäå òåñòîâûõ çàäà÷.
Äëÿ íàõîæäåíèÿ îöåíîê �2
* è �B
* , êàê è â [4], èñïîëüçîâàëàñü ïðîãðàììà DSQTPR
ñ ïðèìåíåíèåì ìîäèôèêàöèè r-àëãîðèòìà [7], ïðåäíàçíà÷åííàÿ äëÿ íàõîæäåíèÿ
äâîéñòâåííûõ ëàãðàíæåâûõ îöåíîê â êâàäðàòè÷íûõ çàäà÷àõ îáùåãî âèäà. Çàìåòèì,
÷òî õîòÿ äëÿ âû÷èñëåíèÿ �2
* íå òðåáóåòñÿ ðåøåíèÿ îáùåé çàäà÷è (ñì., íàïðèìåð,
óòâåðæäåíèå 2), îäíàêî åå èñïîëüçîâàíèå ïîçâîëÿåò ðåøèòü ïðîáëåìó íàõîæäåíèÿ
êîíêðåòíûõ ðåøåíèé çàäà÷è (1) íà ìíîãîîáðàçèè Øòèôåëÿ. Ýòà ïðîáëåìà, âîçíèêà-
þùàÿ ïðè íàõîæäåíèè ëþáîé äâîéñòâåííîé ëàãðàíæåâîé îöåíêè, ñîñòîèò â òîì,
÷òî äàæå â ñëó÷àå ïîëó÷åíèÿ òî÷íîé îöåíêè â ñâÿçè ñ íåîäíîçíà÷íîñòüþ ðåøåíèÿ
ïðÿìîé çàäà÷è (âñåãäà äëÿ çàäà÷è (5), (6), (8), (9) è, êàê ïðàâèëî, äëÿ çàäà÷è
(14)–(17)) îöåíêà äîñòèãàåòñÿ íà ãðàíèöå ïîëîæèòåëüíîé îïðåäåëåííîñòè ìàòðèöû,
÷òî íå ïîçâîëÿåò îïðåäåëèòü x* .  ýòîì ñëó÷àå, äëÿ òîãî ÷òîáû ïîëó÷èòü îäíó èç
òî÷åê ãëîáàëüíîãî ìèíèìóìà, íà ïðàêòèêå ìîæíî âîñïîëüçîâàòüñÿ âîçìóùåíèåì
ýëåìåíòîâ êâàäðàòè÷íîé ôîðìû ôóíêöèè Ëàãðàíæà (ìàòðè÷íîé è ëèíåéíîé åå ÷àñ-
òè) íà ñðàâíèòåëüíî ìàëûå âåëè÷èíû.
Ïðèâåäåì ðåçóëüòàòû ðåøåíèÿ íåêîòîðûõ òåñòîâûõ ïðèìåðîâ.
Ïðèìåð 1. Çàäàíû ìàòðèöû A A A1 2 3� � �diag (1,2,3), diag (4,5,6), diag (7,8,9),
ò.å. öåëåâàÿ ôóíêöèÿ èìååò âèä
f x x x x x x x x x( ) �
11
2
12
2
13
2
21
2
22
2
23
2
31
2
32
2 3 4 5 6 7 8 2
33
29
x .
Äëÿ äàííîãî ïðèìåðà f * � 15, à äâîéñòâåííûå îöåíêè �1 12* � è �2 15* � . Êàê
âèäíî, âî âòîðîì ñëó÷àå èìååì òî÷íóþ íèæíþþ îöåíêó. Çàìåòèì, ÷òî ðàçðûâ
äâîéñòâåííîñòè �1 1� f * *� â ïåðâîì ñëó÷àå ðàâåí òðåì è äîñòàòî÷íî âåëèê
( %� 20 ).
Ïðèìåð 2. Çàäàíû ìàòðèöû
A1
3 7 2 2
7 2 6 9
2 9 4
�
�
�
�
�
�
�
�
�
�
�
/
/ , A2
3 3 7 2
3 5 6
7 2 6 3
�
�
�
�
�
�
�
�
�
�
�
/
/
,
ò.å. öåëåâàÿ ôóíêöèÿ èìååò âèä
f x x x x x x x x( ) �
3 6 4 7 4
11
2
12
2
13
2
11 12 11 13
18 3 5 3 6 7 1212 13 21
2
22
2
23
2
21 22 21 23 22x x x x x x x x x x x23 .
102 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5
Äëÿ äàííîãî ïðèìåðà äâîéñòâåííûå îöåíêè �1 8 78798* ,� è �2 8 50412* ,� . Âî
âòîðîì ñëó÷àå èìååì òî÷íóþ íèæíþþ îöåíêó.  ýòîì ìîæíî óáåäèòüñÿ, çàìåíèâ
â çàäà÷å (5), (6), (8), (9) f x x A x x A xT T( ) �
� � � �
1 1 1 2 2 2 âîçìóùåííîé ôóíêöèåé
f x xij
i j
( )
,
�
�10 6
1
3
. Ïðè ýòîì íàõîæäåíèå îöåíêè �2
* íå óïðîùàåòñÿ äî âèäà (11),
à èìååò «èñõîäíîå» ïðåäñòàâëåíèå (äëÿ êâàäðàòè÷íîé çàäà÷è îáùåãî âèäà)
� � � �
� �
2 2
0
10* * * *
( , ): ( , )
( , , ) ( , )� �
�
u w x K u x
u K u x
Tsup inf
� �
� �
�
�
�
�
�
�
�
�
6
1 1
x uij
i j
n
ii ii
i
n
,
( )� .
Äëÿ òàêîé âîçìóùåííîé çàäà÷è ïîëó÷åíî
x1 0 03070 0 68053 0 73207* ( , , , , , )� T , x2 0 95325 0 24022 018333* ( , , , , , )� T ,
x3 0 30062 0 69222 0 65609* ( , , , , , )� T ,
ïðè êîòîðîì �2 8 50412* ,� è íåâÿçêè âñåõ îãðàíè÷åíèé ìåíüøå 10 6 (îòìåòèì,
÷òî âåêòîð x3
* èãðàåò âñïîìîãàòåëüíóþ ðîëü è íå âõîäèò â ðåøåíèå èñõîäíîé çà-
äà÷è ïðè k � 2).
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. R a p c s a k T . On minimization on Stiefel manifold // Eur. J. Oper. Res. — 2002. — 143. — P. 365–376.
2. B a l o g h J . , C s e n d e s T . , R a p c s a k T . Global optimization problems on Stiefel manifold //
NMCM-2002 Book of Abstracts. — Miscolc, Hungary, 2002. — P. 19–21.
3. Ø î ð Í . Ç . , Ñ ò å ö å í ê î Ñ . È . Êâàäðàòè÷íûå ýêñòðåìàëüíûå çàäà÷è è íåäèôôåðåíöèðóåìàÿ
îïòèìèçàöèÿ. — Êèåâ: Íàóê. äóìêà, 1989. — 208 ñ.
4. Ø î ð Í . Ç . , Ñ ò å ö þ ê Ï . È . , Á å ð å ç î â ñ ê è é Î . À . Äâîéñòâåííûå îöåíêè äëÿ ñïåöèàëüíîé
îïòèìèçàöèîííîé çàäà÷è êâàäðàòè÷íîãî òèïà íà ìíîãîîáðàçèè Øòèôôåëÿ // Òåîðèÿ îïòèìàëüíûõ
ðåøåíèé. — Êèåâ: Èí-ò êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, 2004. — ¹ 3. — C. 3–10.
5. S h o r N . Z . Nondifferentiable optimization and polynomial problems. — Dordrecht: Kluwer, 1998. —
394 p.
6. Á å ð å ç î â ñ ê è é Î . À . Ñâåäåíèå íàõîæäåíèÿ äâîéñòâåííûõ îöåíîê äëÿ êâàäðàòè÷íûõ çàäà÷ ê
ðåøåíèþ çàäà÷ áåçóñëîâíîé îïòèìèçàöèè // Ðàáîòû ìåæäóíàð. ñèìï. «Ïèòàííÿ îïòèìiçàöi¿
îá÷èñëåíü (ÏÎÎ-XXXIII)». — Êèåâ: Èí-ò êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, 2007. —
Ñ. 32–33.
7. S h o r N . Z . a n d S t e t s y u k P . I . Dual solution of quadratic-type problems by r-algorithm (subroutine
DSQTPr) // Abstracts of Second Intern. Workshop «Recent Advances in Non-Differentiable Optimization»
(Oct., 1–4, 2001, Kyiv, Ukraine). — P. 36.
Ïîñòóïèëà 26.09.2007
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 103
|