О некоторых научных результатах Ю. М. Ермольева и его школы в области современной теории оптимизации
Наведено огляд основних результатів, одержаних українськими вченими в області стохастичної оптимізації. Основну увагу приділено роботам вченого та його школи, зокрема квазіградієнтним методам стохастичного програмування, які визнано класичними. Main results obtained by Ukrainian scientists in stocha...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2011 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84247 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О некоторых научных результатах Ю. М. Ермольева и его школы в области современной теории оптимизации / П.С. Кнопов, И.В. Сергиенко // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 3-27. — Бібліогр.: 42 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859946091465670656 |
|---|---|
| author | Кнопов, П.С. Сергиенко, И.В. |
| author_facet | Кнопов, П.С. Сергиенко, И.В. |
| citation_txt | О некоторых научных результатах Ю. М. Ермольева и его школы в области современной теории оптимизации / П.С. Кнопов, И.В. Сергиенко // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 3-27. — Бібліогр.: 42 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Наведено огляд основних результатів, одержаних українськими вченими в області стохастичної оптимізації. Основну увагу приділено роботам вченого та його школи, зокрема квазіградієнтним методам стохастичного програмування, які визнано класичними.
Main results obtained by Ukrainian scientists in stochastic optimization are reviewed. Most attention is paid to the results of the scientist and his school in quasigradient stochastic programming methods, which are considered classical.
|
| first_indexed | 2025-12-07T16:14:17Z |
| format | Article |
| fulltext |
Ï.Ñ. ÊÍÎÏÎÂ, È.Â. ÑÅÐÃÈÅÍÊÎ
ÓÄÊ 519.21 Î ÍÅÊÎÒÎÐÛÕ ÍÀÓ×ÍÛÕ ÐÅÇÓËÜÒÀÒÀÕ
Þ.Ì. ÅÐÌÎËÜÅÂÀ È ÅÃÎ ØÊÎËÛ Â ÎÁËÀÑÒÈ
ÑÎÂÐÅÌÅÍÍÎÉ ÒÅÎÐÈÈ ÎÏÒÈÌÈÇÀÖÈÈ
Êëþ÷åâûå ñëîâà: òåîðèÿ ñòîõàñòè÷åñêîé îïòèìèçàöèè, îïòìàëüíîå óïðàâëå-
íèå, êâàçèãðàäèåíòû.
ÂÂÅÄÅÍÈÅ
Ñ ïåðâûõ ëåò ñóùåñòâîâàíèÿ Èíñòèòóòà êèáåðíåòèêè èìåíè Â.Ì. Ãëóøêîâà ÍÀÍ
Óêðàèíû îäíèìè èç ñàìûõ ïðèîðèòåòíûõ íàó÷íûõ íàïðàâëåíèé áûëè èññëåäîâà-
íèÿ â îáëàñòè òåîðèè îïòèìèçàöèè è îïòèìàëüíîãî óïðàâëåíèÿ, ìîäåëèðîâàíèÿ,
òåîðèè ðèñêà è ñèñòåìíîãî àíàëèçà. Íàó÷íûå ðåçóëüòàòû, ïîëó÷åííûå ó÷åíûìè
èíñòèòóòà â ýòîé îáëàñòè, øèðîêî èçâåñòíû êàê ó íàñ â ñòðàíå, òàê è çà ðóáå-
æîì, à øêîëû ïî òåîðèè íåäèôôåðåíöèðóåìîé è äèñêðåòíîé îïòèìèçàöèè, ñòî-
õàñòè÷åñêîé îïòèìèçàöèè è òåîðèè ðèñêà, îïòèìàëüíîãî óïðàâëåíèÿ ïîëó÷èëè
ìèðîâîå ïðèçíàíèå. Â íàñòîÿùåé ñòàòüå îñòàíîâèìñÿ íà îäíîì èç íàèáîëåå âàæ-
íûõ íàïðàâëåíèé òåîðèè îïòèìèçàöèè — òåîðèè ñòîõàñòè÷åñêîé îïòèìèçàöèè,
îñíîâíîå âíèìàíèå óäåëèâ ïðè ýòîì ðåçóëüòàòàì Þ.Ì. Åðìîëüåâà è åãî øêîëû.
Òðàäèöèîííûå äåòåðìèíèðîâàííûå ìåòîäû îïòèìèçàöèè èñïîëüçóþòñÿ äëÿ
òî÷íî îïðåäåëåííûõ ôóíêöèé öåëè è îãðàíè÷åíèé, ò.å. êîãäà ìîæíî òî÷íî âû-
÷èñëèòü ìèíèìèçèðóåìóþ (èëè ìàêñèìèçèðóåìóþ) f x0 ( ) è ïðîâåðèòü îãðàíè÷å-
íèÿ f x i mi ( ) , :� �0 1 , äëÿ ëþáîãî âåêòîðà ðåøåíèé x x x Xn� �( , , )1 � , ãäå ìíî-
æåñòâî X èìååò «ïðîñòóþ» ñòðóêòóðó (íàïðèìåð, îïðåäåëÿåòñÿ ëèíåéíûìè îãðà-
íè÷åíèÿìè). Îáû÷íî ïðåäïîëàãàåòñÿ òàêæå, ÷òî ãðàäèåíòû èëè ñóáãðàäèåíòû
(äëÿ íåãëàäêèõ ôóíêöèé) f x
i ôóíêöèé f i , i m� 0 1, , ,� , ìîæíî âû÷èñëèòü. Ðàçðà-
áîòàííûå Þ.Ì. Åðìîëüåâûì [1–5] ìåòîäû ñòîõàñòè÷åñêîãî êâàçèãðàäèåíòà (SQG)
èñïîëüçîâàëèñü äëÿ ðåøåíèÿ îáùèõ çàäà÷ îïòèìèçàöèè, êîãäà òî÷íî ðàññ÷èòàòü f i ,
f x
i íåâîçìîæíî. Ëþáàÿ äåòåðìèíèðîâàííàÿ îïòèìèçàöèîííàÿ ìîäåëü, íàïðèìåð
min ( , )| ( , ) , , , ;{ }f x f x i m x X Ri n0 0 1� � � � � �� ,
ñîäåðæèò ïàðàìåòðû �, êîòîðûå â îáùåì ñëó÷àå ìîãóò áûòü ñëó÷àéíûìè. Ýòî
ìîæåò îáúÿñíÿòüñÿ êàê íåïîëíîòîé èíôîðìàöèè î çíà÷åíèÿõ ïàðàìåòðîâ
(îøèáêè èçìåðåíèé, ñòàòèñòè÷åñêèå îöåíêè ïàðàìåòðîâ), òàê è ñàìîé ñòîõàñ-
òè÷åñêîé ïðèðîäîé ïàðàìåòðîâ (ïðîãíîçû, ïîãîäíûå óñëîâèÿ, îñàäêè, êîëåáà-
íèÿ öåí, ñïðîñà, óðîæàéíîñòè, êóðñîâ àêöèé è ò.ï.). Òîãäà ïðè ëþáîì ôèêñè-
ðîâàííîì x îãðàíè÷åíèÿ f xi ( , )� � 0 ìîãóò íå âûïîëíÿòüñÿ äëÿ íåêîòîðûõ ðå-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 3
© Ï.Ñ. Êíîïîâ, È.Â. Ñåðãèåíêî, 2011
àëèçàöèé ñëó÷àéíîãî ïàðàìåòðà �, à öåëåâàÿ ôóíêöèÿ f x0 ( , )� ìîæåò
ïðèíèìàòü ðàçíûå çíà÷åíèÿ, è ïðîáëåìà ñîñòîèò â òîì, ÷òî ñëåäóåò ïîíèìàòü
ïîä ðåøåíèåì òàêîé çàäà÷è. Íàáîð ôóíêöèé f x f x( , ) ( , ),� �� { 0
f x f xm1 ( , ), , ( , )� �� }, � ��, ìîæíî ðàññìàòðèâàòü êàê âåêòîðíóþ õàðàêòå-
ðèñòèêó ðåøåíèÿ x X� è òðàêòîâàòü çàäà÷ó âûáîðà îïòèìàëüíîãî x êàê ïðî-
áëåìó âåêòîðíîé îïòèìèçàöèè, âîîáùå ãîâîðÿ, ñ áåñêîíå÷íûì ÷èñëîì êðèòåðè-
åâ. Âìåñòî � èíîãäà ïîäñòàâëÿþò åãî ñðåäíåå çíà÷åíèå — E�, íî âî ìíîãèõ
ñëó÷àÿõ íåëüçÿ èãíîðèðîâàòü ñòîõàñòè÷åñêóþ ïðèðîäó ïàðàìåòðîâ çàäà÷è. Ïî
ýòîé ïðè÷èíå, íàïðèìåð, â ôèíàíñîâûõ ïðèëîæåíèÿõ âìåñòå ñî ñðåäíèì âûèã-
ðûøåì ó÷èòûâàþò òàêæå äèñïåðñèþ âûèãðûøà, à â ñòðàõîâûõ ïðèëîæåíè-
ÿõ — âåðîÿòíîñòü ðàçîðåíèÿ êîìïàíèè. Ôîðìàëèçàöèåé çàäà÷ îïòèìèçàöèè ñî
ñëó÷àéíûìè ïàðàìåòðàìè çàíèìàåòñÿ òåîðèÿ ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ.
Îòìåòèì, ÷òî òåîðèÿ è íåêîòîðûå ïðèëîæåíèÿ ñòîõàñòè÷åñêîãî êâàçèãðàäèåíòíî-
ãî ìåòîäà ðåçþìèðîâàíû â ðÿäå ñòàòåé Ýíöèêëîïåäèè îïòèìèçàöèè [6].
×àùå âñåãî ïîä çàäà÷åé (îäíîýòàïíîãî) ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ
ïîíèìàþò ýêñòðåìàëüíóþ çàäà÷ó
F x Ef x0 0( ) ( , ) min� �� (1)
ïðè îãðàíè÷åíèÿõ
F x Ef xi i( ) ( , )� �� 0, x X R n� � , (2)
ãäå � — âåêòîð ñëó÷àéíûõ ïàðàìåòðîâ, E — ñèìâîë ìàòåìàòè÷åñêîãî îæèäà-
íèÿ ïî �, x — äåòåðìèíèðîâàííûé âåêòîð ðåøåíèé ñ íåïðåðûâíûìè è/èëè
äèñêðåòíûìè êîîðäèíàòàìè. Îòìåòèì, ÷òî ( , , )� � P — âåðîÿòíîñòíîå ïðîñòðà-
íñòâî çàäà÷è. ×àñòî âìåñòî F xi ( ) ðàññìàòðèâàþò ôóíêöèè (îæèäàåìîé ïîëåç-
íîñòè) âèäà F x Eu f x( ) ( ( , ))� � , ãäå u( ) — íåîòðèöàòåëüíàÿ ìîíîòîííî âîç-
ðàñòàþùàÿ ôóíêöèÿ (ïîëåçíîñòè).
Åñëè ôóíêöèè f xi ( , )� â (1), (2) èçâåñòíû â ÿâíîì âèäå, òî èíòåãðàëû (ìàòå-
ìàòè÷åñêèå îæèäàíèÿ) â íèõ ìîæíî ïðèáëèçèòü ñ ïîìîùüþ êâàäðàòóð èëè ýìïè-
ðè÷åñêèìè ñðåäíèìè:
F x
N
f xiN i k
k
N
( ) ( , )�
�
1
1
� , (3)
ãäå � k , k N�1, , ,� — íåçàâèñèìûå ðåàëèçàöèè ñëó÷àéíûõ ïàðàìåòðîâ çàäà÷è.
Òîãäà ïðîáëåìó (1), (2) ìîæíî àïïðîêñèìèðîâàòü äåòåðìèíèðîâàííîé çàäà÷åé
è ðåøèòü äåòåðìèíèðîâàííûìè ìåòîäàìè. Ýòîò ïîäõîä ê ðåøåíèþ çàäà÷ ñòî-
õàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ, êîòîðûé íàçâàí ìåòîäîì ýìïèðè÷åñêèõ ñðåä-
íèõ, èññëåäîâàëñÿ â ðàáîòàõ [7–10].
Ïðåäëîæåííûé Þ.Ì. Åðìîëüåâûì SQG-ìåòîä ðåøåíèÿ çàäà÷ âûïóêëîãî ñòî-
õàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ ìîæåò ðàññìàòðèâàòüñÿ êàê îáîáùåíèå ìåòîäîâ
ñòîõàñòè÷åñêîé àïïðîêñèìàöèè íà ìíîãîìåðíûå íåãëàäêèå çàäà÷è ñ îãðàíè÷åíèÿìè
è êàê îáîáùåíèå ìåòîäà Ìîíòå-Êàðëî íà çàäà÷è îïòèìèçàöèè, à òàêæå êàê ðàçâèòèå
ìåòîäîâ ñëó÷àéíîãî ïîèñêà. Îñíîâíàÿ îñîáåííîñòü êâàçèãðàäèåíòíûõ ìåòîäîâ ñî-
ñòîèò â òîì, ÷òî îíè íå òðåáóþò âû÷èñëåíèÿ òî÷íûõ çíà÷åíèé öåëåâûõ ôóíêöèé è
îãðàíè÷åíèé, à èñïîëüçóþò ñòàòèñòè÷åñêèå îöåíêè (ðåàëèçàöèè) ïîäûíòåãðàëüíûõ
ôóíêöèé è èõ îáîáùåííûõ ãðàäèåíòîâ. Îíè îòðàæàþò îñíîâíûå èäåè ñòàíäàðòíûõ
ìåòîäîâ îïòèìèçàöèè, ïðîöåäóðû ñëó÷àéíîãî ïîèñêà, ñòîõàñòè÷åñêîé àïïðîêñèìà-
öèè è ñòàòèñòè÷åñêîãî îöåíèâàíèÿ. Ýòî îòêðûâàåò øèðîêèå âîçìîæíîñòè èõ
ïðèìåíåíèÿ äëÿ ðåøåíèÿ çàäà÷ èññëåäîâàíèÿ îïåðàöèé, àäàïòàöèè è îïòèìèçàöèè
ñëîæíûõ ñòîõàñòè÷åñêèõ ñèñòåì ñ ïîìîùüþ èìèòàöèîííîãî ìîäåëèðîâàíèÿ. Ìåòî-
äû SQG ìîæíî èñïîëüçîâàòü äëÿ ðåøåíèÿ òðåõ òèïîâ çàäà÷:
4 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
• äåòåðìèíèðîâàííûõ ïðîáëåì, äëÿ êîòîðûõ ñëîæíî âû÷èñëÿòü íàïðàâëåíèå
ñïóñêà (áîëüøîé ìàñøòàá, íåãëàäêîñòü, ðàñïðåäåëåííîñòü, íåñòàöèîíàðíîñòü ìî-
äåëåé îïòèìèçàöèè);
• ìíîãîýêñòðåìàëüíûõ çàäà÷, êîãäà âàæíî îáîéòè ëîêàëüíî îïòèìàëüíûå
ðåøåíèÿ;
• çàäà÷ ñ ó÷åòîì íåîïðåäåëåííîñòåé è/èëè ñëîæíîñòåé â îöåíêå ôóíêöèé è
èõ ñóáãðàäèåíòîâ (çàäà÷è ñòîõàñòè÷åñêîé, ïðîñòðàíñòâåííîé è äèíàìè÷åñêîé
îïòèìèçàöèè ñ ìíîãîìåðíûìè èíòåãðàëàìè, ìîäåëèðîâàíèå, àíàëèòè÷åñêè íå-
äîñòóïíûå ìîäåëè).
Òàêèì îáðàçîì, ê ìåòîäàì SQG ïðèáåãàþò â òåõ ñëó÷àÿõ, êîãäà ñòðóêòóðà
çàäà÷è íå ïîçâîëÿåò èñïîëüçîâàòü äðóãèå èíñòðóìåíòû äåòåðìèíèðîâàííîé
îïòèìèçàöèè. Ïðè ýòîì íåîáõîäèìîå òðåáîâàíèå — íàëè÷èå ñîâðåìåííûõ êîì-
ïüþòåðíûõ ðåñóðñîâ, äîñòàòî÷íûõ äëÿ äîñòèæåíèÿ íóæíîé òî÷íîñòè
îïòèìàëüíûõ ðåøåíèé, èñïîëüçóåìûõ äëÿ ìíîãèõ ïðèëîæåíèé.
1. ÊËÀÑÑÈ×ÅÑÊÀß ÒÅÎÐÈß ÂÛÏÓÊËÎÃÎ
ÑÒÎÕÀÑÒÈ×ÅÑÊÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß
1.1. Èäåÿ ìåòîäà ñòîõàñòè÷åñêèõ êâàçèãðàäèåíòîâ. Îñíîâíàÿ èäåÿ ìåòîäîâ
SQG [1–5] — èñïîëüçîâàíèå ñòàòèñòè÷åñêèõ (ñìåùåííûõ è íåñìåùåííûõ)
îöåíîê öåëåâîé ôóíêöèè è ôóíêöèé îãðàíè÷åíèé, à òàêæå èõ ãðàäèåíòîâ (ñóá-
ãðàäèåíòîâ). Äðóãèìè ñëîâàìè, ïîñëåäîâàòåëüíîñòü ïðèáëèæàþùèõ ðåøåíèé
x x0 1, ,� ñòðîèòñÿ ñ èñïîëüçîâàíèåì ñëó÷àéíûõ âåëè÷èí � i k( ) è ñëó÷àéíûõ
âåêòîðîâ � i k( ), i m� 0, ,� , òàêèõ, ÷òî óñëîâíîå ìàòåìàòè÷åñêîå îæèäàíèå äëÿ
äàííîé «èñòîðèè» Gk (ñêàæåì, ( , , )x x k0
� ) èìååò âèä
E k G F x a ki
k
i k i[ ( )| ] ( ) ( ),� � � (4)
E k G F x b ki
k x
i k i[ ( )| ] ( ) ( ),� � � (5)
ãäå a ki ( ) , b ki ( ) — «îøèáêè» (ñìåùåííûå) îöåíîê � i k( ) , � i k( ) . Äëÿ òî÷íîé
ñõîäèìîñòè ïîñëåäîâàòåëüíîñòè { }x k ê îïòèìàëüíûì ðåøåíèÿì a ki ( ) , b ki ( )
äîëæíû ñòðåìèòüñÿ (â íåêîòîðîì ñìûñëå) ê íóëþ ïðè k � �. Âåêòîðû � i k( )
íàçûâàþòñÿ ñòîõàñòè÷åñêèìè êâàçèãðàäèåíòàìè. Åñëè b ki ( )
0, òî îíè òàêæå
íàçûâàþòñÿ ñòîõàñòè÷åñêèìè ãðàäèåíòàìè äëÿ íåïðåðûâíî äèôôåðåíöèðóåìîé
F xi ( ) è ñòîõàñòè÷åñêèìè ñóáãðàäèåíòàìè (îáîáùåííûìè ãðàäèåíòàìè) äëÿ íå-
ãëàäêèõ F xi ( ) .  ïîñëåäóþùèõ îáîçíà÷åíèÿõ F x k( ), ( ),� �( )k òàêæå èñïîëü-
çóþòñÿ âìåñòî F x k k0 0 0( ), ( ), ( )� � .
Ðàññìîòðèì ïðîñòåéøèé ìåòîä SQG. Ïðåäïîëîæèì, ÷òî îãðàíè÷åíèé (2)
íåò, X — çàìêíóòîå è îãðàíè÷åííîå (êîìïàêòíîå) ìíîæåñòâî, òàêîå, ÷òî îðòîãî-
íàëüíûå ïðîåêöèè � X y( ) òî÷êè y íà X ëåãêî âû÷èñëèòü: � X y( ) �
= Arg min{ }| | | | : ,y x x X� �2 íàïðèìåð �a x b y a y b� � �( ) max[ , min , ]{ } . Ìåòîä
SQG-ïðîåêöèé îïðåäåëÿåòñÿ èòåðàòèâíî êàê
x x k kk
X
k
k
� � � �1 0 1� [ ( )], , , ,� � � (6)
ãäå � k — ïîëîæèòåëüíûé ðàçìåð øàãà, x 0 — ñëó÷àéíàÿ íà÷àëüíàÿ àïïðîêñèìàöèÿ.
Òðåáóþò îáúÿñíåíèÿ ñëåäóþùèå âîïðîñû ìåòîäà (6) è äðóãèõ ïîäîáíûõ
àëãîðèòìîâ:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 5
(i) ïîñòðîåíèå íà îñíîâå íà÷àëüíîãî âåðîÿòíîñòíîãî ïðîñòðàíñòâà çàäà÷è
( , , )� � P äðóãîãî (àëãîðèòìè÷åñêîãî) âåðîÿòíîñòíîãî ïðîñòðàíñòâà ( , , )� �� �P
è âûÿñíåíèå âîïðîñîâ èçìåðèìîñòè â íåì ïðîöåññà (6);
(ii) ïîñòðîåíèå íàïðàâëåíèÿ äâèæåíèÿ �( )k íà îñíîâå èíôîðìàöèè î ïîäûí-
òåãðàëüíîé ôóíêöèè f x( , )� ;
(iii) óñëîâèÿ ñõîäèìîñòè àëãîðèòìà (6) è âûáîð øàãîâûõ ìíîæèòåëåé � k ;
(iv) îïèñàíèå ìíîæåñòâà X è ðåàëèçàöèÿ îïåðàöèè ïðîåêòèðîâàíèÿ � X ( ) ;
(v) âîçìîæíûå ìîäèôèêàöèè áàçîâîãî àëãîðèòìà.
Ðàññìîòðèì êðàòêî âîïðîñû (i)–(v).
(i) Êàê ïðàâèëî, àëãîðèòìè÷åñêîå âåðîÿòíîñòíîå ïðîñòðàíñòâî ( , , )� �� �P
ñòðîèòñÿ êàê ñ÷åòíîå ïðîèçâåäåíèå êîïèé èñõîäíîãî âåðîÿòíîñòíîãî ïðîñòðàí-
ñòâà çàäà÷è ( , , )� � P è òî÷êè x k ( )� ðàññìàòðèâàþòñÿ êàê ôóíêöèè îò � ��.
Åñëè, êðîìå íàáëþäåíèé ñòîõàñòè÷åñêèõ ïàðàìåòðîâ çàäà÷è, àëãîðèòì âêëþ÷àåò
äðóãèå ñòîõàñòè÷åñêèå ýëåìåíòû (òèïà ðàíäîìèçàöèè ïîèñêà), òî îíè òàêæå
äîëæíû áûòü âêëþ÷åíû â êîíñòðóêöèþ ïðîñòðàíñòâà ( , , )� �� �P .
(ii)  îáùåì ñëó÷àå íàïðàâëåíèÿ �( )k ÿâëÿþòñÿ îöåíêàìè ñóáãðàäèåíòîâ
ôóíêöèè F x( ) â òî÷êå x k è äîëæíû óäîâëåòâîðÿòü óñëîâèþ E k x x k{ }�( )| , ,0
� �
� � �a F x bk
k k( ) .
Ðàññìîòðèì íàèáîëåå âàæíûå òèïè÷íûå ïðèìåðû âû÷èñëåíèÿ SQG.
Ïðèìåð 1. Îïòèìèçàöèÿ ìåòîäîì Ìîíòå-Êàðëî. Ðàçëè÷íûå ïðàêòè÷åñêèå
ïðîáëåìû çà÷àñòóþ íàñòîëüêî ñëîæíû, ÷òî äëÿ òîãî ÷òîáû îïðåäåëèòü, êàê âû-
áîð ïåðåìåííîé x âëèÿåò íà ñèñòåìó â öåëîì, ìîæíî èñïîëüçîâàòü èñêëþ÷èòåëü-
íî ìîäåëèðîâàíèå ìåòîäîì Ìîíòå-Êàðëî [1, 11–15]. Ëþáîå ïîäîáíîå ìîäåëèðî-
âàíèå ìîæíî ðàññìàòðèâàòü êàê íàáëþäåíèå «ñðåäû» � èç ïðîñòðàíñòâà îáðàç-
öîâ �. Äëÿ ïðîñòîòû èçëîæåíèÿ ïðåäïîëîæèì, ÷òî èìååòñÿ òîëüêî îäíî
çíà÷åíèå f x( , )� ïðè ìîäåëèðîâàíèÿ � äëÿ äàííîãî x. Ïðîáëåìà ñîñòîèò â ìèíè-
ìèçàöèè îæèäàåìîé ïðîèçâîäèòåëüíîñòè (ñòîèìîñòè, ðèñêà, ïðèáûëè, «ðàññòîÿ-
íèÿ» îò çàäàííîé öåëè è äð.):
F x Ef x( ) ( , ).� �
Ýòî òèïè÷íàÿ çàäà÷à ñòîõàñòè÷åñêîé îïòèìèçàöèè. Òî÷íûå çíà÷åíèÿ F x( )
íåèçâåñòíû. Äîñòóïíà òîëüêî èíôîðìàöèÿ î òîì, ÷òî ëþáîå òåêóùåå ðåøåíèå x k
è èñïîëíÿåìàÿ ìîäåëü � äàþò � �( ) ( , )k f x k� , äëÿ êîòîðîé óäîâëåòâîðÿåòñÿ
óñëîâèå (4) ïðè a k( )
0. Âåêòîð �( )k ìîæíî âû÷èñëèòü ñ ïîìîùüþ ñòàíäàðòíîé
ïðîöåäóðû ñòîõàñòè÷åñêîé àïðîêñèìàöèè: à) íà ëþáîì øàãå k äëÿ çàäàííîãî x k
ìîäåëèðóþòñÿ ñëó÷àéíûå âûõîäû f x k k( , )� 0 , … , f x ek
k
j k j( , ),� � � ,
j n�1, ,� , ãäå � k
je — ïîëîæèòåëüíîå ïðèðàùåíèå â íàïðàâëåíèè e j j-é
êîîðäèíàòíîé îñè; á) âû÷èñëÿþòñÿ
�( )k
k
j
n
� �
�
� 1
1
[ ( , ) ( , )] ., ,f x e f x ek
k
j k j k k j� �� � � 0
(7)
Âåëè÷èíû � �k k n, ,, ...,0 íå îáÿçàòåëüíî íåçàâèñèìû: ìîæíî èñïîëüçîâàòü
îäèí ðåçóëüòàò ìîäåëèðîâàíèÿ � k íà êàæäîì øàãå k: � � �k k n k, ,0 � � �� . Âà-
ðèàöèÿ òàêîãî ìåòîäà ïîëó÷åíèÿ îöåíêè SQG ñõîäèòñÿ ê íóëþ ïðè k � �, òîãäà
êàê äëÿ íåçàâèñèìûõ ìîäåëåé îíà ñòðåìèòñÿ ê áåñêîíå÷íîñòè. Ïîñêîëüêó
E k x k[ ( )| ]� � � �
k
j
n
k
k
j k jF x e F x e�
�
� �1
1
[ ( ) ( )] , òî äëÿ íåïðåðûâíî äèôôåðåíöè-
6 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
ðóåìîé F ( ) èìååì
E k x F x C kk
x
k
k[ ( )| ] ( ) ( ) ,� � � � (8)
ãäå | | ( )| |C k � � �const äëÿ âñåõ x k èç îãðàíè÷åííîãî ìíîæåñòâà X .
Ïðèìåð 2. Îïòèìèçàöèÿ ïîñðåäñòâîì ñëó÷àéíîãî ïîèñêà. Ïðåäïîëîæèì,
÷òî F x( ) ìîæíî íåïîñðåäñòâåííî îöåíèòü, íî ýòî òðåáóåò ìíîãî âðåìåíè, ïî-
ñêîëüêó F x( ) îïðåäåëÿåò ðåøåíèå äèôôåðåíöèàëüíîãî óðàâíåíèÿ èëè ðåøåíèå
äðóãèõ çàäà÷ îïòèìèçàöèè. ×èñòî ýìïèðè÷åñêèé ìåòîä (ñî ñëó÷àéíûìè çíà÷åíè-
ÿìè x Xk� �1 , F x F xk k( ) ( )� �1 è ò.ä.) ìîæåò çàíÿòü ìíîãî âðåìåíè, ïîñêîëüêó
âåðîÿòíîñòü ïîïàñòü â ïðîèçâîëüíîå ïîäïðîñòðàíñòâî â íåîòðèöàòåëüíîì îðòàí-
òå n-ìåðíîãî åâêëèäîâîãî ïðîñòðàíñòâà ðàâíà 2�n . Îáû÷íîå êîíå÷íî-ðàçíîñòíîå
ïðèáëèæåíèå
F x F x e F x ex
k
k
j
n
k
k
j k j( ) [ ( ) ( )]� � ��
�
� �1
1
(9)
òðåáóåò n�1 ïðèáëèæåíèå F ( ) è, ñëåäîâàòåëüíî, ìîæåò îêàçàòüñÿ òðóäîåì-
êèì. Ìåòîä SQG
� � �( ) / [ ( ) ( )] ,k F x F x
k
k
k
k k k� � ��3 2 1� � (10)
ãäå � k èìååò íåçàâèñèìûå, ðàâíîìåðíî ðàñïðåäåëåííûå íà [ , ]�1 1 êîìïîíåíòû,
òðåáóåò òîëüêî äâóõ îöåíîê F x( ) : â òî÷êàõ x k è x k
k
k� � � íåçàâèñèìî îò
ðàçìåðíîñòè n. Ëåãêî âèäåòü, ÷òî âåêòîð (10) óäîâëåòâîðÿåò (8) äëÿ íåïðåðûâ-
íî äèôôåðåíöèðóåìîé F x( ) .
Ïðèìåð 3. Êîíå÷íî-ðàçíîñòíûå àïïðîêñèìàöèè ñóáãðàäèåíòîâ. Êîíå÷-
íî-ðàçíîñòíûå àïïðîêñèìàöèè (7), (9), (10) íåëüçÿ èñïîëüçîâàòü äëÿ íåäèôôåðåí-
öèðóåìûõ ôóíêöèé, ò.å. äëÿ ñëó÷àéíûõ äâóõýòàïíûõ è ìèíèìàêñíûõ çàäà÷. Ìå-
òîä SQG ïîçâîëÿåò ïîëó÷èòü ïðîñòûå êîíå÷íî-ðàçíîñòíûå àïïðîêñèìàöèè äëÿ
çàäà÷è íåãëàäêîé îïòèìèçàöèè â îáùåì ñëó÷àå (è äåòåðìèíèðîâàííîé, è ñòîõàñ-
òè÷åñêîé). Íåáîëüøàÿ ðàíäîìèçàöèÿ (7), (9), (10) çà ñ÷åò çàìåíû äàííîé òî÷êè x k
ñëó÷àéíîé òî÷êîé x xk k k� � � , ãäå ñëó÷àéíûé âåêòîð � k èìååò ïëîòíîñòü è
| | | |� k � 0 ñ âåðîÿòíîñòüþ 1 ãàðàíòèðóåò èõ ñõîäèìîñòü äëÿ ëîêàëüíî-ëèïøèöå-
âûõ è ðàçðûâíûõ ôóíêöèé [1, 11–15].
Ïðåäïîëîæèì, ÷òî F x( ) — ëîêàëüíî èíòåãðèðóåìàÿ (âîçìîæíî, ðàçðûâíàÿ)
ôóíêöèÿ è âåêòîð � k èìååò äîñòàòî÷íî ãëàäêóþ ïëîòíîñòü, ñêîíöåíòðèðîâàííóþ
íà îãðàíè÷åííîì ìíîæåñòâå. Òîãäà
� � �( ) / [ ( ) ( )] ,k F x F x
k
k
k
k k k� � ��3 2 1� � (11)
� � � � �( ) / [ ( , ) ( , )],k f x f x
k
k
k
k k k k k� � ��3 2 1 1 0� � (12)
— SQG ôóíêöèè F k x EF x k( , ) ( )� � � èëè ñòîõàñòè÷åñêîãî ñãëàæåííîãî êâà-
çèãðàäèåíòà (SMQG) F x( ), êîòîðûé (â íåêîòîðîì ñìûñëå) ñõîäèòñÿ ê F x( ) è
äëÿ êîòîðîãî F k xx ( , ) ñõîäÿòñÿ [11,12] ê ìíîæåñòâó ñóáãðàäèåíòîâ F xx ( ) .
Èìååì
E k x F k x C kk
x
k
k[ ( )| ] ( , ) ( ) ,� � � �
ãäå | | ( )| |C k � � �const äëÿ âñåõ x k èç îãðàíè÷åííîãî ìíîæåñòâà. Àíàëèç ñõîäè-
ìîñòè x k áàçèðóåòñÿ íà îáùèõ èäåÿõ íåñòàöèîíàðíîé îïòèìèçàöèè (ñì. ïðè-
ìåð 5). Âàæíûì ïðåèìóùåñòâîì äàííîãî ïîäõîäà ÿâëÿåòñÿ òî, ÷òî F k x( , )
ñãëàæèâàåò ÷àñòûå îñöèëëÿöèè F x( ) è îòðàæàåò îáùèé òðåíä F x( ), ÷òî ïîçâî-
ëÿåò { }x k îáîéòè íåíóæíûå ëîêàëüíûå ðåøåíèÿ. Äîñòàòî÷íî «áîëüøèå» � k
óñêîðÿþò ïðîöåäóðó ïåðåõîäà ê âàæíûì (ò.å. ãëîáàëüíûì) ðåøåíèÿì.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 7
Ïðèìåð 4. Ãëîáàëüíàÿ îïòèìèçàöèÿ. Ïðîñòåéøèé ñïîñîá äîáàâèòü
«óñòîé÷èâîñòè» â ïðîöåäóðó ãðàäèåíòíîãî òèïà äëÿ èñêëþ÷åíèÿ ëîêàëüíûõ ðå-
øåíèé — âîçìóòèòü ãðàäèåíò F xx
k( ) ñ ïîìîùüþ ñëó÷àéíîãî âåêòîðà � k , ò.å. ðàñ-
ñìàòðèâàòü � �( ) ( )k F xx
k k� � , E k� � 0. Ñïåöèàëüíûé âûáîð � k ñîîòâåòñòâóåò
ìåòîäó èìèòàöèè îòæèãà (äëÿ îáó÷åíèÿ íåéðîííûõ ñåòåé). Åùå îäèí âîçìîæíûé
ñïîñîá èçáàâèòüñÿ îò ëîêàëüíûõ ðåøåíèé — ïîñëåäîâàòåëüíàÿ ãëàäêàÿ àïïðîê-
ñèìàöèÿ [12]. Äðóãèå ìåòîäû ãëîáàëüíîé îïòèìèçàöèè ðàññìîòðåíû â [13].
Ïðèìåð 5. Íåñòàöèîíàðíàÿ îïòèìèçàöèÿ. Ìíîãèå ïðèêëàäíûå ïðîáëåìû,
[1, 12, 14], êàê è â ïðèìåðå 3, ìîæíî ñôîðìóëèðîâàòü êàê çàäà÷è îïòèìèçàöèè
ñ öåëåâîé ôóíêöèåé F k x0 ( , ) è îãðàíè÷åíèÿìè F k xi ( , ) , ìåíÿþùèìèñÿ íà êàæäîì
øàãå k � 0 1, ,�  ýòîì ñëó÷àå SQG-ìåòîä íà øàãå k ïðîèçâîäèò îäèí øàã ìèíè-
ìèçàöèè F k x0 ( , ) , èñïîëüçóÿ îöåíêè F k xix ( , ), i m� 0, ,� . Ïðè F k x F xi i( , ) ( ),�
k � �, ïîëó÷àåì îñîáûé ñëó÷àé. Ñëåäîâàòåëüíî, ìîæíî ïîêàçàòü, ÷òî
F k x F xk
0 0( , ) min ( )� .  îáùåì ñëó÷àå ìîæíî îïðåäåëèòü øèðîêèé ñïåêòð ñè-
òóàöèé, äëÿ êîòîðûõ | ( , ) min ( , )|F k x F x kk
0 0 0� � , k � �.
(iii) Ðàññìîòðèì óñëîâèÿ ñõîäèìîñòè àëãîðèòìà (6) è âûáîð øàãîâûõ ìíî-
æèòåëåé � k . Ìåòîäû SQG ãåíåðèðóþò ñëó÷àéíûå ïîñëåäîâàòåëüíîñòè àïïðîêñè-
ìèðóþùèõ ðåøåíèé { }x k ( )� è çíà÷åíèé { }F x k( ( ))� , çàâèñÿùèõ îò �, èç ñîîòâå-
òñòâóþùèì îáðàçîì îïðåäåëåííîãî âåðîÿòíîñòíîãî ïðîñòðàíñòâà. Áîëåå âàæíî
ñ ïðàêòè÷åñêîé òî÷êè çðåíèÿ òî, ÷òî x k ( )� (èëè F x k( )) ñõîäÿòñÿ ê ìíîæåñòâó ëî-
êàëüíûõ ðåøåíèé X * (F F X* * *( )� ) äëÿ ïî÷òè âñåõ � (ñ âåðîÿòíîñòüþ 1). Ñõî-
äèìîñòü ñ âåðîÿòíîñòüþ 1 ïîñëåäîâàòåëüíîñòè { }F x k( ) ê ìíîæåñòâó F * äîêàçàíà
äëÿ íåãëàäêèõ (îáîáùåííî-äèôôåðåíöèðóåìûõ, ëîêàëüíî-ëèïøèöåâûõ è ÷åòíûõ
ïîëóíåïðåðûâíûõ) ôóíêöèé, êîòîðûå ïîêðûâàþò øèðîêèé ñïåêòð ïðèëîæåíèé.
Ïðåäåëüíûå òî÷êè { }x k ( )� äëÿ êàæäîãî � ôîðìèðóþò ñâÿçíîå ìíîæåñòâî èç X * .
Ñõîäèìîñòü x Xk ( ) *� � ñ âåðîÿòíîñòüþ 1 èìååò ìåñòî â óñëîâèÿõ «âûïóêëîñ-
òè». Ãëîáàëüíàÿ ñõîäèìîñòü â îáùèõ ñëó÷àÿõ òðåáóåò ñïåöèàëüíûõ ñòîõàñòè÷åñ-
êèõ ìåõàíèçìîâ [1, 12, 14]. Âî âñåõ ñëó÷àÿõ äëÿ ñõîäèìîñòè íåîáõîäèì ñïåöèàëü-
íûé âûáîð ðàçìåðà øàãà � k . Èç-çà ñëîæíîñòè çàäà÷ � k íåëüçÿ âûáðàòü ñïîñîá, ãà-
ðàíòèðóþùèé ìîíîòîííîå óáûâàíèå F x F x k( ): ( )�1 � �F x kk( ), , ,0 1 �
Îòíîñèòåëüíî ãèáêèå òðåáîâàíèÿ, êîòîðûå ÷àñòî ãàðàíòèðóþò ñõîäèìîñòü ïîñëå-
äîâàòåëüíîñòè { }F x k( ) ñ âåðîÿòíîñòüþ 1, ñëåäóþùèå:
� �k k
k
� � �
�
�
0
0
, ,
E b k k
k
k k
�
�
� � �
0
2 2[ | | ( )| | | | ( )| | ] .� � � (13)
Ðàññìîòðèì, íàïðèìåð, (7) ñ çàâèñèìûìè íàáëþäåíèÿìè � k ,0 �
� � �� �k k,1
� è f x( , )� � � �const . Íà ïðàêòèêå âñåãäà ìîæíî ïðåäïîëîæèòü,
÷òî | | ( )| |� k � � �const . Òîãäà óñëîâèå (13) óäîâëåòâîðÿåòñÿ äëÿ � k C k� �/ ( ),1
� k D k� �/ ( )1 ñ êîíñòàíòàìè C D, . Îáû÷íî C D, êîððåêòèðóþòñÿ [1, 12] íà êàæ-
äîì øàãå ñ ó÷åòîì èñòîðèè Gk , íàïðèìåð èñïîëüçîâàíèåì çíà÷åíèé
F k k f x s s
s
k
( ) ( ) ( , )� � �
�
1 1
0
� . Ðàçëè÷íûå àäàïòèâíûå SQG-ìåòîäû ñ àäàïòèâíû-
ìè êîððåêòèðîâêàìè � k êàê ôóíêöèÿìè Gk èçó÷àëèñü â [12, 16]. Èäåÿ çàêëþ÷àåò-
8 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
ñÿ â òîì, ÷òîáû âûáðàòü � k òàêèì îáðàçîì, ÷òîáû ìèíèìèçèðîâàòü
E F x k xk k[ ( ( ))| ]� �� . Ýòî âåäåò ê àäàïòèâíûì ìîäèôèêàöèÿì � k , ïðîïîðöèî-
íàëüíûì ñêàëÿðíîìó ïðîèçâåäåíèþ � � �� �( ), ( )k k1 . Âàæíûé âîïðîñ îïðåäåëå-
íèÿ ìîìåíòà îñòàíîâêè è äîâåðèòåëüíûõ èíòåðâàëîâ äëÿ àïïðîêñèìàöèè
ðåøåíèé òàêæå èçó÷àëñÿ â [12].
SQG-ìåòîäû òðåáóþò ñîîòâåòñòâóþùåé òåõíèêè äëÿ äîêàçàòåëüñòâà ñõîäè-
ìîñòè. Îíè ìîãóò ðàññìàòðèâàòüñÿ êàê ñëó÷àéíûé ìåòîä Ëÿïóíîâà äëÿ àíàëèçà
ñòàáèëüíîñòè íåãëàäêèõ äèíàìè÷åñêèõ ñèñòåì [1, 14, 15, 17]. Îñíîâíàÿ èäåÿ —
ïîêàçàòü, ÷òî { }x k ( )� äëÿ âñåõ � îñòàâëÿåò îêðåñòíîñòü òî÷åê, êîòîðûå íå ïðè-
íàäëåæàò X * , ñ óáûâàþùèìè çíà÷åíèÿìè íåêîòîðûõ (â îáùåì ñëó÷àå
íåãëàäêèõ) ôóíêöèé Ëÿïóíîâà.
(iv) Îïèñûâàåòñÿ ìíîæåñòâî X è ðåàëèçóåòñÿ îïåðàöèÿ ïðîåêòèðîâàíèÿ
� X ( ) . Ñ òåîðåòè÷åñêîé òî÷êè çðåíèÿ îãðàíè÷åíèå x X� , ãäå X x f xi� �{ | ( ) ,0
i m x j nj� � �1 2 0 1, , , ; , , ,� � }, óäîáíî ïðåäñòàâëÿòü îäíèì íåðàâåíñòâîì
�( ) max max ( ), max ( )x f x xi i j j� � �{ } 0. Åñëè ìíîæåñòâî X ïðîñòîå (íàïðèìåð,
ïàðàëëåëåïèïåä èëè ñèìïëåêñ), òî ïðîåêòèðîâàíèå íà X íå âûçûâàåò çàòðóäíå-
íèé. Åñëè X çàäàåòñÿ ëèíåéíûìè îãðàíè÷åíèÿìè, òî ïðîåêöèÿ � X
ky( ) âåêòîðà
y x sk k
k
k� � � íà ìíîæåñòâî X ìîæåò áûòü íàéäåíà êàê ðåøåíèå çàäà÷è êâàäðà-
òè÷íîãî ïðîãðàììèðîâàíèÿ: | | | | miny xk
x X� � �
2 , êîòîðóþ ìîæíî ðåøèòü ñ ïî-
ìîùüþ ñòàíäàðòíîãî ìàòåìàòè÷åñêîãî îáåñïå÷åíèÿ. Êðîìå òîãî, ïðåäûäóùóþ òî÷êó
x k ìîæíî âçÿòü êàê íà÷àëüíîå ïðèáëèæåíèå äëÿ ïðîöåäóðû êâàäðàòè÷íîãî ïðîãðàì-
ìèðîâàíèÿ. Åñòü è äðóãèå âîçìîæíîñòè ó÷èòûâàòü ëèíåéíûå îãðàíè÷åíèÿ.
(v) Ðàññìîòðèì âîçìîæíûå ìîäèôèêàöèè áàçîâîãî àëãîðèòìà. ×òî êàñàåòñÿ
ìîäèôèêàöèé áàçîâîé ïðîöåäóðû (6), òî ïðåæäå âñåãî îòìåòèì ìåòîä Íåìèðîâ-
ñêîãî–Þäèíà [18] äëÿ ðåøåíèÿ âûïóêëîé çàäà÷è (1). Ìåòîä ïðîèçâîäèò äâå ïî-
ñëåäîâàòåëüíîñòè { }x xk k, , ãäå x k ãåíåðèðóåòñÿ ïðîöåäóðîé (6), à
x x xk
k
k
k
k� � ��
�
�( )1 1
1
1 , x x0 0� , � �k k i
i
k
k� �
�
�
� �
1 1
1
1
1 2/ , , ,� (14)
Ïðè ýòîì äëÿ ëþáîãî k è äåòåðìèíèðîâàííûõ øàãîâ � k èìåþò ìåñòî îöåíêè
E F x F x xk
i
i
k
i
i
� � �( ) | | | |* *
/� � � �
�
�
�
�
�
�
�
�
� �
1
2
0 2 2
1
ñonst
1
k
.
Ïîñëåäîâàòåëüíîñòü { }x k ëó÷øå ñõîäèòñÿ ê èñêîìîìó ìèíèìóìó, ÷åì { }x k :
â ìåòîäå (6), (14) ìîæíî èñïîëüçîâàòü áîëåå êðóïíûå øàãè � k , íàïðèìåð
� k k� �const / 1, ÷åì â íà÷àëüíîì ìåòîäå (6), ãäå îáû÷íî � k k� const / .
1.2. Îïåðàöèè óñðåäíåíèÿ â ìåòîäàõ ñòîõàñòè÷åñêîãî ïðîãðàììèðîâà-
íèÿ. Ìåòîäû (6) è ìíîãèå äðóãèå SQG-ìåòîäû èìåþò òó æå îñíîâíóþ ñòðóêòóðó, ÷òî
è èõ äåòåðìèíèðîâàííûå àíàëîãè. Ñëåäóþùèé ìåòîä ñòîõàñòè÷åñêîé ëèíåàðèçàöèè
ðàñïîëàãàåò ñóùåñòâåííî íîâîé âîçìîæíîñòüþ. Ðàññìîòðèì ñíîâà ìèíèìèçàöèþ
F x x X( ), � . Ïðåäïîëîæèì ÷òî ôóíêöèÿ F x( ) íåïðåðûâíî äèôôåðåíöèðóåìà, à X —
âûïóêëûé êîìïàêò. Ýòîò ìåòîä çàäàåòñÿ èòåðàòèâíî ñëåäóþùèì îáðàçîì:
x x x xk k
k
k k
k
� � � � � �1 0 1� �( � ), , (15)
� ( ) � ( ) ( ( ) � ( )),� �
� �k k k kk� � � � �1 1 (16)
� � ( ), : ,x k x x Xk � � � �argmin{ }� k � 0 1, , ...,
ãäå x 0 — ñëó÷àéíàÿ íà÷àëüíàÿ àïïðîêñèìàöèÿ èç X .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 9
Èçâåñòíûé äåòåðìèíèðîâàííûé àíàëîã èìååò
k
0, �( ) ( )k F xx
k
. Ïðîñ-
òîé ïðèìåð ïîêàçûâàåò, ÷òî áåç îïåðàöèè óñðåäíåíèÿ (16), ò.å.
k
0, ìåòîä (15)
íå ñõîäèòñÿ. Äëÿ ñõîäèìîñòè íóæíî äîáàâèòü ê (13) óñëîâèå
�
k k k
k
k
E� � � �
�
�
0 0
0
2, / , . (17)
Ìåòîä (15) îáû÷íî èñïîëüçóåòñÿ, êîãäà X îïðåäåëÿåòñÿ ñ ïîìîùüþ ëèíåéíûõ
îãðàíè÷åíèé.  ýòîì ñëó÷àå ëèíåéíàÿ ïîäçàäà÷à ðåøàåòñÿ íà êàæäîì øàãå k.  îò-
ëè÷èå îò ýòîãî ñëó÷àÿ ìåòîä ïðîåêöèé (4) òðåáóåò ðåøåíèÿ êâàäðàòè÷íîé ïîäçà-
äà÷è. Íóæíî ó÷åñòü, ÷òî â îáîèõ ñëó÷àÿõ íà êàæäîì øàãå â öåëåâîé ôóíêöèè è
ôóíêöèÿõ îãðàíè÷åíèé âîçíèêàþò òîëüêî íåáîëüøèå âîçìóùåíèÿ. Ñëåäîâàòåëü-
íî, íåîáõîäèìû íåáîëüøèå ïîïðàâêè ê ðåøåíèÿì ïðåäûäóùåé çàäà÷è. Ýòîò ìå-
òîä ìîæíî ìîäèôèöèðîâàòü äëÿ íåäèôôåðåíöèðóåìûõ ôóíêöèé è îãðàíè÷åíèé,
â ÷àñòíîñòè, èñïîëüçîâàòü SMQG, êàê â (11), (12) (ñòîõàñòè÷åñêèå êîíå÷íî-ðàç-
íîñòíûå àïïðîêñèìàöèè), äëÿ ëîêàëüíî-ëèïøèöåâûõ ôóíêöèé.
Èñïîëüçîâàíèå îïåðàöèè óñðåäíåíèÿ àíàëîãè÷íî (16) ÷àñòî ðåøàþùåå äëÿ
ñõîäèìîñòè ìåòîäîâ SQG, èõ ýôôåêòèâíîñòè è óñòîé÷èâîñòè. Ýòè îïåðàöèè òàê-
æå ïðèìåíÿþòñÿ â îòíîøåíèè �( )k â (6), ãäå âìåñòî �( )k èñïîëüçóåòñÿ âåêòîð
� ( )� k òàêîé, ÷òî äëÿ k � 0 1, ,�
� ( ) � ( ) [ ( ) � ( )],� �
� �k k k kk� � � � �1 1 � ( ) ( ).� �0 0�
Áëàãîäàðÿ èì ïðîöåäóðà (6) ïðèîáðåòàåò ñâîéñòâà èíåðöèîííîñòè â äîïîëíå-
íèå ê åñòåñòâåííûì ãëîáàëüíûì ñâîéñòâàì, îïðåäåëÿåìûì ñëó÷àéíûìè ìåõà-
íèçìàìè. Óñðåäíåíèå òàêæå ìîæåò óìåíüøèòü âàðèàöèþ SQG.
1.3. Ïðåäåëüíîå ïîâåäåíèå ïðîöåññîâ ñòîõàñòè÷åñêîãî ïðîãðàììèðîâà-
íèÿ. Âàæíîå çíà÷åíèå ïðè îïðåäåëåíèè äîâåðèòåëüíûõ îáëàñòåé äëÿ íåèçâåñ-
òíûõ ïàðàìåòðîâ èìååò íàõîæäåíèå àñèìïòîòè÷åñêèõ ðàñïðåäåëåíèé èòåðàòèâ-
íûõ ïîñëåäîâàòåëüíîñòåé ìåòîäà ñòîõàñòè÷åñêèõ êâàçèãðàäèåíòîâ è äîêàçà-
òåëüñòâî ñëàáîé ñõîäèìîñòè ñëó÷àéíûõ ïðîöåññîâ, ïîðîæäåííûõ ýòèìè
ïîñëåäîâàòåëüíîñòÿìè.  ÷àñòíîñòè, â [19] äîêàçàíà ñëàáàÿ ñõîäèìîñòü ïîñëåäî-
âàòåëüíîñòè âåðîÿòíîñòíûõ ìåð, ïîðîæäåííûõ ñëó÷àéíûìè ïðîöåññàìè
x s x xn
s t� �1 2/ ( ) , 1 1� � � � �n s ne n net T[ ] ,
ê ìåðå, èíäóöèðîâàííîé ñëó÷àéíûì ïðîöåññîì õ t( ), ÿâëÿþùèìñÿ ðåøåíèåì
ñòîõàñòè÷åñêîãî äèôôåðåíöèàëüíîãî óðàâíåíèÿ
dx t Ax t dt Ddw t( ) ( ( ) ) ( )� � �� , (18)
D — ïîëîæèòåëüíî-îïðåäåëåííàÿ ìàòðèöà, A — íåâûðîæäåííàÿ ìàòðèöà.
Èñïîëüçîâàâ ðàñïðåäåëåíèå ìàêñèìóìà äëÿ ïðîöåññà õ t( ) , ÿâëÿþùåãîñÿ ðå-
øåíèåì óðàâíåíèÿ (18), ìîæíî ïîñòðîèòü è òðåáóåìóþ äîâåðèòåëüíóþ îáëàñòü
äëÿ íåèçâåñòíîãî ïàðàìåòðà.
2. ÌÈÍÈÌÀÊÑÍÛÅ ÇÀÄÀ×È ÑÒÎÕÀÑÒÈ×ÅÑÊÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß
2.1. SQG-ìåòîäû. Äàííûå ìåòîäû ïðèìåíÿþòñÿ è ê äåòåðìèíèðîâàííûì,
è ê ñòîõàñòè÷åñêèì ìèíèìàêñíûì (SMM) çàäà÷àì. SMM-çàäà÷è âêëþ÷àþò íå-
ãëàäêèå âûáîðî÷íûå (ñëó÷àéíûå) öåëåâûå ôóíêöèè. Âàæíûé êëàññ SMM-çà-
äà÷, êîòîðûé ïðèâåäåí â [1, 14], òðåáóåò ìèíèìèçàöèè ìàòåìàòè÷åñêîãî îæè-
äàíèÿ
F x E g x y x Xy Y( ) max ( , , ), ,� �� � (19)
10 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
ãäå f x g x yy Y( , ) max ( , , )� �� � — âûáîðî÷íàÿ (ñëó÷àéíàÿ) öåëåâàÿ ôóíêöèÿ,
X R n� , Y R r� è � — ýëåìåíò âåðîÿòíîñòíîãî ïðîñòðàíñòâà ( , , )� � P . Åñëè
� ñîäåðæèò åäèíñòâåííóþ òî÷êó, òî ìèíèìèçàöèÿ (19) ñîîòâåòñòâóåò ñòàí-
äàðòíîé äåòåðìèíèðîâàííîé ìèíèìàêñíîé çàäà÷å. Ïîìèìî äåòåðìèíèðîâàí-
íûõ îãðàíè÷åíèé òèïà x X� , çàäà÷à (19) ìîæåò èìåòü îáùèå îãðàíè÷åíèÿ, çà-
äàííûå â òåðìèíàõ ôóíêöèé ìàòåìàòè÷åñêîãî îæèäàíèÿ, íåêîòîðûå èç íèõ
ìîãóò èìåòü òó æå ñòðóêòóðó, ÷òî è ôóíêöèÿ ìàòåìàòè÷åñêîãî îæèäàíèÿ F x( )
â (19). Ìíîæåñòâî Y ìîæåò çàâèñåòü îò ( , )x � , êàê è â äâóõýòàïíîì ñòîõàñòè-
÷åñêîì ïðîãðàììèðîâàíèè. Ôóíêöèè f x( , )� â (19) ÷àñòî èìåþò è áîëåå îá-
ùóþ ñòðóêòóðó, íàïðèìåð â çàäà÷àõ óïðàâëåíèÿ ðèñêàìè â ñëó÷àå êàòàñòðîôè-
÷åñêèõ ñîáûòèé [20]. Ïðåæäå âñåãî âûáîðî÷íàÿ ôóíêöèÿ f ( , ) � — ýòî íåÿâ-
íûì îáðàçîì çàäàííàÿ íåãëàäêàÿ ôóíêöèÿ äàæå äëÿ ëèíåéíîé g y( , , ) � .
Ïîýòîìó âñå îáùèå ìåòîäû SQG, âûâåäåííûå äëÿ îáùåé çàäà÷è íåãëàäêîé
îïòèìèçàöèè (íàïðèìåð, ñòîõàñòè÷åñêèõ êîíå÷íî-ðàçíîñòíûõ àïïðîêñèìàöèé),
ïðèìåíèìû ê çàäà÷å (1). Ñïåöèàëüíûå SQG-ìåòîäû èñïîëüçóþò ñâîéñòâà
ñòðóêòóðû öåëåâîé ôóíêöèè f x( , )� ñëåäóþùèì îáðàçîì.
Ïóñòü y x( , )� — ðåøåíèå âíóòðåííåé çàäà÷è ìàêñèìèçàöèè â (19), ò.å.
f x g x y x( , ) ( , ( , ), )� � �� . ×àñòî ìîæíî ïîêàçàòü, ÷òî g y( , , ) � — ëåãêî àíàëèòè-
÷åñêè âû÷èñëÿåìàÿ GD (îáîáùåííî-äèôôåðåíöèðóåìàÿ) ôóíêöèÿ; ñëåäîâàòåëü-
íî, f g yy Y( , ) max ( , , ) � �� � — GD-ôóíêöèÿ ñ ñóáãðàäèåíòîì
f g y xx x( , ) ( , ( , ), ) � � � � , (20)
ò.å. SQG-ôóíêöèè F x( ) . Íàïðèìåð, åñëè ôóíêöèÿ g y( , , ) � âûïóêëà, òî
f ( , ) � òàêæå âûïóêëà è (20) îïðåäåëÿåò åå ñóáãðàäèåíò. Âåêòîð f xx ( , )� èëè
åãî àïïðîêñèìàöèè ìîæíî èñïîëüçîâàòü â ðàçíûõ SQG-ìåòîäàõ. Íàïðèìåð,
åñëè f ( , ) � — GD-ôóíêöèÿ, òî ìåòîä SQG-ïðîåêöèé îïðåäåëÿåòñÿ êàê
x x f xk
X
k
k x
k k� � �1 � � �[ ( , )], k � 01, , ,� (21)
ãäå x xk k k� �
è
0 1, ,� — íåçàâèñèìûå ñëó÷àéíûå âåêòîðû ñ ïëîòíîñòÿ-
ìè, | | | |
k � 0,
k � 0 ïðè k � � ñ âåðîÿòíîñòüþ 1 è � �0 1, ,� — íåçàâèñèìûå
íàáëþäåíèÿ �. Âåêòîð f xx
k k( , )� — ñòîõàñòè÷åñêèé ñëàáûé êâàçèãðàäèåíò
F x( ) ïðè x x k� . Åñëè � �k k
k
� � �
�
�
0
0
, ñ âåðîÿòíîñòüþ 1, E
k
k
�
�
� �
0
2� è X —
âûïóêëûé êîìïàêò, òî { }F x k( ) ñõîäèòñÿ ñ âåðîÿòíîñòüþ 1 è ïðåäåëüíûå òî÷êè
ñëó÷àéíîé ïîñëåäîâàòåëüíîñòè { }x k ñ âåðîÿòíîñòüþ 1 ïðèíàäëåæàò ñâÿçíîìó
ìíîæåñòâó ëîêàëüíûõ ðåøåíèé [12, 13]. Ñõîäèìîñòü (21) äëÿ
k
0 èìååò
ìåñòî äëÿ òàê íàçûâàåìûõ [1, 14, 15] ñëàáî âûïóêëûõ ôóíêöèé F x( ) , ò.å. òà-
êèõ, ÷òî F y F x F x y x r x yx( ) ( ) ( ( ), ) ( , )� � � � , ãäå r x y x y( , )/| | | |� � 0, x z� ,
y z� . Äëÿ âûïóêëûõ f ( , ) � ïîñëåäîâàòåëüíîñòü { }x k ïðè
k
0 ñõîäèòñÿ
ñ âåðîÿòíîñòüþ 1 ê ìíîæåñòâó îïòèìàëüíûõ ðåøåíèé. Åñëè ôóíêöèÿ ðàñïðå-
äåëåíèÿ � ñêîíöåíòðèðîâàíà â òî÷êå, òî (19) ñâîäèòñÿ ê ñòàíäàðòíîé äåòåðìè-
íèðîâàííîé ìèíèìàêñíîé çàäà÷å è (21) ÿâëÿåòñÿ äëÿ íåå SQG-ïðîöåäóðîé.
Ïðèìåð 6. Ïëàíèðîâàíèå ïðîèçâîäñòâà â óñëîâèÿõ íåîïðåäåëåííîñòè.
 óñëîâèÿõ íåîïðåäåëåííîñòè áóäóùåãî ñïðîñà, öåí, êîýôôèöèåíòîâ ââîäà–âû-
