1612726871-fd1970eb57207f2e4883f7549db906ce (Ларин, Плясунов - Примеры и задачи), страница 6

Åñëè ôóíêöèÿ f (x) âûïóêëà íà âûïóêëîì ìíîæåñòâå X , òîmmXXαi xi ) ≤αi f (xi ),f(i=1i=1ãäå xi ∈ X, αi ≥ 0 äëÿ i = 1, m è α1 + . . . + αm = 1.Ýêñòðåìàëüíûå ñâîéñòâà çàäà÷è ìèíèìèçàöèè âûïóêëîé ôóíêöèè f (x) íà âûïóêëîììíîæåñòâå X ñîäåðæàòñÿ â ñëåäóþùèõ óòâåðæäåíèÿõ.Òåîðåìà 7. Åñëè âûïóêëû ôóíêöèÿ f (x) è ìíîæåñòâî X , òî ëþáàÿ òî÷êà ëîêàëüíîãî ìèíèìóìà x∗ ∈ X áóäåò îïòèìàëüíîé äëÿ çàäà÷è ìèíèìèçàöèè ôóíêöèè f (x) íàìíîæåñòâå X .Òåîðåìà 8.

Åñëè âûïóêëû ôóíêöèÿ f (x) è ìíîæåñòâî X , òî ìíîæåñòâî X ∗ îïòèìàëüíûõ òî÷åê çàäà÷è ìèíèìèçàöèè ôóíêöèè f (x) íà ìíîæåñòâå X âûïóêëî.Òåîðåìà 9. Åñëè ôóíêöèÿ f (x) ñòðîãî âûïóêëà íà âûïóêëîì ìíîæåñòâå X è òî÷êàx∗ ∈ X îïòèìàëüíà, òî îíà åäèíñòâåííà, ò. å. äëÿ âñåõ x ∈ X, x 6= x∗ ñïðàâåäëèâîíåðàâåíñòâî f (x) > f (x∗ ).20Áëèçêèå ýêñòðåìàëüíûå ñâîéñòâà èìååò çàäà÷à ìèíèìèçàöèè êâàçèâûïóêëîé ôóíêöèèíà âûïóêëîì ìíîæåñòâå. Ôóíêöèÿ f (x), îïðåäåë¼ííàÿ íà âûïóêëîì ìíîæåñòâå X , íàçûâàåòñÿ êâàçèâûïóêëîé, åñëè äëÿ ëþáûõ x, y ∈ X è α ∈ (0, 1) âûïîëíÿåòñÿ íåðàâåíñòâîf (αx + (1 − α)y) ≤ max(f (x), f (y)). Åñëè ïðè ëþáûõ x 6= y óêàçàííîå íåðàâåíñòâî ÿâëÿåòñÿñòðîãèì, òî ôóíêöèÿ f (x) íàçûâàåòñÿ ñòðîãî êâàçèâûïóêëîé.Ïðèìåð.

Ïîêàçàòü, ÷òî ìíîæåñòâî X = {x ∈ En | Ax ≥ a, Bx = b} âûïóêëî. Çäåñü Aè B ýòî âåùåñòâåííûå ìàòðèöû ðàçìåðà m × n è l × n ñîîòâåòñòâåííî, a ∈ Em , b ∈ El .Ðåøåíèå. Âîçüì¼ì äâå ïðîèçâîëüíûå òî÷êè x, y ∈ X è ïîëîæèì z = αx + (1 − α)y , ãäåα ∈ [0, 1]. Òîãäà Az = αAx + (1 − α)Ay ≥ αa + (1 − α)a = a è Bz = αBx + (1 − α)By =αb + (1 − α)b = b. Çíà÷èò òî÷êà z ëåæèò â X , ò. å. ìíîæåñòâî X âûïóêëî.Çàäà÷è1.

Ïîêàçàòü, ÷òî ïåðåñå÷åíèå ëþáîãî ÷èñëà âûïóêëûõ ìíîæåñòâ âûïóêëî.2. Ïóñòü ôóíêöèè fj (x) (j = 1, m) âûïóêëû íà En . Ïîêàçàòü, ÷òî ìíîæåñòâî X ={x |fj (x) ≤ 0 (i = 1, m)} âûïóêëî.3. Äîêàçàòü, ÷òî ëþáàÿ âûïóêëàÿ ôóíêöèÿ ÿâëÿåòñÿ êâàçèâûïóêëîé. Ïðèâåñòè ïðèìåð,ïîêàçûâàþùèé, ÷òî îáðàòíîå, âîîáùå ãîâîðÿ, íå âåðíî.4. Ïóñòü ôóíêöèè fj (x) (j = 1, m) âûïóêëû íà âûïóêëîì ìíîæåñòâå X . Ïîêàçàòü, ÷òîôóíêöèÿ f (x) = a1 f1 (x) + . .

. + am fm (x) âûïóêëà íà X åñëè aj ≥ 0 (j = 1, m).5. Ïóñòü ôóíêöèè fi (x) (i ∈ I) âûïóêëû íà âûïóêëîì ìíîæåñòâå X . Ïîêàçàòü, ÷òîôóíêöèÿ f (x) = supi∈I fi (x) òàêæå âûïóêëà íà X .6. Ïóñòü B ñèììåòðè÷åñêàÿ ìàòðèöà ðàçìåðà n × n, à p ∈ En . Ïîêàçàòü, ÷òî ôóíêöèÿf (x) = hBx, xi + hp, xi (ñòðîãî) âûïóêëà òîãäà è òîëüêî òîãäà, êîãäà B (ñòðîãî) ïîëîæèòåëüíî îïðåäåëåíà.7. Ïóñòü f (t) âûïóêëàÿ íåóáûâàþùàÿ ôóíêöèÿ íà [a, b] (âîçìîæíî, a = −∞ è/èëè b =+∞).

Ïóñòü g(x) âûïóêëà íà âûïóêëîì ìíîæåñòâå X ⊂ En , ïðè÷¼ì g(x) ∈ [a, b] ïðè âñåõx ∈ X . Äîêàçàòü, ÷òî ôóíêöèÿ h(x) = f (g(x)) âûïóêëà íà X .8. Ïóñòü f (x) âûïóêëà è íåîòðèöàòåëüíà íà íåêîòîðîì âûïóêëîì ìíîæåñòâå X . Äîêàçàòü, ÷òî g(x) = (f (x))p âûïóêëà äëÿ ëþáîãî öåëîãî p ≥ 1.9. Ïóñòü âûïóêëàÿ äèôôåðåíöèðóåìàÿ ôóíêöèÿ f (x) â íåêîòîðîé òî÷êå x1 ∈ En óäîâëåòâîðÿåò ñîîòíîøåíèþ hf 0 (x1 ), x − x1 i ≥ 0 äëÿ ëþáîãî x ∈ En . Äîêàçàòü, ÷òî x1 òî÷êàãëîáàëüíîãî ìèíèìóìà ôóíêöèè f (x).10. Äîêàçàòü, ÷òî âûïóêëàÿ ôóíêöèÿ f (x), îïðåäåë¼ííàÿ íà âûïóêëîì çàìêíóòîì ìíîæåñòâå X è îòëè÷íàÿ îò êîíñòàíòû, äîñòèãàåò ñâîåãî ãëîáàëüíîãî ìàêñèìóìà íà ãðàíèöåìíîæåñòâà X .11.

Ïîêàçàòü, ÷òî äëÿ ëþáîé êâàçèâûïóêëîé ôóíêöèè f (x), îïðåäåë¼ííîé íà âûïóêëîììíîæåñòâå X , è ëþáîãî ÷èñëà λ, ìíîæåñòâî Z = {x ∈ X | f (x) ≤ λ} âûïóêëî.12. Ïîêàçàòü, ÷òî åñëè ôóíêöèè fj (x) (j = 1, m) êâàçèâûïóêëû, òî ìíîæåñòâî Z = {x ∈X | fj (x) ≤ 0 (j = 1, m)} âûïóêëî.13. Äîêàçàòü, ÷òî ôóíêöèÿ f (x) êâàçèâûïóêëà íà âûïóêëîì ìíîæåñòâå X òîãäà è òîëüêîòîãäà, êîãäà ìíîæåñòâî Z(x) = {y ∈ X | f (y) ≤ f (x)} âûïóêëî äëÿ êàæäîãî x ∈ X .14. Äîêàçàòü, ÷òî åñëè f (x) ñòðîãî êâàçèâûïóêëà íà âûïóêëîì ìíîæåñòâå X è x∗ ∈ Xÿâëÿåòñÿ òî÷êîé å¼ ëîêàëüíîãî ìèíèìóìà, òî x∗ ÿâëÿåòñÿ åäèíñòâåííîé òî÷êîé ãëîáàëüíîãîìèíèìóìà ôóíêöèè f (x) íà ìíîæåñòâå X .15.

Ïóñòü f (x) è g(x) âûïóêëàÿ è âîãíóòàÿ ôóíêöèè ñîîòâåòñòâåííî, îïðåäåë¼ííûåíà âûïóêëîì ìíîæåñòâå X , ïðè÷¼ì äëÿ ëþáîãî x ∈ X âûïîëíÿåòñÿ íåðàâåíñòâî f (x) ≥g(x). Äîêàçàòü, ÷òî ñóùåñòâóåò ëèíåéíàÿ ôóíêöèÿ h(x), òàêàÿ ÷òî f (x) ≥ h(x) ≥ g(x) äëÿêàæäîãî x ∈ X .16. Ïðè êàêèõ çíà÷åíèÿõ ïàðàìåòðà a ìíîæåñòâî X áóäåò âûïóêëûì:à) X = {(x, y) ∈ E2 | a(x − y 2 ) = 0, x + y = 1};21á) X = {(x, y) ∈ E2 | a(x − y 2 ) = 0, x + y = a};â) X = {(x, y) ∈ E2 | a(x − y 2 ) ≤ 0, x + y = a};ã) X = {(x, y) ∈ E2 | x2 (a2 + 3a + 2) − y ≥ 0};ä) X = {(x, y) ∈ E2 | ex (a2 − 5a + 6) − y(a2 + 2) ≤ 0};å) X = {(x, y) ∈ E2 | y = eax , y ≤ x};æ) X = {(x, y) ∈ E2 | x2 /(a2 + 1) + (y + a)2 ≤ 1, x2 + (y − 1)2 ≤ a, };ç) X = {(x, y) ∈ E2 | y ≤ ex , y ≤ ax};è) X = {(x, y) ∈ E2 | x + y ≥ 1, y ≤ ax2 };ê) X = {(x, y) ∈ E2 | y ≥ ln x, y ≥ ax, x > 0}?17.

