Методы оптимизации. Конспект лекций (Буряков) (2010)

Ìîñêîâñêèé Ãîñóäàðñòâåííûé Óíèâåðñèòåòèìåíè Ì. Â. Ëîìîíîñîâàôàêóëüòåò Âû÷èñëèòåëüíîé Ìàòåìàòèêè èÊèáåðíåòèêèÌåòîäû îïòèìèçàöèè.Êîíñïåêò ëåêöèé(V-VI ñåìåñòð)ëåêòîð äîöåíò Ì. Ì. Ïîòàïîâñîñòàâèòåëü (2003) Ì. Ë. Áóðÿêîâ<mib431@mail.ru>äîïîëíèòåëüíûé íàáîð (2010) À . È. Ìåñÿö <month_october@mail.ru>v. 0.064ζ 20.04.2010Ìîñêâà 2010Ñîäåðæàíèå123Òåîðåìû ñóùåñòâîâàíèÿ4Ìåòðè÷åñêèé âàðèàíò òåîðåìû Âåéåðøòðàññà . . . . . . . . .

. . . . . . . . . . .5Ñëàáûé âàðèàíò òåîðåìû Âåéåðøòðàññà9. . . . . . . . . . . . . . . . . . . . . . .Ýëåìåíòû äèôôåðåíöèàëüíîãî èñ÷èñëåíèÿâ íîðìèðîâàííûõ ïðîñòðàíñòâàõ12Ïðîèçâîäíàÿ Ôðåøå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12Ôîðìóëû êîíå÷íûõ ïðèðàùåíèé . . . . . . . . . . . . . . . . . .

. . . . . . . . . .12Ïðèëîæåíèÿ ê çàäà÷àì óïðàâëåíèÿ ëèíåéíûìè äèíàìè÷åñêèìè ñèñòåìàìè14Çàäà÷è óïðàâëåíèÿ ëèíåéíîé äèíàìè÷åñêîé ñèñòåìîé4. . . . . . . . . . . . . . .14Çàäà÷è óïðàâëåíèÿ äèñêðåòíîé ñèñòåìîé ñ êâàäðàòè÷íûìè êðèòåðèÿìè . . . . .18Çàäà÷è óïðàâëåíèÿ ñ ïàðàáîëè÷åñêèìè óðàâíåíèÿìè . . . .

. . . . . . . . . . . .20Ýëåìåíòû âûïóêëîãî àíàëèçà22Òåîðåìà î ëîêàëüíîì ìèíèìóìå âûïóêëîé ôóíêöèè. . . . . . . . . . . . . . . .23Ñèëüíî âûïóêëûé âàðèàíò òåîðåìû Âåéåðøòðàññà . . . . . . . . . . . . . . . . .24Êðèòåðèé âûïóêëîñòè äëÿ äèôôåðåíöèðóåìûõ ôóíêöèé26. . . . . . . . . . . . .Êðèòåðèé ñèëüíîé âûïóêëîñòè äëÿ äèôôåðåíöèðóåìûõ ôóíêöèé. . .

. . . . .28. . . . . . . . . . .29. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32Óñëîâèÿ îïòèìàëüíîñòè â ôîðìå âàðèàöèîííîãî íåðàâåíñòâàÌåòðè÷åñêàÿ ïðîåêöèÿÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïðîåêöèè è å¼ ñâîéñòâà56. . . . .

. . . . . . . .32Ïðîåêöèîííàÿ ôîðìà êðèòåðèÿ îïòèìàëüíîñòè . . . . . . . . . . . . . . . . . . .35Èòåðàöèîííûå ìåòîäû ìèíèìèçàöèè36Ìåòîä ñêîðåéøåãî ñïóñêà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36Íåïðåðûâíûé àíàëîã ìåòîäà ñêîðåéøåãî ñïóñêà . . . . . . .

