Օպտիմիզացիայի մեթոդներ

ՌԱՖԻԿ ԽԱՉԱՏՐՅԱՆ

Օպտիմիզացիայի մեթոդներ

ԵՐԵՎԱՆԻ ՊԵՏԱԿԱՆ ՀԱՄԱԼՍԱՐԱՆ

Ռ. Ա. ԽԱՉԱՏՐՅԱՆ

ՕՊՏԻՄԻԶԱՑԻԱՅԻ

ՄԵԹՈԴՆԵՐ

ՈՒՍՈՒՄՆԱԿԱՆ ՁԵՌՆԱՐԿ

ԵՐԵՎԱՆ

ԵՊՀ ՀՐԱՏԱՐԱԿՉՈՒԹՅՈՒՆ

ՀՏԴ 519.8(07) ԳՄԴ 22.18 ց7 Խ 282

Հրատարակության է երաշխավորել ԵՊՀ ինֆորմատիկայի և կիրառական մաթեմատիկայի ֆակուլտետի գիտական խորհուրդը

Գրախոս՝ ֆիզ. մաթ. գիտ. թեկնածու, դոցենտ Գ. Հակոբյան Խմբագիր՝ ֆիզ. մաթ. գիտ. թեկնածու Ս. Սահակյան

Խաչատրյան Ռ. Ա. Խ 282 Օպտիմիզացիայի մեթոդներ: Ուսումնական ձեռնարկ/ Ռ. Խաչատրյան. -Եր.: ԵՊՀ հրատ., 2014, 134 էջ: Ձեռնարկը նախատեսված է ԵՊՀ ինֆորմատիկայի և կիրառական մաթեմատիկայի ֆակուլտետի ուսանողների համար: Այն կարող է օգտակար լինել նաև բնագիտական ֆակուլտետների ուսանողներին:

ՀՏԴ 519.8(07) ԳՄԴ 22.18 ց7

ISBN 978-5-8084-1921-6 © ԵՊՀ հրատ., 2014 © Խաչատրյան Ռ. Ա., 2014

BOVANDAKOWYOWN

Himnakan gaa arner eoremner

1.1 Naxnakan sahmanowmner . . . . . . . . . . 1.2 qstremowmi a ajin erkrord kargi anhraet ow bavarar paymanner . . .

Gradientayin meod

2.1 Fownkciayi minimizaciayi gradientayin eanakneri ndhanowr nkaragrowyown . 2.2 Qayli kisman eanaki zowgamitowyan eorem . . . . . . . . . . . . . . . . . . . . . . 2.3 G aynacman meod . . . . . . . . . . . . . . 2.4 Apriori meodi zowgamitowyown . . . . . 2.5 Gradienti proyektman meod . . . . . . .

Ow owcik analiz

3.1 Ow owcik bazmowyownneri anjatman eoremner . . . . . . . . . . . . . . . . 3.2 Karaeodori eorem . . . . . . . . . . 3.3 Hellii eorem . . . . . . . . . . . . . . . 3.4 Ow owcik fownkciayi sowbdiferencial 3.5 Kown-Takkeri eorem . . . . . . . . .

..

Lagrani anoro gor akicneri meod

4.1 ptimalowyan a ajin erkrord kargi paymanner . . . . . . . . . . . . . . . . . . 4.2 Lagrani anoro gor akicneri meod (xa  sahmana akowmneri depq) . . .

Variacion haiv

5.1 yleri havasarowm . . . . . . . . . . . . . . 5.2 Lagrani meod variacion havi xndirnerowm . . . . . . . . . . . . . . . . . . 5.3 Variacion havi dasakan izoperimetrik xndir . . . . . . . . . . . . . . . . . . . . . 5.4 qstremowmi bavarar paymanner variacion havi xndirnerowm . . . . . . .

Grakanowyown

NAXABAN

Ays owsowmnakan e nark grva  Er ani pe{ takan hamalsarani informatikayi kira akan maematikayi fakowltetowm heinaki kardaca

dasaxosowyownneri himan vra: e narki npatakn  tal ptimizaciayi oro himnarar meodneri bavarar a ov hamakargva amanakakic aradranq: e nark bakaca  hing glowxneric: A ajin glxowm hama otaki aradrvowm en qs{ tremowmi a ajin erkrord kargi anhraet ow bavarar paymanner o paymanakan ptimizaciayi xndirneri hamar verjavor a ani tara owyownnerowm: Erkrord glowx nvirva  paymanakan o paymanakan ptimizaciayi motavor meodnerin: Nkaragrvowm en gradientayin meodner nrancowm qayli ntrowyan a avel haax gtagor vo kisman, apriori amenaarag vayrjqi eanakner: Errord glxowm apacowcvowm  Kown- Takkeri eorem orpes minimowmi anhraet ow bavarar payman ow owcik ragravorman xndirneri hamar: Ays glxowm trvowm en na oro himnarar eoremner ow owcik analizic, oronq ownen kira akan layn nanakowyown: orrord glxowm aradrvowm  maematikakan ragravorman xndirneri low man Lagrani anoro gor akicneri meod, erb sahmana akowmner trva

en havasarowyownnerov anhavasarowyownnerov: Hingerord glxowm ditarkvowm en variacion havi parzagowyn izoperimetrik xndirner arta vowm  yleri havasarowm orpes qstremowmi anhraet payman:

Yowraqanyowr dasaxosowyan verjowm bervowm en xndirner varowyownner, oronc low owmner ow{ sanoin kgnen aveli lav yowracnel aradrva nyow: e narkowm kan na a ajadranqner, oronq karo en irakanacvel hamakargi gnowyamb: eoremi apacowyc sksvowm  I nanov, isk J nan azdararowm  apacowyci avart: norhakalowyown enq haytnowm EPH vayin analizi maematikakan modelavorman ambioni a{ xatakicnerin` e narkowm nerkayacva nyowi bovandakowyan aradrman eanakneri het kapva

harcerowm gtakar a ajarkowyownneri ditoowyownneri hamar: .A. Xaatryan

HIMNAKAN N ANAKOWMNERI CANK

tarr patkanowm  X bazmowyan X ∩ Y − bazmowyownneri hatowm X ∪ Y − bazmowyownneri miavorowm X\Y − bazmowyownneri tarberowyown

ˆ x ∈ X− x ˆ ˆ ˆ

ˆ X + Y = {z/z = x + y, x ∈ X, y ∈ Y }− ˆ ˆ ˆ ˆ ˆ ˆ ˆ

bazmowyownneri hanrahavakan gowmar X− X bazmowyan akowm intX− X bazmowyan nerqin keteri bazmowyown Rn − n a ani vklidyan tara owyown P (x, y) = ni=1 xi yi − x, y ∈ Rn vektorneri skalyar artadryal p kxk = (x, x)− x ∈ Rn vektori norm Br (a) = {x ∈ Rn /kx − ak ≤ r}− a kentronov r a avov gownd C 1 [a, b]− [a, b] hatva i vra orova anndhat diferenceli fownkcianeri tara owyown het yal normov. ky(·)k1 = max{ max |y(x)|, max |y 0 (x)|} x∈[a,b]

x∈[a,b]

vayin fownkcia, or bavararowm  het yal paymanin.

ˆ o(α)−

o(α) =0 α→0 α lim

Glowx 1

Himnakan gaa arner eoremner Ays glxowm bervowm en oro sahmanowmner eoremner ow owcik analizic: Ditarkvowm  oork fownkciayi minimizaciayi xndir Rn vklidyan tara owyan vra: aradrvowm en ptimalowyan a ajin ow erkrord kargi anhraet ow bavarar paymanner: Enadrvowm , or nerco ano  maematikakan analizi g ayin hanrahavi himnarar gaa arnerin:

1.1

Naxnakan sahmanowmner

Dicowq f (x) = f (x1 , x2 , ... , xn ) n o oxakani fownkcia ` orova Rn vklidyan tara owyan vra: Ee f fownkcian, st bolor o oxakanneri, owni masnaki a ancyalner x ∈ Rn ketowm, apa nra gradient ayd ketowm nanakvowm  het yal kerp. f 0 (x) ≡ (fx0 1 (x), fx0 2 (x), ..., fx0 n (x)) :

Sahmanowm 1.1.1: Dicowq f (x)- erkow angam diferenceli fownkcia  x ∈ Rn ketowm: Het yal simetrik matric kovowm  hesian fx001 x1 (x) fx001 x2 (x)  fx00 x (x) fx00 x (x) 2 1 2 2 H(x) =   fx00n x1 (x) fx00n x2 (x) 

Dicowq



a11 a12  a21 a22 A=  ... ... an1 an2

 ... fx001 xn (x) ... fx002 xn (x)  :  ... fxn xn (x)

 ... a1n ... a2n   ... ...  ... ann

kamayakan matric : Sahmanowm 1.1.2: A matrici k-rd kargi glxavor minor kovowm  i1 < i2 < ... < ik hamarnerov toeri ayd nowyn hamarnerov syowneri hatman teerowm gtnvo tarreric kazmva oroi: Sahmanowm 1.1.3: (Ax, x) qa akowsayin   kovowm ` ˆ drakan oroyal (A > 0), ee (Ax, x) > 0 6= 0, x ∈ Rn ,

∀x 6=

ˆ drakan kisaoroyal (A ≥ 0), ee (Ax, x) ≥ ≥ 0 ∀x ∈ Rn , ˆ bacasakan oroyal (A < 0), ee (Ax, x) < < 0 ∀x 6= 0, x ∈ Rn , ˆ bacasakan kisaoroyal (A ≤ 0), ee (Ax, x) ≤ ≤ 0 ∀x ∈ Rn :

Kar or kira akan nanakowyown owni het yal pndowm (te|s, rinak` [10]): eorem 1.1.1 (Silvestri haytani) : Dicowq A(n × n) simetrik matric :

1) Orpeszi A matric lini drakan oroyal, anhraet  bavarar, or nra glxavor ankyownag ayin minorner linen drakan` ∆1 = a11 > 0, ∆2 =

∆n =

a11 a12 a21 a22 ... ... an1 an2

a11 a12 a21 a22 ... a1n ... a2n ... ... ... ann

> 0, ...,

>0:

2) Orpeszi A matric lini bacasakan oroyal, anhraet  bavarar, or ∆1 < 0, ∆2 > > 0, ..., (−1)n ∆n > 0 :

3) Orpeszi A matric lini drakan kisaoroyal, anhraet  bavarar, or nra glxavor minorner linen o bacasakan: 4) Orpeszi A matric lini bacasakan kisa oroyal, anhraet  bavarar, or zowyg kargi glxavor minorner linen o bacasakan, isk kent kargi glxavor minorner linen o drakan:

Sahmanowm 1.1.4: M ⊆ Rn bazmowyown kovowm  ow owcik, ee cankaca x1 , x2 ∈ M keteri cankaca α ∈ [0, 1] vi hamar tei owni het yal` αx1 + (1 − α)x2 ∈ M :

Sa nanakowm , or bazmowyan patkano erkow keter miacno hatva  nka  ayd nowyn baz{ mowyan mej: Sahmanowm 1.1.5: f (x) fownkcian M ⊆ Rn ow owcik bazmowyan vra kovowm  ow owcik, ee cankaca

x1 , x2 ∈ M keteri cankaca α ∈ [0, 1] vi hamar tei owni f (αx1 + (1 − α)x2 ) ≤ αf (x1 ) + (1 − α)f (x2 )

(1.1.1)

anhavasarowyown: eorem 1.1.2: Dicowq f - ow owcik fownkcia  M ⊆ ⊆ Rn ow owcik bazmowyan vra diferenceli  x∗ ∈ M ketowm: Ayd depqowm f (x) − f (x∗ ) ≥ (f 0 (x∗ ), x − x∗ ) ∀x ∈ M :

(1.1.2)

st ow owcik fownkciayi (1.1.1) sahmanman` kamayakan x ∈ M vektori cankaca α ∈ [0, 1] vi hamar ownenq I

f (αx + (1 − α)x∗ ) ≤ αf (x) + (1 − α)f (x∗ )

anhavasarowyown: Aysteic, havi a nelov, or fownkcian diferenceli  x∗ ketowm, kstananq f (x) − f (x∗ ) ≥

f (x∗ + α(x − x∗ )) − f (x∗ ) = α

f

(f 0 (x∗ ), α(x − x∗ )) + o(α) o(α) = (f 0 (x∗ ), x − x∗ ) + : α α Ancnelov sahmani, erb α → 0, kstananq pahanjvo anhavasarowyown: (1.1.2)- kovowm  ow owcik fownk=

ciayi himnakan anhavasarowyown: Da nanakowm , or ee f ow owcik fownkcian di{ ferenceli  x∗ ketowm, apa nra grafik gtnvowm  (x∗ , f (x∗ )) ketov tarva oa o harowyownic ver :

J

Sahmanowm 1.1.6: f (x) fownkcian M ⊆ Rn ow owcik bazmowyan vra kovowm  owe ow owcik θ > 0 hastatownov, ee f (x1 )−f (x2 ) ≥ (f 0 (x2 ), x1 −x2 )+θkx1 −x2 k2 ∀x1 , x2 ∈ M :

Ee fownkcian erkow angam anndhat diferenceli , apa nra ow owcikowyown amboj tara owyan vra kareli  stowgel hesiani nani mijocov: Ayd masin  het yal pndowm (te|s, rinak` [8]): eorem 1.1.3: Dicowq f - erkow angam anndhat diferenceli  Rn -i vra: Ayd depqowm`

a) ee H(x) ≥ 0 ∀x ∈ Rn , apa f - ow owcik fownkcia  Rn -i vra, b) ee (H(x)h, h) ≥ θkhk2 ∀x, h ∈ Rn , apa f - owe ow owcik  θ hastatownov Rn -i vra:

Dicowq trva  f (x) fownkcian enabazmowyown  Rn - ic:

Rn -i

vra

M -

Sahmanowm 1.1.7: x∗ ∈ M ket kanvanenq`

1) f -i global minimowmi (global maqsimowmi) ket M bazmowyan vra, ee f (x) ≥ f (x∗ ) (f (x) ≤ f (x∗ )) ∀x ∈ M,

2) f -i lokal minimowmi (lokal maqsimowmi) ket M bazmowyan vra, ee goyowyown owni ayd keti aynpisi V rjakayq, or f (x) ≥ f (x∗ ) (f (x) ≤ f (x∗ )) ∀x ∈ M ∩ V :

Fownkciayi minimowmi maqsimowmi keter kovowm en qstremowmi keter:

Tesakan kar or nanakowyown ownen het yal eoremner, oronq berowm enq a anc apacowyci (te|s, rinak` [4]): eorem 1.1.4: Ow owcik bazmowyan vra ow owcik fownkciayi lokal minimowmi ket handisanowm  na global minimowmi ket: eorem 1.1.5: Owe ow owcik fownkcian ak ow owcik bazmowyan vra owni miak minimowmi ket ayd bazmowyan vra: eorem 1.1.6: Dicowq M ⊆ Rn ow owcik kompakt , isk f (x)- ow owcik fownkcia ` orova Rn -i vra: Ee f - M -i vra hastatownic tarber , apa na ayd bazmowyan vra hasnowm  ir me agowyn areqin miayn M -i ezrayin keterowm:

XNDIRNER

1. Dicowq M - ow owcik bazmowyown : Apacowcel, or (α1 + α2 )M = α1 M + α2 M ∀α1 ≥ 0, ∀α2 ≥ 0 :

2. Hnaravor  ardyoq, or erkow o ow owcik bazmow{ yownneri hanrahavakan gowmar lini ow owcik: 3. Hnaravor  ardyoq, or ow owcik o ow owcik bazmowyownneri hanrahavakan gowmar lini ow owcik: 4. Dicowq M - ow owcik bazmowyown : Apacowcel, or a)

intM = M ,

b)

M -

g)

intM = intM :

ow owcik ,