Èññëåäîâàòü ôóíêöèþ f (x) íà âûïóêëîñòü èëè âîãíóòîñòü â îáëàñòè X :à) f (x) = x1 x2 , X = {x | x1 ≥ 0, x2 ≥ 0};á) f (x) = 1/x1 + 1/x2 , X = {x | x1 ≥ 0, x2 ≥ 0};â) f (x) = x2 − |x1 − 2|, X = E2 ;ã) f (x) = x61 + x22 + x23 + x24 + 10x1 + 5x2 − 3x4 − 20, X = E4 ;ä) f (x) = e2x1 +x2 , X = E2 ;å) f (x) = −x52 + x23 /2 + 7x1 − x3 + 6, X = {x | xi ≤ 0, i = 1, 2, 3};æ) f (x) = 3x21 + x22 + 2x23 + x1 x2 + 3x1 x3 + x2 x3 + 3x2 − 6, X = E3 ;ç) f (x) = x31 + 2x23 + 10x1 + x2 − 5x3 + 6, X = {x | xi ≤ 0, i = 1, 2, 3};è) f (x) = 5x21 + x22 /2 + 4x23 + x1 x2 + 2x1 x3 + 2x2 x3 + x3 + 1, X = E3 .18.

Ïðè êàêèõ çíà÷åíèÿõ ïàðàìåòðîâ a, b, c ôóíêöèÿ f (x) áóäåò âûïóêëîé:à) f (x) = ax2 + bx + c;á) f (x) = ax21 + 2bx1 x2 + cx22 ;â) f (x) = ae2x + bex + c?3.2. Êðèòåðèé îïòèìàëüíîñòè; òåîðåìà ÊóíàÒàêêåðàÄàííûé ðàçäåë ïîñâÿù¼í ðàññìîòðåíèþ âîïðîñà îá îïòèìàëüíîñòè íàéäåííîé òî÷êè âîñíîâíîé çàäà÷å âûïóêëîãî ïðîãðàììèðîâàíèÿ.Ðàññìàòðèâàåòñÿ çàäà÷àf (x) −→ min,(1)ãäå X = {x | ϕj (x) ≤ 0 (j = 1, m)}.(2)x∈XÅñëè ôóíêöèè f (x) è ϕj (x) (j = 1, m) âûïóêëû, òî çàäà÷à (1)(2) íàçûâàåòñÿ îñíîâíîéçàäà÷åé âûïóêëîãî ïðîãðàììèðîâàíèÿ.