. . . . . . . . . . . .38Ìåòîä ïðîåêöèè ãðàäèåíòà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39Ìåòîä óñëîâíîãî ãðàäèåíòà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41Ìåòîä Íüþòîíà. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43Ìåòîä ñîïðÿæ¼ííûõ íàïðàâëåíèé (ãðàäèåíòîâ) . . . . . .

. . . . . . . . . . . . .46Ìåòîä ïîêîîðäèíàòíîãî ñïóñêà. . . . . . . . . . . . . . . . . . . . . . . . . . . .49Çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ . . . . . . . . . . . . . . . . . . . . . . . . .51Ñèìïëåêñ-ìåòîä53. . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . .Ìåòîäû ñíÿòèÿ îãðàíè÷åíèé56Ìåòîä øòðàôîâ57. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Ïðàâèëî ìíîæèòåëåé Ëàãðàíæà äëÿ âûïóêëûõ çàäà÷. . . . . . . . . . . . . . .59Ïðàâèëî ìíîæèòåëåé Ëàãðàíæà äëÿ ãëàäêèõ çàäà÷ . . . . . . . . . . .

. . . . . .62Äâîéñòâåííûå ýêñòðåìàëüíûå çàäà÷è . . . . . . . . . . . . . . . . . . . . . . . . .69278Ïðîñòåéøàÿ çàäà÷à îïòèìàëüíîãî óïðàâëåíèÿ.Ïðèíöèï ìàêñèìóìà Ïîíòðÿãèíà72Ïîñòàíîâêà çàäà÷è . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.72Ôóíêöèÿ Ãàìèëüòîíà-Ïîíòðÿãèíà. Ïðèíöèï ìàêñèìóìà . . . . . . . . . . . . . .72Ëèíåàðèçîâàííûé ïðèíöèï ìàêñèìóìà. Ãðàäèåíò ôóíêöèîíàëà77. . . . . . . . .Ðåãóëÿðèçàöèÿ íåêîððåêòíî ïîñòàâëåííûõýêñòðåìàëüíûõ çàäà÷ ïî Òèõîíîâó78A Ïðîãðàììà êóðñà 2002/2003 ó÷åáíîãî ãîäà82Ñïèñîê ëèòåðàòóðû8531Òåîðåìû ñóùåñòâîâàíèÿÎïðåäåëåíèå.M íàçûâàåòñÿ ìåòðè÷åñêèì ïðîñòðàíñòâîì, åñëè íà í¼ìρ : M × M → R1+ , íàçûâàåìîå ìåòðèêîé è óäîâëåòâîðÿþùåå òð¼ìÌíîæåñòâîçàäàíî îòîáðàæåíèåàêñèîìàì:1)ρ(u, v) = ρ(v, u) ∀u, v ∈ M2)ρ(u + v, w) 6 ρ(u, w) + ρ(v, w) ∀u, v, w ∈ M3)ρ(u, v) > 0 ∀u, v ∈ M, ρ(u, v) = 0 ⇔ u = v(ñèììåòðè÷íîñòü);(íåðàâåíñòâî òðåóãîëüíèêà);(íåîòðèöàòåëüíîñòü).Óïðàæíåíèå 1 (3).