5. Apacowcel, or erb bazmowyown ak , ansah{ mana ak ow owcik, apa nra kamayakan ketov kareli  tanel a agay, orn ambojovin nka

klini ayd bazmowyan mej: 6. Owsowmnasirel het yal fownkciayi ow owcikowyown. f (x1 , x2 ) = x21 − 4x1 x2 + 4x22 :

7. Owsowmnasirel het yal fownkciayi ow owcikowyown. f (x1 , x2 , x3 ) = x1 x3 − x21 − x22 :

6. Cowyc tal, or q f (x1 , x2 ) = 1 + x21 + x22

fownkcian ow owcik  R2 -i vra: 8. Nkaragrel bazmowyown, ori vra f (x1 , x2 ) =

x21 x2

fownkcian lini ow owcik: 9.

a, b, c,

parametreri inpisi areqneri depqowm f (x1 , x2 ) = ax21 + bx1 x2 + cx22

fownkcian klini ow owcik R2 -i vra: 10.

f (x) fownkciayi vergrafik M

ow owcik bazmowyan vra kovowm  het yal bazmowyown. epi(f ) ≡ {(α, x) ∈ Rn+1 /x ∈ M, α ≥ f (x)} :

Apacowcel het yal pndowm: Orpeszi f - lini ow owcik M ow owcik bazmowyan vra, anhraet  bavarar, or nra vergrafik lini ow owcik bazmowyown:

11. Dicowq f (x)- ow owcik fownkcia ` orova

ow owcik bazmowyan vra i

x ∈ M, αi ≥ 0, i ∈ [1 : m],

m X

M

αi = 1 :

i=1

Apacowcel, or m m X X i f( αi x ) ≤ αi f (xi ) : i=1

i=1

Ays anhavasarowyown kovowm  Yenseni anhavasarowyown: 12. Dicowq f (x) ow owcik fownkcian sahmana ak  Rn -i vra: Apacowcel, or f - hastatown :

1.2

qstremowmi a ajin erkrord kargi anhra{ et ow bavarar paymanner

eorem 1.2.1 (qstremowmi a ajin kargi anhra{ et payman): Dicowq x∗ - f (x) fownkciayi lokal minimowmi (lokal maqsimowmi) ket  Rn -i vra f - diferenceli  ayd ketowm: Ayd depqowm f fownkciayi gradient x∗ ketowm havasar  zroyi, aysinqn f 0 (x∗ ) = 0, kam, or nowynn ` fx0 i (x∗ ) = 0, i ∈ [1 : n] : I Qani or x∗ - lokal minimowmi (lokal maqsimowmi) ket ,

apa gtvelov fownkciayi diferenceliowyan paymanic,

kamayakan h vektori hamar kownenanq

bavakanaa

oqr

veri

α

0 ≤ f (x∗ + αh) − f (x∗ ) = (f 0 (x∗ ), αh) + o(α) :

Baanelov ays anhavasarowyan erkow maser vi vra gtecnelov α-n zroyi` kstananq

α > 0

(f 0 (x∗ ), h) ≥ 0 ((f 0 (x∗ ), h) ≤ 0) ∀h ∈ Rn :

Aysteic anmijakanoren het owm , or f 0 (x∗ ) = 0 : J

eorem 1.2.2 (Minimowmi a ajin kargi anhraet ow bavarar payman ow owcik fownkciayi hamar): Dicowq f - ow owcik fownkcia  orova Rn -i vra diferenceli  x∗ ketowm: Orpeszi x∗ - lini f -i minimowmi ket Rn -i vra anhraet  bavarar, or f 0 (x∗ ) = 0 : I Anhraetowyown het owm  eorem 1.2.1-ic:

Apacowcenq bavararowyown: gtvelov ow owcik fownkcayi himnakan anhavasarowyownic` stanowm enq f (x) − f (x∗ ) ≥ (f 0 (x∗ ), x − x∗ ) = 0, ∀ x ∈ Rn :

Aysteic het owm , or vra:

x∗ - f -i

minimowmi ket 

Rn -i

J

eorem 1.2.3 (qstremowmi erkrord kargi anh{ raet payman): Dicowq x∗ - f fownkciayi lokal minimowmi (lokal maqsimowmi) ket  Rn -i vra f - erkow angam diferenceli  ayd ketowm:

Ayd depqowm H(x∗ )- drakan kisaoroyal  (bacasakan kisaoroyal ), aysinqn H(x∗ ) ≥ 0 (H(x∗ ) ≤ 0) :

Qani or x∗ - lokal minimowmi (lokal maqsimowmi) ket , isk f - erkow angam diferenceli  ayd ketowm, apa kamayakan h ∈ Rn vektori bavakanaa

oqr α veri hamar ownenq I

0 ≤ f (x∗ + αh) − f (x∗ ) = 1/2(H(x∗ )αh, αh) + o(α2 ) :

Baanelov ays anhavasarowyan erkow maser α2 vi vra gtecnelov α-n zroyi` kstananq pahanjvo anhavasarowyown: J

eorem 1.2.4 (qstremowmi erkrord kargi bavarar paymanner): Dicowq f (x) fownkcian erkow angam diferenceli  x∗ ketowm tei ownen het yal paymanner` f 0 (x∗ ) = 0, H(x∗ ) > 0 (H(x∗ ) < 0) :

Ayd depqowm x∗ - f -i lokal minimowmi (lokal maq{ simowmi) ket  Rn -i vra:

I Enadrenq haka ak: Da nanakowm , or go{ yowyown owni {xk } hajordakanowyown, orr bavararowm  het yal paymannerin. xk → x∗ , f (xk ) < f (x∗ ) (f (xk ) > f (x∗ )) :

Nanakelov αk = kxk − x∗ k,

hk = (xk − x∗ )/αk , kownenanq

xk = x∗ + αk hk :

Qani or khk k = 1, apa ndhanrowyown xaxtelov karo enq enadrel, or hk → h0 6= 0 : Havi a nelov eoremi enadrowyan f 0 (x∗ ) = 0 payman` kownenanq 0 ≥ f (xk ) − f (x∗ ) = 1/2(H(x∗ )αk hk , αk hk ) + o(αk2 ) :

Baanelov ays anhavasarowyown erkow maser vra ancnelov sahmani` kstananq

αk2 -i

(H(x∗ )h0 , h0 ) ≤ 0 (H(x∗ )h0 , h0 ) ≥ 0),

or hakasowm  eoremi enadrowyan: J

Parzagowyn depqerowm qstremowmi a ajin erk{ rord kargi anhraet ow bavarar paymanner fektiv mijocner en fownkciayi qstremowmi keter grit gtnelow hamar: rinak: Gtnel f (x) = x31 + x22 + x23 + x2 x3 − 3x1 + 6x2 + 2

fownkciayi qstremowmi keter R3 -i vra: Low owm: st minimowmi anhraet paymani` ownenq fx0 1 = 3x21 −3 = 0, fx0 2 = 2x2 +x3 +6 = 0, fx0 3 = 2x3 +x2 = 0 :

Low elov ays hamakarg, kstananq erkow stacionar ket` x1 = (1, −4, 2)

x2 = (−1, −4, 2) :

Ownenq na , or fx001 x1 = 6x1 , fx001 x2 = 0, fx001 x3 = 0, fx002 x2 = 2, fx002 x3 = 1, fx003 x3 = 2 :

Aym yowraqanyowr stacionar keti hamar kareli  kazmel hesian stowgel nra nan: x1 keti hamar hesian owni het yal tesq. 

 6 0 0 H(x1 ) =  0 2 1  : 0 1 2

Qani or ∆1 = 6, ∆2 =

6 0 0 6

= 12 > 0, ∆3 = 18 > 0,

apa x1 - lokal minimowmi ket : Owsowmnasirenq x2 ket: Ayd ketowm hesian owni het yal tesq. 

 −6 0 0 H(x2 ) =  0 2 1  : 0 1 2

Qani or ∆1 = −6 < 0, ∆2 = −12 < 0, ∆3 = −18 < 0, apa qstremowmi bavarar paymanner tei ownen: Stowgenq erkrord kargi anhraet paymanner: A ajin kargi glxavor minornern en` −6, 2, 2 ver: Erkrord kargi glxavor minornern en` 3, −12, −12: Errord kargi glxavor minor havasar  ∆3 -i, or bacasakan : Ayspisov, x2 ketowm qstremowmi erkrord kargi anhraet paymanner en katarvowm: Het a{ bar, x2 ket qstremowmi ket :

XNDIRNER

1. Gtnel f (x) fownkciayi qstremowmi keter. f (x) = x31 + x22 + x23 − 4x1 x2 + 3x1 + 2x3 → extr :

2. Stowgel, ardyoq (1, 1) ket het yal fownkciayi qstremowmi ket , e o. f (x) = (x2 − x1 )2 + (1 − x1 )2 + 10(x2 − 1)2 :

Glowx 2

Gradientayin meod Gradientayin meod dasvowm  diferenceli fownkcianeri minimizaciayi vayin himnakan meodneri arqin: Ayd meodi owyown at parz : Ee f (x) fownkcian diferenceli , apa nra hakagradient` h = −f 0 (x) vektor, yowraqanyowr x ketowm cowyc  talis fownkciayi nvazman owowyown: Da himq  talis enadrel, or kamayakan skzbnakan x ketic sksvo xk+1 = xk − αk f 0 (xk ) (αk > 0) ekow{ rent a nowyamb ka owcva hajordakanowyan andamner me k indeqsneri depqowm mot klinen f -i minimowmi ketin: Ayste ays enadrowyown himnavorvowm  oro dasi fownkcianeri αk veri hatowk eanaknerov ntrowyownneri depqerowm: Fownkciayi minimizaciayi bazmazan algorimneri nranc praktik irakanacowmneri het kareli  anoanal [3, 4, 6 ] axatanqnerowm:

2.1

Fownkciayi minimizaciayi gradientayin eanakneri ndhanowr nkaragrowyown

Sahmanowm 2.1.1: h vektor kovowm  f fownkciayi nvazman owowyown x ketowm, ee bavakanaa

oqr drakan α veri hamar tei owni f (x + αh) < f (x)

anhavasarowyown:

Ayl xosqov, h- ayn vektorn , ori owowyamb bavakanaa

oqr arvelis kareli  fownkciayi areqner oqracnel: Lemma 2.1.1: Dicowq f - diferenceli  x ketowm h-n aynpisi vektor , or tei owni (f 0 (x), h) < 0

anhavasarowyown: Ayd depqowm h- f -i nvazman owowyown  x ketowm : I

Qani or f - diferenceli , apa

f (x + αh) = f (x) + α[(f 0 (x), h) +

o(α) ]: α

Aysteic, bavakanaa

oqr drakan α veri hamar mijak akag erowm gra artahaytowyown da nowm  bacasakan: Aynpes or kstananq f (x + αh) < f (x) : J

Ditoowyown: Masnavorapes, orpes nvazman owow{

yown kareli  vercnel

h = −f 0 (x),

or kovowm  ha-

kagradienti owowyown: Kareli  cowyc tal, or hakagradient talis  fownkciayi amenaarag nvazman owowyown: Gradientayin vayrjqi meodner ka owcvowm en het yal kerp: ntrvowm  kamayakan x0 ket Rn ta{ ra owyownic ka owcvowm  xk+1 = xk + αk hk , k = 0, 1, 2, ...

(2.1.1)

ekowrent a nowyown: Ayste hk = −f 0 (xk ), isk αk ver kovowm en qayler, oronq ntrvowm en oroaki rinaa owyamb: Haytni en qayli ntrowyan mi qani eanakner, oronq nerkayacvowm en stor : 1. Qayli ntrowyan apriori eanak: Ays depqowm αk qayler drakan ver en, oronq bavararowm en het yal paymannerin. X

αk = +∞,

X

αk2 < +∞ :

Masnavorapes, ays paymannerin bavararowm en αk =

ln(k + 1) , αk = , k = 0, 1, 2, ... k+1 k+1

vayin hajordakanowyownner: 2. Qayli ntrowyan amenaarag vayrjqi ea{ nak: Ays depqowm αk > 0 qayler ntrvowm en het yal kerp: Kazmowm en g(α) ≡ f (xk + αhk ) fownkcian gtnowm nra minimowmi ket (0, ∞) mijakayqi vra: Ayn ket, orte minimowm hasaneli  hamarvowm  αk , aysinqn` αk ≡ arg min g(α) : α>0

Oro dasi fownkcianeri hamar kareli  stanal analitik bana er αk qayleri oroman hamar, inpes het yal rinakowm: rinak: Dicowq f (x) = 1/2(Ax, x) + (b, x), orte A-n (n × n) a ani simetrik, drakan oroyal matric , isk b-n n a ani vektor : Kareli  cowyc tal, or f - ow owcik , owni miak minimowmi ket Rn -i vra nra gradient orovowm  het yal bana ov. f 0 (x) = Ax+b : Ays depqowm ownenq g(α) ≡ f (xk + αhk ) = 1/2[A(xk + αhk ), xk + αk hk )]+ +(b, xk + αk hk ) = α2 [1/2(Ahk , hk )]+ +α(Axk + b, hk ) + (1/2Axk + b, xk ) :

Dvar  nkatel, or stacva qa akowsayin e andam hasnowm  ir oqragowyn areqin Rn -i vra het yal ketowm. αk = −

(f 0 (xk ), hk ) (Axk + b, hk ) = − ≥0 (Ahk , hk ) (Ahk , hk )

(2.1.2)

ketowm: Het abar, f (xk + αk hk ) = min f (xk + αhk ) = minn f (xk + αhk ) : α≥0

α∈R

3. Qayli ntrowyan kisman eanak: Fiqsowm enq or  drakan ε iv (0, 1) mijakayqic α = 1 vi hamar stowgowm enq f (xk − αf 0 (xk )) − f (xk ) ≤ −εαkf 0 (xk )k2

(2.1.3)

anhavasarowyown: Ee ayn tei owni, apa αk -n hamarowm enq havasar α-i: Haka ak depqowm α-n kisowm

enq noric stowgowm (2.1.3) anhavasarowyown ayspes arownak: Ee or  p-rd qaylowm bavararvowm  (2.1.3) anhavasarowyown, apa αk = 21 : p

XNDIRNER

1. Gtnel het yal fownkcianeri qstremowmi keter amenaarag vayrjqi meodov: Skzbnakan x0 ketic sksa ka owcel {xk } hajordakanowyown (2.1.1) ekowrent a nowyamb qayleri ntrowyown katarel (2.1.2) bana ov: Ee kf 0 (xk )k < ε0 , apa procesn avartel xk -n hamarel fownkciayi qstremowmi ket: Ayste ε0 > 0 iv naxapes trva towyownn : a)

f (x1 , x2 ) = 5x21 +5x22 −6x1 x2 → min, x0 = (1, 1), ε0 = = 0.01;

b)

−3x21 − 2x22 + x2 + 6x2 − 15 → max, x0 = (0, 1), ε0 = = 0.1;

g)

x21 + x22 + 2x1 x2 + x2 → min, x0 = (1, 0), ε0 = 0.01 :

2. Dicowq f - erkow angam diferenceli  x ketowm (f 0 (x), h) = 0, (f 00 (x), h) < 0 :

Apacowcel, or h- owyown :

f

fownkciayi nvazman ow-

3. Dicowq

H(x) = f 00 (x) f 0 (x) 6= 0: Apacowcel,

hesian drakan oroyal  or

h = −H(x)−1 f 0 (x)

vektor f fownkciayi nvazman owowyown : A ajadranq 1: Grel ragir, or minimizacnowm  f (x) = 1/2(Ax, x) + (b, x) fownkcian Rn -i vra: Ayste A-n (n × n) a ani simetrik, drakan oroyal matric , isk b-n n a ani vektor : Mowtqi tvyalnern en A, b, x0 , n, ε, ε0 parametrer: Ayste ε0 -n towyownn : Ka owcel {xk } hajordakanowyown gradientayin ijecman ereq meodnerov hamematel dranq qayleri qanaki tesaketic: Ee kf 0 (xk )k < ε0 , apa procesn avartel hamarel xk -n minimowmi ket: Hamematel stacva ardyownqner x∗ = A−1 b vektori het, or f -i minimowmi ketn  :

2.2

Qayli kisman eanaki zowgamitowyan eorem

Lemma 2.2.1: Dicowq f fownkciayi hamar it en het yal paymanner. 1) f fownkciayi gradient bavararowm  Lipici paymanin, aysinqn goyowyown owni aynpisi L > > 0 hastatown, or kf 0 (x) − f 0 (y)k ≤ Lkx − yk ∀x, y ∈ Rn :

2) f - nerq ic sahmana ak , aysinqn` goyowyown owni aynpisi m > 0 iv, or tei owni f (x) ≥ m ∀x ∈ Rn

anhavasarowyown: Ayd depqowm qayli kisman eanakov verjavor qayleri nacqowm ntrvowm  αk -n αk > (1 − ε)/L > 0, k = 0, 1, 2, ... :

Dicowq hk = −f 0 (xk ): Hamaayn Lagrani mijin areqi veraberyal eoremi` goyowyown owni θ ∈ (0, 1) hastatown aynpisin, or ee α > (1 − ε)/L, apa I

f (xk + αhk ) − f (xk ) = (f 0 (xk + αθhk ), αhk ) = = (f 0 (xk + αθhk ) − f 0 (xk ), αhk ) + α(f 0 (xk ), hk ) ≤ ≤ kLαθhk kkαhk k − αkf 0 (xk )k2 ≤ Lα2 kf 0 (xk )k2 − −αkf 0 (xk )k2 = −αkf 0 (xk )k2 (1 − αL) ≤ −εαkf 0 (xk )k2 : J

eorem 2.2.1: Dicowq f fownkcian bavararowm  lemma 2.2.1-i bolor paymannerin {xk }-n kisman meodov ka owcva hajordakanowyownn : Ayd depqowm f 0 (xk ) → 0, erb k → ∞ : I

Ownenq

f (xk+1 ) − f (xk ) ≤ −εαkf 0 (xk )k2 :

(2.2.1)