âîäà, äîñòóïíûõ ðåñóðñîâ è ò.ä. âûáîð îáúåìà ïðîèçâîäñòâà x x� � 0 äëÿ ïðî-
ãíîçèðóåìîãî ñïðîñà � — çàäà÷à ïðèíÿòèÿ ðåøåíèé íàóäà÷ó. Ñòîèìîñòü f x( , )� ,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 11
ñâÿçàííàÿ ñ ïåðåîöåíêîé è íåäîîöåíêîé �, ÿâëÿåòñÿ, â ïðîñòåéøåì ñëó÷àå, ñëó-
÷àéíîé êóñî÷íî-ïîñòîÿííîé ëèíåéíîé ôóíêöèåé
f x x x( , ) max ( ), ( ) ,� � � � �� � �{ }
ãäå � — åäèíèöà ñòîèìîñòè, ñâÿçàííàÿ ñ èçëèøêîì åäèíèöû ïðîäóêöèè, à � —
ñ åå íåäîñòàòêîì. Çàäà÷à ñîñòîèò â íàõîæäåíèè çíà÷åíèÿ x, «îïòèìàëüíîãî»
â òîì ñìûñëå, ÷òî äëÿ âñåõ ïðåäñêàçóåìûõ çíà÷åíèé ñïðîñà � ôóíêöèè
x x� ( )� îïðåäåëÿåò îïòèìàëüíûé óðîâåíü ïðîèçâîäñòâà. Êðèòåðèé îæèäàå-
ìîé ñòîèìîñòè ïðèâîäèò ê ìèíèìèçàöèè
F x E x x( ) max ( ), ( )� � �{ }� � � � (22)
ïî îòíîøåíèþ ê x x� � 0 äëÿ çàäàííîãî âåðõíåãî ïðåäåëà x. Òàêóþ çàäà÷ó ñòî-
õàñòè÷åñêîé îïòèìèçàöèè ìîæíî ïåðåôîðìóëèðîâàòü êàê äâóõýòàïíóþ ìîäåëü
ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ, èçâåñòíóþ êàê çàäà÷à ðàçíîñ÷èêà ãàçåò.
Ôóíêöèÿ F x( ) â (22) âûïóêëà; ñëåäîâàòåëüíî, ìåòîä (21) ïðè
k
0 ñâîäèòñÿ
ê ñëåäóþùåìó:
x x k x kk k
k
� � � �1 0 0 1min max , ( ) , , , , ,{ { } }� � � (23)
ãäå � �( )k � , åñëè òåêóùèé óðîâåíü ïðîèçâîäñòâà x k ïðåâûøàåò íàáëþäàåìûé
ñïðîñ � k (x k k� � ), è � �( )k � � â ïðîòèâíîì ñëó÷àå. Ìåòîä (23) ìîæíî ðàñ-
ñìàòðèâàòü êàê àäàïòèâíóþ ïðîöåäóðó, êîòîðàÿ ìîæåò èçó÷àòü óðîâåíü îïòè-
ìàëüíîãî ïðîèçâîäñòâà ÷åðåç ïîñëåäîâàòåëüíûå ïðàâêè ê òåêóùèì çíà÷åíèÿì
x x0 1, ,� â çàâèñèìîñòè îò íàáëþäàåìîãî ñïðîñà � �0 1, ,� Îáðàòèì âíèìà-
íèå, ÷òî îïòèìàëüíîå ðåøåíèå (22) è áîëåå îáùèå SMM-çàäà÷è äàþò õàðàêòå-
ðèñòèêè êâàíòèëüíîãî òèïà äëÿ ðåøåíèé, ò.å. ìåðû ðèñêà CVaR [21]. Åñëè,
íàïðèìåð, ðàñïðåäåëåíèå � èìååò ïëîòíîñòü � � �, � � 0, òî îïòèìàëüíîå ðå-
øåíèå x, ìèíèìèçèðóþùåå (22), — ýòî êâàíòèëü, îïðåäåëåííûé êàê
Pr [ ] / ( )� � � �� � �x . Ñëåäîâàòåëüíî, ïðîöåññ (23) — ïðîöåäóðà îãðàíè÷åí-
íîé ïîñëåäîâàòåëüíîé îöåíêè [14]. Çàäà÷à (22) èëëþñòðèðóåò çíà÷èòåëüíîå
îòëè÷èå ìåæäó ìåòîäîì, ïîäðàçóìåâàþùèì ïðÿìûå âû÷èñëåíèÿ x( )� , è ïîä-
õîäîì, â êîòîðîì âìåñòî ïðîäóöèðîâàíèÿ òðèâèàëüíûõ îïòèìàëüíûõ ðåøåíèé
x( )� �� äëÿ ëþáîãî ñöåíàðèÿ � ïîëó÷àåì ðåøåíèå, îïòèìàëüíîå («óñòîé÷è-
âîå») äëÿ âñåõ âîçìîæíûõ �.
Ïðèìåð 7. Ñòîõàñòè÷åñêàÿ ìîäåëü ðàçìåùåíèÿ ïðîèçâîäñòâà. Ýòà ìî-
äåëü [14, 22] îáîáùàåò ïðèìåð 6 è èëëþñòðèðóåò âîçìîæíîå âëèÿíèå ïîâåäåíèÿ
îñíîâíûõ âåðîÿòíîñòíûõ ðàñïðåäåëåíèé. Ïðåäïîëîæèì, ÷òî ïîòðåáèòåëè æèâóò
â ðåãèîíå i è âûáèðàþò öåëåâîé ðåãèîí j ñ âåðîÿòíîñòüþ Pij
, ñâÿçàííîé ñî ñòîè-
ìîñòüþ ïóòåøåñòâèÿ ìåæäó òî÷êàìè ( , )i j è (èëè) äðóãèìè ôàêòîðàìè. Ïóñòü
ij —
ñëó÷àéíîå ÷èñëî ïîåçäîê ïîëüçîâàòåëåé èç i â j è � j — îáùåå ÷èñëî ïîëüçîâàòå-
ëåé, äîñòèãøèõ j: �
j ij
i
m
�
�
1
, j n�1: ,
ij
j
n
ia
�
�
1
, i m�1: . Ðåàëüíîå ÷èñëî � j ïîòðå-
áèòåëåé, ïîïàâøèõ â j, ìîæåò íå ðàâíÿòüñÿ x j . Ñëó÷àéíàÿ ñòîèìîñòü, ñâÿçàííàÿ ñ
ïåðåîöåíêîé èëè íåäîîöåíêîé ñïðîñà �j â ðåãèîíå j, ìîæåò áûòü âûïóêëîé
ôóíêöèåé � �j j jx( )� äëÿ x j j� � èëè � �j j jx( )� äëÿ x j j� � . Çàäà÷à ñîñòîèò
â òîì, ÷òîáû îïðåäåëèòü çíà÷åíèå x j , ìèíèìèçèðóþùåå îæèäàåìóþ ñòîèìîñòü
F x E x x
j
n
j j j j j j( ) max{ ( ), ( )},� � �
�
1
� � � �
12 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
ãäå x xj � � 0. SQG-ïðîöåäóðà äëÿ ðåøåíèÿ äàííîé çàäà÷è àíàëîãè÷íà (23).
Ïðèìå÷àòåëüíî, ÷òî ïðèëîæåíèå SQG-ìåòîäîâ äëÿ ïðîñòðàíñòâåííûõ ìèíè-
ìàêñíûõ çàäà÷ ðàçìåùåíèÿ [23], â îòëè÷èå îò äèñêðåòíûõ ñõåì àïïðîêñèìà-
öèè, íå âëèÿåò íà âûïóêëîñòü.
2.2. Ïðèíÿòèå ðåøåíèé â óñëîâèÿõ ïðåäåëüíûõ ñëó÷àåâ. Ñòàíäàðòíàÿ òå-
îðèÿ ïðåäåëüíûõ ñëó÷àåâ èçó÷àåò ïîâåäåíèå ìàêñèìóìà max( , ..., )� �1 n äëÿ ïî-
ñëåäîâàòåëüíîñòè � �1, ..., n , n � 2 . Öåëåâàÿ ôóíêöèÿ (19) îïðåäåëÿåòñÿ ìàêñèìó-
ìîì âçàèìîçàâèñèìûõ ñëó÷àéíûõ ïåðåìåííûõ g x y( , , )� , y Y� , êîòîðûå çàâèñÿò
òàêæå îò óïðàâëÿþùåé ïåðåìåííîé x. Çàäà÷ó (19) ìîæíî ðàññìàòðèâàòü êàê ìî-
äåëü ïðèíÿòèÿ ðåøåíèé â ïðåäåëüíûõ ñëó÷àÿõ, êîãäà äâà òèïà íåîïðåäåëåííûõ
ïåðåìåííûõ y, � âëèÿþò íà ðåçóëüòàò g x y( , , )� ïðèíÿòèÿ ðåøåíèé x. Íåîïðåäå-
ëåííîñòü â îòíîøåíèè y îöåíèâàåòñÿ èç ýêñòðåìàëüíîãî ñëó÷àéíîãî ñöåíàðèÿ,
â òî âðåìÿ êàê � ðàññìàòðèâàåòñÿ êàê ñëó÷àéíàÿ âåëè÷èíà. Ñëåäîâàòåëüíî,
(19) — ãèáðèäíàÿ çàäà÷à, îáúåäèíÿþùàÿ ÷èñòî äåòåðìèíèñòñêèé ìèíèìàêñíûé
ïîäõîä, ïðèíèìàþùèé ôîðìó ìèíèìèçàöèè F x g x y y Y( ) max ( , , )| ,� � �{ }� � � ,
è ÷èñòî âåðîÿòíîñòíûé áàéåñîâñêèé ïîäõîä ìèíèìèçàöèè ôóíêöèè îæèäàíèÿ
F x Eg x y( ) ( , , )� � äëÿ íåêîòîðîãî îáùåãî ðàñïðåäåëåíèÿ âåëè÷èí ( , )y � . Òàêèå
SQG-ïðîöåäóðû, êàê (21), ìîæíî ðàññìàòðèâàòü êàê àäàïòèâíûé ïîèñê ðîáàñòíûõ
ðåøåíèé, ïðèíèìàåìûõ èñõîäÿ èç îòêëèêà ñðåäû (ìîäåëèðîâàíèÿ) � �0 1, ,�
2.3. Àñèììåòðè÷íàÿ èíôîðìàöèÿ. Ñëåäóþùàÿ èíòåðïðåòàöèÿ ïðèâîäèò ê
ðàçëè÷íûì âàæíûì îáîáùåíèÿì çàäà÷è SMM (19). Ðàññìîòðèì äâóõ àãåíòîâ è
öåëåâóþ ôóíêöèþ g x y( , , )� . Àãåíò 1 âûáèðàåò äåéñòâèå x X� , íå çíàÿ âûáîðà
y Y� àãåíòà 2 è ñîñòîÿíèÿ îêðóæàþùåé ñðåäû �. Àãåíò 2 âûáèðàåò äåéñòâèå y
ïîñëå àãåíòà 1, áóäó÷è èíôîðìèðîâàííûì î çíà÷åíèÿõ x, �. Ôóíêöèÿ F x( ) â (19)
— ãàðàíòèðîâàííûé îæèäàåìûé ðåçóëüòàò àãåíòà 1 äëÿ äåéñòâèÿ x. Åñëè àãåíò 2
íå çíàåò ñîñòîÿíèÿ � ïåðåä âûáîðîì äåéñòâèÿ y, çàäà÷à àãåíòà 1 ñîñòîèò â ìèíè-
ìèçàöèè
F x Eg x yy Y( ) max ( , , ).� � � (24)
Ôóíêöèÿ F x( ) â (24) íåëèíåéíà. Ðàñ÷åò F â ëþáîé òî÷êå òðåáóåò ðåøåíèÿ
ñâîåé îïòèìèçàöèîííîé ïîäçàäà÷è, ò.å. ýòî âëîæåííàÿ çàäà÷à, êîòîðóþ ìîæíî
ðåøèòü ñ ïîìîùüþ ìåòîäîâ SQG è îïåðàöèè óñðåäíåíèÿ.
Ïðèìåð 8. Òî÷íàÿ øòðàôíàÿ ôóíêöèÿ. Äàííûé ìåòîä òàêæå âêëàäûâàåòñÿ
â îáùóþ òåîðèþ SQM. Äëÿ F x Ef xi i( ) ( , )� � , i � 0 1, ,� , îí ñîîòâåòñòâóåò ðåøå-
íèþ îñîáîãî ñëó÷àÿ çàäà÷è (23): ìèíèìèçàöèè òî÷íîé øòðàôíîé ôóíêöèè
F x Ef x C Ef x
i
m
i( ) ( , ) max , ( , )� �
�
0
1
0� �{ }
äëÿ îáùåé çàäà÷è ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ.
2.4. Âûïóêëî-âîãíóòûå ìàòåìàòè÷åñêèå îæèäàíèÿ. Ïðåäïîëîæèì, ÷òî
ôóíêöèÿ � �( , ) ( , , )x y Eg x y� âûïóêëà ïî x è âîãíóòà ïî y, à X Y, — êîìïàêòíûå
âûïóêëûå ìíîæåñòâà. Ïóñòü
x x g x y y y g x yk
X
k
k x
k k k k
X
k
k y
k k� �� � � �1 1� � � � � �[ ( , , )], [ ( , , k )], (25)
ãäå g gx y, — ñóáãðàäèåíòû g x y( , , )� ïî îòíîøåíèþ ê x y, ñîîòâåòñòâåííî. Äëÿ
ïîèñêà ñåäëîâûõ òî÷åê �( , )x y â X Y� ïðèìåíèì ìåòîä SQG-ïðîåêöèè — ñòî-
õàñòè÷åñêèé àíàëîã ìåòîäà Ýððîó–Ãóðâèöà. Ñõîäèìîñòü ïîñëåäîâàòåëüíîñòåé
{ } { }x yk k, ê ñåäëîâûì òî÷êàì òðåáóåò äîñòàòî÷íî ñòðîãèõ ïðåäïîëîæåíèé íà
�( , )x y , íàïðèìåð óñëîâèÿ ñòðîãîé âûïóêëî-âîãíóòîñòè. Ìîæíî ïîêàçàòü, ÷òî äëÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 13
íåëèíåéíûõ ôóíêöèé �( , ) y , �( , )x ïîñëåäîâàòåëüíîñòè { } { }x yk k, íå ñõîäÿò-
ñÿ ïðè ëþáîì âûáîðå ðàçìåðà øàãà � k , çà èñêëþ÷åíèåì íåêîòîðûõ îñîáûõ
ñëó÷àåâ. Ñõîäèìîñòü ïîñëåäîâàòåëüíîñòåé � �s
s
k
s
s
s
k
x
� �
0 0
/ , � �s
s
k
s
s
s
k
y
� �
0 0
/ ,
k � �, ñ âåðîÿòíîñòüþ 1 ê ñåäëîâîé òî÷êå �( , )x y èìååò ìåñòî ïðè ñòàíäàðò-
íûõ ïðåäïîëîæåíèÿõ íà � k , ãàðàíòèðóþùèõ ñõîäèìîñòü ìåòîäà SQG-ïðîåê-
öèè äëÿ âûïóêëîé çàäà÷è [16]. Äðóãàÿ âîçìîæíîñòü — ìîäèôèöèðîâàòü (25),
èñïîëüçóÿ îáùèå èäåè îáùåãî ìåòîäà èëè åãî âàðèàöèè [24].
Ïðèìåð 9. Êîíå÷íîå ìíîæåñòâî Y . Ðàññìîòðèì çàäà÷ó (24) ñ êîíå÷íûì
ìíîæåñòâîì Y , ò.å. ïðåäïîëîæèì, ÷òî F x Eg xi r i( ) max ( , )� � �1 � . Ýòà çàäà÷à ýêâè-
âàëåíòíà ìèíèìèçàöèè F x E y g xy Y i
i
r
i( ) max ( , )� �
�
1
� ñ âûïóêëî-âîãíóòûì ìàòå-
ìàòè÷åñêèì îæèäàíèåì Y y yi i
i
r
� � �
�
!
"!
#
$
!
%!�
0 1
1
, .
Âîçìîæíû äàëüíåéøèå óñîâåðøåíñòâîâàíèÿ ñòîõàñòè÷åñêèõ ìèíèìàêñíûõ
çàäà÷. Ñî÷åòàíèå ìîäåëåé (19), (24) äàåò ìèíèìèçàöèþ
F x E g x y zy Y z Z( ) max max ( , , , ).� � � � (26)
Åñëè g x y z( , , , )� âûïóêëà ïî x è âîãíóòà ïî y, à X , Y — âûïóêëûå êîìïàêòû,
òî ïðîöåäóðà (25) ïðèìåíèìà òàêæå äëÿ ðåøåíèÿ (26), åñëè g x yx
k k k( , , )� ,
g x yy
k k k( , , )� çàìåíèòü íà g x y zx
k k k k( , , , )� , g x y zy
k k k k( , , , )� , ãäå z k — ðå-
øåíèå äåòåðìèíèðîâàííîé ïîäçàäà÷è g x y zk k k k( , , , )� � max ( , , , )z Z
k k kg x y z� � .
2.5. Ñòîõàñòè÷åñêîå ðàâíîâåñèå Íåøà. Ñòîõàñòè÷åñêîå ðàâíîâåñèå èãðû ñ
N ó÷àñòíèêàìè íà X X X X
N
� � � �1 2 � ìîæíî îïðåäåëèòü, èñïîëüçóÿ ôóíêöèè
âûèãðûøåé &i ix E x( ) ( , )� � � , x X� . Îáîçíà÷èì ( , , , , , , )x x y x xi i i n1 1 1� �� �
÷åðåç ( | )y xi . Òî÷êó x x x XN
* * *( , , )� �1 � íàçûâàþò ðàâíîâåñíûì ñîñòîÿíè-
åì Íåøà, åñëè & &i i i ix y x y x X( ) min ( | )| ( | ) .* * *� �{ } Ââåäåì ôóíêöèþ
L x y x y x
i
N
i i i( , ) [ ( ) ( | )]� �
�
1
& & , y y yN� ( , , )1 � , x x x N� ( , , )1 � . Òî÷êà x X* � —
íîðìàëèçîâàííîå ðàâíîâåñíîå ñîñòîÿíèå, åñëè max ( , )*
y X L x y� � 0. Ïîñêîëüêó
max ( , )y X L x y� � 0, ïîèñê ñëó÷àéíî íîðìàëèçîâàííîãî ðàâíîâåñíîãî ñîñòîÿíèÿ
ñâîäèòñÿ ê çàäà÷å SMM: ìèíèìèçèðîâàòü
F x L x y x Xy X( ) max ( , ), .� ��
Âàæíóþ äîïîëíèòåëüíóþ èíôîðìàöèþ î òîì, ÷òî min ( )x X F x� � 0, ìîæíî
ýôôåêòèâíî èñïîëüçîâàòü ïðè ïîèñêå îáùåãî ðåøåíèÿ ìåòîäàìè SQG. Ïðåäïî-
ëîæèì, ÷òî L x y( , ) — âûïóêëî-âîãíóòàÿ ôóíêöèÿ äëÿ x X� , y X� . Òîãäà
ïðîöåäóðà (25) ïðèìåò âèä
x x x i N ki
k
X i
k
k ix
k k
i
� � � � �1 1 0 1� � � �[ ( , )], : , , , ,�
ãäå � ixi
— ñóáãðàäèåíò � �i x( , ) ïî îòíîøåíèþ x. Óñëîâèÿ ñõîäèìîñòè àíàëî-
ãè÷íû èñïîëüçóåìûì â ìåòîäå (25). Ýòè ìåòîäû äëÿ èçó÷åíèÿ ðàâíîâåñíîãî
ñîñòîÿíèÿ Íåøà èñïîëüçóþò àäàïòèâíî ðåãóëèðóåìóþ ïðîöåäóðó [16, 25].
Ïðèìåð 10. Ñëó÷àéíàÿ îëèãîïîëèÿ Êóðíî. Êëàññè÷åñêàÿ ìîäåëü îëèãîïî-
ëèè Êóðíî [25, 26] ÿâëÿåòñÿ êëþ÷åâîé ìîäåëüþ ñîâðåìåííîé òåîðèè ïðîìûø-
14 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
ëåííîé îðãàíèçàöèè. Îáîáùàÿ åå íà ïðîèçâîäñòâî ðàçíûõ òîâàðîâ, ïîëó÷èì ìî-
äåëü ñëåäóþùåãî âèäà. Êîìïàíèÿ i ïðîèçâîäèò ïàêåò ïðåäìåòîâ ïîòðåáëåíèÿ
x Ri
n� , ñîîòâåòñòâóþùàÿ âûïóêëàÿ ñëó÷àéíàÿ ñòîèìîñòü ïðîèçâîäñòâà ñîñòàâ-
ëÿåò c xi i( , )� , à ñëó÷àéíûé ðûíî÷íûé äîõîä p x x
j
n
j i
�
�
�
�
�
�
�
�
�
1
, ),� , ãäå p Q( , )� —
ñòîèìîñòü, ïðè êîòîðîé îáùèé ñïðîñ Q ðàâåí îáùåìó îáúåìó ïîñòàâîê x j
j
n
�
1
.
Ïðåäïîëîæèì, ÷òî p Q a A Q( , ) ( )� �� � , ãäå a R n� è A( )� — n n� ïîëîæèòåëü-
íî-ïîëóîïðåäåëåííàÿ ìàòðèöà (ïî÷òè äëÿ âñåõ �). Òîãäà äëÿ &i i ix c x( , ) ( , )� �� �
� �
�
( , ) ( ( ) , )a x A x xi
j
n
j i
1
� ôóíêöèÿ L x y( , ) âûïóêëî-âîãíóòà.
2.6. Ñòîõàñòè÷åñêàÿ îïòèìèçàöèÿ ñ íåèçâåñòíûìè ðàñïðåäåëåíèÿìè. Âå-
ðîÿòíîñòíàÿ ìåðà P ñòàíäàðòíîé çàäà÷è ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ
ïðåäïîëàãàåòñÿ ñîñðåäîòî÷åííîé íà ïîäìíîæåñòâàõ A ïðîñòðàíñòâà � â òîì
ñìûñëå, ÷òî ìîæíî ãåíåðèðîâàòü âûáîðêè � �0 1, ,� ñëó÷àéíûõ âåëè÷èí � èç P.
Íà ïðàêòèêå âåðîÿòíîñòíàÿ ìåðà P ìîæåò íå áûòü òî÷íî èçâåñòíà: èìåþòñÿ äàí-
íûå î íåêîòîðûõ åå õàðàêòåðèñòèêàõ, â ÷àñòíîñòè îãðàíè÷åíèÿõ íà ñðåäíåå èëè
äðóãèå ìîìåíòû. Òàêèå äàííûå îáû÷íî äàþòñÿ â âèäå îãðàíè÷åíèé
Q x P q x P d s Ks k( , ) ( , ) ( ) , : ,� � �'
�
� � 0 1 (27)
P d( ) ,
�
' �� 1 (28)
ãäå q xk ( , )� — èçâåñòíûå ôóíêöèè (êîòîðûå ÷àñòî íå çàâèñÿò îò x), íàïðèìåð
êàê â îãðàíè÷åíèÿõ c E Cr r
r
l
r
r rl
l
l1
1
11
, , , ,� � �� �� � ñ èçâåñòíûìè êîíñòàíòà-
ìè c, C. Åñëè íåèçâåñòíàÿ âåðîÿòíîñòíàÿ ìåðà îöåíèâàåòñÿ èç õóäøåãî (ïî îò-
íîøåíèþ ê îãðàíè÷åíèÿì) ñëó÷àÿ (27), (28), òî íàøó çàäà÷ó ìîæíî ñôîðìóëè-
ðîâàòü â âèäå SMM: íàéòè âåêòîð x, ìèíèìèçèðóþùèé
F x f x P dP( ) max ( , ) ( ),� � 'P � � (29)
ãäå P — ñåìåéñòâî âåðîÿòíîñòíûõ ìåð, îïðåäåëåííûõ (27), (28). Ðåøåíèå
«âíóòðåííåé» ïîäçàäà÷è â (29) îïðåäåëÿåò âåðîÿòíîñòíóþ ìåðó P x d* ( , )� .
Âàæíî, ÷òî P x* ( , ) ñêîíöåíòðèðîâàíà íå áîëåå ÷åì â K �1 òî÷êàõ [27, 28], è ýòîò
ôàêò ìîæíî ýôôåêòèâíî èñïîëüçîâàòü äëÿ ïëàíèðîâàíèÿ ïðîöåäóðû ðåøåíèÿ.
Äðóãîé âàæíûé ïîäõîä — èñïîëüçîâàíèå äâîéñòâåííûõ ñîîòíîøåíèé [28]
F x f x u q xu s
s
K
s( ) max [ ( , ) ( , )],� �� �
�
0
1
� � �� (30)
äëÿ âíóòðåííåé çàäà÷è ìàêñèìèçàöèè â (29).
Åùå îäèí âàæíûé êëàññ ñëó÷àåâ âîçíèêàåò ïðè äàëüíåéøåé ñïåöèôèêàöèè
íåîïðåäåëåííîñòåé, ñâÿçàííûõ ñ ìåðîé P. Ïðåäïîëîæèì, ñëó÷àéíûå ïàðàìåòðû
ìîæíî ðàçäåëèòü íà äâå ãðóïïû ( , )� � ñ ñîâìåñòíîé ôóíêöèåé ðàñïðåäåëåíèÿ
H ( , )� � âèäà dH h P d d( , ) ( , ) ( ) ( )� � � � � � �� , ãäå P d( )� òî÷íî íåèçâåñòíî, íî óäîâ-
ëåòâîðÿåò (27), (28). Åñëè P áåðåòñÿ èç õóäøåãî ñëó÷àÿ, çàäà÷ó ìîæíî
ïåðåôîðìóëèðîâàòü êàê çàäà÷ó ìèíèìèçàöèè:
F x E E f xP x y( ) [max ( , , )],� ��P � �
� ' '�[ max ( , , ) ( , ) ( )] ( ).P f x h P d dP � � � � � � � (31)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 15
Èñïîëüçóÿ ñîîòíîøåíèÿ äâîéñòâåííîñòè, àíàëîãè÷íûå (30), (31), çàäà÷ó
ìîæíî ïåðåôîðìóëèðîâàòü êàê ìèíèìèçàöèþ âèäà (19) ôóíêöèè
F x u( ) max ,� � �' 0 � � . (32)
Ïðèìåð 11. Íåïîëíûå äàííûå î ôóíêöèè ñòîèìîñòè. Ðàññìîòðèì (31) äëÿ
ôóíêöèè ñòîèìîñòè F x Ec x x X( ) ( , ),� � , ãäå c — ñëó÷àéíûé âåêòîð, c c� ( , )� � ,
è ôóíêöèè qk â (27) íå çàâèñÿò îò x. Òîãäà çàäà÷ó (32) ìîæíî ñôîðìóëèðîâàòü â
òåðìèíàõ ìèíèìèçàöèè
F x c x hu( ) max [( ( , ), ) ( , ).,� � �' 0 � � � � ��
Çäåñü F x( ) — âûïóêëàÿ ôóíêöèÿ, à SQG îïðåäåëÿåòñÿ ñîîòíîøåíèåì (20).
Ñëîæíîñòü îáñóæäàåìîé çäåñü SMM-çàäà÷è âîçíèêàåò âñëåäñòâèå âëîæåí-
íîé ñòðóêòóðû öåëåâîé ôóíêöèè. Âî ìíîãèõ ñëó÷àÿõ îíà âêëþ÷àåò ïîäçàäà÷è äå-
òåðìèíèðîâàííîé îïòèìèçàöèè ïîä çíàêîì ìàòåìàòè÷åñêîãî îæèäàíèÿ.  ïðèëî-
æåíèÿõ ýòè ïîäçàäà÷è ÷àñòî èìåþò ñïåöèàëüíóþ ñòðóêòóðó, íàïðèìåð äîïóñòè-
ìîå ìíîæåñòâî ìîæíî ñâåñòè ê êîíå÷íîìó ÷èñëó àëüòåðíàòèâíûõ âàðèàíòîâ (êàê
â ïðèìåðå 9).  ñëó÷àå áåñêîíå÷íîãî äîïóñòèìîãî ìíîæåñòâà îíè ìîãóò áûòü ïî-
ñëåäîâàòåëüíî ïðèáëèæåíû ñëó÷àéíûìè êîíå÷íûìè ìíîæåñòâàìè ñ êîíå÷íûì
÷èñëîì ýëåìåíòîâ íà êàæäîì øàãå k � 0 1, ,� SQG-ïðîöåäóðû, êàê ïîêàçàíî
â [28]. Äëÿ ïðàêòè÷åñêèõ ïðèëîæåíèé âàæíî ïîíèìàòü, ÷òî ìîäåëè (19), (24),
(26), (29), (31) ôàêòè÷åñêè ñôîðìóëèðîâàíû ïðè ðàçíûõ ïðåäïîëîæåíèÿõ íà ñöå-
íàðèé õóäøåãî ñëó÷àÿ. Íàïðèìåð, â (29) îöåíêà íàõîäèòñÿ äëÿ õóäøåãî ñëó÷àÿ
îæèäàåìîãî âûõîäà, à (19) ðàññìàòðèâàåò õóäøèé ñëó÷àé ñëó÷àéíûõ ñöåíàðèåâ.
3. ÍÅÊÎÒÎÐÛÅ ÀÊÒÓÀËÜÍÛÅ ÏÐÎÁËÅÌÛ ÑÒÎÕÀÑÒÈ×ÅÑÊÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
3.1. Íåãëàäêèå çàäà÷è. Îáùèå àðãóìåíòû èñïîëüçîâàíèÿ SQG-ìåòîäîâ äëÿ
íåãëàäêèõ çàäà÷ òðåáóþò ñïåöèàëüíîãî îáñóæäåíèÿ è îáîñíîâàíèÿ. Äîñòàòî÷-
íî ïðîäóêòèâíûì è èíòåðåñíûì îêàçàëñÿ ïîäõîä ê ðåøåíèþ íåãëàäêèõ çàäà÷,
îñíîâàííûé íà ïðîöåäóðàõ ñãëàæèâàíèÿ è óñðåäíåíèÿ â îïðåäåëåííîì ñìûñ-
ëå. Â íàñòîÿùåå âðåìÿ áîëüøîé èíòåðåñ ïðåäñòàâëÿåò êëàññ çàäà÷ ñ òàê íàçû-
âàåìûìè îáîáùåííî-äèôôåðåíöèðóåìûìè GD-ôóíêöèÿìè [1, 13, 29–31]. Êëàññ
GD-ôóíêöèé çàìêíóòûé ïî îòíîøåíèþ ê îïåðàòîðàì min, max è èõ ñóïåðïî-
çèöèè. Äëÿ ìíîæåñòâà ñóáãðàäèåíòîâ �f ñïðàâåíäëèâà ôîðìóëà
� � � �max ( ), ( ) ( ) max( , ) ,{ } co{ }f x f x f x f fi1 2 1 2 (33)
è ñóáãðàäèåíòû ñëîæíîé ôóíêöèè &( , , )f f r1 � âû÷èñëÿþòñÿ ïî î÷åâèäíûì è
èçâåñòíûì öåïíûì ïðàâèëàì. Êëàññ GD-ôóíêöèé òàêæå çàìêíóò ïî îòíîøå-
íèþ ê îïåðàòîðó ìàòåìàòè÷åñêîãî îæèäàíèÿ
� � � �F x E f x F x Ef x( ) ( , ), ( ) ( , ),� � (34)
ãäå f ( , ) � — GD-ôóíêöèÿ.
Îòìåòèì, ÷òî êëàññ GD-ôóíêöèé ñîäåðæèò ôóíêöèè, íåïðåðûâíî äèôôåðåí-
öèðîâàííûå, âûïóêëûå, âîãíóòûå, ïîëóãëàäêèå è çàìêíóòûå îòíîñèòåëüíî îïå-
ðàöèé ìàêñèìóìà, ìèíèìóìà, ñóïåðïîçèöèè è âçÿòèÿ ìàòåìàòè÷åñêîãî îæèäà-
íèÿ. Äëÿ ìèíèìèçàöèè GD-ôóíêöèé îáîñíîâàíû îáîáùåííî-ãðàäèåíòíûé è ñòî-
õàñòè÷åñêèé îáîáùåííî-ãðàäèåíòíûé ìåòîäû. Ôîðìóëû (33), (34) äàþò
ïîëåçíûé èíñòðóìåíò äëÿ âû÷èñëåíèÿ ñóáãðàäèåíòà. Ê ñîæàëåíèþ, äëÿ îáùåãî
êëàññà íåãëàäêèõ ôóíêöèé èõ ïðÿìîå èñïîëüçîâàíèå óñëîæíåíî è â íåêîòîðûõ
ñëó÷àÿõ íåïðîäóêòèâíî. Íàèáîëåå ýôôåêòèâíî èñïîëüçîâàíèå ìåòîäà SMQG
àíàëîãè÷íî (11), (12).
16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
3.2. Ñèñòåìû ñ äèñêðåòíûìè ñîáûòèÿìè. Ìíîãèå ñèñòåìû ñ äèñêðåòíûìè
ñîáûòèÿìè èìåþò ðàçðûâíûå ïîêàçàòåëè ôóíêöèîíèðîâàíèÿ (äëèíû î÷åðåäåé â
ñèñòåìàõ ìàññîâîãî îáñëóæèâàíèÿ, âðåìÿ îáñëóæèâàíèÿ â ñèñòåìàõ ñ îòêàçàìè è
ðåãåíåðàöèåé, óðîâíè çàïàñîâ ïðè ñëó÷àéíîì ñïðîñå â ýêîíîìè÷åñêèõ ñèñòåìàõ).
Ëîêàëüíàÿ îïòèìèçàöèÿ ýòèõ ñèñòåì òðåáóåò ñîâåðøåííî íîâîãî àíàëèòè÷åñêîãî
àïïàðàòà è ñîîòâåòñòâóþùèõ ÷èñëåííûõ ìåòîäîâ. Ëþáàÿ çàäà÷à ñòîõàñòè÷åñêîé
îïòèìèçàöèè ÿâëÿåòñÿ ñàìà ïî ñåáå çàäà÷åé ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè:
ïî ñóòè, êàæäîé ðåàëèçàöèè ñëó÷àéíûõ ïàðàìåòðîâ (ñöåíàðèþ) ñîîòâåòñòâóåò
ñâîÿ öåëåâàÿ ôóíêöèÿ è ñâîå ðåøåíèå.  ñòîõàñòè÷åñêîì ïðîãðàììèðîâàíèè, êàê
ïðàâèëî, àãðåãèðóþò ýòè ñëó÷àéíûå öåëåâûå ôóíêöèè ñ ïîìîùüþ îïåðàöèé ìà-
òåìàòè÷åñêîãî îæèäàíèÿ. Îäíàêî ýòî íå åäèíñòâåííûé ñïîñîá ïîñòðîåíèÿ îáîá-
ùåííîé öåëåâîé ôóíêöèè. Äðóãàÿ âàæíàÿ ôóíêöèÿ òàêîãî ðîäà — ôóíêöèÿ âåðî-
ÿòíîñòè, âûðàæàþùàÿ âåðîÿòíîñòü òîãî, ÷òî íåêîòîðàÿ ñëó÷àéíàÿ âåëè÷èíà, çà-
âèñÿùàÿ îò íåïðåðûâíûõ è äèñêðåòíûõ ïàðàìåòðîâ, íå ïðåâûøàåò çàäàííîé
ãðàíèöû èëè ïðèíàäëåæèò çàäàííîé îáëàñòè. Ñ ïîìîùüþ ôóíêöèé âåðîÿòíîñòè
îïèñûâàþò íàäåæíîñòü òåõíè÷åñêèõ ñèñòåì, ðèñê â ýêîíîìèêå è áèçíåñå. Ôóíê-
öèè âåðîÿòíîñòè è ìàòåìàòè÷åñêîãî îæèäàíèÿ ÿâëÿþòñÿ ÷àñòíûìè ñëó÷àÿìè
ôóíêöèé îæèäàåìîé ïîëåçíîñòè, ñ ïîìîùüþ êîòîðûõ ôîðìóëèðóþòñÿ çàäà÷è
ïðèíÿòèÿ ðåøåíèé ïðè íåîïðåäåëåííîñòè. Ôóíêöèè îæèäàåìîé ïîëåçíîñòè ìî-
ãóò áûòü íåâûïóêëûìè, íåãëàäêèìè è äàæå ðàçðûâíûìè è, ñëåäîâàòåëüíî,
òðåáóþò ñïåöèàëüíûõ ìåòîäîâ îïòèìèçàöèè.
Ïðè îïòèìèçàöèè ñèñòåì ñ äèñêðåòíûìè ñîáûòèÿìè âîçíèêàåò âîïðîñ î ãëî-
áàëüíîé îïòèìèçàöèè ñèñòåìû, ïîñêîëüêó îïòèìèçèðóþùèåñÿ ôóíêöèè âîîáùå
íåâûïóêëûå. Ìîæíî áûëî áû ïðèìåíèòü îáùåèçâåñòíûå ìåòîäû ãëîáàëüíîé
îïòèìèçàöèè, íî ýòî óñëîæíÿåòñÿ òåì, ÷òî ôóíêöèè, ïîäëåæàùèå îïòèìèçàöèè,
ïðåäñòàâëÿþò ñîáîé ìàòåìàòè÷åñêèå îæèäàíèÿ, ò.å. ìíîãîìåðíûå èíòåãðàëû, è
èõ òî÷íîå âû÷èñëåíèå ëèáî î÷åíü òðóäîåìêî, ëèáî ïðàêòè÷åñêè íåâîçìîæíî. Ïî-
ýòîìó íåîáõîäèìû îñîáûå ïîäõîäû ê ãëîáàëüíîé îïòèìèçàöèè òàêèõ ñòîõàñòè-
÷åñêèõ ñèñòåì. Áîëüøèíñòâî êëàññè÷åñêèõ çàäà÷ èññëåäîâàíèÿ îïåðàöèé, êîòî-
ðûå ÷àñòî ôîðìóëèðóþòñÿ êàê çàäà÷è äèñêðåòíîãî (èëè ñìåøàííîãî) ïðîãðàì-
ìèðîâàíèÿ (çàäà÷à î ðþêçàêå, î íàçíà÷åíèè, î ðàñïîëîæåíèè, î ðàñïðåäåëåíèè
ðåñóðñîâ è äð.), â îáùåì ñëó÷àå ìîãóò ñîäåðæàòü ñëó÷àéíûå ïàðàìåòðû. Ïðè ýòîì
îíè äîëæíû áûòü ïåðåôîðìóëèðîâàíû êàê çàäà÷è ñòîõàñòè÷åñêîãî äèñêðåòíîãî
ïðîãðàììèðîâàíèÿ (îäíî-, äâóõ- èëè ìíîãîýòàïíîãî, ñ âåðîÿòíîñòíûìè îãðàíè÷å-
íèÿìè, ñ ôóíêöèÿìè ðèñêà). Ôîðìàëüíî çàäà÷à äèñêðåòíîãî ñòîõàñòè÷åñêîãî ïðî-
ãðàììèðîâàíèÿ — ýòî çàäà÷à âûáîðà, íàïðèìåð, ìèíèìàëüíîãî ìàòåìàòè÷åñêîãî
îæèäàíèÿ èç êîíå÷íîãî (àñòðîíîìè÷åñêîãî) ìíîæåñòâà âàðèàíòîâ.
Ðàññìîòðèì íåêîòîðûå âàæíûå çàäà÷è, ñâÿçàííûå ñ ýòîé ïðîáëåìàòèêîé.
Çàäà÷è ñ âåðîÿòíîñòíûìè îãðàíè÷åíèÿìè. Çàäà÷à
f x
x
( ) min� (35)
ïðè âåðîÿòíîñòíîì îãðàíè÷åíèè
P{ }g x( , )� �� � �0 1 (36)
ìîæåò áûòü ïðèáëèæåíà ñëåäóþùåé ïðîñòîé çàäà÷åé áåç îãðàíè÷åíèé (ñ ïàðà-
ìåòðîì øòðàôà N ):
F x f x N g x
x
( ) ( ) max , ( , ) min,� � �E { }0 � (37)
ãäå E Emax , ( , ) ( , ) ( , ){ } { }0 0g x g x I g x� � �� � .  ðàáîòàõ [32, 33] òàêàÿ çàìåíà
èñïîëüçîâàëàñü äëÿ îïòèìèçàöèè ïîðòôåëÿ äîãîâîðîâ ñòðàõîâàíèÿ ïðè îãðàíè-
÷åíèÿõ íà âåðîÿòíîñòü áàíêðîòñòâà êîìïàíèè ñòðàõîâêè. Ñëó÷àéíàÿ âåëè÷èíà
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 17
max , ( , ){ }0 g x � ìîæåò èíòåðïðåòèðîâàòüñÿ êàê âåëè÷èíà çàèìñòâîâàíèÿ äëÿ ïî-
êðûòèÿ ïîëîæèòåëüíûõ ïîòåðü g x( , )� , à N — öåíà çà òàêîå çàèìñòâîâàíèå.
Îêàçûâàåòñÿ, ÷òî çàäà÷è (35), (36) è (37) òåñíî ñâÿçàíû. Íàïðèìåð, â [32, 33]
îïòèìàëüíîå çíà÷åíèå (35), (36) ìîæåò áûòü ïðèáëèæåíî îïòèìàëüíûì çíà÷å-
íèåì (37) ñ íåêîòîðûì áîëüøèì ïàðàìåòðîì N (�� øòðàôà.
Êâàíòèëè è óñëîâíûå ñðåäíèå ïðè çàäàííîì ðèñêå. Âàæíûì äëÿ ôèíàí-
ñîâûõ ïðèëîæåíèé ÿâëÿåòñÿ ñïåöèàëüíûé ñëó÷àé çàäà÷è (35), (36) — ìèíèìèçà-
öèÿ êâàíòèëÿ çàäàííîãî óðîâíÿ
Q x y g x y
x
� � �( ) min | ( , ) min .� � � � �{ { } }P 1 (38)
Âìåñòî (38) ñíîâà ìîæíî ðåøàòü çàäà÷ó ìèíèìèçàöèè øòðàôíîé ôóíêöèè (37):
F x y y N g x y
x y
( , ) max , ( , ) min ,
,
� � � �E { }0 � (39)
êîòîðàÿ ÿâëÿåòñÿ ñïåöèàëüíûì ñëó÷àåì ñòîõàñòè÷åñêèõ ìèíèìàêñíûõ çàäà÷.
Èç óñëîâèé îïòèìàëüíîñòè äëÿ ýòîé ïðîáëåìû ñëåäóåò, ÷òî îïòèìàëüíîå çíà-
÷åíèå y (äëÿ äàííîãî x) — ýòî 1/ N êâàíòèëü ñëó÷àéíîé âåëè÷èíû h.
Óñëîâíîå ñðåäíåå ïðè ðèñêå � (CVaR — conditional value at risk) îïðåäåëÿåò-
ñÿ òàê:
C x g x I g x Q x� �
�
� �( ) ( , ) ( , ) ( ) .� � �
1
0E { }
Ìèíèìèçàöèÿ C x� ( ) ïðè åñòåñòâåííûõ ïðåäïîëîæåíèÿõ ýêâèâàëåíòíà [21]
ñëåäóþùåé âûïóêëîé çàäà÷å ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ:
R x y g x y
y x
( , ) max , ( , ) min.
,
�
�
�� � � �
1
0E { }}
Òàêèì îáðàçîì, CVaR-ìèíèìèçàöèÿ (40) èìååò ôîðìó (39) ïðè N �
1
�
.
Ïðîáëåìó (39) ìîæíî èíòåðïðåòèðîâàòü ýêîíîìè÷åñêè. Ïðåäïîëîæèì, ÷òî
g x( , )� ïðåäñòàâëÿåò ñòîõàñòè÷åñêèå äîïîëíèòåëüíûå ïîòåðè â çàâèñèìîñòè îò
ðåøåíèÿ x è ñëó÷àéíîãî ïàðàìåòðà �. Ýòè ïîòåðè ïîêðûâàþòñÿ çà ñ÷åò çàáëàãîâ-
ðåìåííîãî çàèìñòâîâàíèÿ ñðåäñòâ â ðàçìåðå y ïðè ïðîöåíòíîé ñòàâêå 1 è ïîñò-
ôàêòóì â ðàçìåðå max , ( , ){ }0 g x y� � ïî ñòàâêå N . Òàêàÿ ñòðàòåãèÿ ïîâåäåíèÿ îá-
åñïå÷èâàåò áîëüøóþ ãèáêîñòü ïî ñðàâíåíèþ ñ ÷èñòî äåòåðìèíèðîâàííûì ðåøå-
íèåì x, êàê â (35), (36).
Ïðîöåññ ðèñêà. Êëàññè÷åñêèé äèñêðåòíûé ïðîöåññ ðèñêà îïèñûâàåò èçìå-
íåíèå âî âðåìåíè ðåçåðâîâ R xt ( ) ñòðàõîâîé êîìïàíèè:
R x R x C x t Tt t t� � � � �1 0 0 1( ) ( ) ( ), , , , ,� �
ãäå R0 0� — íà÷àëüíûé êàïèòàë êîìïàíèè, � t x( ) — âçíîñû ñòðàõîâàíèÿ è
C xt ( ) — ñëó÷àéíûå àãðåãèðîâàííûå âûïëàòû äî ìîìåíòà t, âêëþ÷àÿ íàëîãè, äèâèäåí-
äû è ò.ä., x — âåêòîð ðåøåíèé. Ôóíêöèè � t x( ) , C xt ( ) ñ÷èòàþòñÿ íåïðåðûâíî äèôôå-
ðåíöèðîâàííûìè (èëè îáîáùåííî äèôôåðåíöèðîâàííûìè) ïî x. Êîìïîíåíòû âåêòîðà x
ìîãóò âêëþ÷àòü ïàðàìåòðû ïîðòôåëÿ àêòèâîâ è êîíòðàêòîâ ñòðàõîâàíèÿ [32, 33].
Ïðîáëåìà ñîñòîèò â òîì, ÷òîáû îïòèìèçèðîâàòü ðàáîòó êîìïàíèè íà âðå-
ìåííîì ãîðèçîíòå [ , ]0 T ñ ïîìîùüþ íàáîðà èíäèêàòîðîâ, íàïðèìåð:
• ñëó÷àéíîå âðåìÿ îñòàíîâêè
�( ) max [ , ]: ( ) , ,x t T R x s s ts� � � ( � �{ }0 0 0 (40)
êîòîðîå íàçûâàþò ìîìåíòîì íåïëàòåæåñïîñîáíîñòè, åñëè �( )x T� , ëèáî
R xx T� ( ) ( )� � 0 ;
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
• âåðîÿòíîñòü áàíêðîòñòâà íà èíòåðâàëå âðåìåíè [ , ]0 T
P E( ) ( ( ) , ); � � � � �1 0 0I R x t Tt{ } (41)
• ÷àñòè÷íàÿ îæèäàåìàÿ ïðèáûëü (íà òðàåêòîðèÿõ âûæèâàíèÿ)
F x R x I R x t TT T t( ) ( ) ( ) , ;� � � �E { }0 0 (42)
• îæèäàåìàÿ îòðèöàòåëüíàÿ ãëóáèíà áàíêðîòñòâà
H x R xT x( ) min , ( )( )� E { }0 � � � � � �
�
E
t
T
t tR x I R t R x
0
0 0 0( ) , ; ( ) ;{ }� � (43)
• êðèòåðèé ñòàáèëüíîñòè
S x R x R x t TT t t( ) ( ) ( ) ( ),� � � � �P E{ } =1 0
� � � � � � �E EI R x R x t Tt t{ }( ) ( ) ( ), , .1 0 0 1
(44)
Êðèòåðèé ñòàáèëüíîñòè îöåíèâàåò âåðîÿòíîñòü òîãî, ÷òî êîìïàíèÿ ðàçâèâà-
åòñÿ íå íàìíîãî õóæå, ÷åì ñðåäíÿÿ òðàåêòîðèÿ. Ñòðóêòóðà ýòîãî êðèòåðèÿ ïîäîá-
íà (41). Îòìåòèì, ÷òî ôóíêöèÿ �( )x ìîæåò áûòü ðàçðûâíàÿ ïî x. Ýòî ìîæåò âû-
çâàòü ðàçðûâíîñòü âñåõ ôóíêöèé (41)–(44).
Óñëîâèå À. Äëÿ ëþáîé ôèêñèðîâàííîé òî÷êè x X� , t T�[ , ]0 è c,
� 0
(i) P{ }R x ct ( ) � � 0;
(ii) äëÿ P{ }R x c c Lt ( ) [ , ]� � � �
íåêîòîðîé êîíñòàíòû L � 0.
 óñëîâèÿõ À(i) óïîìÿíóòûå âûøå èíäèêàòîðû íåïðåðûâíû, à â óñëîâèÿõ
À(ii) — ëèïøèöåâû â X [13].
Ðàçðûâíûå ôóíêöèè ïîëåçíîñòè è ðèñêà. Ñ ââåäåíèåì íåîïðåäåëåííîñòè
è ðèñêîâ ïîëíàÿ îöåíêà ðåøåíèÿ x çàâèñèò îò ñîîòíîøåíèÿ ìåæäó ðàçëè÷íûìè
ñîöèàëüíî-ýêîíîìè÷åñêèìè è ýêîëîãè÷åñêèìè èíäèêàòîðàìè (ðàñõîäû, âûãîäû,
äîõîäû, óáûòêè) è èíäèêàòîðàìè ðèñêîâ. Äîñòàòî÷íî ïîëíî ýòîò êëàññ çàäà÷ è
ñîîòâåòñòâóþùèé êëàññ ìåð ðèñêà îïèñàí â [34]. Êëàññè÷åñêèé ïðèìåð — ýôôåê-
òèâíûå ñòðàòåãèè ïî êðèòåðèÿì ñðåäíåå–äèñïåðñèÿ, îáåñïå÷èâàþùèì áàëàíñ
ìåæäó ñðåäíèìè îæèäàåìûìè äîõîäàìè ïî âñåì èíâåñòèöèÿì è äèñïåðñèåé.
Ê ñîæàëåíèþ, êîíöåïöèÿ ýôôåêòèâíûõ ñòðàòåãèé ïî êðèòåðèÿì ñðåäíèé äî-
õîä–äèñïåðñèÿ ìîæåò ââîäèòü â çàáëóæäåíèå è äàæå áûòü îøèáî÷íîé äëÿ íåíîð-
ìàëüíûõ ðàñïðåäåëåíèé âåðîÿòíîñòè (îñîáåííî äëÿ êàòàñòðîôè÷åñêèõ ðèñêîâ),
êîòîðûå òðåáóþò ñëîæíûõ èíäèêàòîðîâ ðèñêà è ñîîòâåòñòâóþùèõ ïîíÿòèé
óñòîé÷èâûõ ñòðàòåãèé. Òî÷íåå, íà ïðàêòèêå äàííîå ðåøåíèå x ïðèâîäèò ê ðàçíûì
ðåçóëüòàòàì f x f x f xm( , ) ( ( , ), , ( , )),� � �� 1 � êîòîðûå çàâèñÿò îò íåêîòîðûõ íå-
îïðåäåëåííûõ (ñëó÷àéíûõ) ïåðåìåííûõ �. Ôîðìàëüíî îöåíêó ðåøåíèÿ x ìîæíî
ïðåäñòàâèòü â âèäå ôóíêöèè ìàòåìàòè÷åñêîãî îæèäàíèÿ
U x u f x f xm( ) ( ( , ), , ( , )),� E 1 � ��
ãäå u ( ) — ôóíêöèÿ ïîëåçíîñòè, îïðåäåëåííàÿ íà f R m� . Ýôôåêòèâíûå ðå-
øåíèÿ ïî êðèòåðèÿì ñðåäíåå–äèñïåðñèÿ, êîòîðûå ìàêñèìèçèðîâàëè Ef x( , )� �
� �N f x f xE E[ ( , ) ( , )]� � 2 , N � 0, ìîæíî ïîëó÷èòü ìàêñèìèçàöèåé ôóíêöèè ïî-
ëåçíîñòè òîãî æå òèïà:
max [ ( , ) ( ( , ) ) ].
,x y
f x N f x yE � �� � 2
Òðàäèöèîííî ôóíêöèÿ ïîëåçíîñòè ñ÷èòàåòñÿ íåïðåðûâíîé è äèôôåðåíöèðî-
âàííîé. Ëåãêî âèäåòü, ÷òî âñå ðàññìîòðåííûå â ýòîì ðàçäåëå ôóíêöèè ðèñêà ìî-
ãóò áûòü ïðåäñòàâëåíû â òîé æå ôîðìå, íî ñ íåãëàäêèìè è äàæå ðàçðûâíûìè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 19
ôóíêöèÿìè ïîëåçíîñòè. Íàïðèìåð, åñëè u ( ) — èíäèêàòîðíàÿ ôóíêöèÿ äëÿ ñî-
áûòèÿ { }f R f cm� �| , òî U x f x c( ) ( , ) .� �P{ }�
Åñëè
u f f f I f
f
f f
( , )
, ,
, ,
1 2 1 2
2
1 2
0
0 0
0
� � �
�
�
�
"
{ }
òî ïîëó÷àåì ôóíêöèþ U x f x d
f x
( ) ( , ) ( ).
( , )
�
�
'
2 0
1
�
� �P  ÷àñòíîì ñëó÷àå
f x1 ( , )�
f x f x2 ( , ) ( , )� �� èìååì U x f x( ) max , ( , ) .� E { }0 �
Ôóíêöèè U x( ) ñ íåãëàäêèì è ðàçðûâíûì ïîäûíòåãðàëüíûì âûðàæåíèåì
u ( ) ìîãóò áûòü óíèâåðñàëüíûì ñðåäñòâîì äëÿ àíàëèçà âåñüìà ðàçëè÷íûõ ïðîá-
ëåì óïðàâëåíèÿ ðèñêàìè. Äðóãèìè ñëîâàìè, ìîæíî íàçûâàòü òàêèå ôóíêöèè, êàê
U x( ), ñëó÷àéíûìè ôóíêöèÿìè ðèñêà, èëè îáîáùåííûìè ôóíêöèÿìè ïîëåçíîñòè.
Ìîæíî íàçâàòü U x( ) òàêæå îáîáùåííîé îæèäàåìîé ôóíêöèåé ïîëåçíîñòè. Çàìå-
òèì, ÷òî õîòÿ èíäèêàòîðû (41)–(44) îïðåäåëåíû ñ ïîìîùüþ âðåìåíè îñòàíîâêè
�( )x , îíè ìîãóò áûòü òàêæå âûðàæåíû â âèäå Eu R R x R xT( , ( ), , ( ))0 1 � ñ íåêîòî-
ðîé ðàçðûâíîé ôóíêöèåé u ( ) .
3.3. Íåâûïóêëûå çàäà÷è. Ðÿä ïðàêòè÷åñêèõ çàäà÷, òàêèõ êàê îïòèìèçàöèè
òåõíè÷åñêèõ ñèñòåì, ïîäâåðæåííûõ äèñêðåòíîìó âìåøàòåëüñòâó ñëó÷àÿ, ïðèâî-
äÿò ê íåâûïóêëûì íåãëàäêèì (è äàæå ðàçðûâíûì) öåëåâûì ôóíêöèÿì [11]. Òàêèå
ïðèëîæåíèÿ òðåáóþò îáîáùåíèÿ ìåòîäà ñòîõàñòè÷åñêèõ êâàçèãðàäèåíòîâ íà íå-
âûïóêëûå çàäà÷è.
Ïðèìåð 12. Ìèíèìàêñíûé ïðèíöèï ïðèíÿòèÿ ðåøåíèé ïðè ñòîõàñòè÷åñêîé
íåîïðåäåëåííîñòè ïðèâîäèò ê ñëåäóþùåé çàäà÷å:
min [ ( ) max ( , , )],x X y YF x E f x y� �� �
ãäå f x y( , , )� — íåïðåðûâíî äèôôåðåíöèðîâàííàÿ ïî x äëÿ âñåõ ( , )ó � (íå
îáÿçàòåëüíî âûïóêëàÿ) ôóíêöèÿ, âûðàæàþùàÿ ïîòåðè ïðè ðåøåíèè x, âíåø-
íèõ äåòåðìèíèðîâàííûõ ôàêòîðàõ ó Y� è âíåøíåì ñëó÷àéíîì ôàêòîðå �,
X è Y — íåêîòîðûå ìíîæåñòâà. Åñëè ôóíêöèÿ f x y( , , )� íå ÿâëÿåòñÿ âûïóê-
ëîé ïî x (ñêàæåì, òîëüêî íåïðåðûâíî äèôôåðåíöèðîâàííàÿ ïî x), òî öåëåâàÿ
ôóíêöèÿ F x( ) òàêæå ìîæåò áûòü íåâûïóêëîé.
Ïðèìåð 13. Çàäà÷à îïòèìèçàöèè ñðåäíåãî âðåìåíè æèçíè ñåòè èìååò âèä
max [ ( ) max min ( )],x X p P e p epF x E f x� � ��
ãäå p — ïóòü èç ìíîæåñòâà ñåòåé P, ñîåäèíÿþùèõ âõîä è âûõîä ñåòè, f xep ( ) —
ñëó÷àéíîå âðåìÿ æèçíè ýëåìåíòà e ïóòè p.  ýòîì ñëó÷àå ôóíêöèÿ (ïîëåçíî-
ñòè) u t tp P e p ep( ) max min� � � íåâûïóêëàÿ è íåãëàäêàÿ. Ïðîáëåìà çàêëþ÷àåòñÿ
â âû÷èñëåíèè îáîáùåííûõ ñòîõàñòè÷åñêèõ ãðàäèåíòîâ ôóíêöèè F x( ) è íàõîæ-
äåíèè ëîêàëüíîãî è/èëè ãëîáàëüíîãî ìèíèìóìà F x( ) íà X . Äðóãèå ïðèìåðû
íåâûïóêëûõ íåãëàäêèõ çàäà÷ îïòèìèçàöèè ñòîõàñòè÷åñêèõ ñèñòåì ñ äèñêðåò-
íûìè ñîáûòèÿìè îáñóæäàþòñÿ â [11, 13], ãäå ïîêàçàíî, ÷òî íàëè÷èå îïåðàöèé
ìàêñèìóìà è ìèíèìóìà â âûðàæåíèÿõ äëÿ âðåìåííûõ õàðàêòåðèñòèê ñèñòåì
ñ äèñêðåòíûìè ñîáûòèÿìè òèïè÷íà.
Ïðèìåð 14. Ðàññìîòðèì ïðîèçâîäñòâåííóþ ñèñòåìó (ëèíèþ), ñîñòîÿùóþ èç
i n�1 2, , ,� ïîñëåäîâàòåëüíî ñîåäèíåííûõ ñòàíêîâ. Äåòàëü, êîòîðàÿ ïîñòóïàåò
íà ëèíèþ â ñëó÷àéíûé ìîìåíò âðåìåíè �0 , ïîñëåäîâàòåëüíî îáðàáàòûâàåòñÿ
êàæäûì ñòàíêîì. Ïðè ýòîì âðåìÿ îáðàáîòêè � i äåòàëè i-ì ñòàíêîì ñëó÷àéíî.
Ïóñòü ïåðåìåííàÿ xi
îáîçíà÷àåò ìîìåíò âêëþ÷åíèÿ i-ãî ñòàíêà, yi — ìîìåíò,
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
êîãäà îáðàáîòàííàÿ äåòàëü ïîêèäàåò ñòàíîê i . Ïóñòü ai è bi îáîçíà÷àþò ðàñõîäû
ñèñòåìû (â åäèíèöó âðåìåíè), ñâÿçàííûå ñ îæèäàíèåì âêëþ÷åíèÿ i-ãî ñòàíêà è
îáðàáîòêè äåòàëè ýòèì ñòàíêîì ñîîòâåòñòâåííî. Òîãäà îáùèå ñëó÷àéíûå ðàñõî-
äû ñèñòåìû f x yn ( , , )� ìîæíî âû÷èñëèòü ïîñëåäîâàòåëüíî:
f x y f x y a y x b x yi i
i i i i i i( , ) ( , ) max ( , ( )� � � ��1 { },
f 0 0� , y y xi i i
i� ��max ,{ }1 �
äëÿ i n�1, ,� , ãäå x x xn� ( , , )1 � , y y yn� ( , , )1 � , � � �� ( , , )1 � n . Òàêèì îá-
ðàçîì, ôóíêöèè f x yi ( , ) ñòðîÿòñÿ ñ ïîìîùüþ îïåðàöèé max è min (– max) è
ïîýòîìó ÿâëÿþòñÿ íåâûïóêëûìè è íåãëàäêèìè. Ðàçðûâíûå ôóíêöèè èçäåðæåê
âîçíèêàþò â ñëó÷àå ïåðèîäè÷åñêè ðàáîòàþùèõ èëè îòêàçûâàþùèõ ñòàíêîâ.
Ïðîáëåìà çàêëþ÷àåòñÿ â ëîêàëüíîé è/èëè ãëîáàëüíîé ìèíèìèçàöèè ôóíêöèè
îæèäàåìûõ çàòðàò F x Ef x yn( ) ( , )� ïðè îãðàíè÷åíèÿõ x xn1, ,� .
Ïðèìåð 15. Ôóíêöèÿ âèäà F x u f x( ) ( ( ))� E � íàçûâàåòñÿ ôóíêöèåé îæèäàå-
ìîé ïîëåçíîñòè, ãäå u( ) âûðàæàåò ïîëåçíîñòü (äëÿ ëèöà, ïðèíèìàþùåãî ðåøå-
íèå) ðàçíûõ çíà÷åíèé ôóíêöèè âûèãðûøà f ( , ) , çàâèñèìîé îò ðåøåíèÿ x è
ñëó÷àéíûõ ôàêòîðîâ �. Î÷åâèäíî, ôóíêöèÿ ïîëåçíîñòè u f x( ( ))� ìîæåò áûòü íå-
âûïóêëîé ïî x äàæå â ñëó÷àå âûïóêëîé ôóíêöèè f x( )� . Åñëè u( ) ( ) � � , ãäå
�( )t �{0 äëÿ t� 0 è 1 äëÿ t � 0}, òî ñîîòâåòñòâóþùàÿ ôóíêöèÿ îæèäàåìîé ïîëåç-
íîñòè F x( ) ñîâïàäàåò ñ ôóíêöèåé âåðîÿòíîñòè P x P f x( ) ( , )� �{ }� 0 . Î÷åâèäíî,
ôóíêöèÿ âåðîÿòíîñòè ìîæåò áûòü íåãëàäêîé è äàæå ðàçðûâíîé.
Ôóíêöèÿ u( ) ìîæåò áûòü ôóíêöèåé ïðèíàäëåæíîñòè ( ( ) )0 1� �u çíà÷åíèé
âåêòîðíîãî êðèòåðèÿ f íåêîòîðîé ðàçìûòîé öåëåâîé îáëàñòè, òîãäà u f x( ( ))�
âûðàæàåò ñòåïåíü äîñòèæåíèÿ ðàçìûòîé öåëè äëÿ ðåøåíèÿ x, à F x Eu f x( ) ( ( , ))� � —
îæèäàåìóþ ñòåïåíü äîñòèæåíèÿ ðàçìûòîé öåëè.
Îïòèìèçàöèîííûå çàäà÷è äëÿ ïðèâåäåííûõ ïðèìåðîâ èìåþò âèä
min [ ( ) ( , )],x X F x f x� � Ex � (45)
ãäå x — âåêòîð óïðàâëÿåìûõ/îïòèìèçèðóåìûõ ïåðåìåííûõ, � — ñëó÷àéíûé
ïàðàìåòð, îïðåäåëåííûé íà âåðîÿòíîñòíîì ïðîñòðàíñòâå ( , , )� � P , f x( , �� è
F x( ) — ñëó÷àéíàÿ è îæèäàåìàÿ ôóíêöèè ýôôåêòèâíîñòè, X — äîïóñòèìîå
ìíîæåñòâî èç R n .  ýòèõ çàäà÷àõ ñóùåñòâåííî, ÷òî ôóíêöèÿ f ( , ) � íå èìååò
õîðîøèõ àíàëèòè÷åñêèõ ñâîéñòâ, â îáùåì ñëó÷àå îíà ìîæåò áûòü íåâûïóêëîé,
íåãëàäêîé è äàæå ðàçðûâíîé.
 íåêîòîðûõ çàäà÷àõ ôóíêöèÿ ìàòåìàòè÷åñêîãî îæèäàíèÿ F x f x( ) ( , )� E �
ìîæåò áûòü ãëàäêîé, íåñìîòðÿ íà íåãëàäêèå ïîäûíòåãðàëüíûå ôóíêöèè f x( , ��.
Òîãäà äëÿ îïòèìèçàöèè F x( ) ìîæíî ïðèìåíèòü êëàññè÷åñêèé ìåòîä ñòîõàñòè÷åñ-
êîé àïïðîêñèìàöèè. Îòìåòèì, ÷òî ãëàäêîñòü ôóíêöèè F x f x( ) ( , )� E � ìîæåò
áûòü ðàçíîé, â ÷àñòíîñòè F x( ) ìîæåò áûòü äèôôåðåíöèðîâàííîé, íî íå íåïðå-
ðûâíî äèôôåðåíöèðîâàííîé.  ïîñëåäíåì ñëó÷àå íåîáõîäèìî èñïîëüçîâàòü ìå-
òîäû è èäåè íåãëàäêîé îïòèìèçàöèè.
3.4. Ñòîõàñòè÷åñêàÿ íåïàðàìåòðè÷åñêàÿ îïòèìèçàöèÿ è ðîáàñòíûå áàéå-
ñîâñêèå îöåíêè. Ýòîò êëàññ çàäà÷ òåñíî ñâÿçàí ñ èññëåäîâàíèåì áàéåñîâñêèõ
îöåíîê â ñëó÷àå, êîãäà îòñóòñòâóåò ïîëíàÿ èíôîðìàöèÿ îá àïðèîðíîì ðàñïðåäå-
ëåíèè, îäíàêî èìååòñÿ èíôîðìàöèÿ î ïðèíàäëåæíîñòè àïðèîðíîãî ðàñïðåäåëå-
íèÿ íåêîòîðîìó êëàññó ôóíêöèé. Òàêàÿ ñèòóàöèÿ âîçíèêàåò, íàïðèìåð, ïðè îöå-
íèâàíèè íåèçâåñòíûõ ïàðàìåòðîâ íàäåæíîñòè âèñîêîòåõíîëîãè÷åñêèõ ñèñòåì,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 21
êîãäà ñòàòèñòè÷åñêèå âûáîðêè, êîòîðûå êàñàþòñÿ îòêàçîâ ýëåìåíòîâ ñèñòåìû,
î÷åíü ìàëû è ïîýòîìó íåò âîçìîæíîñòè àäåêâàòíî âûáðàòü òî èëè äðóãîå àïðèîðíîå
ðàñïðåäåëåíèå.  ýòèõ óñëîâèÿõ ïðîáëåìà âû÷èñëåíèÿ áàéåñîâñêèõ îöåíîê íåòðèâè-
àëüíà. Ïðè âûáîðå àïðèîðíîé ôóíêöèè ðàñïðåäåëåíèÿ ñïåöèàëèñòû ÷àñòî ðóêîâî-
äñòâîâàëèñü ñîîáðàæåíèÿìè ïðîñòîòû ìàòåìàòè÷åñêîãî àïïàðàòà, ñ ïîìîùüþ êîòîðî-
ãî âû÷èñëÿþòñÿ áàéåñîâñêèå îöåíêè, èñïîëüçóÿ ïðè ýòîì òàê íàçûâàåìûå ñîïðÿæåí-
íûå îöåíêè. Îäíàêî ýòîò ïîõîä î÷åíü ÷àñòî ïðèâîäèò ê ñåðüåçíûì îøèáêàì.
Âî èçáåæàíèå ïðîèçâîëüíîãî âûáîðà àïðèîðíîé ôóíêöèè ðàñïðåäåëåíèÿ
ïðåäëîæåí ìèíèìàêñíûé ïîäõîä. Îñíîâíàÿ åãî èäåÿ ñîñòîèò â òîì, ÷òî çàäàåòñÿ
öåëûé êëàññ àïðèîðíûõ ôóíêöèé ðàñïðåäåëåíèÿ è âûáèðàåòñÿ îöåíêà, êîòîðàÿ
ìèíèìèçèðóåò ñóïðåìóì öåëåâîâîãî ôóíêöèîíàëà â ýòîì êëàññå ôóíêöèé. Ðàçðà-
áîòàíû ìåòîäû ðåøåíèÿ ýòèõ äîñòàòî÷íî ñëîæíûõ çàäà÷ ñòîõàñòè÷åñêîé îïòè-
ìèçàöèè â ôóíêöèîíàëüíûõ ïðîñòðàíñòâàõ, àëãîðèòìû èõ ÷èñëåííîé ðåàëèçà-
öèè, ïðîâåäåíû âû÷èñëèòåëüíûå ýêñïåðèìåíòû. Îñîáîå âíèìàíèå óäåëÿëîñü
ñëó÷àþ, êîãäà èìåþòñÿ îãðàíè÷åíèÿ íà ìîìåíòû èëè êâàíòèëè. Ïðè ýòîì äîêàçà-
íî, ÷òî çàäà÷à ñòîõàñòè÷åñêîé îïòèìèçàöèè ñâîäèòñÿ ê çàäà÷å ëèíåéíîãî ïðî-
ãðàììèðîâàíèÿ. Âû÷èñëåíû ðîáàñòíûå áàéåñîâñêèå îöåíêè, íèæíèå è âåðõíèå
ïðåäåëû äëÿ îöåíîê, êîòîðûå ÿâëÿþòñÿ ìåðîé íåîïðåäåëåííîñòè, ïîðîæäåííîé
îãðàíè÷åííîé àïðèîðíîé èíôîðìàöèåé. Ïîêàçàíî, ÷òî ïðè ðåøåíèè êîíêðåòíûõ
çàäà÷ îöåíèâàíèÿ ïàðàìåòðîâ íàäåæíîñòè ïðåäëîæåííûå ìåòîäû ñóùåñòâåííî
óëó÷øàþò êà÷åñòâî ýòèõ îöåíîê.
Òàêèì îáðàçîì, â çàâèñèìîñòè îò âèäà îãðàíè÷åíèé íà ôóíêöèè ðàñïðåäåëå-
íèÿ îïòèìèçàöèîííûå çàäà÷è, ñôîðìóëèðîâàííûå âûøå, ìîæíî êëàñèôèöèðî-
âàòü ñëåäóþùèì îáðàçîì.
1. Çàäà÷è îïòèìèçàöèè ëèíåéíûõ ôóíêöèîíàëîâ â êëàññå ôóíêöèé ðàñïðåäå-
ëåíèÿ, óäîâëåòâîðÿþùèõ ëèíåéíûì îãðàíè÷åíèÿì â âèäå ðàâåíñòâ:
�( ) ( ) ( ) ( ),H f x dH x
X
� �' 0 inf sup (46)
ïðè îãðàíè÷åíèÿõ
dH x
X
( ) ,�' 1 (47)
� i i
X
iH f x dH x a i m( ) ( ) ( ) , , , , ,� � �' 12 � (48)
ãäå X — êîìïàêòíîå ìíîæåñòâî â ïðîñòðàíñòâå R n .
2. Çàäà÷è îïòèìèçàöèè ëèíåéíûõ ôóíêöèîíàëîâ (24) â êëàññå ôóíêöèé ðàñ-
ïðåäåëåíèé, èìåþùèõ ôèêñèðîâàííûå m ïåðâûõ ìîìåíòîâ
dH x
a
b
( ) ,�' 1 x dH xi
i
a
b
( ) ,�' � i m a b� ��� � � �1, , ,� . (49)
(çàìåòèì, ÷òî çàäà÷è (46)–(49) ÷àñòè÷íî îáñóæäàëèñü â ðàçä. 2.6).
3. Çàäà÷è îïòèìèçàöèè äðîáíî-ëèíåéíûõ ôóíêöèîíàëîâ
�( )
( ) ( )
( ) ( )
( )H
g x dH x
g x dH x
X
X
� �
'
'
1
2
inf sup (50)
â êëàññå ôóíêöèé ðàñïðåäåëåíèé, óäîâëåòâîðÿþùèõ ëèíåéíûì îãðàíè÷åíèÿì
òèïà íåðàâåíñòâ (47), (48).
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
4. Çàäà÷è îïòèìèçàöèè äðîáíî-ëèíåéíûõ ôóíêöèîíàëîâ (50) (ãäå X a b� [ , ] )
â êëàññå ôóíêöèé ðàñïðåäåëåíèÿ, èìåþùèõ ôèêñèðîâàííûå m ïåðâûõ ìîìåíòîâ (49).
5. Ìèíèìàêñíûå çàäà÷è ñ äðîáíî-ëèíåéíûì ôóíêöèîíàëîì
inf sup
y H
X
X
g y x dH x
g x dH x
( )
( , ) ( )
( ) ( )
1
2
'
'
(51)
ïðè îãðàíè÷åíèÿõ íà ôóíêöèè ðàñïðåäåëåíèÿ (47), (48). Ïðè ýòîì ïðåäïîëàãà-
åòñÿ, ÷òî ôóíêöèÿ g y x1 ( , ) âûïóêëà îòíîñèòåëüíî y ïðè ôèêñèðîâàííîì x.
6. Ìèíèìàêñíûå çàäà÷è ñ äðîáíî-ëèíåéíûì ôóíêöèîíàëîì (50) ïðè îãðàíè-
÷åíèÿõ íà ôèêñèðîâàííûå m ïåðâûõ ìîìåíòîâ (49).
Çàäà÷è ïåðâîãî è âòîðîãî òèïîâ âîçíèêàþò ïðè ðåøåíèè çàäà÷è íàõîæäåíèÿ
íèæíåãî è âåðõíåãî ïðåäåëîâ äèàïàçîíà âîçìîæíûõ çíà÷åíèé áàéåñîâñêîãî ðèñ-
êà äëÿ îöåíêè
�
�H x( ) íåèçâåñòíîãî ïàðàìåòðà �.
Çàäà÷è òðåòüåãî è ÷åòâåðòîãî òèïîâ âîçíèêàþò ïðè:
a) ðåøåíèè çàäà÷è ïîèñêà ðîáàñòíîé áàéåñîâñêîé îöåíêè, åñëè íàèõóäøåé
ñ÷èòàåòñÿ òàêàÿ àïðèîðíàÿ ôóíêöèÿ ðàñïðåäåëåíèÿ H * �), êîòîðîé îòâå÷àåò
âåðõíèé ïðåäåë �* äèàïàçîíà ( , )*
*� � âîçìîæíûõ çíà÷åíèé áàéåñîâñêîé îöåíêè;
á) ðåøåíèè çàäà÷è ïîèñêà íèæíåãî �* è âåðõíåãî �*ïðåäåëîâ äèàïàçîíà
( , )*
*� � âîçìîæíûõ çíà÷åíèé àïîñòåðèîðíîé îöåíêè ìàòåìàòè÷åñêîãî îæèäàíèÿ
ïàðàìåòðà � ïðè ôèêñèðîâàííûõ âûáîðî÷íûõ äàííûõ x ;
â) ðåøåíèè çàäà÷è ïîèñêà íèæíåãî � �� ( ( ))
�
H x , âåðõíåãî � �* ( ( ))
�
H x ïðåäå-
ëîâ äèàïàçîíà (� �� ( ( ))
�
H x , � �* ( ( ))
�
H x ) âîçìîæíûõ çíà÷åíèé àïîñòåðèîðíîãî
áàéåñîâñêîãî ðèñêà äëÿ îöåíêè
�
�H .
Ìèíèìàêñíûå çàäà÷è ïÿòîãî è øåñòîãî òèïîâ âîçíèêàþò ïðè ðåøåíèè çàäà-
÷è ïîèñêà ðîáàñòíîé áàéåñîâñêîé îöåíêè, åñëè íàèõóäøåé ñ÷èòàåòñÿ òàêàÿ àïðè-
îðíàÿ ôóíêöèÿ ðàñïðåäåëåíèÿ H * �), êîòîðîé îòâå÷àåò íàèáîëüøåå çíà÷åíèå
àïîñòåðèîðíîãî ðèñêà. Âíóòðåííèìè çàäà÷àìè â ýòèõ ìèíèìàêñíûõ çàäà÷àõ ÿâ-
ëÿþòñÿ îïòèìèçàöèîííûå çàäà÷è òðåòüåãî èëè ÷åòâåðòîãî òèïà. Ïîýòîìó àëãî-
ðèòìû ðåøåíèÿ ìèíèìàêñíûõ çàäà÷ èñïîëüçóþò àëãîðèòìû ðåøåíèÿ çàäà÷
òðåòüåãî èëè ÷åòâåðòîãî òèïà.
Òàêèì îáðàçîì, äëÿ ðåøåíèÿ ïîèñêà ðîáàñòíûõ áàéåñîâñêèõ îöåíîê, à òàêæå
íèæíèõ è âåðõíèõ ïðåäåëîâ íåîáõîäèìî ðàçðàáîòàòü àëãîðèòìû äëÿ ðåøåíèÿ çà-
äà÷ ïåðâûõ ÷åòûðåõ òèïîâ. Ðåøåíèå âñåãî óêàçàííîãî öèêëà ïðîáëåì ïðèâåäåíî
â ðàáîòàõ [35, 36 ].
3.5. Îáùèå îãðàíè÷åíèÿ. Îãðàíè÷åíèÿ (1), äëÿ êîòîðûõ ôóíêöèè F xi ( )
òî÷íî íåèçâåñòíû, ìîãóò ðàññìàòðèâàòüñÿ ñ ïîìîùüþ ôóíêöèé øòðàôîâ, îïåðà-
öèé óñðåäíåíèÿ è ìíîæèòåëåé Ëàãðàíæà. Ðàññìîòðèì çàäà÷ó ìèíèìèçàöèè
F x x X0 ( ), � , ïðè îãðàíè÷åíèÿõ (1). Âìåñòî ýòîãî ìîæíî ìèíèìèçèðîâàòü ôóíê-
öèþ øòðàôà, íàïðèìåð
&( , ) ( ) max{ , ( )}x c F x c F x
i
m
i� �
�
0
1
0
íà X , ãäå c — äîñòàòî÷íî áîëüøàÿ âåëè÷èíà. Åñëè òî÷íûå çíà÷åíèÿ F xi ( ) íå-
äîñòóïíû, çíà÷åíèå max , ( ){ }0 F xi íåèçâåñòíî. Çàìåòèì, ÷òî åñëè F i ÿâëÿþòñÿ
GD-ôóíêöèÿìè, òî &( , ) c — òàêæå GD-ôóíêöèÿ ñ ñóáãðàäèåíòîì &x xF� �0
�
�
c F F
i
m
i
x
imax ,
1
0{ } , ãäå Fx
0 , Fx
i — ñóáãðàäèåíòû F 0 , F i .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 23
Ïðåäïîëîæèì, ÷òî äîñòóïíû ñòàòèñòè÷åñêèå îöåíêè �0 ( )k , � i k( ), óäîâëåò-
âîðÿþùèå (5). Ðàññìîòðèì ïðîöåäóðó SQG ñ âñòðîåííîé îïåðàöèåé óñðåäíåíèÿ,
îïèñàííîé â ï. 1.2:
x x k c F x kk
X
k
k
i
m
i
i�
�
� � �
1 0
1
0� [ ( ( ) max , � ( ) ( ))]� � �{ } ,
� ( ) � ( ) [ ( ) � ( )], : .F k F k k F k i mi i k
i
i� � � � �1 1
�
Ñõîäèìîñòü äàííîãî ìåòîäà ñ âåðîÿòíîñòüþ 1 òðåáóåò óñëîâèé, àíàëîãè÷-
íûõ èñïîëüçóåìûì â (13). Â ýòèõ æå óñëîâèÿõ ñõîäèòñÿ ñëåäóþùàÿ ïðîöåäóðà:
x xk
X
k
k
k� � �1 � [ ],� �
� �
�
k
i
k i
i i
k F F k
k F k
k
k k
� � �
�
0 0
0
( ), max ( ) ,
( ), ( )
( )
åñëè
åñëè .
�
!
"!
Ïðåäïîëîæèì, ÷òî F x i mi ( ), , , ,� 01 � , — âûïóêëûå ôóíêöèè è X — âûïóê-
ëûé êîìïàêò. Ìåòîä ìíîæèòåëåé Ëàãðàíæà äëÿ SQG õàðàêòåðèçóåòñÿ
îòíîøåíèÿìè
x x k k kk
X
k
k i
i
m
i�
�
� � �
*
+
,
,
-
.
/
/
*
+
,
,
-
.
/
/
1 0
1
� � � � �( ) ( ) ( ) , (52)
� �
�i i k ik k k C( ) min[max , ( ) ( ) , ],� � �1 0{ }
ãäå � i k( ), � i k( ) — îöåíêè F xi k( ), F xx
i k( ), êàê â (2), (3); Fx
i — ñóáãðàäèåíòû
F xi ( ); C — äîñòàòî÷íî áîëüøîå çíà÷åíèå; � k ,
k — ðàçìåðû øàãà àïïðîêñè-
ìàöèè.
Ïðîöåäóðó (52) ìîæíî èíòåðïðåòèðîâàòü â êîíòåêñòå íåñòàöèîíàðíîé îïòè-
ìèçàöèè: x k�1 — ðåçóëüòàò îäíîãî øàãà ïðîöåäóðû (6), ïðèìåíÿåìîé ê íåñòàöè-
îíàðíîé ôóíêöèè &( , ) ( ) ( ) ( )k x F x k F xi
i
m
i� �
�
0
1
� ñ SQG � � �0
1
( ) ( ) ( )k k ki
i
m
i�
�
.
Êàê ïîêàçàíî â [15], min ( )
s k
sF x
�
0 ñõîäèòñÿ ê min ( )F x0 (â äîïóñòèìîì ìíîæåñòâå)
ñ âåðîÿòíîñòüþ 1 ïðè óñëîâèè, ÷òî F x0 ( ) ñòðîãî âûïóêëà, �
k k� è (13) óäîâ-
ëåòâîðÿåòñÿ äëÿ | | ( )| |� k 2 , çàìåíÿåìûìè íà
i
m
i k
�
0
2| | ( )| |� . Ñõîäèìîñòü âûïóêëûõ
ôóíêöèé F x0 ( ) (íå îáÿçàòåëüíî ñòðîãî âûïóêëûõ) óñòàíàâëèâàåòñÿ ïðè äîïîëíè-
òåëüíûõ ïðåäïîëîæåíèÿõ íà
k , àíàëîãè÷íûõ (17). Ñõîäèìîñòü ïîñëåäîâàòåëü-
íîñòåé � �s
s
k
s
s
s
k
x
� �
0 0
/ , � � �s
s
k
s
s
k
s
� �
0 0
( ) / , � � �( ) ( ( ), , ( ))s s sm� 1 � , ê ñåäëîâûì
òî÷êàì ôóíêöèè Ëàãðàíæà íå òðåáóåò ñòðîãîé âûïóêëîñòè F x0 ( ) è ðàçíûõ
ðàçìåðîâ øàãà � k ,
k
4. ÊÎÍÅÍÎ-ÐÀÇÍÎÑÒÍÛÅ ÌÅÒÎÄÛ ÇÀÄÀ×È ÎÏÒÈÌÀËÜÍÎÃÎ ÓÏÐÀÂËÅÍÈß
Ðàññìîòðèì íåôîðìàëüíóþ ïîñòàíîâêó çàäà÷ îïòèìàëüíîãî óïðàâëåíèÿ. Èìå-
åòñÿ íåêîòîðàÿ ñèñòåìà, ïîâåäåíèå êîòîðîé õàðàêòåðèçóåòñÿ äâóìÿ âèäàìè ïà-
ðàìåòðîâ: ñîñòîÿíèåì è óïðàâëåíèåì. Òðåáóåòñÿ âûáðàòü ïàðàìåòðû óïðàâëå-
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
íèÿ òàêèì îáðàçîì, ÷òîáû ïîâåäåíèå ñèñòåìû áûëî â íåêîòîðîì ñìûñëå îïòè-
ìàëüíûì. Ïðè ýòîì íà íåå ìîãóò âëèÿòü òàêæå ñëó÷àéíûå âîçìóùåíèÿ èëè
äðóãèå íåóïðàâëÿåìûå ïàðàìåòðû. Åñëè ìîäåëè îïèñûâàþòñÿ ñ ïîìîùüþ äèô-
ôåðåíöèàëüíûõ èëè èíòåãðî-äèôôåðåíöèàëüíûõ óðàâíåíèé, òî îäèí èç ïîäõî-
äîâ äëÿ íàõîæäåíèÿ îïòèìàëüíîãî óïðàâëåíèÿ çàêëþ÷àåòñÿ â ïîñòðîåíèè êî-
íå÷íî-ðàçíîñòíîé àïïðîêñèìàöèè èñõîäíîé çàäà÷è è îöåíêè òî÷íîñòè åå ðå-
øåíèÿ îòíîñèòåëüíî ïåðâîíà÷àëüíîé íåïðåðûâíîé çàäà÷è. Ïðè ýòîì
âîçíèêàþò ñëåäóùèå âîïðîñû.
1. Ïðè êàêèõ óñëîâèÿõ èìååò ìåñòî ñõîäèìîñòü ïîñëåäîâàòåëüíîñòè îïòè-
ìàëüíûõ óïðàâëåíèé ðàçíîñòíûõ àíàëîãîâ, ïîëó÷àåìûõ ïðè íåîãðàíè÷åííîì
óìåíüøåíèè ðàçìåðîâ ñåòêè ðàçáèåíèÿ. Ñëîæíîñòü îáúÿñíÿåòñÿ òåì, ÷òî ïðàâûå
÷àñòè äèôôåðåíöèàëüíûõ óðàâíåíèé è èõ êîýôôèöèåíòû çàâèñÿò îò óïðàâëåíèé,
êîòîðûå ìîãóò áûòü ðàçðûâíûìè ôóíêöèÿìè.
2. Åñëè èìååò ìåñòî óêàçàííàÿ âûøå ñõîäèìîñòü, òî âîçíèêàåò âîïðîñ î ïî-
èñêå îïòèìàëüíîãî óïðàâëåíèÿ êîíå÷íî-ðàçíîñòíîé çàäà÷è.
3. Èññëåäîâàíèå ñêîðîñòè ñõîäèìîñòè îïòèìàëüíûõ óïðàâëåíèé ðàçíîñòíûõ
àíàëîãîâ, ïîñòðîåíèå ðàçíîñòíûõ ñõåì ñ âûñîêèìè ïîðÿäêàìè àïïðîêñèìàöèè.
4. Èññëåäîâàíèå âîïðîñîâ, ñâÿçàííûõ ñ óñòîé÷èâîñòüþ ðàçíîñòíîé ñõåìû
ïðè ôèêñèðîâàííîé ñåòêå ðàçáèåíèÿ.
 ðàáîòàõ [37, 38 ] èññëåäóåòñÿ ÷àñòü èç ïåðå÷èñëåííûõ çàäà÷, ïðè ýòîì