Ïðèâåñòè ïðèìåðû ôóíêöèé, íå äîñòèãàþùèõ infíà çàìêíóòîì,íî íå îãðàíè÷åííîì ìíîæåñòâå è îãðàíè÷åííîì, íî íåçàìêíóòîì ìíîæåñòâå.ρÎïðåäåëåíèå. Ïîñëåäîâàòåëüíîñòü {uk } ñõîäèòñÿ ïî ìåòðèêå ρ (uk → u) â ìåòðè÷åñêîì ïðîñòðàíñòâåM,åñëèρ(uk , u) → 0k → ∞.ïðè äàëüíåéøåì â ìåòðè÷åñêèõ ïðîñòðàíñòâàõ åñëèïîñëåäîâàòåëüíîñòüÎïðåäåëåíèå.{uk }ñõîäèòñÿ êu,Ïîñëåäîâàòåëüíîñòüòî áóäåì ãîâîðèòü, ÷òîu áóäåì íàçûâàòü ïðåäåëîì {uk }.{uk } íàçûâàåòñÿ ôóíäàìåíòàëüíîé,àρ(ui , uj ) → 0Îïðåäåëåíèå.ρuk → u,i, j → ∞.ïðèÌåòðè÷åñêîå ïðîñòðàíñòâîåñëèMíàçûâàåòñÿïîëíûì,åñëè ëþáàÿ ôóí-äàìåíòàëüíàÿ ïîñëåäîâàòåëüíîñòü â ýòîì ïðîñòðàíñòâå ñõîäèòñÿ ê ýëåìåíòó èçM.Ïðèìåðû ïîëíûõ ïðîñòðàíñòâ:1.M = Rn ìåòðè÷åñêîå ïðîñòðàíñòâî ñ ìåòðèêîévu nuX= t (ui − vi )2 ;ρ(u, v) = ku − vkRni=12.M = C[a, b] ìíîæåñòâî íåïðåðûâíûõ íà[a, b]ôóíêöèé ìåòðè÷åñêîå ïðîñòðàí-ñòâî ñ ìåòðèêîéρ(f, g) = max |f (x) − g(x)|.a6x6bÎïðåäåëåíèå.J(u) íàçûâàåòñÿ íåïðåðûâíîé [ïîëóíåïðåðûâíîé ñíèçó ] (ïîòî÷êå u0 , åñëè äëÿ ëþáîé ñõîäÿùåéñÿ ê u0 ïîñëåäîâàòåëüíîÔóíêöèÿëóíåïðåðûâíîé ñâåðõó )â{uk } èç U ñóùåñòâóåòlim J(uk ) 6 J(u0 ) (ñì.

ðèñ. 1.)ñòè ýëåìåíòîâïðåäåëlim J(uk ) = J(u0 )k→∞lim J(uk ) > J(u0 )k→∞k→∞U íàçûâàåòñÿ êîìïàêòíûì (ρ-êîìïàêòîì ) â M, åñëè óëþáîé ïîñëåäîâàòåëüíîñòè {uk } èç U ñóùåñòâóåò ñõîäÿùàÿñÿ ê ýëåìåíòó èç U ïîäïîñëåäîâàòåëüíîñòü {ukm }.Çàìå÷àíèå.  êîíå÷íîìåðíîì ïðîñòðàíñòâå (Rn ) ìíîæåñòâî U êîìïàêòíî òîãäà èÎïðåäåëåíèå.Ìíîæåñòâîòîëüêî òîãäà, êîãäà îíî çàìêíóòî è îãðàíè÷åíî.  áåñêîíå÷íîìåðíûõ ïðîñòðàíñòâàõ æåçàìêíóòîñòü è îãðàíè÷åííîñòü ÿâëÿþòñÿ ëèøü íåîáõîäèìûìè óñëîâèÿìè êîìïàêòíîñòè.4J(u)J(u)66q-u0íåïðåðûâíîñòü-u0uïîëóíåïðåðûâíîñòü ñíèçóuJ(u)J(u)66qq-u0uïîëóíåïðåðûâíîñòü ñâåðõóu0íåïðåðûâíîñòè íåò-uÐèñ. 1: ê îïðåäåëåíèþ âèäîâ íåïðåðûâíîñòè.Ââåä¼ì ðÿä îáîçíà÷åíèé, êîòîðûìè ìû áóäåì ïîëüçîâàòüñÿ íà ïðîòÿæåíèè âñåãî êóðñà. ÏóñòüJ(u)- èññëåäóåìàÿ íà ýêñòðåìàëüíîñòü ôóíêöèÿ; òîãäàJ(u) → inf, u ∈ U ∈ M (îñíîâíàÿçàäà÷à)sup J(u) = J ∗ ;inf J(u) = J∗ ,u∈Uu∈UU∗ = {v ∈ U|J(v) = J∗ };u∗ = argmin J(u) ∈ U∗ .u∈UÄîãîâîðèìñÿ, ÷òî â äàëüíåéøåì áóäåì ðàññìàòðâàòü òîëüêî çàäà÷è ìèíèìèçàöèè;ìàêñèìèçàöèÿ ñâîäèòñÿ ê ýòîé çàäà÷å çàìåíîéJíà−J .Ïóñòü M ìåòðè÷åñêîåïðîñòðàíñòâî, ìíîæåñòâî U ⊆ M êîìïàêò, ôóíêöèÿ J(u) ïîëóíåïðåðûâíà ñíèçó íàU.