Aysteic het owm , or f (xk+1 ) ≤ f (xk ): Aysinqn, {f (xk )} hajordakanowyown monoton nvazo  nerq ic sah{ mana ak : Het abar, hajordakanowyown zowgamet , aysinqn` f (xk ) − f (xk+1 ) → 0 :

(2.2.1)-ic het owm , or kf 0 (xk )k2 ≤

f (xk ) − f (xk+1 ) : εαk

Aysteic, qani or, st lemma 2.2.1-i, αk > (1−ε)/L > > 0, apa f 0 (xk ) → 0 : J

eorem 2.2.2: Enadrenq goyowyown ownen aynpisi drakan D > 0, d > 0 hastatownner, or Dkhk2 ≥ (f 00 (x)h, h) ≥ dkhk2 ∀x, h ∈ Rn :

(2.2.2)

Ayd depqowm kisman eanakov ka owcva {xk } hajordakanowyown zowgamitowm  f -i miak x∗ minimowmi ketin erkraa akan progresiayi aragowyamb: Aysinqn` goyowyown ownen C > 0 q ∈ (0, 1), hastatownner aynpisin, or kxk − x∗ k ≤ Cq k , k = 0, 1, ... :

I

Qani or f 0 (x∗ ) = 0, apa, st eylori bana i,

f (x) − f (x∗ ) = (f 00 (x∗ + θ(x − x∗ ))(x − x∗ ), x − x∗ ),

orte θ ∈ (0, 1): Aysteic, havi a nelov havasarowyown, stanowm enq D d kx − x∗ k2 ≤ f (x) − f (x∗ ) ≤ kx − x∗ k :

(2.2.2)

an{

(2.2.3)

Havi a nelov ays payman nerkayacnelov f fownkcian eylori bana i tesqov x ketowm` kownenanq f (x∗ ) − f (x) = (f 0 (x), x∗ − x)+ +1/2(f 00 (x + θ(x∗ − x))(x∗ − x), x∗ − x) ≥ ≥ −kf 0 (x)kkx − x∗ k + d/2kx − x∗ k2 :

Aysteic kstananq f (x) − f (x∗ ) ≤ kf 0 (x)kkx − x∗ k − d/2kx − x∗ k2 : (2.2.4)

Havi a nelov na (2.2.3) anhavasarowyan ax mas` (2.2.4)-ic kstananq d kx − x∗ k2 ≤ kf 0 (x)kkx − x∗ k − d/2kx − x∗ k2 :

Het abar, kx − x∗ k ≤

kf 0 (x)k : d

(2.2.5)

gtvelov (2.2.3)-(2.2.5) anhavasarowyownneric` sta{ nowm enq kf 0 (x)k2 f (x) − f (x ) ≤ − d/D(f (x) − f (x∗ )) : d ∗

Aysteic kf 0 (x)k2 ≥ d(1 + d/D)(f (x) − f (x∗ )) :

(2.2.6)

Kira elov (2.2.6) anhavasarowyown kisman meodi f (xk+1 ) − f (xk ) ≤ −εαk kf 0 (xk )k2

anhavasarowyownowm` kstananq f (xk+1 ) − f (x∗ ) ≤ [1 − εαk d(1 + d/D)]((f (xk ) − f (x∗ )) :

Aysteic, havi a nelov αk > anhavasarowyown, kstananq

ᾱ ≡ (1 − ε)/L > 0

f (xk ) − f (x∗ ) ≤ (f (x0 ) − f (x∗ ))q̄ k ,

orte

(2.2.7)

q̄ = 1 − εαd(1 + d/D) :

Verjapes, gtvelov yownic, kstananq r kxk − x∗ k ≤

orte

r C=

(2.2.3)

(2.2.7)

anhavasarow{

2p f (xk ) − f (x∗ ) ≤ Cq k , d

√ 2p f (x0 ) − f (x∗ ), q = q̄ : d

J

Qayli kisman eanaki praktik irakanacowmneri amanak sovorabar gtvowm en nra het yal modi{ fikacva tarberakic: k-rd qaylowm orpes fownkciayi nvazman owowyown vercnowm en hk = −

f 0 (xk ) kf 0 (xk )k

vektor, isk αk qayli erkarowyown ntrvowm  kisman eanaki het yal paymanic. f (xk + αhk ) − f (xk ) ≤ −αεkf 0 (xk )k :

(2.2.8)

Hajord xk+1 ket ka owcvowm  xk+1 = xk + αk hk

(2.2.9)

ekowrent a nowyamb: Aym qayli kisman eanak meknabanenq het yal parz rinaki mijocov: rinak: Qayli kisman eanakov gtnel f (x1 , x2 ) = 4x21 + 4x22 + 6x1 x2

fownkciayi minimowmi ket R2 -i vra: Orpes skzbnakan motavorowyown vercnel x0 = (−2, 1) ket: ε parametri areq vercnel havasar 0.5-i: Katarel iteraciayi mek qayl: Low owm: Qayli kisman eanaki iteraciayi (2.2.9) bana  ays xndri hamar owni het yal tesq. x

k+1

 =

xk+1 xk+1



 =

xk1 xk2



 + αk

hk1 hk2

 :

(2.2.10)

Masnaki a ancyalneri gradienti normi hamar ownenq het yal bana er. fx0 1 (x1 , x2 ) = 8x1 + 6x2 , fx0 2 (x1 , x2 ) = 8x2 + 6x1 , (2.2.11) p (2.2.12) kf 0 (x)k = (8x1 + 6x2 )2 + (8x2 + 6x1 )2 , 8xk1 + 6xk2 k 6xk1 + 8xk2 , h = − : kf 0 (xk )k kf 0 (xk )k A ajin iteraciayowm k = 0: gtagor elov (2.2.10) − (2.2.13) bana hk1 = −

nanq

(2.2.13)

er` ksta{

fx0 1 (x01 , x02 ) = 8x01 + 6x02 = 8(−2) + 6 = −10,

fx0 2 (x01 , x02 ) = 6x01 + 8x02 = −4, kf 0 (x0 )k =

p (−10)2 + (−4)2 ≈ 10.77, h01 = h02 =

≈ 0.93, 10.77

≈ 0.37 : 10.77

Dicowq α = 1: Ayd depqowm, havi a nelov ays ardyownqner, meknarkayin (−2, 1) areq (2.2.10)-, kstananq  x≡

−2



 −

0.93 0.37

A ajin iteraciayi hamar man owni het yal tesq.



α0

 =

−1.07 1.63

 :

qayli ntrowyan pay{

f (x) − f (x0 ) ≤ −0.5αkf 0 (x0 )k :

Katarelov hamapatasxan havarkner` nkatowm enq, or ays anhavasarowyan ax mas motavorapes havasar  −1.6-i, isk aj mas havasar  −5.4-i: Het abar, ayn tei owni: Aym kisenq α iv noric stowgenq anhavasarowyown: Ays depqowm x = (−1.58, 1.18) :

Qani or f (x0 ) = 8, f (x) ≈ 4.16, apa anhavasarowyan ax mas havasar  4.16−8 = −3.84, isk aj mas, het  nkatel, or havasar  −2.69-i: Ayspisov, nva anhavasarowyown tei owni het abar` α0 = 0.5, x1 = (−1.54, 1.18) :

XNDIRNER

Qayli kisman eanakov low el het yal qstremowmi xndirner: Vercnel x0 = (1, 1), ε = 0.5 : Katarel iteraciayi mek qayl: 1. 2x21 + 2x22 + 4x1 + 6x2 − 2x1 x2 → min : 2.

2.3

−2x21 − 2x22 − 2x1 x2 + 2 → max :

G aynacman meod

Ditarkenq paymanakan ptimizaciayi het yal xndir. f (x) → min, x ∈ M :

(2.3.1)

Ays xndrowm f - diferenceli ow owcik fownkcia , isk M ⊂ Rn - kompakt ow owcik bazmowyown : Tanq g aynacman meodi hama ot nkaragrowyown: ntrowm enq kamayakan x0 ket M bazmowyownic ka owcowm enq {xk } hajordakanowyown xk+1 = xk + αk hk , k = 0, 1, ...

ekowrent a nowyamb: Ayste hk vektor f -i aynpisi nvazman owowyown  xk ∈ M ketowm, or bavakanaa

oqr αk qayleri depqowm xk+1 ∈ M : hk vektori oroman hamar k-rd qaylowm low owm enq het yal mijankyal xndir. (f 0 (xk ), x − xk ) → min, x ∈ M :

Enadrenq x̄k -n ayd xndri or  low owm : Nanakenq ηk = (f 0 (xk ), x̄k − xk ), hk = x̄k − xk :

vektor kovowm  paymanakan hakagradient: Aknhayt , or ηk ≤ 0: Iroq, hk

ηk = min(f 0 (xk ), x − xk ) ≤ (f 0 (xk ), xk − xk ) ≤ 0 : x∈M

Ee ηk < 0 , apa ntrowm enq αk qayl kisman meodov: Vercnowm enq α = 1 stowgowm f (xk + αhk ) − f (xk ) ≤ αεηk

(2.3.2)

anhavasarowyown: Ee ayn tei owni, apa hamarowm enq αk = 1, haka ak depqowm α-n kisowm enq noric stowgowm nva anhavasarowyown ayspes arownak: Erb a ajin angam tei ownena (2.3.2) anhavasarowyown, apa ayd α-n hamarvowm  αk -i areq cikl avartvowm : Aynowhet ka owcowm enq xk+1 ket

ekowrent a nowyamb. xk+1 = xk + αk hk :

eorem 2.3.1: Dicowq

a) M ⊂ Rn - ow owcik kompakt , b) f (x)- diferenceli 

ow owcik M -i vra,

g) f 0 (x) gradient M bazmowyan vra bava{ rarowm  Lipici paymanin: Ayd depqowm 1) ee or  k-rd qaylowm ηk = 0, apa xk -n (2.3.1) xndri low owmn  algorimn avartvowm ,

2) ee ηk < 0, k = 0, 1, 2, ..., apa f (xk ) → min f (x) : x∈M

Dicowq ηk = 0: st ow owcik fownkciayi himnakan anhavasarowyan` ownenq I

f (x) − f (xk ) ≥ (f 0 (xk ), x − xk ) ≥ ηk = 0 ∀x ∈ M,

aysinqn xk -n (2.3.1) xndri low owmn : Cowyc tanq, or hk owowyamb bavakanaa

oqr arvelis mnowm enq M bazmowyan mej: Iroq, qani or M - ow owcik , apa xk +αhk = xk +α(x̄k −xk ) = (1−α)xk +αx̄k ∈ M, ∀α ∈ [0, 1] :

Qani or f -i gradient M kompakti vra bavararowm  Lipici paymanin xk ∈ M , apa kareli  cowyc tal, or verjavor qayleric heto (2.3.2) anhavasarowyown tei owni het abar αk qayl ntrvowm : Miaamanak goyowyown owni aynpisi ᾱ > 0 iv, or αk > ᾱ > 0, k = 0, 1, ... (te|s, rinak` [8], lemma 3.1, j 229): Aym apacowcenq, or f (xk ) → min f (x) : x∈M

Hamaayn (2.3.2) anhavasarowyan` ownenq f (xk+1 ) ≤ f (xk ) + εαk ηk :

(2.3.3)

Gowmarelov (2.3.3) anhavasarowyownner k ∈ [0 : m − indeqsneri hamar` kstananq

− 1]

min f (x) − f (x0 ) ≤ f (xm ) − f (x0 ) ≤ x∈M

m−1 X k=0

αk η k :

Aysteic het owm , or bacasakan andamnerov αk ηk arq zowgamet : Het abar, nra ndhanowr andam gtowm  zroyi`

P

αk ηk → 0 :

(2.3.4)

Qani or αk > ᾱ > 0, apa (2.3.4)-ic het owm , or ηk → 0: Aysteic, ntrelov xk → x∗ ∈ M zow{ gamet enahajordakanowyown gtvelov ow owcik fownkciayi himnakan anhavasarowyownic, kstananq` j

f (x) − f (xkj ) ≥ (f 0 (xkj ), x − xkj ) ≥ ηkj ∀x ∈ M : (2.3.5) → x∗ , apa (2.3.5) xk Qani or ηk → 0 anhavasarowyownowm ancnelov sahmani, kstananq` j

j

f (x) − f (x∗ ) ≥ 0 ∀x ∈ M,

aysinqn, x∗ - f -i minimowmi ketn  M bazmowyan vra: Ayspisov, apacowcvec, or {f (xk )} hajordakanowyan {f (xk )} enahajordakanowyown zowgamitowm  minx∈M f (x): Myows komic, qani or {f (xk )} hajordakanowyown monoton nvazo , apa ayn nowynpes kzowgamiti minx∈M f (x)-in: j

J

XNDIRNER

1. Apacowcel pndowmner het yal xndri hamar. (c, x) → min, x ∈ M :

a) Ee M = {x ∈ Rn /kx − x0 k ≤ r}, apa x∗ = x0 +

vektor xndri low owmn :

c r kck

b) Ee M = {x ∈ Rn /aj ≤ xj ≤ bj , j ∈ [1 : n]}, apa  aj , ee cj ≥ 0, ∗ xj = bj , ee cj < 0 koordinatnerov vektor xndri low owmn : 2. Gtnel f (x) = x21 + x22 fownkciayi paymanakan hakagradient x = (2, 3) ketowm M = {x ∈ ∈ R2 /x1 + x2 ≤ 6, x1 ≥ 0, x2 ≥ 0} bazmowyan vra: A ajadranq 2: Kazmel ragir, or irakanacnowm

 f (x) = 1/2(Ax, x) + (b, x) fownkciayi minimizacian M = {x ∈ Rn /Cx ≤ d, x ≥ 0} bazmowyan vra paymanakan gradienti meodov: Ayste A-n (n × n) a ani simetrik drakan oroyal matric , isk C-n (m × n) a ani matric : k-rd qaylowm gtagor elov simpleqs algorim` stanal

ηk = min(f 0 (xk ), x − xk ) x∈M

xndri or  low owm: Algorimi kanga i hamar ndownel |ηk | < ε0 payman, orte ε0 > 0 naxapes trva

towyown : Ee nva payman katarvowm , apa xk vektor hamarel xndri low owm avartel algorim: Skzbnakan x0 ∈ M keti ntrowyown nowynpes katarel simpleqs algorimov:

2.4

Apriori meodi zowgamitowyown

eorem 2.4.1: Dicowq f - ow owcik fownkcia ` orova Rn -i vra M ∗ - nra minimowmi keteri bazmowyownn  Rn -i vra: Enadrenq M ∗ 6= ∅: Dicowq {xk }-n het yal ekowrent a nowyamb ka owcva

hajordakanowyown .

n

x ∈R , x

k+1

f 0 (xk ) = x − αk 0 k , k = 0, 1, 2, ..., (2.4.1) kf (x )k k

orte αk -er drakan ver en` bavararo X

paymannerin: Ayd depqowm

αk = +∞,

X

αk2 < +∞ :

(2.4.2)

xk → x̄ ∈ M ∗ :

Aysinqn` {xk } hajordakanowyown zowgamitowm  f -i or  x minimowmi keti: I Nanakenq v k = f 0 (xk ): Vercnenq or  x∗ ∈ M ∗ ket havenq nra he avorowyown {xk } hajordakanowyan

andamneric: Ownenq

kxk+1 − x∗ k2 = kxk − x∗ k2 +

2αk k ∗ (v , x − xk ) + αk2 : (2.4.3) kv k k

Qani or x∗ - f -i minimowmi ket  M -i vra, apa (v k , x∗ − xk ) ≤ f (x∗ ) − f (xk ) ≤ 0 :

Havi a nelov ays payman (2.4.3)-` kstananq kxk+1 − x∗ k2 ≤ kxk − x∗ k2 +

m−1 X

αi2 :

(2.4.4)

i=0

Qani or αk 2 arq zowgamet , apa (2.4.4) anhavasarowyownic het owm , or {xk }-n sah{ mana ak hajordakanowyown : Aysteic het owm , or sahmana ak klini na {vk } hajordakanowyown: Aysinqn, goyowyown owni C > 0 iv aynpisin, or P

kv k k ≤ C :

(2.4.5)

Cowyc tanq, or goyowyown owni indeqsneri aynpisi {ks } enahajordakanowyown, or (v ks , x∗ − xks ) → 0,

erb ks → ∞ :

(2.4.6)

Enadrenq haka ak: Ayd depqowm goyowyown owni aynpisi N > 0 iv, or in-or K hamaric sksa tei owni (f 0 (xk ), x∗ − xk ) < −N < 0, ∀k > K

(2.4.7)

anhavasarowyown: gtvelov (2.4.3)-(2.4.7) anhavasarowyownneric` kstananq kxk+1 − x∗ k2 ≤ kx0 − x∗ k2 −

k k X 2N X αi + αi2 : (2.4.8) C i=0 i=0

Ays anhavasarowyan mej ancnelov sahmani, erb k → ∞, kstananq, or nra aj mas gtowm  −∞, isk ax mas o bacasakan iv , in hakasowyown : Aym {xk } enahajordakanowyan keteri hamar, kira elov ow owcik fownkciayi himnakan anhavasarowyown, kownenanq` s

0 ≥ f (x∗ ) − f (xks ) ≥ (v ks , x∗ − xks ) :

Ayste ancnelov sahmani, erb ks → ∞ havi a nelov na (2.4.6)-, kstananq f (xks ) → f (x∗ ) = min f (x) : x∈M

Qani or {xk }- sahmana ak hajordakanowyown , apa nranic kareli  anjatel zowgamet en{ ahajordakanowyown: ndhanrowyown xaxtelov, enadrenq or xk → x̄: Aysteic, gtvelov f -i anndhatowyownic, kstananq s

s

f (xks ) → f (x̄) = f (x∗ ) = min f (x), x∈M

aysinqn`

x̄ ∈ M ∗ :

Cowyc tanq, or xk → x̄ : Qani or xk → x̄, apa kamayakan ε > 0 vi hamar goyowyown owni aynpisi K hamar, or erb ks > K, apa tei owni s

kxks − x̄k2 <

ε

(2.4.9)

anhavasarowyown: Karo enq na hamarel, or can{ kaca p hamari hamar tei owni ks +p−1

X

αi2 <

i=ks

ε

(2.4.10)

anhavasarowyown: gtvelov (2.4.3) (2.4.9)-(2.4.10) anhavasarowyownneric` stanowm enq, or erb ks > K , apa cankaca p bnakan vi hamar tei owni het yal anhavasarowyown` ks +p−1

kp

ks +p

ks

− x̄k ≤ kx − x̄k +

X

αi2 <

i=ks

ε ε + =ε: 2 2

Isk sa nanakowm , or xk → x̄ : J

XNDIRNER

Apriori meodov low el het yal xndirner: Vercnel x0 = (1, 1), αk = 1/k + 1, k = 0, 1, 2, ... : Katarel iteraciayi erkow qayl: 1. 3x21 + x22 + 11x2 + 3x1 → min : 2.

2.5

−2x21 − x22 + 8x1 + 6x2 − 25 → max :

Gradienti proyektman meod

Dicowq M ⊆ Rn - ak ow owcik bazmowyown : Nanakenq ΠM (a)-ov a vektori proyekcian M bazmowyan vra: Aysinqn` ΠM (a)-n M bazmowyan amenamotik ketn  a vektoric: marit  het yal pndowm (te|s, rinak` [8]):

Lemma 2.5.1: ΠM perator bavararowm  Lipici paymanin L = 1 hastatownov, aysinqn` kΠM (x) − ΠM (y)k ≤ kx − yk ∀ x, y ∈ Rn :

(2.5.1)

Ditarkenq maematikakan ragravorman het yal xndir` f (x) → min, x ∈ M :

Ayste f (x)- diferenceli fownkcia , isk M - ow owcik bazmowyown : Gradienti proyekman meodov ays xndri low man hamar ka owcvowm  {xk } hajordakanowyown het yal ekowrent a nowyamb. x0 ∈ M, xk+1 = ΠM (xk − αk f 0 (xk )), k = 0, 1, 2, ... :

Owsowmnasirenq ayn paymanner, oronc depqowm ays hajordakanowyown kzowgamiti f -i or  minimowmi keti: Lemma 2.5.2: Dicowq f - θ hastatownov owe ow owcik fownkcia  M ow owcik bazmowyan vra: Ayd depqowm tei owni het yal anhavasarowyown. (f 0 (x) − f 0 (y), x − y) ≥ 2θkx − yk2 ∀ x, y ∈ M : (2.5.2) I st f fownkciayi owe ow owcikowyan (1.1.2) sahmanman` kamayakan x, y ∈ M keteri hamar ownenq` f (x) − f (y) ≥ (f 0 (x), x − y) + θkx − yk2 , f (y) − f (x) ≥ (f 0 (y), y − x) + θkx − yk2 :

Gowmarelov ays erkow anhavasarowyownner` kstananq (2.5.2) anhavasarowyown: J

Henvelov ays ardyownqneri vra` apacowcenq pro{ yekman meodi zowgamitowyan het yal eorem: eorem 2.5.1: Dicowq f - θ hastatownov owe ow owcik fownkcia  M ak ow owcik bazmowyan vra: Enadrenq na , or f 0 gradient bavararowm  Lipici paymanin M bazmowyan vra L > 0 hastatownov, aysinqn kf 0 (x) − f 0 (y)k ≤ Lkx − yk ∀x, y ∈ M :

Ayd depqowm, ee proyekman meodowm orpes αk qayler vercnenq mi nowyn hastatown (0, L4θ2 ) mijakayqic, apa {xk } hajordakanowyown kzowgamiti f -i miak minimowmi ketin erkraa akan progresiayi aragowyamb: I

Ditarkenq het yal perator` Aα : M → M, Aα (x) ≡ ΠM (x − αf 0 (x)) :

Cowyc tanq, or ayn semo perator : gtagor elov (2.5.1) − (2.5.2) anhavasarowyownner` kownenanq. kAα (x) − Aα (y)k2 = kΠM (x − αf 0 (x)) − ΠM (y − αf 0 (y))k2 ≤ ≤ kx − αf 0 (x) − y + αf 0 (y)k2 ≤ kx − y + α(f 0 (y) − f 0 (x))k2 = = kx − yk2 + 2α(x − y, f 0 (y) − f 0 (x)) + α2 kf 0 (x) − f 0 (y)k2 = ≤ kx − yk2 (1 − 4θα + α2 L2 ) :

(2.5.3)

ntrenq α aypes, or q≡

√ 1 − 4αθ + α2 L2

iv oqr lini mekic: Ee α ∈ (0, L4θ ), apa q < 1 het abar Aα perator klini semo: Dicowq x∗ - nra anar ketn  M bazmowyan vra, aysinqn`

ΠM (x∗ − αf 0 (x∗ )) = x∗ :

(2.5.4)

Cowyc tanq, or ayd anar ket f -i minimowmi ketn : Iroq, qani or proyektman perator bavararowm  (ΠM (a) − a, x − ΠM (a)) ≥ 0 ∀a ∈ Rn , ∀x ∈ M

(2.5.5)

anhavasarowyan (te|s, rinak` [8]), apa ayste teadrelov a = x∗ − αf 0 (x∗ ), ΠM (a) = x∗ havi a nelov (2.5.4)-, kstananq` (x∗ − x∗ + αf 0 (x∗ ), x − x∗ ) ≥ 0 ⇒ ⇒ (f 0 (x∗ ), x − x∗ ) ≥ 0 ∀ x ∈ M :

(2.5.6)

Verjapes, havi a nelov na ow owcik fownkciayi himnakan anhavasarowyown, (2.5.6)-ic kownenanq f (x) − f (x∗ ) ≥ (f 0 (x∗ , x − x∗ ) ≥ 0 ∀x ∈ M,

aysinqn x∗ - f -i minimowmi ketn : Baci dranic (2.5.3)-ic het owm , or kxk+1 − x∗ k = kAα xk − Aα x∗ k ≤ qkxk − x∗ k ≤ ... ≤ q k+1 kx0 − x∗ k :

Isk sa nanakowm , or {xk } hajordakanowyown zowgamitowm  x∗ ketin erkraa akan progresiayi aragowyamb: J

XNDIRNER

1. Dicowq a ∈ Rn kamayakan ket : Apacowcel, or ee a)

M = {x ∈ Rn /kx − x0 k ≤ r},

apa

ΠM (a) = x0 +

a − x0 r; ka − x0 k

b) ee M = {x ∈ Rn /bj ≤ xj ≤ cj , apa   bj , aj , (ΠM (a))j =  cj ,

g) ee M = {x ∈ Rn /xj ≥ 0, apa

j ∈ [1 : n]},

ee aj < bj ee bj ≤ aj ≤ cj ee aj > cj ; j ∈ [1 : n]},

ΠM (a) = (max(0, a1 ), ..., max(0, an )) :

A ajadranq 3: Kazmel ragir, or gradienti pro-

yektman meodov kirakanacni

f (x) = 1/2(Ax, x) + (b, x)

qa akowsayin fownkciayi minimizacian gndi zowgahe anisti vra: Orpes proyektman peratorner vercnel ver owm nva bana er: L hastatown vercnel A matrici norm, owe ow owcikowyan θ hastatown vercnel matrici minimal se akan areq, isk 2θ : L2 kxk+1 − xk k < ε0

αk =

Kanga i qayl hamarel naxapes trva towyown :

ε0 > 0

payman, orte

Glowx 3

Ow owcik analiz Ow owcik analiz maematikakan analizi bain , orn owsowmnasirowm  ow owcik bazmowyownneri ow owcik fownkcianeri hatkowyownner: Ow owcik analizi gaa arner aster fowndamental nanakowyown ownen ptimizaciayi vayin meodneri tesowyownowm: Dranq layn kira owyownner ow nen na kira akan maematikayi aynpisi bnagava nerowm inpisiq en` xaeri tesowyown, gor owyneri hetazotowm, maematikakan konomikan ayln: Ays glowx kareli  ditarkel orpes ow owcik analizi nera owyown: Ayste berva

aster pndowmner gtagor vowm en hetagayowm maematikakan ragravorman xndirnerowm Lagrani anoro gor akicneri meod himnavorelow hamar: Nenq, or kan na lracowci

aster, oronq  akerpva en xndirneri tesqov: Hark enq hamarowm nel, or ow owcik analizi amanakakic meodnerin kareli  anoanal [5, 7, 11 ] axatanqnerowm:

3.1

Ow owcik bazmowyownneri anjatman eoremner

Sahmanowm 3.1.1: Dicowq p ∈ Rn -n o zroyakan vektor , isk α-n irakan iv : H = {x ∈ Rn /(p, x) = α}

bazmowyown kovowm  hiperharowyown, isk H+ = {x ∈ Rn /(p, x) ≥ α}, H− = {x ∈ Rn /(p, x) ≤ α}

bazmowyownner` ayd hiperharowyamb nva ki{ satara owyownner: Sahmanowm 3.1.2: M1 , M2 ⊆ Rn bazmowyownner kovowm en anjatvo hiperharowyamb, ee goyowyown owni aynpisi p 6= 0 vektor, or (p, x) ≤ (p, y) ∀x ∈ M1 , ∀y ∈ M2 :

Sa nanakowm , or goyowyown owni aynpisi perharowyown, or

H

hi{

M1 ⊆ H− , M2 ⊆ H+ :

eorem 3.1.1: Dicowq M1 , M2 ⊆ Rn aynpisi ow owcik bazmowyownner en, or M1 ∩ M2 = ∅: Ayd depqowm nranq anjatvowm en hiperharowyamb: I

eoremi apacowyc henvowm  het yal erkow pn{ dowmneri vra: Lemma 3.1.1: Ee M - ak ow owcik bazmowyown  a∈ / M, apa ayd ket hiperharowyamb anjatvowm  M bazmowyownic: I

Gtnenq a keti proekcian M bazmowyan vra: Cowyc tanq, or ayn goyowyown owni miakn : Vercnenq a kentronov r ≡ infx∈M ka − xk + ε a avov Br (a) gownd, orte ε > 0 fiqsa iv : Qani, or gownd ak sahmana ak bazmowyownn , apa M ∩ Br (a) hatowm kompakt : Het abar, a keti he avorowyown ayd hatowmic hasaneli : Dvar  hamozvel, or ayd ket amenamotikn  na M bazmowyownic, aysinqn da ΠM (a) ketn  : Cowyc tanq ΠM (a)-i miakowyown: Enadrenq goyowyown owni erkow amenamotik ket: Dicowq dranq b, c ketern en: Ee a, b, c keter e ankyown en kazmowm, apa ayn havasarasrown , ori srownq havasar  d ≡ inf x∈M kx − ak, isk himq [c, b] hatva n : Qani, or M ow owcik , apa [c, b] ∈ M : Het abar a gagaic tara barowyan himq [c, b] hatva i mijnaketn : Qani or barowyown oqr  srownqic srownq minimal he avorowyownn , apa stacanq hakasowyown: Nenq na a, b, c keter mi nowyn g i vra gtnvel en karo, qani or a ∈/ M : Aym [ΠM (a), a] hatva i g mijnaketov tanenq hiperharowyown, ori normal a − ΠM (a) vektorn : Cowyc tanq, or ayd hiperharowyown anjatowm  a ket M bazmowyownic: Dicowq H+ ayn kisatara owyownn , or parownakowm  a ket, isk H−

kisatara owyown i parownakowm a-n: Cowyc tanq, or M ⊂ H− :

Nax parz , or g keti proekcian M bazmowyan vra ΠM (a) ketn : Enadrenq, or goyowyown owni e ∈ M ∩ H− : Ayd depqowm g, ΠM (a), e gaganerov e ankyan mej g gagaic tarva barrowyan himq kpatkana [ΠM (a), e] ⊆ M hatva in ayd barrowyown oqr  [g, ΠM (a)] hatva i erkarowyownic, or hakasowyown , qani or ayn g keti minimal he avorowyownn  M bazmowyownic: J

Lemma 3.1.2: Dicowq M ow owcik bazmowyown , isk a ∈ / M : Ayd depqowm a ket hiperharowyamb anjatvowm  M bazmowyownic:

Ee a ∈/ M , apa hangowm enq naxord depqin, qani or ays depqowm a ket kareli  hiperharowyamb anjatel M bazmowyownic het abar` M bazmowyownic: Aym enadrenq, or a-n M -i ezrayin ket : Ayd depqowm goyowyown owni aynpisi {xk } ∈/ M hajordakanowyown, or xk → a : Hamaayn lemma 3.1.1-i yowraqanyowr xk ket kareli  anjatel M bazmowyownic hiperharowyamb: Da nanakowm , or goyowyown ownen aynpisi pk miavor vektorner, or I

(pk , x) ≤ (pk , xk ) ∀x ∈ M :

sahmana akelov ndhanrowyown, kareli  enadrel, or pk → p0 6= 0 : Ancnelov sahmani` kstananq (p0 , x) ≤ (p0 , a) ∀x ∈ M,

in nanakowm  a keti hiperharowyamb:

M

bazmowyan anjatowm

J

Aym ancnenq eoremi apacowycin: Nanakenq M ≡ ≡ M1 − M2 : M - ow owcik  qani or M1 ∩ M2 = ∅, apa 0 ∈/ M : Hamaayn lemma 3.1.2-i` 0 ket kareli  anjatel M bazmowyownic: Da nanakowm , or goyowyown owni aynpisi p 6= 0 vektor, or (p, x − y) ≤ 0 ∀x ∈ M1 , ∀y ∈ M2 :

Aysteic, (p, x) ≤ (p, y) ∀x ∈ M1 , ∀y ∈ M2 : J

Het anq 3.1.1: Dicowq M ⊆ Rn - ow owcik baz{ mowyown , isk a-n nra ezrayin ket: Ayd depqowm a ketov kareli  tanel aynpisi hiperharowyown, or M bazmowyown nka lini ayd hiperharowyamb

nva kisatara owyownneric or  mekowm: Aydpisi hiperharowyown kovowm  henman hiperharowyown: Sahmanowm 3.1.3: Dicowq M1 M2 ⊆ Rn : Kasenq, or ayd bazmowyownner xist en anjatvowm hi{ perharowyamb, ee goyowyown ownen aynpisi p vektor ε > 0 iv, or (p, x) ≤ (p, y) − ε ∀x ∈ M1 , ∀y ∈ M2 :

Hetaga dasaxosowyownneri oro eoremneri, masnavorapes Lagrani anoro gor akicneri meodi, himnavor aradrman hamar kar or  het yal pndowm, or berowm enq a anc apacowyci (te|s, rinak` [7-8]):

eorem 3.1.2: Dicowq M1 ⊂ Rn ak ow owcik baz{ mowyown , isk M2 ⊂ Rn ow owcik kompakt  M1 ∩ M2 = ∅ :

Ayd depqowm ays bazmowyownner xist anjatvowm en hiperharowyamb:

XNDIRNER

1. Grel ayn hiperharowyan havasarowm, orn anjatowm  (−1, 2, 1, −3) ket M ⊆ R4 bazmowyownic, or trvowm  anhavasarowyownneri het yal hamakargov.  5x1 + x2 − 5x3 − 3x4 ≤ 1,    −3x2 − 2x2 + 5x3 + x4 ≤ 2, 3x2 + x3 + 2x4 ≤ 0,    x1 + x2 + 3x3 − x4 ≤ 9 :

2. Apacowcel het yal pndown: Orpeszi M ⊆ Rn

ak bazmowyown lini ow owcik, anhraet  bavarar, or cankaca b ∈/ M ket xist anjatvi hiperharowyamb M bazmowyownic: 3. Dicowq ow owcik bazmowyan trva ketov kareli  tanel erkow henman hiperharowyown: Apacowcel, or ayd ketov ancnowm en aniv bazmowyan henman hiperharowyownner:

4. Dicowq M1 , M2 ⊂ mowyownner en, or

Rn

intM2 6= ∅

aynpisi ow owcik baz{

M1 ∩ intM2 = ∅ :

Apacowcel, or M1 M2 bazmowyowner anjatvowm en hiperharowyamb:

3.2

Karaeodori eorem

Sahmanowm 3.2.1: Dicowq M - Rn -i enabazmowyown : Ayd bazmowyan ow owcik aan kovowm  het yal bazmowyown. n

convM ≡ {y ∈ R /y =

k X

αi xi , xi ∈ M,

i=1 k X

αi = 1, αi ≥ 0, i ∈ [1 : k], k = 1, 2, ...} :

i=1

Lemma 3.2.1: Dicowq o zroyakan x ∈ Rn vektor nerkayacvowm  X = {x1 , x2 , ... , xm } hamaxmbi vektorneri g ayin o bacasakan kombinaciayov (g ayin kombinaciayi gor akicner o bacasakan ver en): Ayd depqowm x- nerkayacvowm  na ayd hamakargi g oren ankax mi enahamakargi vektorneri g ayin o bacasakan kombinaciayi mijocov: I

Dicowq

x=

m X

αi xi , αi ≥ 0, i ∈ [1 : m] :

i=1

Ee X hamaxmbi vektorner g oren ankax en, apa pndowmn apacowcva : Dicowq aym X hamaxmbi vektorner g oren kaxva en: Ayd depqowm goyowyown ownen λ1 , λ2 , ..., λm ver, oroncic gone mek zro  aynpisin, or x=

m X

λi xi :

i=1

Karo enq enadrel, or ayd gor akicneic or  mek drakan : Nanakenq αs αi = : λi >0 λi λs

α0 ≡ min

Ownenq` x=

m X i=1

i

αi x − α0

m X

i

λi x =

m X

i=1

(αi − α0 λi )xi :

i=1

Aknhayt , or α s − α 0 λs = 0

αi − α0 λi ≥ 0 ∀i :

Aysteic het owm , or x vektor nerkacvowm  X -i in-or vektorneri o bacasakan kombinaciayov, oronc qanak oqr  m-ic: Ayspes arownakelov` khangenq g oren ankax hamakargi: J

eorem 3.2.1: Dicowq x ∈ Rn vektor nerkayacvowm  het yal tesqov. x=

m X

λi xi , λi ≥ 0, i ∈ [1 : m],

i=1

m X

λi = 1, m > n :

i=1

(3.2.1)

Ayd depqowm X = {x1 , ..., xm } hamaxmbi mej goyowyown owni aynpisi mi {xi1 , xi2 , ..., xin+1 } enahamaxowmb o bacasakan αi1 ≥ 0, αi2 ≥ 0, ... αin+1 ≥ 0 ver, or P n+1 j=1

αij = 1

x=

n+1 X

α i j xi j :

j=1

Ditarkenq ownenq I

(x, 1) ∈ Rn+1 (x, 1) =

m X

vektor: st (3.2.1)-i`

λi (xi , 1) :

i=1

Hamaayn lemma 3.2.1-i` goyowyown ownen vektorneri g oren ankax aynpisi {xi , xi , ..., xi } hamaxowmb o bacasakan ver αi , α2 , , ..., αi , or

(x, 1) =

k

k

k X

αij (xij , 1) :

j=1

Aysinqn` x=

k X

ij

αij x , αi1 ≥ 0, αi2 ≥ 0, ..., αik ≥ 0,

j=1

k X

αij = 1 :

j=1

(3.2.2)

Bayc, qani or n + 1 a ani tara owyownowm g oren ankax hamakargi vektorneri qanak n+1-ic avel  , apa k ≤ n+1 : Ee k = n+1, apa eoremn apacowcva

: Ee k < n + 1, apa avelacnelov zroyakan andamner (3.2.2) gowmari andamneri qanak darnowm enq n + 1 : J

Het anq 3.2.1 (Karaeodori eorem): Dicowq M - R -i enabazmowyown : Ayd depqowm` n

convM = {y ∈ Rn /y =

n+1 X

αi xi , xi ∈ M,

i=1 n+1 X

αi = 1, αi ≥ 0, i ∈ [1 : n + 1]} :

i=1

XNDIRNER

1. Gtnel het yal bazmowyownneri ow owcik aan{ ner: a) M = {(x1 , x2 ) ∈ R2 /x1 x2 = 1}; b) M = {(x1 , x2 ) ∈ R2 /x2 = exp(−x1 )}; g) M = {(x1 , x2 ) ∈ R2 /x1 , x2 ∈ [0, 1]} ∪ {(x1 , x2 ) ∈ ∈ R2 /x2 = x1 } :

2. Apacowcel, or bac bazmowyan ow owcik aan bac bazmowyown : 3. Apacowcel, or kompakt bazmowyan ow owcik a{ an kompakt : 4. Anjatvowm  ardyoq (1, −1, 0) ket M = conv{(−1, 1, 2), (2, −1, −3), (−2, 3, −1), (−5, −1, 3)}

bazmowyownic hiperharowyamb:

5. Apacowcel, or convM - minimal ayn ow owcik bazmowyownn , or parownakowm  M -: 6. Apacowcel het yal pndowm: Orpeszi M ⊆ Rn baz{ mowyown lini ow owcik, anhraet  bavarar, or convM = M :

7. Dicowq M = conv{x1 , x2 , ..., xm }, isk f (x)- ow owcik fownkcia , orova M bazmowyan vra: Apacowcel, or max f (x) = max f (xi ) : x∈M

i∈[1:m]

Cowcowm: gtvel Yenseni anhavasarowyownic:

8. Gtnel f (x1 , x2 ) = 25(x1 − 2)2 + (x2 − 2)2 fownkciayi me agowyn areq het yal bazmowyan vra.   x1 + x2 ≥ 2, x1 − x2 ≥ −2, x1 + x2 ≤ 6, x1 − 3x2 ≤ 2,  x1 , x 2 ≥ 0

3.3

:

Hellii eorem

eorem 3.3.1 ( adon): Dicowq trva  vektorneri X = {x1 , x2 , ..., xk } (k ≥ n + 2) hamaxowmb Rn -owm: Ayd depqowm ayd bazmowyown kareli  trohel erkow enabazmowyownneri` Y Z aynpisin, or convY ∩ convZ 6= ∅ :

I

Ditarkenq vektorneri {x2 − x1 , x3 − x1 , ..., xk − x1 }

hamaxowmb: Qani or ays bazmowyan vektorneri qanak me kam havasar  n + 1, apa nranq g oren kaxva en: Het abar, goyowyown ownen α2 , α3 , ..., αk ver, oroncic gone mek havasar  zroyi aynpisin, or k X

(xi − x1 ) = 0 ⇒

i=2

k X

αi xi = 0,

orte α1 = −

i=1

k X

αi :

i=2

Ayspisov, goyowyown ownen aynpisi α1 , ..., αk gor a{ kicner, orocic gone mek havasar  zroyi aynpisin, or k X

i

αi x = 0,

k X

i=1

αi = 0 :

(3.3.1)

i=1

Ayn αi gor akicner, oronq havasar en zroyi den gcenq ndhanrowyown xaxtelov enadrenq, or α1 > 0, ..., αk0 > 0, αk0 +1 < 0, ..., αk < 0 :

Nanakenq ν=

k X

k X

αi = −

αi :

i=k0 +1

i=1

(3.3.1)-ic kstananq

k X αi i=1

ν

i

x =

k X i=k0 +1

−

αi i x : ν

(3.3.2)

Nanakelov

Y = {x1 , ..., xk },

Z = {xk +1 , ..., xk }

(3.3.2)-ic kstananq

x≡

k X αi i=1

ν

i

x =

k X

−

i=k0 +1

αi i x ∈ convX ∩ convY : ν

J

eorem 3.3.2 (Helli): Ee {Aα }-n Rn tara owyan kompakt ow owcik enabazmowyownneri aynpisi ntaniq , or nra cankaca n + 1 qanakov bazmowyownneri hatowm datark , apa \

Aα 6= ∅ :

α

Qani, or Aα bazmowyownner kompakt en, apa bavakan  cowyc tal, or ayd ntaniqi cankaca verjavor qanakov bazmowyownneri hatowm datark : Apacowyc katarenq indowkciayov` st bazmowyownneri qanaki: Dicowq A1 , A2 , ..., Ak (k > n+1) bazmowyownner en ntaniqic ayd bazmowyownneric cankaca k − 1-i hatowm datark : Apacowcenq, or I

k \

Ai 6= ∅ :

i=1

Nanakenq Di = A1 ∩ A2 ∩ ... ∩ Ai−1 ∩ Ai+1 ... ∩ Ak , i ∈ [1 : k] : (3.3.3)

st enadrowyan` Di , i ∈ [1 : k] bazmowyownner datark en: ntrenq kamayakan xi ∈ Di lementner  avorenq X = {x1 , x2 , ..., xk } hamaxowmb: st adoni eoremi` ayd hamaxowmb kareli  trohel S T aynpisi erkow maseri, or X = Y Z, Y Z = ∅ convY

\

convZ 6= ∅ :

Enadrenq

Y = {x1 , x2 , ..., xk }, Z = {xk +1 , ..., xk } :

Cowyc tanq, or ee x ∈ convY

apa x∈

k \

convZ,

Ai :

i=1

Ownenq

x=

\

k X

k X

i

λi x ,

i=1

λi = 1,

λi ≥ 0, i ∈ [1 : k 0 ] :

i=1

Aysteic, qani or i

x ∈

k \

Aj , ∀i ≤ k 0

j=k0 +1

Aj , j ∈ [1 : k]

bazmowyownner ow owcik en, apa x∈

k \ j=k0 +1

Aj :

Myows komic, qani or x=

k X

λ j xj ,

j=k0 +1

apa

x∈

k \

Aj :

j=1

Ayspisov, x∈

k \

Aj :

j=1

J

XNDIRNER

1. Dicowq R2 harowyan n hat keter bavararowm en het yal paymanin. nrancic cankaca ereq gtnvowm en miavor a avov in-or rjani nersowm: Apacowcel, or bolor ketern en gtnvowm miavor a avov mi nowyn rjani nersowm: Cowcowm: Dicowq a1 , a2 , ..., an - trva ketern en: Ditarkel Ai = {x ∈ R2 /kx − ai k ≤ 1}, i ∈ [1 : n]

rjanneri bazmowyown ayd ntaniqi nkatmamb kira el Hellii eorem:

2. Dicowq M ⊂ Rn ow owcik kompakt bazmowyown

a kva  bac kisatara owyownneri ntaniqov: Apacowcel, or ayd ntaniqic kareli  ntrel n + 1 hat kisatara owyownner, oronq nowynpes a kowm en M -: 3. Dicowq M ⊂ R2 - d tramag ov kompakt √ bazmowyown : Apacowcel, or goyowyown owni d/ 3 a avov rjan, or parownakowm  M -: Cowcowm: Nax cowyc tal, or ayd bazmowyan √ cankaca ereq keteri hamar goyowyown owni d/ 3 a avov rjan, or parownakowm  ayd keter: Aynowhet ayd rjanneri nkatmamb kira el Hellii eorem: Nenq, or Hellii eoremi bazmaiv kira owyownnerin kareli  anoanal [9]-owm:

3.4

Ow owcik fownkciayi sowbdiferencial

Sahmanowm 3.4.1: Dicowq f - ow owcik fownkcia ` orova Rn -i vra: v vektor kovowm  sowbgradient x0 ketowm, ee tei owni f (x) − f (x0 ) ≥ (v, x − x0 ) ∀x ∈ Rn

(3.4.1)

anhavasarowyown: f -i sowbgradientneri bazmowyown x0 ketowm kovowm  sowbdiferencial nanakvowm  ∂f (x0 ) simvolov:

eorem 3.4.1: ∂f (x0 ) bazmowyown o datark ow owcik kompakt :

I Nax cowyc tanq ∂f (x0 )-i owowcikowyown: Ee v1 ∈ ∂f (x0 ), v2 ∈ ∂f (x0 ), apa

f (x)−f (x0 ) ≥ (αv 1 +(1−α)v 2 , x−x0 ) ∀x ∈ Rn , ∀α ∈ [0, 1],

orteic het owm  ∂f (x0 )-i ow owcikowyown: ∂f (x0 ) bazmowyan akowyown aknhayt : Apacowcenq, or ayn datark : Ditarkenq f fownkciayi vergrafik` epi(f ) = {(β, x) ∈ Rn+1 /β ≥ f (x)} :

Qani or ays bazmowyown ak  ow owcik, apa nra ezrayin (f (x ), x ) ketic kareli  tanel henman hiperharowyown: Da nanakowm , or goyowyown owni aynpisi o zroyakan (c, v) ∈ Rn+1 vektor, or cβ + (v, x) ≥ cf (x0 ) + (v, x0 ) ∀(β, x) ∈ epi(f ) :

(3.4.2)

Ee c = 0 , apa (3.4.2)-ic stanowm enq (v, x − x0 ) ≥ 0 ∀x ∈ Rn :

anhavasarowyown: Aysteic het owm , or v = 0, or hakasowyown , qani or (c, v) 6= 0 : Cowyc tanq, or c > 0: (3.4.2) anhavasarowyown x = x0 depqowm owni c(β − f (x0 )) ≥ 0

tesq, orteic anmijakanoren het owm , or c > 0 : Aym (3.4.2) anhavasarowyan erkow maser baanenq c > 0 vi vra aynowhet teadrelov β = f (x) kstananq v f (x) − f (x0 ) ≥ (− , x − x0 ), c

orteic het owm , or v − ∈ ∂f (x0 ) : c

Apacowcenq, or ∂f (x0 ) bazmowyown sahmana ak : Enadrenq haka ak: Ayd depqowm goyowyown kownena aynpisi {vk } (vk ∈ ∂f (x0 )) hajordakanowyown, or kv k k → ∞ : (3.4.1) anhavasarowyownowm teadrelov x = x0 + v k /kv k k, kstananq f (x) − f (x0 ) ≥ kv k k :

(3.4.3)

Qani or f - anndhat , apa (3.4.3) anhavasarowyan ax mas sahmana ak , isk aj mas gtowm  anverjowyan, erb k → ∞, in hakasowyown : J

Fownkciayi minimizaciayi algorimneri makman hamar kar or  nkaragrel havel fownkciayi nvazman owowyownner yowraqanyowr ketowm: Diferenceliowyan depqowm ayd harc mexanikoren low vowm ` nvazman owowyown hakagradienti owowyownn : Sakayn erb fownkcian diferenceli  ayd xndir bard : Bayc ow owcik oro dasi fownkcianeri hamar sowbgradienti gnowyamb hnaravor  nkaragrel fownkcianeri nvazman owowyownner ka owcel minimizaciayi algorimner: Stor berva pndowmner nkaragrowm en ayd fownkcianer nranc nvazman owowyownner: it en het yal pndowmner (te|s, rinak` [4, 7]):

eorem 3.4.2: Dicowq f1 (x), f2 (x), ..., fk (x) diferenceli ow owcik fownkcianer en: Nanakenq f (x) ≡ max fi (x) : i∈[1:k]

Ayd depqowm ∂f (x) = conv{fi0 (x), i ∈ I(x)},

orte I(x) = {i ∈ [1 : k]/fi (x) = f (x)} : eorem 3.4.3: Dicowq tei ownen eorem 3.4.2-i paymanner 0∈ / ∂f (x) :

Ayd depqowm h=−

Π∂f (x) (0) kΠ∂f (x) (0)k

vektor f fownkciayi nvazman owowyownn  x ketowm:

Ver nva eoremner hnaravorowyown en talis amenaarag vayrjqi meodov oro depqerowm gtnelow ow owcik o diferenceli fownkciayi minimowmi keter: Meknabanenq da rinaki mijocov: rinak: Dicowq f (x1 , x2 ) ≡ max fi (x1 , x2 ), i∈[1:3]

orte f1 (x1 , x1 ) = 2x1 + x2 , f2 (x1 , x2 ) = −x1 − 2x2 , f3 (x1 , x2 ) = −x1 + x2 − 3 :

Petq  gtnel f -i minimowmi ket R2 -i vra: Orpes skzbnakan motavorowyown vercnenq x0 = (0, 0) ket: Qani or f1 (x0 ) = f2 (x0 ) = 0, f3 (x0 ) = −3,

apa I(x0 ) kownenanq`

het abar, st eorem 3.4.2-i,

= {1, 2}

∂f (x0 ) = conv{f10 (0, 0), f20 (0, 0)} = conv{(2, 1), (−1, −2)}.

Parz , or

0∈ / ∂f (x0 ),

owsti st eorem 3.4.3-i`

√ 2 2 , ) h = (− 2 2 √

vektor klini f -i nvazman owowyown x0 ketowm: Aym amenaarag vayrjqi meodov gtnenq α0 qayli erkarowyown ka owcenq x1 ket het yal bana ov. x1 = x0 + α0 h0 :

Ownenq

√

√ 2 √ g(α) ≡ f (x + αh ) = max{− α, − α, α − 3} =

√ =

Aysteic

√ max{−α, 2α − 3 2} :

α0 = arg

min f (x0 + αh0 ) = α∈(0,+∞)

√

2:

Het abar, x1 = x0 + α0 h0 = (−1, 1) : Qani or

f1 (x1 ) = f2 (x1 ) = f3 (x1 ) = −1,

apa I(x1 ) = {1, 2, 3} : Het abar, ∂f (x1 ) = conv{f10 (x1 ), f20 (x1 ), f30 (x1 )} = = conv{(2, 1) (−1, −2) (−1, −1)} :

Het  nkatel, or 0 ∈ ∂f (x1 ): Aysteic het owm , or x1 vektor f ow owcik fownkciayi minimowmi ket : Inpes er owm  eorem 3.4.3-ic ow owcik fownkciayi nvazman owowyownner gtnelow hamar kar or xndir  oroel 0 keti proyekcian ow owcik kompakti vra: Nkaragrenq mi iteracion algorim, ori mijocov cankaca towyamb kareli  gtnel 0 keti proyekcian ow owcik bazmanisti vra: Dicowq trva  n a ani vektorneri X = {x1 , x2 , ..., xm } hamaxowmb: Petq  gtnel 0 keti proyekcian M = convX bazmowyan vra, aysinqn` ΠM (0)-n: Ka owcowm enq {vk } hajordakanowyown het yal kerp. ˆ

Orpes v0 skzbnakan motavorowyown vercnowm enq ayn vektor X hamaxmbic, or bavararowm  het yal paymanin. (v 0 , v 0 ) = min (xi , xi ) : i∈[1:m]

ˆ

Enadrenq arden ownenq vk ∈ M vektor: Nkaragrenq vk+1 ka owcman algorim: ntrowm

enq X hamaxmbic ayn xk vektor, or bavararowm  (xk , v k ) = min (v k , xi ) : i∈[1:m]

havasarowyan: Aynowhet havowm enq δ(v k ) ≡ (v k − xk , v k ), tk =

δ(v k ) kxk − v k k

me owyownner: vektor ka owcowm enq het yal ekowrent a nowyamb.

ˆ v k+1

v k+1 = v k + tk (xk − v k ) :

marit  het yal pndowm, or berowm enq a anc apacowyci (te|s, rinak` [4]): eorem 3.4.4: Dicowq {v k } hajordakanowyown ka owcvel  ver nva algorimov: Ayd depqowm v k → ΠM (0), erb k → ∞ : A ajadranq 4: Katarel ver nva algorimi

ragrayin irakanacowm C ++ lezvov: Gtnel ΠM (0) vektor, ee ˙ 1.5, 1), (2, 3, 4)} : M = conv{(1, 1, 1), (2, 2, 2), (1,

XNDIRNER

1. Dicowq f ow owcik fownkcian diferenceli  x0 ketowm: Apacowcel, or ∂f (x0 ) = {f 0 (x0 )} :

2. Dicowq f (x) = kxk : Cowyc tal, or ∂f (0) = B1 (0) :

3. Havel het yal ow owcik fownkcianeri sowbdiferencialner: a)

f (x) = |x − 1| + |x + 1|,

b)

f (x) = max{4x + 1, x − 2},

g)

f (x1 , x2 ) = |x1 − 1/2|x2 | + x2 |,

d)

f (x1 , x2 ) = |x1 + x2 |,

e)

f (x1 , x2 ) = ||x1 | + x2 − 1| :

4. Apacowcel het yal pndowm: Orpeszi x0 ket lini f ow owcik fownkciayi minimowmi ket Rn -i vra, anhraet  bavarar, or 0 ∈ ∂f (x0 ) :

5.

parametreri bolor areqneri depqowm low el het yal xndirner. c

a) b) 6.

kxk − (c, x) → min, x ≥ 0, x ∈ Rn , kxk2

+ kx − ck → min, x ∈ Rn ,

f (x1 , x2 ) = x21 + x1 x2 + x22 + 3|x1 + x2 − 2| → min :

Low owm: Orpeszi (x1 , x2 ) ket lini f -i minimowmi ket,

anhraet 

v ∈ ∂g(x1 , x2 )

bavarar, or goyowyown ownena aynpisi vektor, or

0 ∈ ∂f (x1 , x2 ) ⇔ (2x1 + x2 , 2x2 + x1 ) + 3v = 0,

(3.4.3)

orte g(x1 , x2 ) ≡ |x1 + x2 − 2|: Dvar  tesnel, or   (1, 1), (−1, −1), ∂g(x1 , x2 ) =  conv{(1, 1), (−1, −1)},

ee x1 + x2 > 2 ee x1 + x2 < 2 ee x1 + x2 = 2 :

Ee x1 + x2 > 2, apa (3.4.3) paymanic kstananq 

2x1 + x2 + 3 = 0, 2x2 + x1 + 3 = 0,

⇒ x1 + x2 = −2,

aysinqn hamakarg hamateeli : Ee x1 + x2 < 2, apa hamakarg nowynpes low owm owni: Ee x1 + x2 = 2, apa   2x1 + x2 + 3α = 0, 2x2 + x1 + 3α = 0,  α ∈ [−1, 1],

⇒ α = −1, x1 = x2 = 1 :

aysinqn (1, 1) ket xndri low owmn : 7. x21 + x22 + 2max(x1 , x2 ) → min :

8.

x21 + x22 + 2

9.

x21 + x22 + 4|x1 + x2 − 1| → min :

p

(x1 − 1)2 + (x2 − 2)2 → min :

10. Amenaarag vayrjqi meodov gtnel f (x1 , x2 ) ≡ max fi (x1 , x2 ) i∈[1:3]

fownkciayi minimowmi ket: Katarel iteraciayi erkow qayl: Ayste f1 (x1 , x1 ) = x1 + x2 , f2 (x1 , x2 ) = −x1 − x2 , f3 (x1 , x2 ) = −x1 + x2 − 5 :

3.5

Kown-Takkeri eorem

Dicowq fi (x), i ∈ [0 : m], fownkcianer ow owcik en R -i vra: Ditarkenq f0 (x) fownkciayi minimizaciayi xndir M ≡ {x ∈ Rn /fi (x) ≤ 0, i ∈ [1 : m]} bazmowyan vra. n

f0 (x) → min, x ∈ M :

(3.5.1)

Het  cowyc tal, or M - ow owcik bazmowyown : (3.5.1) xndir kovowm  ow owcik ragravorman xndir: f0 (x) fownkciayi minimowmi keter M bazmowyan vra kovowm en (3.5.1) xndri low owmner: Kazmenq Lagrani fownkcian ` L(x, λ) = λ0 f0 (x) + λ1 f1 (x) + ... + λm fm (x),

orte λ = (λ0 , λ1 , ..., λm ) ∈ Rm+1 :

eorem 3.5.1 (Kown-Takker: Anhraetowyown): Dicowq x∗ ket handisanowm  (3.5.1) xndri low owm: Ayd depqowm goyowyown ownen λ0 ≥ 0, λ1 ≥ 0, ..., λm ≥ 0 ver, oroncic gone mek zro  aynpisin, or

1) L(x, λ) ≥ L(x∗ , λ) ∀x ∈ Rn , 2) λi fi (x∗ ) = 0, i ∈ [1 : m]:

sahmana akelov ndhanrowyown, kareli  enadrel, or f0 (x∗ ) = 0 : Haka ak depqowm kditarkenq f˜0 (x) = f0 (x) − f0 (x∗ ) fownkcian, or nowynpes ow owcik  f˜0 (x∗ ) = 0 : Ditarkenq het yal bazmowyown. I

C = {(µ0 , µ1 , ..., µm ) ∈ Rm+1 /∃x ∈ Rn : f0 (x) < µ0 , fi (x) ≤ µi , i ∈ [1 : m]} :

Ays bazmowyown ow owcik : Ayn anmijapes het owm  sahmanowmic: C -n datark : Iskapes, qani or f0 (x∗ ) < 1, fi (x∗ ) ≤ 1, i ∈ [1 : m],

apa (1, 1, ..., 1) ∈ C :

Aknhayt  na , or 0 ∈/ C, qani or haka ak depqowm goyowyown kownenar aynpisi x ket, or f0 (x) < 0, fi (x) ≤ 0, i ∈ [1 : m],

in hakasowyown : 0 ket anjatenq hiperharowyamb C ow owcik bazmowyownic: Da nanakowm , or goyowyown ownen

λi , i ∈ [0 : m],

or

m X

ver, oroncic gone mek zro , aynpisin,

λi µi ≥ 0 ∀(µ0 , µ1 , ..., µm ) ∈ C :

(3.5.2)

i=0

Cowyc tanq, or λi ≥ 0, i ∈ [0 : m] : Enadrenq, or in-or i0 indeqsi hamar tei owni λi < 0 anhavasarowyown: Aknhayt , or cankaca δ > 0 µi > 0 vi hamar µ ≡ (δ, 0, .., µi , 0, ..0) ∈ C : Teadrelov µ vektori koordinatner (3.5.2) anhavasarowyownowm` kstananq

δλ0 + µi0 λi0 ≥ 0 :

(3.5.3))

Ayste ancnelov sahmani, erb δ → 0 µi → +∞ kstananq, or (3.5.3) anhavasarowyan ax mas gtowm  −∞, isk aj mas zro , or hakasowyown : Aym apacowcenq eoremi erkrord pndowm: (3.5.2) anhavasarowyownowm teadrelov

µ0 = δ > 0, µ1 = 0, ..., µi = fi (x∗ ), µi+1 = 0, .., µm = 0,

ver kstananq` δλ0 + λi fi (x∗ ) ≥ 0 :

Ayste ancnelov sahmani, erb δ gti zroyi` kstananq λi fi (x∗ ) ≥ 0 :

Bayc, qani or λi ≥ 0 , or

(2.5.4)

fi (x∗ ) ≤ 0, apa (2.5.4)-ic het λi fi (x∗ ) = 0 :

owm

(3.5.5)

Aym apacowcenq eoremi ezrakacowyan a ajin ket: Iroq, cankaca x ∈ Rn -i hamar (3.5.3) an{ havasarowyownowm teadrelov µ0 = δ + f0 (x), µ1 = f1 (x), ..., µm = fm (x)

koordinatnerov µ vektor, kstananq λ0 (δ + f0 (x)) + λ1 f1 (x) + ... + λm fm (x) ≥ 0 :

Ancnelov sahmani, erb δ → 0, kstananq` λ0 f0 (x) + λ1 f1 (x) + ... + λm fm (x) ≥ 0 ∀x ∈ Rn

(3.5.6)

(3.5.5)-(3.5. 6)-ic het owm  or L(x, λ) =

m X

λi fi (x) ≥ 0 =

i=0

= λ0 f0 (x∗ )+λ1 f1 (x∗ )+...+λm fm (x∗ ) = L(x∗ , λ) ∀x ∈ Rn : J

eorem 3.5.2 (Kown-Takker: Bavararowyown): Dicowq x∗ ket bavararowm  (3.5.1) xndri bolor sahmana akowmnerin` fi (x∗ ) ≤ 0, i ∈ [1 : m],

goyowyown ownen aynpisi λ0 > 0, λ1 ≥ 0, λ2 ≥ ≥ 0, ..., λm ≥ 0 ver, or tei ownen eorem 3.5.1-i 1)-2) paymanner: Ayd depqowm x∗ vektor (3.5.1) xndri low owm :

sahmana akelov ndhanrowyown, karo enq enadrel, or λ0 = 1 : Ayd depqowm, havi a nelov 1) 2) paymanner, kownenanq` I

f0 (x)+

m X

λi fi (x) ≥ f0 (x∗ )+

i=1

m X

λi fi (x∗ ) = f0 (x∗ ) ∀x ∈ Rn :

i=1

(3.5.7)

Ee x vektor aynpisin , or fi (x) ≤ 0 ∀i ∈ [1 : m], apa (3.5.7) anhavasarowyownic kstananq f0 (x) ≥ f0 (x∗ ) : J

payman (3.5.1) xndrowm het yaln . goyowyown owni aynpisi x̄ vektor, or egowlyarowyan

payman: Ays

fi (x̄) < 0, i ∈ [1 : m] :

Cowyc tanq, or ays paymani depqowm λ0 gor akic kareli  vercnel havasar meki: Iroq, ee λ0 = 0, apa eorem 3.5.1-i 1) 2) ezrakacowyownneric het owm , or m X

λi fi (x̄) ≥ 0,

i=1

or hakasowyown , qani or m X

λi fi (x̄) < 0 :

i=1

Nenq, or ee fi (x), i ∈ [1 : m], fownkcianer anndhat en, apa egowlyarowyan payman ow owcik rag{ ravorman xndrowm nanakowm , or M bazmowyown owni nerqin ket: J

Het anq 3.5.1: Dicowq M = {x ∈ Rn /aj ≤ xj ≤ bj ,

j ∈ [1 : n]},

orte −∞ ≤ aj < bj ≤ +∞, j ∈ [1 : n] : Orpeszi x∗ ∈ M ket lini ow owcik diferenceli f (x) fownkciayi minimowmi ket M bazmowyan vra, anhraet  bavarar, or kamayakan j ∈ [1 : n] hamar   = 0, ee aj < x∗j < bj , ∗ fxj (x ) ≥ 0, ee x∗j = aj 6= −∞,  ≤ 0, ee x∗j = bj 6= +∞ :

Qani or Kown-Takkeri eorem minimowmi anhraet bavarar payman , apa oro depqerowm ayn owyl  talis bacahayt tesqov gtnel anhavasarowyan tipi sahmana akowmnerov maematikakan ragravorman xndirneri low owmner: rinak 1: Low el het yal xndir. f (x1 , x2 ) = 2x21 + x1 x2 + x22 → min, −1 ≤ x1 ≤ 1, x2 ≥ 2 :

Qani or f - owe ow owcik fowkcia , isk sahmana akowmnerov trvo bazmowyown ak  ow owcik, apa ays xndirn owni miak low owm ayn bavararowm  het yal erkow paymannerin.   = 0, ee − 1 < x1 < 1, ≥ 0, ee x1 = −1, fx (x1 , x2 ) = 4x1 + x2  ≤ 0, ee x1 = 1;

fx0 2 (x1 , x2 )

 = x1 + 2x2

= 0, ≥ 0,

ee x2 > 2, ee x2 = 2 :

Aym ays paymanneric kareli kazmel vec hamakarger low el dranq: Sakayn dvar  hamozvel, or 

− 1 < x1 < 1, x2 = 2

4x1 + x2 = 0, x1 + 2x2 ≥ 0,

hamakarg hamateeli  (−1/2, 2) vektor nra low owmn : Het abar ayd vektor na minimizaciayi xndri miak low owmn  : rinak 2: Low el het yal xndir. x21 + (x2 − 2)2 → min, x21 + x22 − 1 ≤ 0, x1 ≥ 0, x2 ≥ 0 :

Qani or owylatreli areqneri bazmowyown owni nerqin ket, apa Lagrani fownkciayowm λ0 gor akic kareli  vercnel havasar meki: Kira elov Kown-Takkeri eorem` kstananq.  0 Lx1 (x, λ) = 2x1 + 2λ1 x1 − λ2 = 0,      L0x2 (x, λ) = 2(x2 − 2) + 2λ1 x2 − λ3 = 0, λ1 ≥ 0, λ2 ≥ 0, λ3 ≥ 0,    λ1 (x21 + x22 − 1) = 0, λ2 x2 = 0, λ3 x3 = 0 :   2 x1 + x22 − 1 ≤ 0, x1 ≥ 0, x2 ≥ 0 :

(3.5.8)

Ditarkenq het yal depqer: 1)

λ1 = 0, λ2 = 0, λ3 = 0: Ayd depqowm (3.5.8) hamakargic stanowm enq x1 = 0, x2 = 2, or i bavararowm x21 + x22 − 1 ≤ 0 anhavasarowyan:

2)

λ1 6= 0, λ2 = 0, λ3 = 0:

Ays depqowm(3.5.8)

hamakargic kstananq  2  x1 + x22 − 1 = 0, 2x1 (1 + λ1 ) = 0,  2(x2 − 2) + 2λ1 x2 = 0 :

Ee λ1 = −1, apa errord havasarowm tei owni: Ee λ1 6= −1, apa kstananq x1 = 0, x2 = 1, λ1 = 1, λ2 = 0 :

Qani or minimizacvo fownkcian owe ow owcik , isk owylatreli vektorneri bazmowyown ak  ow owcik, apa (0, 1) ket xndri miak low owmn :

XNDIRNER

1. Kown-Takkeri eoremi gnowyamb low el hetevyal xndirner. a) (x1 + 1)2 + (x2 − 4)2 + 1 → min, 2x1 − x2 − 2 ≤ 0, x1 ≥ 0 x2 ≥ 0 :

b)

(x1 + 2)2 + (x2 + 2)2 → min, x21 + x22 ≤ 0, x1 ≥ 0, x2 ≥ 0 :

g) d)

x21 + x22 → min, 2x21 + (x2 − 4)2 ≤ 1 : 4x21 − x1 x2 + 4x22 → min, 4 ≤ x1 ≤ 8, −1 ≤ x2 ≤ ≤2:

2. Stowgel, ardyoq (0, 4) vektor het yal xndri low owmn , e o. x21 + (x2 − 2)2 → min, x21 + 2(x2 − 2)2 ≤ 8, x21 + 2x22 ≤ 32 :

3. Stowgel, ardyoq (0, 1) vektor het yal xndri low owmn , e o. exp(x1 − x2 ) → min, x1 + x2 ≤ 1, x1 ≥ 0, x2 ≤ 0 :

Glowx 4

Lagrani anoro gor akicneri meod Lagrani anoro gor akicneri meod ptimizaciayi ayn himnarar skzbownqneric , ori mijocov paymanakan ptimizaciayi xndirner bervowm en o paymanakan ptimizaciayi xndirneri: Masnavorapes, ays glxowm ditarkvowm en maematikakan ragravorman aynpisi xndirner, oroncowm sahmana akowmner trvowm en havasarowyownnerov anhavasarowyownnerov: Enadrvowm , or npatakayin fownkcian sahmana akowmner nerkayacno fownkcianer oork en: Cowyc  trvowm, or aydpisi xndirneri qstremalner gtnvowm en Lagrani fownkciayi stacionar keteri bazmowyan mej: Verjin amanakners, or  arvowm himnavorel Lagrani meod maematikakan rag81

ravorman o oork xndirneri hamar: Nman owsowmnasirowyownnerin kareli  anoanal [7, 11] axatanqnerowm:

4.1

ptimalowyan a ajin paymanner

erkrord kargi

Sahmanowm 4.1.1: h ∈ Rn vektor kovowm  M bazmowyan x∗ ∈ M ketowm oa o, ee goyowyown owni aynpisi ϕ : [−1, 1] → Rn , ϕ(α) = o(α)

artapatkerowm, or bavakanaa

oqr α > 0 veri hamar tei owni het yal payman` x∗ + αh + ϕ(α) ∈ M :

simvolov nanakenq M bazmowyan x∗ ketowm tarva oa o vektorneri bazmowyown: KM (x∗ )

Sahmanowm 4.1.2: Ee K -n kon , apa K ∗ ≡ {y ∈ Rn /(y, x) ≥ 0 ∀x ∈ K}

bazmowyown kovowm  K -i hamalow kon: eorem 4.1.1 (Lyowsterniki eorem oa o harowyan masin): Dicowq M = {x ∈ Rn /fi (x) = 0, i ∈ [1 : m]},

orte fi , i ∈ [1 : m], fownkcianer anndhat diferenceli en: Dicowq x∗ ∈ M enadrenq, or fi0 (x∗ ), i ∈ [1 : m], gradientner g oren ankax en: Ayd depqowm KM (x∗ ) = H ≡ {h ∈ Rn / (fi0 (x∗ ), h) = 0, i ∈ [1 : m]} :

Aysinqn H enatara owyown oa o kon  M bazmowyan hamar x∗ ketowm: I Cowyc tanq, or H harowyan kamayakan vektor oa o vektor : Nanakenq  (x∗ ) (x∗ )... f1x (x∗ ) f1x f1x n  f2x (x∗ ) f2x (x∗ )... f2x (x∗ )  n  A=   (x∗ ) fmx (x∗ ) fmx (x∗ )... fmx n 

Kazmenq havasarowmneri het yal hamakarg` gi (α, r) = fi (x∗ + αh + A> r) = 0, i ∈ [1 : m], (4.1.1)

orte r- m a ani vektor : Cowyc tanq, or ays hamakarg bavararowm  anbacahayt fownkciayi veraberyal eoremi bolor paymannerin: Iroq, gi (0, 0) = 0, giα (0, 0) = (fi0 (x∗ ), h) = 0, i ∈ [1 : m] :

Aknhayt  na , or fownkcional matric

{gir } j (0, 0)

koordinatnerov ketowm havasar

 B ≡ AA> matricin, orn owni hakadar: Het abar, goyowyown owni r(α) artapatkerowm, orova zro keti in-or rjakayqowm, aynpisin, or ayn ayd rjakayqowm bavararowm  (4.1.1) hamakargin r(0) = 0, r0 (0) = −B −1 gα0 (0, 0) = 0,

orte gα0 (0, 0) = (g1α (0, 0), ..., gmα (0, 0)) :

Het abar` lim

α→0

r(α) − r(0) r(α) = lim = r0 (0) = 0 : α→0 α α

(4.1.2)

Nanakelov ϕ(α) = A> r(α), (4.1.1)-(4.1. 2) paymanneric kstananq ϕ(α) = o(α)

gi (x∗ + αh + ϕ(α)) = 0 ∀i ∈ [1 : m] :

Isk sa nanakowm , or h ∈ KM (x∗ ) : Ayspisov apacowcvec, or H ⊆ KM (x∗ ) : Aym cowyc tanq, or KM (x∗ ) ⊆ H : Dicowq h ∈ ∈ KM (x∗ ): st oa o vektori sahmanman goyowyown owni aynpisi ϕ(α) = o(α) artapatkerowm, or bavakanaa

oqr drakan α veri hamar fi (x∗ + αh + ϕ(α)) = 0, i ∈ [1 : m] :

Aysteic, hamaayn diferenceliowyan paymani, kamayakan i-i depqowm kownenanq 0 = fi (x∗ +αh+ϕ(α))−fi (x∗ ) = α[(fi0 (x∗ ), h)+

o(α) ]: α

Owsti (fi0 (x∗ ), h) +

o(α) = 0 ⇒ (fi0 (x∗ ), h) = 0 ⇒ h ∈ H : α

J

Ditarkenq paymanakan ptimizaciayi nd{ hanowr xndir. f (x) → min, x ∈ M :

(4.1.3)

eorem 4.1.2 (Minimowmi ndhanowr anhraet payman): Dicowq f fownkcian diferenceli , isk x∗ ∈ M ket (4.1.3) xndri low owm : Ayd depqowm ∗ f 0 (x∗ ) ∈ KM (x∗ ) :

I

Enadrenq ∗ (x∗ ) : f 0 (x∗ ) ∈ / KM

Ayd depqowm goyowyown owni aynpisi h ∈ KM (x∗ ) vektor, or (f 0 (x∗ ), h) < 0: Aysteic qani or f - diferenceli , apa bavakanaa

oqr α > 0 veri hamar kownenanq f (x∗ + αh) = f (x∗ ) + α[(f 0 (x∗ ), h) +

o(α) ] < f (x∗ ) : α

Sa hakasowyown , qani or x∗ -n minimowmi ket  M bazmowyan vra: J

f -i

lokal

eorem 4.1.3 (Hamalow koni ka owcowm): Dicowq tei ownen eorem 4.1.1-i paymanner: Ayd depqowm` ∗ KM (x∗ )

⊥

n

= H = A ≡ {y ∈ R /y =

m X

λi fi0 (x∗ ),

i=1

λi ∈ R, i ∈ [1 : m]} : I Nax, qani or H - KM (x∗ ) = H , apa

enatara owyown 

∗ KM (x∗ ) = H ⊥ :

Aym cowyc tanq, or A ⊆ H⊥ :

Iroq, dicowq ∀h ∈ H, ∀y ∈ A ⇒ y =

m X

λi fi0 (x∗ ) ⇒

i=1

⇒ (y, h) =

m X

λi (fi0 (x∗ ), h) = 0 ⇒ y ∈ H ⊥ :

i=1

Aym enadrenq, or goyowyown owni aynpisi b ∈ ∈ H ⊥ vektor, or b ∈ / A : Qani or fi0 (x∗ ), i ∈ ∈ [1 : m] gradientner g oren ankax en, apa A-n m a ani enatara owyown , or ak ow owcik bazmowyown : Anjatenq ayn b ketic: Hamaayn xist anjatman eorem 3.1.2-i` goyowyown ownen aynpisi p vektor ε > 0 iv, or (p, a) ≤ (p, b) − ε ∀ a ∈ A :

(4.1.4)

Cowyc tanq, or (p, a) = 0 ∀a ∈ A :

Ee or  a ∈ A-i hamar (p, a) > 0, apa teadrelov αa ∈ A (α ≥ 0) vektorner (4.1.4) anhavasarowyan mej gtecnelov α-n anvejowyan kstananq hakasowyown, qani or anhavasarowyan ax mas kgti +∞, isk aj mas verjavor iv : Ee (p, a) < 0, apa katarelov nowyn datoowyownner, noric kganq hakasowyan: Ayspisov, (p, a) = 0 ∀a ∈ A : Aysteic (fi0 (x∗ ), p) = 0, i ∈ [1 : m] ⇒ p ∈ H ⇒ (p, b) = 0 : (4.1.5)

Bayc (4.1.4) anhavasarowyownic het owm , or (p, b) > ε > 0, in hakasowm  (4.1.5)-in : Ayspisov, apacowcvec, or ∗ KM (x∗ ) = H ⊥ = A :

J

Aym ditarkenq havasarowyan tipi sahmana akowmnerov paymanakan ptimizaciayi hete{ vyal xndir` f0 (x) → extr, fi (x) = 0, i ∈ [1 : m] :

(4.1.6)

Enadrvowm , or fi , i ∈ [0 : m], fownkcianer anndhat diferenceli en Rn -i vra: Pahanjvowm  gtnel f0 (x) fownkciayi qstremowmi keter M ≡ {x ∈ Rn / fi (x) = 0, i ∈ [1 : m]}

bazmowyan vra: Ayd keter kovowm en (4.1.6) xn{ dri low owmner: M bazmowyan keter kovowm en (4.1.6) xndri owylatreli keter: Dicowq λ = (λ0 , ..., λm ) ∈ Rm+1 : Kazmenq Lagrani fownkcian` L(x, λ) =

m X

λi fi (x) :

i=0

eorem 4.1.4 (Lagrani anoro gor akicneri meod): Dicowq x∗ ket (4.1.6) xndri low owmn : Ayd depqowm goyowyown ownen λ0 , λ1 , λ2 , ..., λm ver, oroncic gone mek zroyic tarber  aynpisin , or m X

λi fi0 (x∗ ) = 0,

i=0

kam or nowynn  L0x (x∗ , λ) = 0 ⇔ L0xi (x∗ , λ) = 0, i ∈ [1 : n] :

(4.1.7)

λ0 , λ1 , . . . , λm ver kovowm en Lagrani baz-

mapatkiner kam anoro gor akicner:

Enadrenq, or x∗ ket (4.1.6) xndrowm lokal minimowmi ket  (lokal maqsimowmi depq qnnarkvowm  analog  ov): Ee fi0 (x∗ ), f20 (x∗ ), .., fm0 (x∗ ) gradientner g oren ankax en, apa, st minimowmi ndhanowr anhraet paymani eorem 4.1.3-i, kownenanq I

∗ (x∗ ) = f00 (x∗ ) ∈ KM

= {y/y =

m X

λi fi0 (x∗ ), λi ∈ R, i ∈ [1 : m]} :

i=1

Aysteic anmijakanoren het owm , or goyowyown ownen λ1 , λ2 , ..., λm ver, aynpisin, or f00 (x∗ )

=

m X

λi fi0 (x∗ ) :

i=1

Ays depqowm eoremi pndowm apacowcva : Ee fi0 (x∗ ), f20 (x∗ ), .., fm0 (x∗ ) gradientner g oren kaxva en, apa goyowyown kownenan gor akicner λi , i ∈ [1 : m], orocic gone mek zro  aynpisin, or m X

λi fi0 (x∗ ) = 0 :

i=1

Aysteic het owm , or 0f00 (x∗ )

+

m X

λi fi0 (x∗ ) = 0 :

i=1

J

Aym enadrenq, or (4.1.6) xndrowm bolor fownkcianer erkow angam anndhat diferenceli en: it  het yal pndowm (te|s, rinak` [4]): eorem 4.1.5 (qstremowmi erkrord kargi anhraet payman): Dicowq x∗ - (4.1.6) xndrowm lokal minimowmi (lokal maqsimowmi) ket  f10 (x∗ ), f20 (x∗ ), ..., fm (x∗ ) vektorner g oren ankax en: Ayd depqowm goyowyown ownen

λ0 = 1, λ1 , ..., λm ver aynpisin, or tei owni

het yal payman.

(L00xx (x∗ , λ)h, h) ≥ 0 ((L00xx (x∗ , λ)h, h) ≤ 0) ∀h ∈ H = = {h ∈ Rn /(fi0 (x∗ ), h) = 0, i ∈ [1 : m]} :

eorem 4.1.6 (Erkrord kargi bavarar payman): Dicowq x∗ - (4.1.6) xndri owylatreli ket  goyowyown owni aynpisi λ ∈ Rm+1 vektor, or tei ownen het yal paymanner.

1) λ0 = 1, 2) L0xi (x∗ , λ) = 0, i ∈ [1 : n], 3) kamayakan o zroyakan h ∈ H vektori hamar tei owni (L00xx (x∗ , λ)h, h) > 0 ((L00xx (x∗ , λ)h, h) < 0) (4.1.8)

anhavasarowyown:

Ayd depqowm x∗ - (4.1.6) xndrowm lokal minimowmi (lokal maqsimowmi) ket : I

Ee x∗ ket M bazmowyan a annacva

ket , apa eoremi ezrakacowyown trivial : Dicowq aym x∗ - M bazmowyan sahmanayin ket  ayn xndrowm lokal minimowmi ket : Ayd depqowm goyowyown kownena aynpisi {xk } hajordakanowyown, or bavararowm  het yal paymannerin. xk ∈ M, xk → x∗ , f0 (xk ) < f0 (x∗ ) :

(4.1.9)

xk

-n nerkayacnenq het yal tesqov. xk = x∗ + αk hk ,

orte hk = (xk − x∗ )/αk :

Qani or, khk k = 1, apa ndhanrowyown sahmana akelov karo enq enadrel, or hk → h 6= 0 :

Havi a nelov (4.1.9) payman` ownenq 0 = fi (xk )−fi (x∗ ) = (fi0 (x∗ ), αk hk )+o(αk ), i ∈ [1 : m] :

Baanelov ays a nowyownner ancnelov sahmani` kstananq

αk -i

vra

(fi0 (x∗ ), h) = 0, i ∈ [1 : m] :

Aysinqn` h ∈ H : Qani or, st enadrowyan, λ0 = 1, apa (4.1.9)-ic stanowm enq m X

L(xk , λ) = f0 (xk ) +

λi fi (xk ) ≤ f0 (xk ) ≤

i=1

≤ f0 (x∗ ) = f0 (x∗ ) +

m X

λi fi (x∗ ) = L(x∗ , λ) : (4.1.10)

i=1

eoremi paymanneric het owm , or L(x, λ) Lagrani fownkcian erkow angam diferenceli  x∗ ketowm: Het abar, nerkayacnelov ayd fownkcian, st eylori bana i, x∗ ketowm, stanowm enq L(xk , λ) = L(x∗ , λ) + (L0x (x∗ , λ), αk hk )+

+ (L00xx (x∗ , λ)(αk hk ), αk hk ) + o(αk2 ) : or, st enadrowyan, L0x (x∗ , λ) = 0,

Qani aysteic , or

apa (4.1.10) anhavasarowyownic het owm

αk2 00 ∗ (L (x , λ)hk , hk )) + o(αk2 ) ≤ 0 : 2 xx

Ays anhavasarowyan erkow maser baanelov αk2 vi vra ancnelov sahmani` kstananq (L00xx (x∗ , λ)h, h) ≤ 0,

or hakasowm  eoremi (4.1.8) paymanin: J

Parzagowyn depqerowm Lagrani anoro gor akicneri meod owyl  talis bacahayt tesqov gtnel maematikakan ragravorman xndirneri low owmner havasarowyownneri tipi sahmana akowmneri depqowm: Dra hamar petq  katarel het yal qayler. ˆ ˆ

ˆ ˆ

Kazmel Lagrani fownkcian: Grel qstremowmi a ajin kargi anhraet payman Lagrani fownkciayi hamar stanal havasarowmneri hamakarg, orov bnowagrvowm  xndri stacionar keteri bazmowyown: Gtnel stacva hamakargi low owmner: qstremowmi erkrord kargi bavarar paymanneri mijocov ayd low owmneric anjatel qstremowmi keter:

Ays algorim meknabanenq rinaknerov: rinak 1: Low el het yal xndir. f0 (x) = x21 + x22 → extr, f1 (x) = (x1 − 1)2 + x22 − 4 = 0 :

Low owm: Kazmenq Lagrani fownkcian L(x, λ) = λ0 f0 (x) + λ1 f1 (x) = = λ0 (x21 + x22 ) + λ1 ((x1 − 1)2 + x22 − 4) :

st (4.1.7) anhraet paymani` ownenq  0  Lx1 (x, λ0 , λ1 ) = 2λ0 x1 + 2λ1 (x1 − 1) = 0, L0 (x, λ0 , λ1 ) = 2λ0 x2 + 2λ1 x2 = 0,  x2 f1 (x) = (x1 − 1)2 + x22 − 4 = 0 : (4.1.11) Ee, λ0 = 0, apa (4.1.11) hamakargic stanowm enq 2λ1 (x1 − 1) = 0, 2λ1 x2 = 0, (x1 − 1)2 + x22 − 4 = 0 : (4.1.12)

Qani or λ0 , λ1 gor akicner miaamanak zro en, apa λ1 6= 0 : Het abar, (4.1.12) hamakargi a ajin erkow pay{ manneric kstananq x1 = 1, x2 = 0,

or i bavararowm errord havasarman: Ayspi{ sov, λ0 6= 0: ndhanrowyown sahmana akelov,

karo enq enadrel, or λ0 = 1 : Ayd depqowm (4.1.11) hamakarg kndowni het yal tesq`   2x1 + 2λ1 (x1 − 1) = 0, 2x2 + 2λ1 x2 = 0,  (x1 − 1)2 + x2 − 4 = 0 :

(4.1.13)

Ditarkenq ays hamakargi erkrord havasarowm: Ee x2 = 0, apa errordic kstananq x1 = 3, x1 = = −1, isk a ajin havasarowmic` λ1 = −3/2 : Ee x2 6= 0, apa erkroric kownenanq λ1 = −1 : Ayd depqowm a ajin havasarowm tei owni, ay{ sinqn (4.1.13) hamakarg hamateeli : Ayspisov stanowm enq erkow stacionar keter` x∗1 = 3, x∗2 = 0, λ1 = − 32 ;

x∗1 = −1, x∗2 = 0, λ1 = − 21 :

Stowgenq erkrord kargi (4.1.8) bavarar paymanner ayd keteri hamar: Ownenq` (L00xx h, h) = 2(1 + λ1 )h21 + 2(1 + λ1 )h22 , h ∈ H = {h = (h1 , h2 ) ∈ R2 /2(x∗1 − 1)h1 + 2x∗2 h2 = 0 :

Aysteic het  tesnel, or tei owni

A(3, 0)

keti hamar

(L00xx h, h) < 0 ∀h ∈ H, h 6= 0,

anhavasarowyown: Owsti, A-n lokal maqsimowmi ket : Nman  ov hamozvowm enq, or B(−1, 0)-n lokal minimowmi ket : Myows komic, qani or f0

fownkcian hasnowm  ir me agowyn ow oqragowyn areqnerin, apa B ket global minimowmi ket , isk A-n global maqsimowmi ket : rinak 2: Low el het yal xndir. f0 (x) = x21 + x22 + x23 → min, f1 (x) = x21 + x22 − x3 = 0, f2 (x) = x1 + x2 + x3 − 4 = 0 :

st (4.1.7) anhraet paymani` ownenq`  0 Lx1 (x, λ) = 2λ0 x1 + 2λ1 x1 + λ2 = 0,      L0x2 (x, λ) = 2λ0 x2 + 2λ1 x2 + λ2 = 0, L0x3 (x, λ) = 2λ0 x3 − λ1 + λ2 = 0,    f1 (x) = x21 + x22 − x3 = 0,   f2 (x) = x1 + x2 + x3 − 4 = 0 :

Ee, λ0 = 0, apa kstananq havasarowmneri het yal hamakarg.  2λ1 x1 + λ2 = 0,      2λ1 x2 + λ2 = 0, −λ1 + λ2 = 0,   x2 + x22 − x3 = 0,    1 x1 + x2 + x3 − 3 = 0 :

(4.1.14)

Ee λ1 = 0, apa (4.1.14) hamakargi errord havasarowmic het owm , or λ2 = 0, or hnaravor , orovhet bolor gor akicner miaamanak zro en: Ee λ1 6= 0, apa (4.1.14) hamakargi a ajin ereq havasarowmneric stanowm enq x1 = x2 = − :

Teadrelov ays areqner hamakargi verjin erkow havasarowmneri mej` stanowm enq haka{ sowyown: Ayspisov, λ0 6= 0: ndownenq λ0 = 1: Ayd depqowm hamakarg kndowni het yal tesq.  2x1 (1 + λ1 ) + λ2 = 0,      2x2 (1 + λ2 ) + λ2 = 0, 2x3 − λ1 + λ2 = 0,   x2 + x22 − x3 = 0,    1 x1 + x2 + x3 − 4 = 0,

(4.1.15)

(4.1.15) hamakarg owni het yal erkow low owmner. ; x∗1 = 1, x∗2 = 1, x∗3 = 2, λ1 = 32 , λ2 = − 10 , λ2 = − 68 : x∗1 = −2, x∗2 = −2, x∗3 = 8, λ1 = − 20

Stowgenq erkrord kargi (4.1.8) bavarar pay{ manner A(1, 1, 2) B(−2, −2, 8) keteri hamar: Ownenq (L00xx h, h) = 2(1 + λ1 )h21 + 2(1 + λ1 )h22 + 2h2 h3 , h ∈ H = {h ∈ R3 /2x∗1 h1 + 2x∗2 h2 − h3 = 0, h1 + h2 + h3 = 0} :

Aysteic A(1, 1, 2) keti hamar kstananq h1 = −h2 , h3 = 0 ⇒ (L00xx h, h) =

10 2 h > 0 ∀h 6= 0 : 3 2

Aysinqn` A-n lokal minimowmi ket : Nowyn  ov stanowm enq, or B(−2, −2, 8)-n lokal maqsimowmi ket :

XNDIRNER

1. Low el het yal xndir. x21 + x22 → min, x21 + x22 − 8 = 0 :

2. Low el het yal xndir. x21 + x22 → min, x21 + 2x22 − 8 = 0 :

3. Stowgel, ardyoq low owmn , e o:

(0, 2)

ket het yal xndri

x21 + x22 → min, x2 + x21 − 2 = 0 :

4. Stowgel, ardyoq low owmn , e o:

(−2, 2)

ket het yal xndri

x1 x2 → min, x21 + x22 − 8 = 0 :

5. Low el het yal xndir. 2x21 + x22 + 2x23 → extr, 2x1 + x2 + 2x3 = 12, x1 + 2x2 + x3 = 10 :

6. Low el het yal xndir. x21 − x22 + x23 → max, x1 + 2x22 − x3 = 4, 2x1 + 2x2 + x3 = 14 :

4.2

Lagrani anoro gor akicneri meod (xa  sahmana akowmneri depq)

Aym ditarkenq paymanakan ptimizaciayi ndhanowr xndir, orte sahmana akowmner trvowm en havasarowyownnerov anhavasarowyownnerov` f0 (x) → extr,

fi (x) = 0, i ∈ [1 : k], fi (x) ≤ 0, i ∈ [k + 1 : m] : (4.2.1) Ayste enadrvowm , or fi (x), i ∈ [0 : m], fownkcianer anndhat diferenceli en Rn -i

vra:

ket kovowm  owylatreli, ee ayn bavararowm  (4.2.1) xndri bolor sahmana akowmnerin: x∗ ∈ Rn ket kovowm  (4.2.1) xndri low owm, ee ayn f0 (x) fownkciayi qstremowmi ket  x ∈ Rn

M ≡ {x ∈ Rn / fi (x) = 0, i ∈ [1 : k], fi (x) ≤ 0, i ∈ [k + 1 : m]}

bazmowyan vra: Sahmanowm 4.2.1: Dicowq x̄ owylatreli ket  (4.2.1) xndrowm: fi (x) ≤ 0 (i ∈ [k + 1 : m]) sahmana akowm kovowm  aktiv ayd ketowm, ee fi (x̄) = 0: Ee fi (x̄) < 0, apa ayd sahmana akowm kovowm  pasiv:

simvolov nanakenq x̄ ketowm aktiv sahmana akowmneri indeqsneri bazmowyown` Ia (x̄)

Ia (x̄) = {i ∈ [k + 1, m]/ fi (x̄) = 0} :

it en het yal pndowmner (te|s, rinak` [4, 6]): eorem 4.2.1 (qstremowmi a ajin kargi anhraet payman): Dicowq x∗ ket (4.2.1) xndrowm lokal minimowmi (lokal maqsimowmi) ket : Ayd depqowm goyowyown ownen λ0 , ..., λm ver, oroncic gone mek zroyic tarber  aynpisin, or

a) L0xi (x∗ ) = 0, i ∈ [1 : n], orte L(x, λ) =

m X

λi fi (x),

i=0

b) λi ≥ 0 (λi ≤ 0), i ∈ [k + 1 : m], g) λi fi (x∗ ) = 0, i ∈ [k + 1 : m] :

g) payman kovowm  pasiv-aktiv sahmana akowmneri payman: eorem 4.2.2 (A ajin kargi bavarar payman): Dicowq x∗ vektor bavararowm  he{ t yal paymannerin.

1) x∗ -  (4.2.1) xndri owylatreli ket , 2) goyowyown owni λ = (λ0 , λ1 , ..., λm ) vektor λ0 = 1 paymanov aynpisin, or (x∗ , λ) zowyg bavararowm  eorem 4.2.1-i a), b), g) paymannerin, 3) x∗ ketowm (4.2.1) xndri aktiv sahma{ na akowmneri havasarowyownneri qanakneri gowmar havasar  n-i:

Ayd depqowm, ee λi > 0, i ∈ Ia (x∗ ), apa x∗ - (4.2.1) xndrowm lokal minimowmi ket , ee λi < 0, i ∈ Ia (x∗ ), apa x∗ - (4.2.1) xndrowm lokal maqsimowmi ket :

Aym  akerpenq qayleri ayn herakanowyown, oronc mijocov kareli  low el xa  sahma{ na akowmnerov maematikakan ragravorman xndirner: ˆ ˆ

ˆ

ˆ ˆ

Kazmel Lagrani fownkcian: Grel qstremowmi a ajin kargi anhraet payman Lagrani fownkciayi hamar stanal havasarowmneri hamakarg, orov bnowagrvowm  xndri stacionar keteri bazmowyown: Grel pasiv-aktiv sahmana akowmneri paymanner anhavasarowyownnerin hamapatasxano Lagrani gor akicneri o bacasakan (o drakan) linelow paymanner: Low el stacva hamakarger` havi a nelov Lagrani gor akicneri nanner: ptimalowyan a ajin kargi bavarar paymanneri mijocov ayd low owmneric anjatel qstremowmi keter:

Ays algorim meknabanenq rinaki mijocov: rinak: Low el het yal xndir. x1 − x22 → extr, x1 − x2 − 1 = 0, x21 + x22 − 5 ≤ 0 :

Kazmenq Lagrani fownkcian L(x, λ) = λ0 (x1 −x22 )+λ1 (x1 −x2 −1)+λ2 (x21 +x22 −5) :

st qstremowmi anhraet paymani` ownenq ha{ vasarowmneri anhavasarowmneri het yal ha{ makarg. (a) (b) (c) (d) (e)

L0x1 (x, λ) = λ0 + λ1 + 2λ2 x1 = 0, L0x2 (x, λ) = −2λ0 x2 − λ1 + 2λ2 x2 = 0, x1 − x2 − 1 = 0, x21 + x22 − 5 ≤ 0, λ2 ≥ 0, λ2 (x21 + x22 − 5) = 0 :

Ditarkenq erkow depq. 1) 2)

λ0 = 0,

λ0 6= 0:

A ajin depqowm hamakargi (a) sarowmneric kstananq 

λ1 + 2λ2 x1 = 0, −λ1 + 2λ2 x2 = 0

(b) hava(4.2.2)

hamakarg: Ee λ2 = 0, apa (4.2.2) hamakargic kstananq λ1 = 0, aysinqn bolor bolor gor{

akicner zro en, or hakasowyown : Ee λ2 6= 0, apa (g) (e) paymanneric kstananq 

x21 + x22 − 5 = 0, x1 − x2 − 1 = 0 :

hamakarg: Ays hamakarg owni erkow low owm. 

kam



x1 = 2, x2 = 1

(4.2.3)

x1 = −1, x2 = −2 :

(4.2.4)

Gowmarelov (4.2.2) hamakargi havasarowmner` kstananq 2λ2 (x1 + x2 ) ⇒ x1 = −x2 ,

or hakasowm  (4.2.3) (4.2.4) hamakargerin: Het abar, a ajin depq hnaravor : Ditarkenq erkrord depq. λ0 6= 0: ndownelov λ0 = 1` (a)-( b) paymanneric kstananq 

1 + λ1 + 2λ2 x1 = 0, −2x2 − λ1 + 2λ2 x2 = 0 :

Ee λ2 = 0, apa (4.2.5) hamakargic havasarowyownic kstananq

(4.2.5)

(g)

  1 + λ1 = 0, −2x2 − λ1 = 0,  x1 − x2 − 1 = 0 :

Low elov ays hamakarg` stanowm enq stacionar het yal ket. A(3/2, 1/2), λ1 = −1, λ2 = 0 :

λ2 6= 0

depqowm ownenq  2 x + x22 − 5,    1 x1 − x2 − 1 = 0, 1 + λ1 + 2λ2 x1 = 0,    −2x2 − λ1 + 2x2 = 0 :

hamakarg: Low elov ays hamakarg` stanowm enq s erkow stacionar keter. B(2, 1), λ1 = −5/3, λ2 = 1/6, C(−1, −2), λ1 = 2/3, λ2 = 5/6 :

Ays ereq keteri hamar stowgenq qstremowmi a ajin kargi bavarar paymanner: B keti hamar aktiv  x21 + x22 − 5 ≤ 0 sahmana akowm nran hamapatasxan Lagrani gor akic drakan : Myows komic, aktiv sahmana akowmneri havasarowyownneri qanakneri gowmar havasar  erkowsi, or anhaytneri ivn : Nanakowm  B -n lokal minimowmi ket : Nowyn  ov` C -n lokal minimowmi ket : Bayc qani or xndri sahmana akowmneri bazmowyown kompakt , apa npatakayin fownkcian owni global minimowmi maqsimowmi keter: Havelov stacva keterowm npatakayin fownkciayi areqner` parzowm enq, or A ket global maqsimowmi ket , C -n global minimowmi ket , isk B -n lokal minimowmi ket :

XNDIRNER

1. Low el xa  sahmana akowmnerov het yal xndir. x21 − x2 → min, x1 + x2 − 6 = 0, 1 − x1 ≤ 0, x21 + x22 − 26 ≤ 0 :

2. Low el xa  sahmana akowmnerov het yal xndir. x21 + x22 + x23 → min, 2x1 − x2 + x3 ≤ 5, x1 + x2 + x3 = 3 :

3. Gtnel oa o KM (x) kon M bazmowyan hamar x ketowm: a) M = {(x1 , x2 ) ∈ R2 \int(R+2 ) : x21 + x22 ≤ 1}, x = (0, 1);

b) g) d)

) : x21 + x22 ≤ 1}, M = {(x1 , x2 ) ∈ R2 \int(R+ x = (0, 0);

M = {(x1 , x2 )/x21 ≤ x32 }, x = (0, 0); M = {0, 1, , ..., , ...}, x = 0; n M = {0, 1, , ..., n , ...}, x = 0 :

e) 4. Apacowcel het yal pndowm: Orpeszi K ⊆ Rn kon lini ow owcik, anhraet  bavarar, or ∀x, y ∈ K ⇒ x + y ∈ K : 5. Dicowq K ⊆ Rn ak ow owcik kon : Apacowcel, or K ∗∗ = K :

6. Dicowq K1 , K2 ⊆ Rn - ak ow owcik koner en: Apacowcel, or a) (K1 + K2 )∗ = K1∗ ∩ K2∗ ; b) (K1 ∩ K2 )∗ = K1∗ + K2∗ : Low owm: Ownenq (K1 ∩ K2 )∗ = (K1∗∗ ∩ K2∗∗ )∗ = = ((K1∗ + K2∗ )∗ )∗ = (K1∗ + K2∗ )∗∗ = K1∗ + K2∗ :

Glowx 5

Variacion haiv Variacion haiv ptimizaciayi bain , orte owsowmnasirvowm en integralayin tipi fownkcionalneri minimizaciayi xndirner oro fownkcional tara owyownnerowm: Ays glxowm ditarkvowm  Zx1 I(y) =

L(x, y, y 0 ) dx

x0

tipi fownkcionali minimizaciayi (maqsimi{ zaciayi) xndir C 1 [x0 , x1 ] fownkcional tara owyan vra: Cowyc  trvowm, or ayd fownk{ cionali qstremowmner bavararowm en ezrayin paymannerov erkrord kargi mi diferencial havasarman, or kovowm  yleri havasarowm: Ayd havasarowmov kap  ste vowm variacion havi diferencial havasarowmneri tesowyown106

neri mij : Ayd isk pata ov variacion havi meodner gtagor owm en ezrayin paymannerov diferencial havasarowmneri low owmneri goyowyan apacowycnerowm: Ays glxowm variacion havi parzagowyn xndirneri qstremalneri bnoroman hamar trvowm en oro bavarar paymanner: Variacion havi tesowyan aveli xor owsowmnasirowyownnerin kareli  anoanal [1-2, 12-13] axatanqnerowm:

5.1

yleri havasarowm

Dicowq L(x, y, y0 ) orpes ereq o oxakani fownkcia erkow angam anndhat diferenceli  R3 -i vra: Pahanjvowm  gtnel aynpisi y(x) ∈ C 1 [x0 , x1 ] fownkcia, or bavarari y(x0 ) = y0 , y(x1 ) = y1 ezrayin paymannerin Rx handisana I(y) ≡ L(x, y, y0 ) dx fownkcionali x lokal minimowmi (lokal maqsimowmi) ket C 1 [x0 , x1 ] tara owyan normi imastov: Ays xndir  akerpvowm  het yal kerp.

Zx1 I(y) ≡

L(x, y, y 0 ) dx → extr,

(5.1.1)

x0

y(x0 ) = y0 , y(x1 ) = y1 ,

or kovowm  amracva ezrerov variacion xndir: Ayn variacion havi parzagowyn xndirn : Aym tanq I fownkcionali lokal minimowmi (lokal

maqsimowmi) sahmanowm normi imastov:

C 1 [x0 , x1 ]

tara owyan

Sahmanowm 5.1.1: Dicowq M ≡ {y ∈ C 1 [x0 , x1 ]/y(x0 ) = y0 , y(x1 ) = y1 } : y ∗ ∈ M kovowm  I fownkcionali lokal minimowmi (lokal maqsimowmi) ket M bazmowyan vra, ee goyowyown owni δ > 0 iv aynpisin, or bolor y ∈ ∈ M fownkcianeri hamar, oronq bavararowm en ky − y ∗ k1 < δ paymanin, tei owni I(y) ≥ I(y ∗ ) (I(y) ≤ I(y ∗ ) :

anhavasarowyown: y ∗ - kovowm  na (5.1.1) xndri low owm: eorem 5.1.1: Ee y ∗ (x) fownkcian (5.1.1) xndri low owmn , apa ayn bavararowm  −

d 0 L 0 + L0y = 0, dx y

(5.1.2)

diferencial havasarman, or kovowm  yleri havasarowm:

Enadrenq, or y∗ - (5.1.1) xndrowm lokal minimowmi ket  (lokal maqsimowmi depq qn{ narkvowm  analog  ov): Dicowq h(·) ∈ C01 [x0 , x1 ]: Aysinqn I

h(·) ∈ C 1 [x0 , x1 ]

h(x0 ) = 0, h(x1 ) = 0 :

Ditarkenq mek o oxakani het yal fownkcian. Zx1 ϕ(α) =

L(x, y ∗ (x) + αh(x), (y ∗ (x))0 + αh0 (x)) dx :

x0

(5.1.3)

Qani or y∗ - I fownkcionali lokal minimowmi ket , apa bavakanaa

oqr α veri hamar tei owni ϕ(α) ≥ ϕ(0)

anhavasarowyown: Aysinqn` 0 ket ϕ fownkciayi lokal minimowmi ket : Het abar` ϕ0 (0) = 0 :

Aysteic, st parametric kaxva integrali a ancman kanoni, kownenanq Zx1 ϕ0 (0) = (L0y h + L0y0 h0 ) dx = 0 :

(5.1.4)

x0

Katareenq maserov integrowm, havi a nelov h(x0 ) = 0, h(x1 ) = 0 paymanner, kstananq Zx1

Zx1

L0y0 h0 dx = L0y0 (h(x1 ) − h(x0 )) −

x0

x0

Zx1 =−

d 0 L 0 h dx : dx y

x0

d 0 L 0 h dx = dx y

Aysteic (5.1.4)-ic kstananq Zx1 d (L0y − L0y0 )h(x) dx = 0 ∀h(x) ∈ C 1 [x0 , x1 ], dx x0

h(x0 ) = 0, h(x1 ) = 0 :

(5.1.5)

Aym cowyc tanq, or (5.1.5) paymanic het owm  yleri havasarowm: Nanakenq a(x) ≡ L0y (x, y ∗ , (y ∗ )0 ) −

d 0 Ly0 (x, y ∗ , (y ∗ )0 ) : dx

Cowyc tanq, or a(x) = 0 ∀x ∈ [x0 , x1 ] :

Enadrenq, or in-or ξ ∈ [x0 , x1 ] ketowm a(ξ) 6= 6= 0: ndhanrowyown xaxtelov, enadrenq, or a(ξ) > 0: Qani or a(x)- anndhat fownkcia , apa goyowyown kownena ξ keti mi rjakayq` (ξ − δ, ξ + δ) ⊆ [x0 , x1 ], aynpisin, or a(x) > 0 ∀x ∈ (ξ − δ, ξ + δ) :

Dicowq

p = ξ − δ, q = ξ + δ :

Aym ditarkenq het yal h(x) fownkcian.   0, (x − p)2 (x − q)2 , h(x) =  0,

ee x ∈ [x0 , p] ee x ∈ [p, q] ee x ∈ [q, x1 ]

Parz , or h(·) ∈ C 1 [x0 , x1 ] Ownenq

h(x0 ) = h(x1 ) = 0 :

Zq

Zx1 a(x)h(x)dx = x0

a(x)h(x) dx > 0, p

or hakasowm  (5.1.5)-in: J

rinak (yleri havasarman low owm handisa{

nowm  lokal minimowmi ket): Z0 I(y) ≡

(y 0 )2 dx → min, y(0) = 0, y(1) = 1 :

Kazmenq yleri havasarowm d 3(y 0 )2 = 0 ⇒ 3(y 0 )2 = C ⇒ y 0 = const ⇒ dx ⇒ y(x) = C1 x + C2 :

Havi a nelov xndri ezrayin paymanner` kstananq y∗ (x) = x, or xndri miak qstremaln : Cowyc tanq, or ayn lokal minimowmi ket : Dicowq h(·) ∈ C01 [0, 1] :

Ayd depqowm ∗

Z1

I(y + h) =

0 3

Z1 dx + 3

(1 + h ) dx =

Z1

h0 dx+

Z1 +

0 2

∗

Z1

(h ) (3 + h ) dx = I(y ) +

(h0 )2 (3 + h0 ) dx :

Aysteic, aknhayt , or ee khk1 < 3, apa 3 + h(x) > 0 ∀x ∈ [0, 1] :

Het abar`

I(y ∗ + h) ≥ I(y ∗ ),

aysinqn` y∗ (·)- lokal minimowmi ket :

XNDIRNER

1. Low el variacion havi het yal parzagowyn xndirner: a)

Z1

((y 0 )2 + y 2 ) dx → min, y(0) = 0, y(1) = 1 :

b)

Z0

(12xy − (y 0 )2 )dx → min, y(−1) = 1, y(0) = 0 :

−1

g)

Zπ/2 ((y 0 )2 − y 2 ) dx → min, y(0) = 1, y(π/2) = 0 :

d)

Z1

(y 2 + (y 0 )2 + 2y exp(x)) dx → min, y(0) =

= 0, y(1) = 1 :

e)

Z3/2 ((y 0 )2 + 2y) dx → min, y(0) = 0, y(3/2) = 1 :

z)

Z1

(4y sin x − y 2 − (y 0 )2 ) dx → max, y(0) = y(1) =

=0:

)

Zπ/2 (6y sin 2x + y 2 − (y 0 )2 ) dx → max, y(0) =

= y(π/2) = 0 :

2. Amenaarag vayrjqi xndir: Owaig harowyan mej mi nowyn owaigi vra gtnvo O(0, 0) B(x1 , y1 ) keter miacnel aynpisi oork korov (gtnel havasarowm), orov anrowyan owi azdecowyamb arvo nyowakan ket ver i O ketic a anc skzbnakan aragowyan khasni nerq i B ket amenakar amanakowm: Low owm: Dicowq y(x) oork kor , or miacnowm  O B keter: Dicowq M (x, y(x)) kamayakan ket  kori vra: st nergiayi pahpanman renqi` ownenq mv 2 /2 = mgy(x),

orte m- nyowakan keti massan , isk v-n` aragowyown M ketowm, g-n` azat ankman aragacowm: Aysteic kstananq v=

p 2gy(x) :

Myows komic, ownenq ds v= = dt

p

1 + (y 0 )2 dy , dt

orte ds- lementar aei erkarowyownn : Het abar, T (y) = √ 2g

Zx1 p 1 + (y 0 (x))2 p dx, y(x)

orte T (y)- ayn amanakamijocn , ori n{ acqowm ket trva

korov A ketic hasnowm  B √ ket: Qani or 1/ 2g > 0 hastatown , apa T (y) fownkcionali minimizaciayi xndrowm kareli  ayn havi a nel: Verjnakanoren kstananq qstremowmi het yal xndir. Zx1 p 1 + (y 0 (x))2 dx → min, I(y) ≡ y(x)

(5.1.6)

y(0) = 0, y(x1 ) = y1 :

Kazmenq yleri havasarowm: Qani or (5.1.6)-owm enaintegral L fownkcional bacahayt kaxva

 x o oxakanic, apa yleri havasarowmn owni het yal tesq. L − y 0 L0y0 = C (te|s,

rinak` [2]) :

Aysteic mer rinaki hamar kownenanq L − y 0 L0y0 =

1 + (y 0 )2 y0 − y0 p =C: √ y 1 + (y 0 )2 y

Parzecnelowc heto kstananq y(1 + (y 0 )2 ) =

Nanakenq y 0 = ctgt ⇒ y =

= C1 : C2

C1 = C1 sin2 t ⇒ 1 + (ctgt)

⇒ dy = 2C1 sintcostdt :

Aysteic kstananq dx =

dy 2C1 sintcostdt = = 2C1 sin2 tdt ⇒ y ctgt

⇒ x(t) = C1 /2(2t − sin2t) + C2 :

Qani or y(0) = 0, apa C2 = 0: Nanakelov p = 2t` kstananq cikloidneri ntaniq x = C1 /2(p − sinp), y = C1 /2(1 − cosp) :

hastatown orovowm  ayn paymanic, or cikloid petq  ancni B ketov: 3. Bolor oork koreri mej, oronq miacnowm en harowyan A(2, 1) B(1, 0) keter, gtel ayn kor, orov v = x aragowyamb arvo nyowakan ket A ketic khasni B ket amenakar amanakowm: C1

5.2

Lagrani meod variacion havi xndirnerowm

Ditarkenq het yal xndir. Zx1 I0 (y) ≡

f0 (x, y, y 0 ) dx → extr,

x0

(5.2.1)

Zx1 Ii (y) =

fi (x, y, y 0 ) dx = αi , i ∈ [1 : m],

(5.2.2)

x0

y(x0 ) = y0 , y(x1 ) = y1 :

(5.2.3)

Ays xndir kovowm  variacion havi izoperimetrik xndir: Enadrvowm , or fi , i ∈ ∈ [0 : m] fownkcianer, orpes ereq o oxakani fownkcianer, erkow angam anndhat diferenceli en R3 -i vra, Isk α1 , α2 , ..., αm hastatownner trva ver en: y ∗1 [x0 , x1 ] fownkcian kovowm  owylatreli, ee ayn bavararowm  (5.2. 2)-(5.2.3) paymannerin: Sahmanowm 5.2.1: Kasenq, or owylatreli y ∗ fownkcian (5.2.1)-(5.2.3) xndrowm lokal minimowm  (lokal maqsimowm ), ee goyowyown owni δ > 0 iv aynpisin, or bolor owylatreli y fownkcianeri hamar, oronq bavararowm en ky − y ∗ k1 < δ paymanin, tei owni I0 (y) ≥ I0 (y ∗ ) (I0 (y) ≤ I0 (y ∗ )

anhavasarowyown:

Kazmenq Lagrani fownkcian` L(x, y, y 0 , λ) ≡ λ0 f0 (x, y, y 0 ) + λ1 f1 (x, y, y 0 ) + ...+ +λm fm (x, y, y 0 ),

orte λ = (λ0 , λ1 , ..., λm ) ∈ Rm+1 :

eorem 5.2.1: Dicowq y ∗ (x) fownkcian (5.2.1) xndri low owm : Ayd depqowm goyowyown ownen λ0 , ..., λm ver, oroncic gone mek zro  aynpisin, or y ∗ (x)- bavararowm  −

d 0 L 0 + L0y = 0 dx y

diferencial havasarman y(x0 ) = y0 , y(x1 ) = y1 ezrayin paymannerov: I Dicowq y ∗ fownkcian (5.2.1)-(5.2.3) xndrowm lokal minimowm  (lokal maqsimowmi depq qnnarkvowm  analog  ov): Nanakenq δIi (y ∗ , h) ≡ lim α↓0

Ii (y ∗ + αh) − Ii (y ∗ ) : α

Het  cowyc tal, or Zx1 d δIi (y , h) = (− fiy0 0 + fiy0 )h(x) dx, i ∈ [0 : m] : dx ∗

x0

Aysteic het owm , or δIi (y∗ , h) fownkcional h-i nkatmamb g ayin : Ditarkenq het yal g ayin perator. A : C01 → Rm+1 ,

Ah ≡ (δI0 (y ∗ , h), δI1 (y ∗ , h), ..., δIm (y ∗ , h)) : ImA-ov

nanakenq A peratori patker: Hnaravor  erkow depq. 1)

ImA ⊂ Rm+1 ,

2)

ImA = Rm+1 :

A ajin depqowm ImA- Rm+1 -i se akan enatara owyownn : Het abar, goyowyown owni o zroyakan aynpisi λ = (λ0 , ..., λm+1 ) vektor, or owahayac  ayd enatara owyan, aysinqn` (λ, Ah) = 0 ⇒ λ0 δI0 (y ∗ , h) + ... + λm δIm (y ∗ , h) = 0 ∀h ∈ C01 :

Aysteic kstananq Zx1 d (− L0y0 + L0 y)h(x) dx = 0 ∀h ∈ C01 : dx

(5.2.2)

x0

Inpes parzagowyn xndrowm, ayste nowynpes kareli  cowyc tal, or (5.2.2)-ic het owm , or −

d 0 Ly0 + L0 y = 0 : dx

Ditarkenq erkrord depq: Dicowq {e0 , ..., em } hamakarg bazis  kazmowm Rm+1 tara owyownowm: ntrenq h0 , h1 , ..., hm fownkcianer aynpisin, or  1, ee i = j; ∗ δIj (y , hi ) = 0, ee i 6= j : Kazmenq havasarowmneri het yal hamakarg.  Pm  ϕ0 (β0 , ..., βm ) ≡ I0 (y ∗ + j=0 βj hj ) = I0 (y ∗ ) − ε, 

ϕi (β0 , ..., βm ) ≡ Ii (y ∗ +

Pm

j=0

βj hj ) = αi , i ∈ [1 : m] : (5.2.3)

Ays hamakargowm ε- parametr : Ownenq ∂ϕi (0) = δIi (y ∗ , hj ) : ∂βj

Aysteic het owm , or (5.2.3) hamakarg bavararowm  hakadar artapatkerowmneri masin eoremi bolor paymannerin (te|s, rinak` [2], j 31): Da nanakowm , or goyowyown owni vektor fownkcia` β(ε) ≡ (β0 (ε), ..., βm (ε)), or orova en zro keti in or mi rjakayqowm, aynpisin, or ayd rjkayqowm na bavararowm  (5.2.3) hamakargin β(ε) → 0, erb β → 0 : Het abar, ee ε parametr drakan , apa kstananq hakasowyown, qani or y∗ - (5.2.1) xndri lokal minimowmi ket : J

rinak (yleri havasarman low owm izoperi-

metrik xndrowm global minimowmi ket ): Z1 I0 (y) =

(y 0 )2 → min,

Z1 I1 (y) =

y dx = 0, y(0) = 0, y(1) = 1 :

Low owm: Kazmenq Lagrani fownkcian L = λ0 (y 0 )2 + λ1 y :

yleri havasarowm ays fownkciayi hamar he{ t yaln . −

d 0 L 0 + L0y = 0 ⇒ −2λ0 y 00 + λ1 = 0 : dx y

Ee λ0 = 0, apa λ1 = 0 Lagrani bolor gor akicner havasar en zroyi: Ayd depqowm owylatreli qstremalner kan: yleri havasarman mej teadrenq λ0 = 1: Ayd depqowm ayd havasarman ndhanowr low owm klini y(x) = = C1 x2 + C2 x + C3 fownkcian: C1 , C2 , C3 anoro gor akicner oroenq ezrayin izoperimetriayi het yal paymanneric.  y(0) = 0 ⇒ C3 = 0,    y(1) = 1 ⇒ C + C = 1, R R    ydx = 0 ⇒ (C1 x2 + C2 x) dx = 0 ⇒

⇒ C1 /3 + C2 /2 = 0 :

Aysteic kstananq miak owylatreli qstremal` y ∗ (x) = 3x2 − 2x :

Apacowcenq, or ayn global minimowmi ket : Dicowq y(·) owylatreli fownkcia : Ayd depqowm ∗

y(·) − y (·) = h(·) ∈

C01 [0, 1]

Z1 h dx = 0 :

Ownenq` ∗

Z1

I0 (y(·))−I0 (y (·)) =

∗ 0

Z1

0 2

((y ) +h ) dx−

Z1 =

∗ 0

Z1

0 2

Z1

(h ) dx ≥ 2

2(y ) hdx +

((y ∗ )0 )2 dx =

(y ∗ )0 h0 dx :

Katarelov maserov integrowm` kstananq Z1

∗ 0 0

Z1

(y ) h dx =

∗

(y ) dh = y

∗

h|10

Z1 −

(y ∗ )00 h dx =

Z1 = −6

h dx = 0 :

Ayspisov,

I0 (y ∗ (·)) ≥ I0 (y ∗ (·))

cankaca owylatreli y(·) fownkciayi hamar: rinak (Didonayi xndir maqsimal makeresov seanakerpi masin): Trva  f (x) fownkcian [−x0 , x0 ] hatva i vra: Grafik nerkayacno kori erkarowyown hastatown : Gtnel grafiki tesq aynpes, or ko{ ragi seani makeres lini me agowyn: Ays xndir  akerpvowm  het yal kerp. Zx0 y(x) dx → max, −x0

Zx0 p

1 + (y 0 )2 dx = l, y(−x0 ) = y(x0 ) = 0 :

−x0

Low owm: Kazmenq Lagrani fownkcian L(y, y 0 , λ) = λ0 y + λ1

p 1 + (y 0 )2 :

Qani, or Lagrani fownkcian bacahayt kaxva

 x o oxakanic, apa yleri havasarowm owni het yal tesq. −λ1 : L − y 0 L0y0 = C ⇒ λ0 y − C = p 1 + (y 0 )2

(5.2.4)

Aysteic het owm , or ee λ0 = 0, apa kam kam y0 = 0: A ajin depq hnaravor , orovhet Lagrani gor akicner miaamanak zro linel en karo: Erkrord depqowm, havi a nelov ezrayin izoperimetrayi paymanner, kownenanq λ1 = 0,

y ∗ (x) ≡ 0, l = 2x0 :

Ee λ0 = 1, apa nanakelov kstananq`

y 0 = tgt,

y(t) − C = −λ1 cos t :

(5.2.4)-ic (5.2.5)

Myows komic, ownenq dy dy = tgt ⇒ dx = ⇒ x(t) − C1 = λ1 sin t : (5.2.6) dx tgt

(5.2.5)-(5.2.6) havasarowyownneric het owm , or (x − C1 )2 + (y − C)2 = λ21 :

Ezrayin paymanneric stanowm enq, or C1 = 0: Ayspisov, ee l < 2x0 , apa xndir low owm owni: Ee l = 2x0 , apa y∗ (x) ≡ 0 : Ee l > 2x0 xndir owni ptimal low owm, apa nra grafik

petq  ownena rjanag ayin aei tesq: Ayd rjanagi  ancnowm  (−x0 , 0) (x0 , 0) keterov, isk nra kentron gtnvowm  OY a ancqi vra: Kareli  cowyc tal, or ee l > πx0 , apa xndir ptimal low owm owni:

XNDIRNER

Lagrani gor akicneri meodov low el variacion havi het yal izoperimetrik xndirner: a)

Z1

0 2

Z1

(y ) dx → min,

y dx = 0, y(0) = 0, y(1) =

b)

=1: Z1 Z1 0 2 (y ) dx → min, xydx = 0, y(0) = y(1) =

g)

=0: Zπ Zπ (y 0 )2 dx → min, ysinx dx = 0, y(0) =

d)

= y(π) = 1 : Zπ Zπ 0 2 (y ) dx → min, ycosxdx = π/2, y(0) =

= 1, y(π) = −1 :

e)

Zπ

Zπ ysinx dx → min,

(y )2 dx = 3π/2, y(0) =

= 1, y(π) = π :

5.3

Variacion havi dasakan izoperimetrik xndir

Xndir: Apacowcel, or l erkarowyan ktor a

ktor oork, parz har ak koreri mej amename

makeres zbaecnowm  rjanagi : Low owm: Dicowq x = x(s), y = y(s), s ∈ [0, l]

kori parametrakan havasarowmnern en: Havi a nelov o oxakan aei erkarowyan diferenciali makeresi haytni bana er` kareli  tal xndri het yal maematikakan  akerpowm. Zl S(x, y) =

x(s)

dy dx dy ds → max, ( )2 + ( )2 = 1 : ds ds ds

x(s)

arqov`

y(s)

fownkcianer nerkayacnenq Fowriei

∞ X 2πn 2πn x(s) = a0 + (an cos s + bn sin s), (5.3.1) l l n=1 ∞ X 2πn 2πn y(s) = c0 + (cn cos s + dn sin s) (5.3.2) : l l n=1

Aysteic ays fownkcianeri a ancialneri hamar kownenanq het yal bana er. ∞

2πn 2πn 2πn dx X 2πn (− = an sin s+ bn cos s), ds l l l l n=1 (5.3.3) ∞ X dy 2πn 2πn 2πn 2πn (− = cn sin s+ dn cos s: ds n=1 l l l l (5.3.4) Haytni  na , or ee αn , βn , n = 0, 1, 2, ... ver f fownkciayi Fowriei gor akicnern en, isk γn , δn , n = 0, 1, 2, ... ver` ϕ-i gor akicnern en,

apa

l

Zl

l

Zl

∞

α2 X 2 f (s)ds = 0 + (αn + βn2 ), i=1

∞ X f (s)ϕ(s)ds = α0 γ0 + (αn γn + βn δn ) : n=1

Aysteic, nkati ownenalov na (5.3.3)-(5.3.4) bana er, har patkeri makeresi hamar ksta{ nanq het yal bana . S=π

∞ X

n(an dn − bn cn ) :

n=1

Qani or

Zl ((

dy dx 2 ) + ( )2 ) ds = l, ds ds

(5.3.5)

apa, havi a nelov na a ancialneri (5.3.3)-(5.3.5) bana er, kstananq, or kori l erkarowyown petq  bavarari het yal havasarman. ∞ 2π 2 X 2 2 n (an + b2n + c2n + d2n ) : l= l n=1

Makeresi (5.3.5) kori erkarowyan na eric het owm , or

(5.3.6) (5.3.6)

ba{

∞ πX l2 −S = ((nan − dn )2 + (nbn + cn )2 + 4π 2 n=1

+(n2 − 1)(c2n + d2n )) ≥ 0 :

(5.3.7)

Ayspisov stacanq hanhrahayt het yal izoperimetrik anhavasarowyown. S≤

l2 : 4π

Parz , or (5.3.7) anhavasarowyown kvera vi havasarowyan, erb a1 = d1 , b1 + c1 = 0, an = bn = cn = dn = 0, n = 2, 3, ... :

Aysteic

aysinqn`

x = a0 + a1 cos s + b1 sin s, y = c0 − b1 cos s + a1 sin s,

l2 (x − a0 )2 + (y − c0 )2 = a21 + b21 = : 4π

XNDIRNER

1. Dicowq ownenq erkow ow owcik qa ankyownner, oronc koeri erkarowyownner mi nowyn a, b, c, d vern en: Enadrenq nrancic mekin kareli  artag el rjanagi : Apacowcel, or nra makeres me  kam havasar myows qa ankyan makeresic: 2. Trva parag ov ow owcik n- ankyown bazm{ ankyownneri mej gtnel ayn bazmankyown, ori makeresn amename n : 3. Trva rjanin nerg el amename makeresov n- ankyown bazmankyown: 4. Ditarkenq l erkarowyamb bolor ayn har oork korer, oronc A skzbnaket B verjnaket gtnvowm en harowyan trva

L owi vra, isk korer nka en L owi mi nowyn kisaharowyan mej (tarber koreri hamar A B keter karo en linel tarber): Gtnel ayn kor, orov [A, B] hatva ov sahmana akva patkeri makeres lini me agowyn:

5.4

qstremowmi bavarar paymanner variacion havi xndirnerowm

Aym berenq variacion havi parzagowyn xndri rinak, st ori yleri havasarowm owni miak

low owm, or qstremowm : Aysinqn` yleri hava{ sarowm qstremowmi miayn anhraet payman : Ditarkenq het yal xndir. 3π/2 Z

((y 0 )2 −y 2 ) dx → min, y(0) = y(3π/2) = 0 :

I(y) ≡

yleri havasarowm owni het yal tesq. y 00 + y = 0 ⇒ y(x) = C1 sin x + C2 cos x :

Havi a nelov xndri ezrayin paymanner` kstananq y∗ (x) ≡ 0 : Ditarkenq fownkcianeri yn (x) =

2x sin( ) n

hajordakanowyown: Aknhayt , or ays fownkcianer owylatreli en C1

yn (·) → y ∗ (·) :

Myows komic ownenq I(yn ) = −

5π < 0 = I(y ∗ ), n2

aysinqn y∗ - lokal minimowmi ket : Aym berenq bavarar mi payman, orov stowgvowm , e erb yleri havasarman low owm klini lokal minimowmi ket: Dicowq y∗ (x)- variacion havi parzagowyn xndri yleri havasarman low owm : Nanakenq P (x) ≡ L00y0 y0 (x, y ∗ (x), (y ∗ (x))0 ),

Q(x) = −

d 00 Lyy0 (x, y ∗ (x), (y ∗ (x))0 )+ dx

+L00yy (x, y ∗ (x), (y ∗ (x))0 ) :

Kazmenq het yal diferencial havasarowm, or kovowm  Yakobii havasarowm. d dh (P ) − Qh = 0 : dx dx

(5.4.1)

Dicowq y∗ (x) qstremal bavararowm  het yal erkow paymannerin. ˆ y ∗ (x)-

bavararowm  Yakobii paymanin, ee (5.4.1) havasarowm skzbnakan h(x0 ) = = 0 paymanov owni o trivial aynpisi h(x) low owm, or h(x) 6= 0 ∀ x ∈ (x0 , x1 ] :

ˆ y ∗ (x)-

ee

bavararowm  Leandri paymanin, P (x) > 0 ∀x ∈ [x0 , x1 ] :

marit  het yal pndowm (te|s, rinak` [1-2]): eorem 5.4.1: Dicowq y ∗ (x)- (5.1.1) variacion havi parzagowyn xndri yleri havasarman low owmn  bavararvowm en Yakobii Leandri paymanner: Ayd depqowm y ∗ (x)- (5.1.1) xndrowm lokal minimowmi ket :

rinak (Karagowyn anaparhi xndir): Z1 p

1 + (y 0 )2 dx → min, y(0) = 0, y(1) = 1 :

(5.4.2)

Low owm: Qani or ayste L fownkcian bacahayt

kaxva  x o oxakanic, apa yleri hava{ sarowm owni het yal tesq. L − y 0 L0y0 = C ⇒

p (y 0 )2 1 + (y 0 )2 − p =C⇒ 1 + (y 0 )2

⇒ y(x) = C1 x + C2 :

Havi a nelov (5.4.2) ezrayin paymanner` kstananq y∗ (x) = x : Stowgenq Yakobii payman: Ownenq d 00 L 0 ≡ 0, dx yy = √ : P (x) = p 2 2 1 + ((y ∗ )0 )2 Q(x) = L00yy −

Yakobii havasarowm owni het yal tesq. d2 h =0: dx2

Aysteic het owm , or h(x) = C1 x + C2 :

Owsti h(x) = C1 x, C1 6= 0 fownkcian h(0) = 0 skzbnakan paymanov Yakobii havasarman o

tiivial low owm , or zro i da nowm (0, 1] kisabac mijakayqi o mi ketowm: Het abar, Yakobii bavarar payman tei owni: Leandri √payman nowynpes tei owni, qani or P (x) ≡ 1/2 2 > 0 : Ayspisov, y∗ (x) = x fownkcian karagowyn anaparhi xndri low owmn :

XNDIRNER

gtagor elov Yakobii Leandri paymanner` low el variacion havi het yal xndirner: a)

Zπ/2 ((y 0 )2 − y 2 ) dx → min, y(0) = 0, y(π/2) = 1 :

b)

Zπ/2 ((y 0 )2 − y 2 + 4ycosx) dx → min, y(0) =

g)

= 0, y(π/2) = π/2 : Z 1 ((y 0 )2 + y 2 + 4ysh(x))dx → min, y(0) =

d)

= −1, y(1) = 0 : Zπ/2 ((y 0 )2 − 4y 2 ) dx → min, y(0) = 0, y(π/4) = 1 :

e)

Zπ/2 (y 2 − 2(y 0 )2 + 2y) dx → min, y(0) = y(π/2) =

=0:

Grakanowyown [1]

Â.Ì. Àëåêñååâ, Â. Ì. Òèõîìèðîâ, Ñ. Â. Ôîìèí, Îïòèìàëüíîå óïðàâëåíèå, Íàóêà, M., 1979.

[2]

Â.Ì. Àëåêñååâ, Ý.Ì. Ãàëååâ, Â.Ì. Òèõîìèðîâ, Ñáîðíèê çàäà÷ ïî îïòèìèçàöèè, Íàóê, Ì., 1984.

[3]

È. Ë. Àêóëè÷, Ìàòåìàòè÷åñêèå ïðîãðàììèðîâàíèå â ïðèìåðàõ è çàäà÷àõ, Âûñøàÿ øêîëà, M., 1986.

[4]

Ô. Ï. Âàñèëüåâ, ×èñëåííûå ìåòîäû ðåøåíèÿ ýêñòðåìàëüíûõ çàäà÷, Íàóêà, Ì., 1980.

[5]

Å.Ñ. Ïîëîâèíêèí Å.Ñ., Ì. Â. Áàëàøîâ, Ýëåìåíòû âûïóêëîãî è ñèëüíî âûïóêëîãî àíàëèçà, ôèçìàòëèò, M., 2004.

[6]

À. Â. Ïàíòåëååâ, Ò.À. Ëåòîâà, Ìåòîäû îïòèìèçàöèè â ïðèìåðàõ è çàäà÷àõ, Âûñøàÿ øêîëà, M., 2002.

[7]

Á.Í. Ïøåíè÷íûé, Âûïóêëûé àíàëèç è ýêñòðåìàëüíûå çàäà÷è, Íàóêà, Ì., 1980.

[8]

À. Ã. Ñóõàðåâ, À.Â. Òèìîõîâ, Â.Â. Ôåäåðîâ, Êóðñ ìåòîäîâ îïòèìèçàöèè, Íàóêà, Ì., 1986.

[9]

Ê. Ëåéõòâåéñ, Âûïóêëûå ìíîæåñòâà, Íàóêà, Ì., 1985.

[10]

Â. Â. Âîåâîäèí, Ëèíåéíàÿ àëãåáðà, Íàóêà, Ì., 1987.

[11]

R.T. Rockafellar , J.B. Roger, Variational Analisis,

Springer-Verlag,

Berlin,

Heidelberg,

1998.

[12] V. Avetisyan, M. Poosyan, Variacion haiv ptimal ka avarowm (dasaxo{ sowyownner), EPH hrat., Er an, 2008: [13] V. . Barseyan, Variacion haiv, EPH hrat., Er an, 2011:

ՌԱՖԻԿ ԱՂԱՍՈՒ ԽԱՉԱՏՐՅԱՆ

ՕՊՏԻՄԻԶԱՑԻԱՅԻ

ՄԵԹՈԴՆԵՐ

ՈՒՍՈՒՄՆԱԿԱՆ ՁԵՌՆԱՐԿ

Համակարգչային ձևավորող՝ Ռ. Ա. Խաչատրյան Կազմի ձևավորող՝ Ա. Պատվականյան Հրատ. սրբագրող՝ Լ. Հ. Հովհաննիսյան

Չափսը՝ 60x841/16: 8.375 տպ. մամուլ: Տպաքանակը՝ 100:

ԵՊՀ հրատարակչություն ք. Երևան, 0025, Ալեք Մանուկյան 1

ՌԱՖԻԿ ԽԱՉԱՏՐՅԱՆ

Օպտիմիզացիայի մեթոդներ