ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈÅ ÂÛÏÓÊËÎÅ
— ðàçäåë ïðîãðàììèðîâàíèÿ ìàòåìàòè÷åñêîãî, èçó÷àþùèé çàäà÷è ìèíèìèçàöèè, â êîòîðûõ ìèíèìèçèðóåìàÿ ôóíêöèÿ âûïóêëà, à îãðàíè÷åíèÿ çàäàþòñÿ òàêæå âûïóêëûìè ôóíêöèÿìè.  îáùåé ôîðìå çàäà÷à Ï. â. ìîæåò áûòü çàïèñàíà òàê: ìèíèìèçèðîâàòü ô-öèþ

ïðè îãðàíè÷åíèÿõ
ãäå
-
-ìåðíûé âåêòîð,
îò — âûïóêëûå ô-öèè. Çàäà÷è Ï. â. âñòðå÷àþòñÿ â ìàòåìàòè÷åñêîé ýêîíîìèêå, ýëåêòðè÷åñêèõ öåïåé òåîðèè; çàäà÷è àïïðîêñèìàöèè ô-öèé òàêæå ïðåäñòàâëÿþò ñîáîé çàäà÷è Ï. â.  ÷àñòíîñòè, â çàäà÷àõ àïïðîêñèìàöèè ô-öèé ïîÿâëÿþòñÿ òàêèå âûïóêëûå ô-öèè, êîòîðûå íå ÿâëÿþòñÿ äèôôåðåíöèðóåìûìè, îíè òðåáóþò ñïåö. èçó÷åíèÿ.
Ïóñòü
âûïóêëàÿ ô-öèÿ, îïðåäåëåííàÿ ïðè âñåõ õ. Îáîçíà÷èì ÷åðåç
ìí-âî òàêèõ âåêòîðîâ ñ, äëÿ êîòîðûõ ïðè âñåõ ó âûïîëíÿåòñÿ íåðàâåíñòâî:
ãäå
ñêàëÿðíîå ïðîèçâåäåíèå. Ìí-âî
íåïóñòî, âûïóêëî, çàìêíóòî è îãðàíè÷åíî.  ñëó÷àå, åñëè
äèôôåðåíöèðóåìàÿ ô-öèÿ â òî÷êå õ, ìí-âî
ñîñòîèò èç åäèíñòâåííîãî âåêòîðà ñ, ñîâïàäàþùåãî ñ ãðàäèåíòîì ô-öèè
Õàðàêòåðèñòèêà òî÷êè ìèíèìóìà â çàäà÷å Ï. â. äàåòñÿ òåîðåìîé Êóíà — Òàêêåðà: åñëè
ðåøåíèå çàäà÷è Ï. â., òî íàéäóòñÿ òàêèå íåîòðèöàòåëüíûå, íå âñå ðàâíûå íóëþ ÷èñëà
÷òî
Ïðè ýòîì, åñëè
, òî óñëîâèÿ ÿâëÿþòñÿ è äîñòàòî÷íûìè. Ñóùåñòâóåò ðÿä óñëîâèé, ïðè êîòîðûõ ìîæíî ãàðàíòèðîâàòü, ÷òî
. Ïðîñòåéøåå èç íèõ: åñëè ñóùåñòâóåò òî÷êà
òàêàÿ, ÷òî
, òî ìîæíî ïîëîæèòü
.  ýòîì ñëó÷àå òåîðåìà Êóíà — Òàêêåðà ìîæåò áûòü ïåðåôîðìóëèðîâàíà â ñëåäóþùåì ýêâèâàëåíòíîì âèäå. Ïîëîæèì
Òîãäà äëÿ òîãî, ÷òîáû òî÷êà
áûëà ðåøåíèåì çàäà÷è Ï. â., íåîáõîäèìî è äîñòàòî÷íî ñóùåñòâîâàíèå òàêèõ ÷èñåë
, ÷òî
ïðè÷åì íåðàâåíñòâî âûïîëíÿåòñÿ äëÿ âñåõ õ è äëÿ âñåõ
Åñëè âûïîëíÿþòñÿ íåðàâåíñòâà (2), òî ãîâîðÿò, ÷òî òî÷êà
åñòü ñåäëîâàÿ òî÷êà ô-öèè
.
Ïðèâåäåííûå íåîáõîäèìûå óñëîâèÿ ýêñòðåìóìà çàïèñàíû â ãëîáàëüíîé ôîðìå. Îäíàêî èì ìîæíî ïðèäàòü è äèôô. ôîðìó. À èìåííî: äëÿ òîãî, ÷òîáû òî÷êà
áûëà ðåøåíèåì çàäà÷è Ï. â., íåîáõîäèìî, ÷òîáû íàøëèñü òàêèå ÷èñëà
íå âñå ðàâíûå íóëþ, è òàêèå âåêòîðû
, ÷òî
îò. Åñëè
òî óñëîâèÿ ÿâëÿþòñÿ äîñòàòî÷íûìè.
Ñëåäóþùèå ô-ëû äëÿ âû÷èñëåíèÿ ìíîæåñòâ
ïîçâîëÿþò ýôôåêòèâíî çàïèñûâàòü íåîáõîäèìîå óñëîâèå ýêñòðåìóìà â äèôô. ôîðìå: åñëè
òî
. È åñëè
, òî äëÿ ëþáîãî
íàéäóòñÿ òàêèå ÷èñëà
è âåêòîðû
÷òî
. Çäåñü
ìí-âî òåõ èíäåêñîâ
, äëÿ êîòîðûõ
Ýòè ô-ëû ïîçâîëÿþò ñòðîèòü ìí-âà
äëÿ âûïóêëûõ ô-öèé, îáðàçîâàííûõ â ðåçóëüòàòå ñóïåðïîçèöèè äðóãèõ âûïóêëûõ ô-öèé.
 íåêîòîðûõ ñëó÷àÿõ çàäà÷à Ï. â. ìîæåò ñòàâèòüñÿ â äðóãîé ôîðìå, â êîòîðîé îãðàíè÷åíèÿ íà ïåðåìåííûå çàäàíû íå â âèäå ñèñòåìû íåðàâåíñòâ. Ïóñòü òðåáóåòñÿ ìèíèìèçèðîâàòü âûïóêëóþ ô-öèþ