Òîãäà:Òåîðåìà 1 (ìåòðè÷åñêèé âàðèàíò òåîðåìû Âåéåðøòðàññà).1) J∗ > −∞;2) U∗ 6= ∅;3) èç òîãî, ÷òîJ(uk ) → J∗uk ∈ Uïðèk → ∞,ñëåäóåò, ÷òî ρ(uk , U∗ ) → 0.Äîêàçàòåëüñòâî.J∗ (êîòîðàÿ â îáùåì ñëó÷àå ìîæåò ðàâíÿòüñÿ{uk } ⊆ U òàêàÿ, ÷òî J(uk ) → J∗ ïðè k → ∞.Ïî îïðåäåëåíèþ òî÷íîé íèæíåé ãðàíèè−∞)Òàê êàêñóùåñòâóåò ïîñëåäîâàòåëüíîñòüU êîìïàêò, òî ó ýòîé ïîñëåäîâàòåëüíîñòè ñóùåñòâóåò ïîäïîñëåäîâàòåëüíîñòü5{ukm }òàêàÿ, ÷òîýòîé òî÷êåuukm → u ∈ Uïðèm → ∞.Òîãäà èç ïîëóíåïðåðûâíîñòèJ(u)ñíèçó âñëåäóåò, ÷òî−∞ < J(u) 6 lim J(ukm ) = {ò.ê. {ukm }ï/ï-òü{uk }} = lim J(uk ) = J∗ .k→∞m→∞Òàêèì îáðàçîì,Èç òîãî, ÷òîJ∗ êîíå÷íî (J∗ > −∞).u ∈ U è J(u) 6 J∗ ñëåäóåò,u ∈ U∗ 6= ∅.÷òîÑëåäîâàòåëüíîU∗ 6= ∅.Äîêàæåì òåïåðü òðåòüå óòâåðæäåíèå îò ïðîòèâíîãî. Ïðåäïîëîæèì, ÷òî ñóùåñòâóåò{ukm } òàêàÿ, ÷òî ρ(ukm , U∗ ) > ρ0 > 0.