Ïóñòü çàäàíà íåêîòîðàÿ òî÷êà x∗ ∈ X . Îãðàíè÷åíèå ϕj (x) ≤ 0 íàçûâàåòñÿ àêòèâíûì â ýòîé òî÷êå, åñëè ϕj (x∗ ) = 0. Ìíîæåñòâî èíäåêñîâàêòèâíûõ îãðàíè÷åíèé îáîçíà÷èì ÷åðåçI(x∗ ) = {j ∈ {1, . . . , m} | ϕj (x∗ ) = 0}.ÔóíêöèÿF (x, y) = f (x) +mXyj ϕj (x),j=1îïðåäåë¼ííàÿ äëÿ âñåõ x ∈ En , y ≥ 0, íàçûâàåòñÿ ôóíêöèåé Ëàãðàíæà äëÿ çàäà÷è âûïóêëîãî ïðîãðàììèðîâàíèÿ. Ïàðà (x∗ , y ∗ ), ãäå x∗ ∈ En , y ∗ ≥ 0, íàçûâàåòñÿ ñåäëîâîé òî÷êîéôóíêöèè F (x, y), åñëè F (x∗ , y) ≤ F (x∗ , y ∗ ) ≤ F (x, y ∗ ) äëÿ âñåõ x ∈ En , y ≥ 0.

 äàëüíåéøåìáóäåì ñ÷èòàòü, ÷òî ôóíêöèè f (x) è ϕj (x) (j = 1, m) (è, ñëåäîâàòåëüíî, ôóíêöèÿ Ëàãðàíæà)íåïðåðûâíî äèôôåðåíöèðóåìû.22Òåîðåìà 10. Äëÿ òîãî ÷òîáû òî÷êà x∗ ∈ X áûëà òî÷êîé ãëîáàëüíîãî ìèíèìóìà îñíîâ-íîé çàäà÷è âûïóêëîãî ïðîãðàììèðîâàíèÿ (1)(2), äîñòàòî÷íî ñóùåñòâîâàíèÿ òàêèõ ÷èñåëyj ≥ 0 (j ∈ I(x∗ )), ÷òî âûïîëíÿåòñÿ ðàâåíñòâî−f 0 (x∗ ) =Xyj ϕ0j (x∗ ).j∈I(x∗ )Äðóãèìè ñëîâàìè, åñëè (x∗ , y ∗ ) ñåäëîâàÿ òî÷êà ôóíêöèè Ëàãðàíæà, òî x∗ ýòî òî÷êà ãëîáàëüíîãî ìèíèìóìà äëÿ çàäà÷è âûïóêëîãî ïðîãðàììèðîâàíèÿ. ×òîáû âûïîëíÿëîñüîáðàòíîå óòâåðæäåíèå, íåîáõîäèìî íàëîæèòü äîïîëíèòåëüíîå óñëîâèå íà ìíîæåñòâî X . Åñëè ñóùåñòâóåò òàêàÿ òî÷êà x ∈ X , ÷òî ϕj (x) < 0 äëÿ âñåõ j = 1, m, òî ãîâîðÿò, ÷òî ýòîìíîæåñòâî óäîâëåòâîðÿåò óñëîâèþ ðåãóëÿðíîñòè Ñëåéòåðà.Òåîðåìà ÊóíàÒàêêåðà (äèôôåðåíöèðóåìûé ñëó÷àé).