ïðè óñëîâèè, ÷òî õ ïðèíàäëåæèò âûïóêëîìó ìíîæåñòâó X. Ïóñòü òî÷êà
ðåøåíèå çàäà÷è. Îïðåäåëèì âûïóêëûé êîíóñ
êàê ìíîæåñòâî âñåõ ýëåìåíòîâ ó, ïðåäñòàâèìûõ â âèäå
ãäå
Ñîïðÿæåííûé èëè äâîéñòâåííûé îòíîñèòåëüíî
êîíóñ (îáîçíà÷àåòñÿ
) îïðåäåëÿåòñÿ, êàê ìí-âî âñåõ âåêòîðîâ ñ, óäîâëåòâîðÿþùèõ íåðàâåíñòâó
äëÿ âñåõ
Òîãäà äëÿ òîãî,
÷òîáû òî÷êà
áûëà ðåøåíèåì ïîñòàâëåííîé çàäà÷è, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ñóùåñòâîâàë òàêîé âåêòîð
÷òî
Äëÿ ýôôåêòèâíîãî ïîñòðîåíèÿ êîíóñà
ìîæíî âîñïîëüçîâàòüñÿ ñëåäóþùèì ðåçóëüòàòîì: åñëè
âûïóêëàÿ ô-äèÿ è ñóùåñòâóåò òàêàÿ òî÷êà
÷òî
òî êîíóñ
äëÿ îáëàñòè X, ñîñòîÿùåé èç òî÷åê õ òàêèõ, ÷òî
, ñîñòîèò èç åäèíñòâåííîé òî÷êè 0, åñëè
è èç âåêòîðîâ ñ, ïðåäñòàâèìûõ â âèäå
åñëè
Äëÿ ÷èñëåííîãî ðåøåíèÿ çàäà÷è ÃÃ. â. ðàçðàáîòàí ðÿä ýôôåêòèâíûõ àëãîðèòìîâ (ñì. Âîçìîæíûõ íàïðàâëåíèé ìåòîä, Ãèïåðïëîñêîñòè îòñåêàþùåé ìåòîä, Îáîáùåííûõ ãðàäèåíòîâ ìåòîä).
Ëèò.: Ïøåíè÷íûé Á.Í. Íåîáõîäèìûå óñëîâèÿ ýêñòðåìóìà. Ì., 1969 [áèáëèîãð. ñ. 148—151]; Çóõîâèöêèé Ñ. È., Àâäååâà Ë. È. Ëèíåéíîå è âûïóêëîå ïðîãðàììèðîâàíèå. Ì., 1967; Çîéòåíäåéê Ã. Ìåòîäû âîçìîæíûõ íàïðàâëåíèé. Ïåð. ñ àíãë. Ì., 1963 [áèáëèîãð. ñ. 171—1741.
Â. Í. Ïøåíè÷íûé.