Òàê êàê U êîìïàêò, òî óïîäïîñëåäîâàòåëüíîñòè ñóùåñòâóåò ïîäïîäïîñëåäîâàòåëüíîñòü {ukm } òàêàÿ, ÷òîlïîäïîñëåäîâàòåëüíîñòüýòîél→∞ρ(ukml , u) → 0äëÿ íåêîòîðîãîu (u ∈ U).Îòñþäà, ñ ó÷¼òîì ïîëóíåïðåðûâíîñòèJ(u)ñíèçó, èìååì:J(u) 6 lim J(ukml ) = lim J(uk ) = J∗ .k→∞l→∞Òî åñòü äëÿ òî÷êèu ∈ U∗ρ(ukml , U∗ ) = inf ρ(ukml , u∗ ) 6 ρ(ukml , u) → 0 ïðè l → ∞.u∗ ∈U∗Ïîëó÷åííîå ïðîòèâîðå÷èå (ïîäïîñëåäîâàòåëüíîñòü ñõîäèòñÿ ê íóëþ, òîãäà êàê ñàìà ïîñëåäîâàòåëüíîñòü îòäåëåíà îò íóëÿ ïîëîæèòåëüíûìρ0 )çàâåðøàåò äîêàçàòåëüñòâîòðåòüåãî óòâåðæäåíèÿ. Òåîðåìà ïîëíîñòüþ äîêàçàíà.Îïðåäåëåíèå.Çàäà÷è, óäîâëåòâîðÿþùèå óñëîâèÿì (âûâîäàì) Òåîðåìû 1 íàçûâàþòêîððåêòíî ïîñòàâëåííûìè â ìåòðè÷åñêîì ïðîñòðàíñòâå M.Óïðàæíåíèå 2 (3). Äîêàçàòü, ÷òî â C[a, b] åäèíè÷íûéøàðU = {kf kC 6 1}ÿâ-ëÿåòñÿ çàìêíóòûì è îãðàíè÷åííûì ìíîæåñòâîì, íî ïðè ýòîì êîìïàêòîì íå ÿâëÿåòñÿ.(Íàïîìíèì, ÷òî ìåòðèêàÏðèìåð.k·kCäëÿ îòðåçêà(êîãäà ìíîæåñòâîU[a, b] îïðåäåëÿåòñÿ êàê kf (x)kC = max |f (x)|.)x∈[a,b]íå êîìïàêò è Òåîðåìà 1 íå ïðèìåíèìà)M = C[−1, 1], ρ(f, g) = max |f (t) − g(t)| = kf − gkC , U = {kf kC 6 1},−16t61J(f ) =w0f (t) dt −−1w1f (t) dt.0U îãðàíè÷åíî è çàìêíóòî, íî íå ÿâëÿåòñÿ êîìïàêòîì (ñì.

Óïðàæíåíèå 2); J(u) íåïðåðûâåí:|J(f ) − J(g)| 6w0|f (t) − g(t)| dt +−1w1|f (t) − g(t)| dt 6 2·kf − gkC0(òî åñòü äàæå Ëèïøèö-íåïðåðûâåí ñ êîíñòàíòîéöèîíàëàJ(u)ðàâåíJ∗ = −2 = J(u∗ )2).Íî â òîæå âðåìÿ ìèíèìóì ôóíê-è, êàê ëåãêî âèäåòü, äîñòèãàåòñÿ íà ôóíêöèè(ñì. ðèñ. 2):u∗ (t) =−1, −1 6 t < 01 06t61661−101t−1Ðèñ. 2:u∗ (t)C[−1, 1],êîìïàêò, íî infêîòîðàÿ, î÷åâèäíî, íå ïðèíàäëåæèò êëàññóÏðèìåð.(êîãäà ìíîæåñòâîUíåòî åñòü ìíîæåñòâîU∗ïóñòî.äîñòèãàåòñÿ)Âîçüì¼ì â ïðåäûäóùåì ïðèìåðå â êà÷åñòâå ôóíêöèîíàëàJ(f ) =r1f (t) dt.Òîãäà−1J∗ = −2, U∗ = {u∗ } =6 ∅, u∗ = u∗ (t) ≡ −1 ∈ U.Îïðåäåëåíèå.

Ëèíåéíîå ïðîñòðàíñòâî L íàçûâàåòñÿ íîðìèðîâàííûì, åñëè ñóùåñòâó1åò òàêàÿ ôóíêöèÿ kuk : L → R , íàçûâàåìàÿ íîðìîé, ÷òî:1)kαuk = |α|·kuk ∀u ∈ L, ∀α ∈ R2)ku + vk 6 kuk + kvk ∀u, v ∈ L3)kuk > 0 ∀u ∈ L, kuk = 0 ⇔ u = 0(íåîòðèöàòåëüíàÿ îäíîðîäíîñòü);(íåðàâåíñòâî òðåóãîëüíèêà);(íåîòðèöàòåëüíîñòü).u = 0 ⇒ kuk = 0, òî kuk íàçûâàþò ïîëóíîðìîé.M, åñëè ñóùåñòâóåòu0 ∈ M è R < 0 òàêèå, ÷òî äëÿ âñåõ u èç U âûïîëíÿåòñÿ óñëîâèå ρ(u, u0 ) 6 R.Îïðåäåëåíèå. Íîðìèðîâàííîå ëèíåéíîå ïðîñòðàíñòâî L, ïîëíîå îòíîñèòåëüíî ìåòðèêè ρ(u, v) = ku − vk, íàçûâàåòñÿ áàíàõîâûì.Îïðåäåëåíèå.