Åñëè ôóíêöèè f (x) è ϕj (x)(j = 1, m) âûïóêëû, à ìíîæåñòâî X = {x | ϕj (x) ≤ 0 (j = 1, m)} óäîâëåòâîðÿåò óñëîâèÿìðåãóëÿðíîñòè Ñëåéòåðà, òî äëÿ îïòèìàëüíîñòè òî÷êè x∗ ∈ X íåîáõîäèìî è äîñòàòî÷íîñóùåñòâîâàíèÿ òàêèõ ÷èñåë yj ≥ 0 (j ∈ I(x∗ )), ÷òî−f 0 (x∗ ) =Xyj ϕ0j (x∗ ).(3)j∈I(x∗ )Êàê ïîêàçûâàåò ñëåäóþùàÿ òåîðåìà, åñëè âñå îãðàíè÷åíèÿ ëèíåéíû, òî óñëîâèÿ ðåãóëÿðíîñòè Ñëåéòåðà â òåîðåìå ÊóíàÒàêêåðà íå îáÿçàòåëüíû.Òåîðåìà 11. Äëÿ òîãî ÷òîáû òî÷êà x∗ ∈ X áûëà òî÷êîé ãëîáàëüíîãî ìèíèìóìà âûïóêëîé ôóíêöèè f (x) íà ìíîæåñòâå X = {x | haj , xi − bj ≤ 0 (j = 1, m)}, íåîáõîäèìî èäîñòàòî÷íî ñóùåñòâîâàíèå òàêèõ ÷èñåë yj ≥ 0 (j = 1, m), ÷òîX−f 0 (x∗ ) =yj aj .j∈I(x∗ ) Ïðèëîæåíèè ðàññìàòðèâàåòñÿ ìåòîä âîçìîæíûõ íàïðàâëåíèé, â êîòîðîì èñïîëüçóåòñÿñëåäóþùàÿÒåîðåìà 12.