îñíîâíîå âíèìàíèå óäåëÿåòñÿ íàõîæäåíèþ óñëîâèé ñõîäèìîñòè ïî ôóíêöèîíàëó
îïòèìàëüíîãî óïðàâëåíèÿ ðàçíîñòíîãî àíàëîãà ê îïòèìàëüíîìó óïðàâëåíèþ íå-
ïðåðûâíîé çàäà÷è. Ïðè ýòîì èññëåäóþòñÿ îáúåêòû, ïîâåäåíèå êîòîðûõ îïèñû-
âþòñÿ êàê îáûêíîâåííûìè äèôôåðåíöèàëüíûìè óðàâíåíèÿìè, òàê è ñòîõàñòè-
÷åñêèìè â ÷àñòíûõ ïðîèçâîäíûõ. Ðàññìîòðåíû òàêæå ðàçëè÷íûå ïîäõîäû ê ïî-
ñòðîåíèþ ñïåöèàëüíûõ ìåòîäîâ íåëèíåéíîãî è ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ
äëÿ ðåøåíèÿ ðàçíîñòíîãî àíàëîãà çàäà÷è îïòèìàëüíîãî óïðàâëåíèÿ. Ýòè ðàáîòû
ïî ïðàâó ñ÷èòàþòñÿ ïèîíåðñêèìè è ïîëó÷èëè ïðèçíàíèå ñïåöèàëèñòîâ â îáëàñòè
îïòèìàëüíîãî óïðàâëåíèÿ è òåîðèè îïòèìèçàöèè. Äðóãîé êëàññ çàäà÷ îïòèìàëü-
íîãî óïðàâëåíèÿ ìàðêîâñêèìè ñòîõàñòè÷åñêèìè ñèñòåìàìè, òàê íàçûâàåìûìè
ñèñòåìàìè ñ ëîêàëüíûì âçàèìîäåéñòâèåì, â êîòîðîì îñíîâíîå âíèìàíèå óäåëåíî
íàõîæäåíèÿ óñëîâèé ñóùåñòâîâàíèÿ îïòèìàëüíûõ ñòðàòåãèé, àëãîðèòìàì èõ íà-
õîæäåíèÿ è ðàçëè÷íûì ïðèëîæåíèÿì â ðàçëè÷íûõ îáëàñòÿõ ýêîíîìèêè, òåîðèè
ðàñïîçíàâàíèÿ, êîìóíèêàöèîííûõ ñåòåé è ò.ä., ðàññìîòðåí â [39].
ÇÀÊËÞ×ÅÍÈÅ
Ê ñîæàëåíèþ, ìû íå èìåëè âîçìîæíîñòè îõâàòèòü âåñü êðóã çàäà÷, ñâÿçàííûõ
ñ òåîðèåé ñòîõàñòè÷åñêîé îïòèìèçàöèåé, è èçëîæèòü â ïîëíîé ìåðå ïîëó÷åííûå
íàó÷íûå ðåçóëüòàòû óêðàèíñêîé øêîëû. Ìû íå ñòàâèëè öåëüþ äàâàòü ïîëíûå
ôîðìóëèðîâêè íàó÷íûõ ðåçóëüòàòîâ — ýòî íåâîçìîæíî ââèäó îãðàíè÷åííîãî
îáúåìà ñòàòüè (íàïðèìåð, âîïðîñû íåãëàäêîé ñòîõàñòè÷åñêîé îïòèìèçàöèè,
îïòèìàëüíîãî óïðàâëåíèÿ ñòîõàñòè÷åñêèìè ñèñèåìàìè è äðóãèå îïèñàíû äîñòà-
òî÷íî ñæàòî è â íåïîëíîé ìåðå). Ïîäðîáíåå îçíàêîìèòüñÿ ñ íàó÷íûìè èññëåäî-
âàíèÿìè â ýòîé îáëàñòè (è, â ÷àñòíîñòè, ñ ðàáîòàìè ñîòðóäíèêîâ íàøåãî èíñòè-
òóòà) ìîæíî, íàïðèìåð, â ìîíîãðàôèÿõ [14, 40–42]. Ìû ïîïûòàëèñü äîñòàòî÷íî
êðàòêî èçëîæèòü ðÿä ôóíäàìåíòàëüíûõ íàó÷íûõ ðåçóëüòàòîâ â îáëàñòè ñòîõà-
ñòè÷åñêîé îïòèìèçàöèè è åå ðàçëè÷íûõ ïðèëîæåíèé, ïîëó÷åííûõ Þ.Ì. Åð-
ìîëüåâûì, åãî ó÷åíèêàìè è êîëëåãàìè óêðàèíñêîé øêîëû ñòîõàñòè÷åñêîé îïòè-
ìèçàöèè, ñîçäàíííîé Þðèåì Ìèõàéëîâè÷åì Åðìîëüåâûì è ïîëó÷èâøåé øèðî-
êîå ìèðîâîå ïðèçíàíèå.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 25
CÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ.
1. Å ð ì î ë ü å â Þ . Ì . Ìåòîäû ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ. — Ì.: Íàóêà, 1976. —
240 ñ.
2. Å ð ì î ë ü å â Þ . Ì . , Í å ê ð û ë î â à Ç .  . Ìåòîä ñòîõàñòè÷åñêèõ ñóáãðàäèåíòîâ è åãî ïðè-
ëîæåíèÿ // Òåîðèÿ îïòèìàëüíûõ ðåøåíèé. — 1967. — Âûï. 1. — Ñ. 24–47.
3. Å ð ì î ë ü å â Þ . Ì . , Ø î ð Í . Ç . Ìåòîä ñëó÷àéíîãî ïîèñêà äëÿ äâóõýòàïíûõ ñòîõàñòè÷åñ-
êèõ çàäà÷ è åãî îáîáùåíèÿ // Êèáåðíåòèêà. — 1968. — ¹ 1. — Ñ. 90–92.
4. Å ð ì î ë ü å â Þ . Ì . , ß ñ ò ð å ì ñ ê è é À . È . Ñòîõàñòè÷åñêèå ìîäåëè è ìåòîäû â ýêîíîìè-
÷åñêîì ïëàíèðîâàíèè. — Ì.: Íàóêà, 1979. — 253 ñ.
5. E r m o l i e v Y . M . Stochastic Quasigradient Methods. — Numerical Techniques for Stochastic
Optimization , Y. Ermoliev and R.Wets, eds. — Berlin: Springer-Verlag, 1988. — P. 141–185.
6. E r m o l i e v Y . M . Stochastic quasigradient methods in minimax problems, two-stage stochastic
programming: quasigradient method. Stochastic Quasigradient Methods: Applications, Stochastic
Quasigradient Methods: General Theory // Encyclopedia of Optimization / C.A. Floudas,
P.M. Pardalos (eds). — New York: Springer-Verlag, 2009. — P. 3813–3818; 3955–3959;
3807–3813; 3801–3807.
7. Í î ð ê è í  . È . Îá óñëîâèÿõ è ñêîðîñòè ñõîäèìîñòè ìåòîäà ýìïèðè÷åñêèõ ñðåäíèõ â ìàòå-
ìàòè÷åñêîé ñòàòèñòèêå è ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèè // Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. — 1992. — ¹ 2. — C. 107–120 .
8. K n o p o v P . S . , K a s i t s k a y a E . J . Empirical estimates in Stochastic optimization and
identification. — Dordrecht; Boston; London: Kluwer Academ. Publ., 2005. — 250 p.
9. Å ð ì î ë ü å â Þ . Ì . , Ê í î ï î â Ï . Ñ . Ìåòîä ýìïèðè÷åñêèõ ñðåäíèõ â çàäà÷àõ ñòîõàñòè÷åñ-
êîãî ïðîãðàììèðîâàíèÿ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 6. — Ñ. 773–785.
10. K n o p o v P . S . , K a s i t s k a y a E . J . Properties of empirical estimates in stochastic optimization
and identification problems // Annals of Oper. Res. — 1995. — N 56. — P. 225–239.
11. E r m o l i e v Y . M . a n d N o r k i n V . I . On nonsmooth and discontinuous problems of stochastic
systems optimization // European J. of Oper. Res. — 1997. — ¹ 2. — Ð. 230–243.
12. G a i v o r o n s k i A . SQG: Software for solving stochastic programming problems with stochastic
qusigradient methods / S.W. Wallance and W.T. Ziemba (eds) // Appl. of Stochast. Program., SIAM,
MPS, 2005. — P. 38–60
13. Å ð ì î ë ü å â Þ . Ì . , Í î ð ê è í  . È . Ñòîõàñòè÷åñêèé îáîáùåííûé ãðàäèåíòãûé ìåòîä äëÿ
ðåøåíèÿ íåâûïóêëûõ íåãëàäêèõ çàäà÷ ñòîõàñòè÷åñêîé îïòèìèçàöèè // Êèáåðíåòèêà è ñèñòåì-
íûé àíàëèç. — 1998. — ¹ 2. — Ñ. 50–71.
14. E r m o l i e v Y u . M . , W e t s R . (eds.) Techniques for stochastic optimization. — Berlin:
Springer, 1988. — 571 p.
15. Ì è õ à ë å â è ÷ Â . Ñ . , Ã ó ï à ë À . Ì . , Í î ð ê è í Â . È . Ìåòîäû íåâûïóêëîé îïòèìèçàöèè.
— Ì.: Íàóêà, 1987. — 280 ñ.
16. Ó ð ÿ ñ ü å â Ñ . Ï . Àäàïòèâíûå àëãîðèòìû ñòîõàñòè÷åñêîé îïòèìèçàöèè è òåîðèè èãð. — Ì.:
Íàóêà, 1990. — 184 ñ.
17. Í ó ð ì è í ñ ê è é Å . À . ×èñëåííûå ìåòîäû ðåøåíèÿ äåòåðìèíèðîâàííûõ è ñòîõàñòè÷åñêèõ
ìèíèìàêñíûõ çàäà÷. — Êèåâ: Íàóê. äóìêà, 1979. — 176 ñ.
18. Í å ì è ð î â ñ ê è é À . Ñ . , Þ ä è í Ä . Á . Ñëîæíîñòü çàäà÷ è ýôôåêòèâíîñòü ìåòîäîâ îïòèìè-
çàöèè. — Ì.: Íàóêà, 1979. — 384 ñ.
19. Ê à í è î â ñ ê è é Þ . Ì . , Ê í î ï î â Ï . Ñ . , Í å ê ð û ë î â à Ç . Â . Ïðåäåëüíûå òåîðåìû äëÿ
ïðîöåññîâ ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ. — Êèåâ: Íàóê. äóìêà, 1980. — 156 ñ.
20. Å ð ì î ë ü å â Þ . Ì . , Å ð ì î ë ü å â à Ò . Þ . , Ì à ê ä î í à ë ü ä Ã . Í î ð ê è í Â . È . Ïðîáëå-
ìû ñòðàõîâàíèÿ êàòàñòðîôè÷åñêèõ ðèñêîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2001. —
¹ 2. — Ñ. 90–110.
21. R o c k a f e l l a r R . T . , U r y a s e v S . Optimization of conditional value at risk // The Journ. of
Risk. — 2000. — 2, N 3. — Ð. 21–41.
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
22. E r m o l i e v Y . , L e o n a r d i G . Some proposals for stochastic facility locations models //
Mathematical model. — 1982. — 5, N. 5. — P. 407–420.
23. K e y z e r M . , E r m o l i e v Y . Modeling producer decisions in a spatial continuum // The Theory
of Markets / P. Herings, G. Van der Laan, A. Talman (eds.). — Amsterdam; Oxford; New York:
North-Holland, 1999. — P. 281–305.
24. E c k s t e i n J . , B e r t s e k a s D . P . On the Douglas-Rachford splitting method and the proximal
point algorithm for maximal monotone operators // Mathemat. Program. — 1992. — N 55. —
Ð. 293–318.
25. F l a m S . D . Learning equilibrium play: a myopic approach // Comput. Optimiz. and Applic. —
1999. — 14. — Ð. 87–100.
26. C o u r n o t A . Researches into the mathematical principles of the theory of wealth (ed. N. Bacon).
— New York: Macmillan, 1897.
27. E r m o l i e v Y . , N e d e v a C . Stochastic optimization problem with partially known distribution
5 functions. — Laxenburg Austria: Intern. In-t for App. Systems Analysis, 1982. — P. 62–60
28. E r m o l i e v Y u . , G a i v o r o n s k i A . , N e d e v a S . Stochastic optimization problems with
incomplete information on distribution functions // SIAM J. Control Optim. — 1985. — 23, N 56. —
P. 697–716.
29. à ó ï à ë À . Ì . Ñòîõàñòè÷åñêèå ìåòîäû ðåøåíèÿ íåãëàäêèõ ýêñòðåìàëüíûõ çàäà÷. — Êèåâ:
Íàóê äóìêà, 1979. — 150 ñ.
30. N o r k i n V . I . , P f l u g G . C h . , R u s z c z y n s k i A . A branch and bound method for
stochastic global optimization // Math. Program. — 1998. — 83. — P. 425–450.
31. E r m o l i e v Y . M . , N o r k i n V . I . Stochastic optimization of risk functions / K. Marti,
Y. Ermoliev, and G. Pflug (eds.): Dynamic stochastic optimization. — Berlin; Heidelberg: Springer,
2004. — P. 225–247.
32. E r m o l i e v Y . M . , E r m o l i e v a T . Y . , M a c D o n a l d G . J . , N o r k i n V . I . Insurability
of catastrophic risks: the stochastic optimization model // Optimization. — 2000. — 47. —
P. 251–265.
33. E r m o l i e v Y . M . , E r m o l i e v a T . Y . M a c D o n a l d G . , a n d N o r k i n V . I . Stochastic
optimization of insurance portfolios for managing exposure to catastrophic risks // Annals of Oper.
Res. — 2000. — 99. — P. 207–225.
34. Ê è ð è ë þ ê Â . Ñ . Î êëàññå ïîëèýäðàëüíûõ êîãåðåíòíûõ ìåð ðèñêà // Êèáåðíåòèêà è ñèñòåì-
íûé àíàëèç. — 2004. — ¹ 4. — Ñ. 155–167.
35. G o l o d n i k o v A . N . , K n o p o v P . S . , P e p e l y a e v V . A . Investigation of Bayesian
estimates for binomial failure models // Simulation and optimization Methods in Risk and Reliability
Theory. Nova Sci. publ. Inc. / P.S. Knopov and P. Pardalos (eds.). — 2009. — P. 173–220.
36. Ã î ë î ä í è ê î â À . Í . , Å ð ì î ë ü å â Þ . Ì . , Ê í î ï î â Ï . Ñ . îöåíèâàíèå ïàðàìåòðîâ íàä-
åæíîñòè â óñëîâèÿõ íåäîñòàòî÷íîé èíôîðìàöèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010.
— ¹ 3. — Ñ. 109–125.
37. Å ð ì î ë ü å â Þ . Ì . , à ó ë å í ê î  . Ï . , Ö à ð å í ê î Ò . È . Êîíå÷íî-ðàçíîñòíûé ìåòîä â
çàäà÷àõ îïòèìàëüíîãî óïðàâëåíèÿ. — Êèåâ: Íàóê. äóìêà, 1978. — 164 ñ.
38. Å ð ì î ë ü å â Þ . Ì . , ß ø ê è ð Î . Â . , ß ø ê è ð Þ . Ì . Ìåòîäû íåäèôôåðåíöèðóåìîé è ñòî-
õàñòè÷åñêîé îïòèìèçàöèè â ôèçè÷åñêèõ èññëåäîâàíèÿõ. — Êèåâ: Íàóê. äóìêà. — 1995. — 170 ñ.
39. C h o r n e i R . Ê . , D a d u n a H . , K n o p o v P . S . Control of spatially structured random
processes and random fields with applications. — New York: Springer, 2006. — 262 p.
40. M a r t i K , E r m o l i e v Y u . , P f l u g G . (eds). Dynamic stochastic optimization // Lecture Notes
in Economics and Mathematical Systems. — Berlin; Heidelberg; New York: Springer-Verlag, 2003.
— 336 p.
41. M a r t i K . , E r m o l i e v Y . , M a k o w s k i M . , P f l u g G . Modeling and policy issues.
Lecture Notes in Economics and mathematical Systems. — Berlin: Springer, 2006. — 330 p.
42. M a r t i K , E r m o l i e v Y u . , M a k o w s k i M . Coping with uncertainty. Robust solutions.
Lecture Notes in Economics and mathematical Systems. — Berlin; Heidelberg: Springer, 2010. —
277 p.
Ïîñòóïèëà 16.06.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 27
|
| id | nasplib_isofts_kiev_ua-123456789-84247 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T16:14:17Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Кнопов, П.С. Сергиенко, И.В. 2015-07-04T14:50:42Z 2015-07-04T14:50:42Z 2011 О некоторых научных результатах Ю. М. Ермольева и его школы в области современной теории оптимизации / П.С. Кнопов, И.В. Сергиенко // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 3-27. — Бібліогр.: 42 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84247 519.21 Наведено огляд основних результатів, одержаних українськими вченими в області стохастичної оптимізації. Основну увагу приділено роботам вченого та його школи, зокрема квазіградієнтним методам стохастичного програмування, які визнано класичними. Main results obtained by Ukrainian scientists in stochastic optimization are reviewed. Most attention is paid to the results of the scientist and his school in quasigradient stochastic programming methods, which are considered classical. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика О некоторых научных результатах Ю. М. Ермольева и его школы в области современной теории оптимизации Про деякі наукові результати Ю.М. Єрмольєва та його школи в області сучасної теорії оптимізаці On scientific results of Yu.M. Ermoliev and his school in the modern stochastic optimization theory Article published earlier |
| spellingShingle | О некоторых научных результатах Ю. М. Ермольева и его школы в области современной теории оптимизации Кнопов, П.С. Сергиенко, И.В. Кибернетика |
| title | О некоторых научных результатах Ю. М. Ермольева и его школы в области современной теории оптимизации |
| title_alt | Про деякі наукові результати Ю.М. Єрмольєва та його школи в області сучасної теорії оптимізаці On scientific results of Yu.M. Ermoliev and his school in the modern stochastic optimization theory |
| title_full | О некоторых научных результатах Ю. М. Ермольева и его школы в области современной теории оптимизации |
| title_fullStr | О некоторых научных результатах Ю. М. Ермольева и его школы в области современной теории оптимизации |
| title_full_unstemmed | О некоторых научных результатах Ю. М. Ермольева и его школы в области современной теории оптимизации |
| title_short | О некоторых научных результатах Ю. М. Ермольева и его школы в области современной теории оптимизации |
| title_sort | о некоторых научных результатах ю. м. ермольева и его школы в области современной теории оптимизации |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84247 |
| work_keys_str_mv | AT knopovps onekotoryhnaučnyhrezulʹtatahûmermolʹevaiegoškolyvoblastisovremennoiteoriioptimizacii AT sergienkoiv onekotoryhnaučnyhrezulʹtatahûmermolʹevaiegoškolyvoblastisovremennoiteoriioptimizacii AT knopovps prodeâkínaukovírezulʹtatiûmêrmolʹêvataiogoškolivoblastísučasnoíteorííoptimízací AT sergienkoiv prodeâkínaukovírezulʹtatiûmêrmolʹêvataiogoškolivoblastísučasnoíteorííoptimízací AT knopovps onscientificresultsofyumermolievandhisschoolinthemodernstochasticoptimizationtheory AT sergienkoiv onscientificresultsofyumermolievandhisschoolinthemodernstochasticoptimizationtheory |