Ëèíåéíîå ïðîñòðàíñòâî L íàçûâàåòñÿ åâêëèäîâûì, åñëè íà í¼ì çàäàíîñêàëÿðíîå ïðîèçâåäåíèå hu, vi : L × L → R1 :Åñëè â ïóíêòå 3) âûïîëíåíî ëèøü óñëîâèåÎïðåäåëåíèå.UÌíîæåñòâî1)hu, vi = hv, ui∀u, v ∈ L2)hu + v, wi = hu, wi + hv, wi3)hαu, vi = α hu, vi4)hu, ui > 0, hu, ui = 0 ⇔ u = 0(ñèììåòðè÷íîñòü);∀u, v, w ∈ L∀u, v ∈ L, ∀α ∈ R ëþáîì åâêëèäîâîì ïðîñòðàíñòâåàρ(u, v) = ku − vkÎïðåäåëåíèå.íàçûâàåòñÿ îãðàíè÷åííûì â(ëèíåéíàÿ îäíîðîäíîñòü);(íåîòðèöàòåëüíîñòü).kuk =phu, ui ÿâëÿåòñÿ íîðìîé (åâêëèäîâîé íîðìîé ), ìåòðèêîé.Åâêëèäîâî ïðîñòðàíñòâîρ(u, v) =íàçûâàåòñÿ(ëèíåéíàÿ àääèòèâíîñòü);ãèëüáåðòîâûì.pH,ïîëíîå îòíîñèòåëüíî ìåòðèêèhu − v, u − viH , äàëüíåéøåì áóêâîéñòðàíñòâà.7Háóäåì îáîçíà÷àòü ãèëüáåðòîâû ïðî-Óïðàæíåíèå 3 (3).Äîêàçàòü, ÷òîrbÿâëÿåòñÿ åâêëèäîâûì ïðîñòðàíñòâîì ñîhu, vi =u(t)v(t) dt, íî íå ÿâëÿåòñÿ ãèëüáåðòîâûì.a(îãðàíè÷åííîå çàìêíóòîå ìíîæåñòâî â ãèëüáåðòîâîì áåñêîíå÷íîìåðíîìñêàëÿðíûì ïðîèçâåäåíèåìÏðèìåð.C[a, b]ïðîñòðàíñòâå, íå ÿâëÿþùååñÿ êîìïàêòîì)  ëþáîì áåñêîíå÷íîìåðíîì ãèëüáðåòîâîì ïðîñòðàíñòâå åäèíè÷íûé øàðU = {u ∈ H : kukH 6 1}íå ÿâëÿåòñÿ êîìïàêòîì.∞È äåéñòâèòåëüíî, âîçüì¼ì ëþáóþ îðòîíîðìèðîâàííóþ ñèñòåìó {ek }k=1 (çäåñü âàæåíôàêò áåñêîíå÷íîìåðíîñòè ïðîñòðàíñòâà).

Òàê êàê íîðìà ek ðàâíà åäèíèöå, òî ek ∈ U. Âñëó÷àå, êîãäàk 6= m,èìååì:kek − em k2H = hek − em , ek − em i = 1 − 2 hek , em i + 1 = 2.Îòñþäà ñëåäóåò, ÷òî ïîñëåäîâàòåëüíîñòü{ek }íå ÿâëÿåòñÿ ôóíäàìåíòàëüíîé, ñëåäî-âàòåëüíî, íèêàêàÿ å¼ ïîäïîñëåäîâàòåëüíîñòü òàêæå íå ÿâëÿåòñÿ ôóíäàìåíòàëüíîé.Ïðèìåðû ãèëüáåðòîâûõ ïðîñòðàíñòâ:1.H = Rn , hu, vi =nPui vi ;i=12.nPH = l2 , u = (u1 , u2 , .