Äëÿ òîãî ÷òîáû òî÷êà x∗ ∈ X áûëà òî÷êîé ãëîáàëüíîãî ìèíèìóìà çàäà÷è âûïóêëîãî ïðîãðàììèðîâàíèÿ (1)(2), äîñòàòî÷íî, ÷òîáû äëÿ âñåõ âåêòîðîâ s, óäîâëåòâîðÿþùèõ ñèñòåìå hϕ0j (x∗ ), si ≤ 0 (j ∈ I(x∗ )), âûïîëíÿëîñü óñëîâèå hf 0 (x∗ ), si ≥ 0.Ðàññìîòðèì ïðèìåðû ïðèìåíåíèÿ ïðèâåä¼ííûõ âûøå òåîðåì. Îáùàÿ ñõåìà ïðîâåðêèîïòèìàëüíîñòè òî÷êè x∗ äëÿ çàäà÷è (1)(2) òàêîâà:1. Óáåäèòüñÿ, ÷òî ðåøàåìàÿ çàäà÷à äåéñòâèòåëüíî ÿâëÿåòñÿ çàäà÷åé âûïóêëîãî ïðîãðàììèðîâàíèÿ (ò.

å., ÷òî âñå ôóíêöèè âûïóêëû è çàäà÷à íà ìèíèìóì).2. Ïðîâåðèòü, ÷òî X óäîâëåòâîðÿåò óñëîâèÿì Ñëåéòåðà (êðîìå ñëó÷àÿ ëèíåéíûõ îãðàíè÷åíèé).3. Ïðîâåðèòü, ÷òî x∗ ∈ X è íàéòè ìíîæåñòâî èíäåêñîâ àêòèâíûõ îãðàíè÷åíèé I(x∗ ).4. Çàïèñàòü è ðåøèòü ñèñòåìó (3). Òî÷êà x∗ áóäåò îïòèìàëüíîé â òîì è òîëüêî â òîìñëó÷àå, åñëè ñèñòåìà (3) èìååò ðåøåíèå y ∗ ≥ 0.√√, 3−2 5 ) â çàäà÷åÏðèìåð 1.

Ïðîâåðèòü íà√îïòèìàëüíîñòü òî÷êèx0 = (0, 2) è x00 = ( 5−12√f (x) = 2x21 + 4x22 − 2x1 x2 − 4( 5 − 2)x1 − 5(2 − 5)x2 −→ min ïðè îãðàíè÷åíèÿõ x21 + x22 ≤4, x21 − x2 ≤ 0, x1 + x2 ≥ 1, x1 ≥ 0.Ðåøåíèå. Ôóíêöèÿ f (x) âûïóêëà, ïîñêîëüêó ìàòðèö൶4 −200f (x) =−2 823ñòðîãî ïîëîæèòåëüíî îïðåäåëåíà. Âûïóêëîñòü ôóíêöèé ϕ1 (x) = x21 + x22 − 4, ϕ2 (x) = x21 −x2 , ϕ3 (x) = −x1 − x2 + 1 è ϕ4 (x) = −x1 òàêæå íåòðóäíî ïðîâåðèòü.Ïîñêîëüêó â òî÷êå x = (0.5, 1) âûïîëíÿþòñÿ íåðàâåíñòâà ϕj (x) < 0 äëÿ âñåõ j = 1, 2, 3, 4,òî ìíîæåñòâî X = {x | ϕj (x) ≤ 0, j = 1, 2, 3, 4} óäîâëåòâîðÿåò óñëîâèþ Ñëåéòåðà.Ïîäñòàâëÿÿ òî÷êè x0 è x00 ïîñëåäîâàòåëüíî â êàæäîå èç îãðàíè÷åíèé, óáåæäàåìñÿ, ÷òîîáå ýòè òî÷êè ëåæàò â X è íàõîäèì ìíîæåñòâà èíäåêñîâ àêòèâíûõ îãðàíè÷åíèé: I(x0 ) ={1, 4}, I(x00 ) = {2, 3}.Ñèñòåìà (3) äëÿ òî÷êè x0 èìååò âèä −f 0 (x0 ) = y1 ϕ01 (x0 ) + y4 ϕ04 (x0 ), ò. å.µ √¶µ ¶µ¶4 √5 − 40−1= y1+ y4.40−5 5 − 6√√Îòñþäà, y1 = (−5 5 − 6)/4, y4 = 4 − 4 5.