ՕՊՏԻՄԻԶԱՑԻԱՅԻ ՄԵԹՈԴՆԵՐ

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

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

.

.

519.8(07) 22.18 7

.

. .

. .

.

, .

. .

.

: .

.-

.:

/ ., 2014, 134

:

:

:

519.8(07) 22.18 7

ISBN 978-5-8084-1921-6 Օ Օ

., 2014 . ., 2014

BՈՎԱՆDԱKՈՒYՈՒՆ

Հիմնական գաա արներ թեորեմներ

1.1 Նախնական սահմանումներ . . . . . . . . . . 1.2 Էքստրեմումի ա աջին երկրորդ կարգի անհրաժեշտ ու բավարար պայմանները . . .

Գրադիենտային մեթոդը

2.1 Ֆունկցիայի մինիմիզացիայի գրադիենտային եղանակների ընդհանուր նկարագրությունը . 2.2 Քայլի կիսման եղանակի զուգամիտության թեորեմը . . . . . . . . . . . . . . . . . . . . . . 2.3 Գ այնացման մեթոդը . . . . . . . . . . . . . . 2.4 Ապրիորի մեթոդի զուգամիտությունը . . . . . 2.5 Գրադիենտի պրոյեկտման մեթոդը . . . . . . .

Ու ուցիկ անաոից

3.1 Ու ուցիկ բազմությունների անջատման թեորեմները . . . . . . . . . . . . . . . . 3.2 Կարաթեոդորի թեորեմը . . . . . . . . . . 3.3 Հելլիի թեորեմը . . . . . . . . . . . . . . . 3.4 Ու ուցիկ ֆունկցիայի սուբդիֆերենցիալը 3.5 Կուն-Տակկերի թեորեմը . . . . . . . . .

..

Լագրանժի անորոշ գոր ակիցների մեթոդը

4.1 Օպտիմալության ա աջին երկրորդ կարգի պայմանները . . . . . . . . . . . . . . . . . . 4.2 Լագրանժի անորոշ գոր ակիցների մեթոդը (խա ը սահմանա ակումների դեպքը) . . .

Վարիացիոն hաշիv

5.1 Էյլերի հավասարումը . . . . . . . . . . . . . . 5.2 Լագրանժի մեթոդը վարիացիոն հաշվի խնդիրներում . . . . . . . . . . . . . . . . . . 5.3 Վարիացիոն հաշվի դասական իզոպերիմետրիկ խնդիրը . . . . . . . . . . . . . . . . . . . . . 5.4 Էքստրեմումի բավարար պայմանները վարիացիոն հաշվի խնդիրներում . . . . . . .

Գրականություն

ՆԱԽԱBԱՆ

Այս ուսումնական ձե նարկը գրվա է Եր անի պետական համալսարանի ինֆորմատիկայի կիրա ական մաթեմատիկայի ֆակուլտետում հեղինակի կարդացա

դասախոսությունների հիման վրա: ե նարկի նպատակն է տալ պտիմիզացիայի որոշ հիմնարար մեթոդների բավարար չա ով համակարգվա ժամանակակից շարադրանք: ե նարկը բաղկացա է հինգ գլուխներից: Ա աջին գլխում համա ոտակի շարադրվում են էքստրեմումի ա աջին երկրորդ կարգի անհրաժեշտ ու բավարար պայմանները ոչ պայմանական պտիմիզացիայի խնդիրների համար վերջավոր չա անի տարա ություններում: Երկրորդ գլուխը նվիրվա է պայմանական ոչ պայմանական պտիմիզացիայի մոտավոր մեթոդներին: Նկարագրվում են գրադիենտային մեթոդները նրանցում քայլի ընտրության ա ավել հաճախ գտագոր վող կիսման, ապրիորի ամենաարագ վայրէջքի եղանակները: Երրորդ գլխում ապացուցվում է Կուն- Տակկերի թեորեմը որպես մինիմումի անհրաժեշտ ու բավարար պայման ու ուցիկ րագրավորման խնդիրների համար: Այս գլխում տրվում են նա որոշ հիմնարար թեորեմներ ու ուցիկ անալիզից, որոնք ունեն կիրա ական լայն նշանակություն: որրորդ գլխում շարադրվում է մաթեմատիկական ըրագրավորման խնդիրների լու ման Լագրանժի անորոշ գոր ակիցների մեթոդը, երբ սահմանա ակումները տրվա

են հավասարություններով անհավասարություններով: Հինգերորդ գլխում դիտարկվում են վարիացիոն հաշվի պարզագույն իզոպերիմետրիկ խնդիրները արտա վում է Էյլերի հավասարումը որպես Էքստրեմումի անհրաժեշտ պայման:

Յուրաքանչյուր դասախոսության վերջում բերվում են խնդիրներ վարժություններ, որոնց լու ումները ուսանողին կգնեն ավելի լավ յուրացնել շարադրվա նյութը: ե նարկում կան նա ա աջադրանքներ, որոնք կարող են իրականացվել համակարգչի գնությամբ: Թեորեմի ապացույցը սկսվում է I նշանով, իսկ J նշանը ազդարարում է ապացույցի ավարտը: նորհակալություն ենք հայտնում ԵՊՀ թվային անալիզի մաթեմատիկական մոդելավորման ամբիոնի աշխատակիցներին՝ ձե նարկում ներկայացվա նյութի բովանդակության շարադրման եղանակների հետ կապվա

հարցերում գտակար ա աջարկությունների դիտողությունների համար: .Ա. Xաչատրյան

ՀԻՄՆԱԿԱՆ Ն ԱՆԱԿOWՄՆԵՐԻ ՑԱՆԿ

տարրը պատկանում է Ճ բազմությանը Ճ ∩ Y − բազմությունների հատում Ճ ∪ Y − բազմությունների միավորում Ճ\Y − բազմությունների տարբերություն

» x ∈ Ճ− x » » »

» Ճ Է Y - {Տ/Տ - x Է y, x ∈ Ճ, y ∈ Y }− » » » » » » »

բազմությունների հանրահաշվական գումար Ճ− Ճ բազմության ակում ոոtՃ− Ճ բազմության ներքին կետերի բազմություն Rn − ո չա անի էվկլիդյան տարա ություն (x, y) - n4-1 x4 y4 − x, y ∈ Rn վեկտորների սկալյար արտադրյալ p kxk - (x, x)− x ∈ Rn վեկտորի նորմ Br (a) - {x ∈ Rn /kx − ak ≤ 7}− a կենտրոնով 7 շա ավղով գունդ Շ 1 |a, Ե|− |a, Ե| հատվա ի վրա որոշվա անընդհատ դիֆերենցելի ֆունկցիաների տարա ություն հետ յալ նորմով. ky(·)k1 - max{ max |y(x)|, max |y 0 (x)|} x∈1a,b|

x∈1a,b|

թվային ֆունկցիա, որը բավարարում է հետ յալ պայմանին.

» օ(α)−

օ(α) α→0 α lim

Գլուխ 1

Հիմնական գաա արներ թեորեմներ Այս գլխում բերվում են որոշ սահմանումներ թեորեմներ ու ուցիկ անալիզից: Դիտարկվում է ողորկ ֆունկցիայի մինիմիզացիայի խնդիրը Rn էվկլիդյան տարա ության վրա: արադրվում են պտիմալության ա աջին ու երկրորդ կարգի անհրաժեշտ ու բավարար պայմանները: Ենթադրվում է, որ ընթերցողը անոթ է մաթեմատիկական անալիզի գ ային հանրահաշվի հիմնարար գաղա արներին:

1.1

Նախնական սահմանումներ

Դիցուք f (x) - f (x1 , x2 , ... , xn ) ո ո ոխականի ֆունկցիա է՝ որոշվա Rn Էվկլիդյան տարա ության վրա: Եթե f ֆունկցիան, ըստ բոլոր ո ոխականների, ունի մասնակի ա անցյալներ x ∈ Rn կետում, ապա նրա գրադիենտը այդ կետում նշանակվում է հետ յալ կերպ. f 0 (x) ≡ (fx0 1 (x), fx0 ո (x), ..., fx0 Շ (x)) :

Սահմանում 1.1.1: Դիցուք f (x)-ը երկու անգամ դիֆերենցելի ֆունկցիա է x ∈ Rn կետում: Ճետ յալ սիմետրիկ մատրիցը կոչվում է հեսիան fx001 x1 (x) fx001 xո (x)  fx00 x (x) fx00 x (x) ո 1 ո ո H(x) -   fx00Շ x1 (x) fx00Շ xո (x) 

Դիցուք



a11 a12  a21 a22 Ճ-  ... ... an1 an2

 ... fx001 xՇ (x) ... fx00ո xՇ (x)  :  ... fxՇ xՇ (x)

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

կամայական մատրից է: Սահմանում 1.1.2: Ճ մատրիցի k-րդ կարգի գլխավոր մինոր կոչվում է ո1 Հ ո2 Հ ... Հ ոk համարներով տողերի այդ նույն համարներով սյուների հատման տեղերում գտնվող տարրերից կազմվա որոշիչը: Սահմանում 1.1.3: (Ճx, x) քա ակուսային  ը կոչվում է՝ » դրական որոշյալ (Ճ » 0), եթե (Ճx, x) » 0 6- 0, x ∈ Rn ,

∀x 6-

» դրական կիսաորոշյալ (Ճ ≥ 0), եթե (Ճx, x) ≥ ≥ 0 ∀x ∈ Rn , » բացասական որոշյալ (Ճ Հ 0), եթե (Ճx, x) Հ Հ 0 ∀x 6- 0, x ∈ Rn , » բացասական կիսաորոշյալ (Ճ ≤ 0), եթե (Ճx, x) ≤ ≤ 0 ∀x ∈ Rn :

Կար որ կիրա ական նշանակություն ունի հետ յալ պընդումը (տենս, րինակ՝ |10|): Թեորեմ 1.1.1 (Սիլվեստրի հայտանիշը) : Դիցուք A(ո × ո) սիմետրիկ մատրից է:

1) Որպեսզի Ճ մատրիցը լինի դրական որոշյալ, անհրաժեշտ է բավարար, որ նրա գլխավոր անկյունագ ային մինորները լինեն դրական՝ ∆1 - a11 » 0, ∆2 -

∆n -

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

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

» 0, ...,

»0:

2) Որպեսզի Ճ մատրիցը լինի բացասական որոշյալ, անհրաժեշտ է բավարար, որ ∆1 Հ 0, ∆2 » » 0, ..., (−1)n ∆n » 0 :

3) Որպեսզի Ճ մատրիցը լինի դրական կիսաորոշյալ, անհրաժեշտ է բավարար, որ նրա գլխավոր մինորները լինեն ոչ բացասական: 4) Որպեսզի Ճ մատրիցը լինի բացասական կիսա որոշյալ, անհրաժեշտ է բավարար, որ զույգ կարգի գլխավոր մինորները լինեն ոչ բացասական, իսկ կենտ կարգի գլխավոր մինորները լինեն ոչ դրական:

Սահմանում 1.1.4: 1 ⊆ Rn բազմությունը կոչվում է ow owciց, եթե ցանկացա x1 , x2 ∈ 1 կետերի ցանկացա α ∈ |0, 1| թվի համար տեղի ունի հետ յալը՝ αx1 Է (1 − α)x2 ∈ 1 :

Սա նշանակում է, որ բազմությանը պատկանող երկու կետերը միացնող հատվա ը ընկա է այդ նույն բազմության մեջ: Սահմանում 1.1.5: f (x) ֆունկցիան 1 ⊆ Rn ու ուցիկ բազմության վրա կոչվում է ow owciց, եթե ցանկացա

x1 , x2 ∈ 1 կետերի ցանկացա α ∈ |0, 1| թվի համար տեղի ունի f (αx1 Է (1 − α)x2 ) ≤ αf (x1 ) Է (1 − α)f (x2 )

(1.1.1)

անհավասարությունը: Թեորեմ 1.1.2: Դիցուք f -ը ու ուցիկ ֆունկցիա է 1 ⊆ ⊆ Rn ու ուցիկ բազմության վրա դիֆերենցելի է x∗ ∈ 1 կետում: Այդ դեպքում f (x) − f (x∗ ) ≥ (f 0 (x∗ ), x − x∗ ) ∀x ∈ 1 :

(1.1.2)

Ըստ ու ուցիկ ֆունկցիայի (1.1.1) սահմանման՝ կամայական x ∈ 1 վեկտորի ցանկացա α ∈ |0, 1| թվի համար ունենք I

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

անհավասարությունը: Այստեղից, հաշվի ա նելով, որ ֆունկցիան դիֆերենցելի է x∗ կետում, կստանանք f (x) − f (x∗ ) ≥

f (x∗ Է α(x − x∗ )) − f (x∗ ) α

f

(f 0 (x∗ ), α(x − x∗ )) Է օ(α) օ(α) - (f 0 (x∗ ), x − x∗ ) Է : α α Անցնելով սահմանի, երբ α → 0, կստանանք պահանջվող անհավասարությունը: (1.1.2)-ը կոչվում է ու ուցիկ ֆունկ-

ցիայի հիմնական անհավասարություն: Դա նշանակում է, որ եթե f ու ուցիկ ֆունկցիան դիֆերենցելի է x∗ կետում, ապա նրա գրաֆիկը գտնվում է (x∗ , f (x∗ )) կետով տարվա շոշա ող հարթությունից վեր :

J

Սահմանում 1.1.6: f (x) ֆունկցիան 1 ⊆ Rn ու ուցիկ բազմության վրա կոչվում է owեղ ow owciց θ » 0 հաստատունով, եթե f (x1 )−f (x2 ) ≥ (f 0 (x2 ), x1 −x2 )Էθkx1 −x2 k2 ∀x1 , x2 ∈ 1 :

Եթե ֆունկցիան երկու անգամ անընդհատ դիֆերենցելի է, ապա նրա ու ուցիկությունը ամբողջ տարա ության վրա կարելի է ստուգել հեսիանի նշանի միջոցով: Այդ մասին է հետ յալ պնդումը (տենս, րինակ՝ |8|): Թեորեմ 1.1.3: Դիցուք f -ը երկու անգամ անընդհատ դիֆերենցելի է Rn -ի վրա: Այդ դեպքում՝

ա) եթե H(x) ≥ 0 ∀x ∈ Rn , ապա f -ը ու ուցիկ ֆունկցիա է Rn -ի վրա, բ) եթե (H(x)հ, հ) ≥ θkհk2 ∀x, հ ∈ Rn , ապա f -ը ուժեղ ու ուցիկ է θ հաստատունով Rn -ի վրա:

Դիցուք տրվա է f (x) ֆունկցիան ենթաբազմություն է Rn - ից:

Rn -ի

վրա

1 -ը

Սահմանում 1.1.7: x∗ ∈ 1 կետը կանվանենք՝

1) f -ի գլոբալ մինիմումի (գլոբալ մաքսիմումի) կետ 1 բազմության վրա, եթե f (x) ≥ f (x∗ ) (f (x) ≤ f (x∗ )) ∀x ∈ 1,

2) f -ի լոկալ մինիմումի (լոկալ մաքսիմումի) կետ 1 բազմության վրա, եթե գոյություն ունի այդ կետի այնպիսի V շրջակայք, որ f (x) ≥ f (x∗ ) (f (x) ≤ f (x∗ )) ∀x ∈ 1 ∩ V :

Fունկցիայի մինիմումի մաքսիմումի կետերը կոչվում են էքստրեմումի կետեր:

Տեսական կար որ նշանակություն ունեն հետ յալ թեորեմները, որոնք բերում ենք ա անց ապացույցի (տենս, րինակ՝ |4|): Թեորեմ 1.1.4: Ու ուցիկ բազմության վրա ու ուցիկ ֆունկցիայի լոկալ մինիմումի կետը հանդիսանում է նա գլոբալ մինիմումի կետ: Թեորեմ 1.1.5: Ուժեղ ու ուցիկ ֆունկցիան ակ ու ուցիկ բազմության վրա ունի միակ մինիմումի կետ այդ բազմության վրա: Թեորեմ 1.1.6: Դիցուք 1 ⊆ Rn ու ուցիկ կոմպակտ է, իսկ f (x)-ը ու ուցիկ ֆունկցիա է՝ որոշվա Rn -ի վրա: Եթե f -ը 1 -ի վրա հաստատունից տարբեր է, ապա նա այդ բազմության վրա հասնում է իր մե ագույն արժեքին միայն 1 -ի եզրային կետերում:

ԽՆԴԻՐՆԵՐ

1. Դիցուք 1 -ը ու ուցիկ բազմություն է: Ապացուցել, որ (α1 Է α2 )1 - α1 1 Է α2 1 ∀α1 ≥ 0, ∀α2 ≥ 0 :

2. Հնարավոր է արդյոք, որ երկու ոչ ու ուցիկ բազմությունների հանրահաշվական գումարը լինի ու ուցիկ: 3. Հնարավոր է արդյոք, որ ու ուցիկ ոչ ու ուցիկ բազմությունների հանրահաշվական գումարը լինի ու ուցիկ: 4. Դիցուք 1 -ը ու ուցիկ բազմություն է: Ապացուցել, որ ա)

ոոt1 - 1 ,

բ)

1 -ը

գ)

ոոt1 - ոոt1 :

ու ուցիկ է,

5. Ապացուցել, որ երբ բազմությունը ակ է, անսահմանա ակ ու ուցիկ, ապա նրա կամայական կետով կարելի է տանել ճա ագայթ, որն ամբողջովին ընկա

կլինի այդ բազմության մեջ: 6. Ուսումնասիրել հետ յալ ֆունկցիայի ու ուցիկությունը. f (x1 , x2 ) - x21 − 4x1 x2 Է 4x22 :

7. Ուսումնասիրել հետ յալ ֆունկցիայի ու ուցիկությունը. f (x1 , x2 , x3 ) - x1 x3 − x21 − x22 :

6. Ցույց տալ, որ q f (x1 , x2 ) - 1 Է x21 Է x22

ֆունկցիան ու ուցիկ է R2 -ի վրա: 8. Նկարագրել բազմություն, որի վրա f (x1 , x2 ) -

x21 x2

ֆունկցիան լինի ու ուցիկ: 9.

a, Ե, Ը,

պարամետրերի ինչպիսի արժեքների դեպքում f (x1 , x2 ) - ax21 Է Եx1 x2 Է Ըx22

ֆունկցիան կլինի ու ուցիկ R2 -ի վրա: 10.

f (x) ֆունկցիայի վերգրաֆիկ 1

ու ուցիկ բազմության վրա կոչվում է հետ յալ բազմությունը. eքո(f ) ≡ {(α, x) ∈ Rn+1 /x ∈ 1, α ≥ f (x)} :

Ապացուցել հետ յալ պնդումը: Որպեսզի f -ը լինի ու ուցիկ 1 ու ուցիկ բազմության վրա, անհրաժեշտ է բավարար, որ նրա վերգրաֆիկը լինի ու ուցիկ բազմություն:

11. Դիցուք f (x)-ը ու ուցիկ ֆունկցիա է՝ որոշվա

ու ուցիկ բազմության վրա

x ∈ 1, α4 ≥ 0, ո ∈ |1 : ո|,

m Տ

α4 - 1 :

4-1

Ապացուցել, որ m m Տ Տ f( α4 x ) ≤ α4 f (x4 ) : 4-1

4-1

Այս անհավասարությունը կոչվում է Յենսենի անհավասարություն: 12. Դիցուք f (x) ու ուցիկ ֆունկցիան սահմանա ակ է Rn -ի վրա: Ապացուցել, որ f -ը հաստատուն է:

1.2

Էքստրեմումի ա առին երկրորդ կարգի անհրաժեշտ ու բավարար պայմանները

Թեորեմ 1.2.1 (Էքստրեմումի ա աջին կարգի անհրաժեշտ պայմանը): Դիցուք x∗ -ը f (x) ֆունկցիայի լոկալ մինիմումի (լոկալ մաքսիմումի) կետ է Rn -ի վրա f -ը դիֆերենցելի է այդ կետում: Այդ դեպքում f ֆունկցիայի գրադիենտը x∗ կետում հավասար է զրոյի, այսինքն f 0 (x∗ ) - 0, կամ, որ նույնն է՝ fx0 i (x∗ ) - 0, ո ∈ |1 : ո| : I Քանի որ x∗ -ը լոկալ մինիմումի (լոկալ մաքսիմումի) կետ է,

ապա գտվելով ֆունկցիայի դիֆերենցելիության պայմանից,

կամայական հ վեկտորի համար կունենանք

բավականաչա

ոքր

թվերի

α

0 ≤ f (x∗ Է αհ) − f (x∗ ) - (f 0 (x∗ ), αհ) Է օ(α) :

Բաժանելով այս անհավասարության երկու մասերը թվի վրա ձգտեցնելով α-ն զրոյի՝ կստանանք

α » 0

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

Այստեղից անմիջականորեն հետ ում է, որ f 0 (x∗ ) - 0 : J

Թեորեմ 1.2.2 (Մինիմումի ա աջին կարգի անհրաժեշտ ու բավարար պայմանը ու ուցիկ ֆունկցիայի համար): Դիցուք f -ը ու ուցիկ ֆունկցիա է որոշվա Rn -ի վրա դիֆերենցելի է x∗ կետում: Որպեսզի x∗ -ը լինի f -ի մինիմումի կետ Rn -ի վրա անհրաժեշտ է բավարար, որ f 0 (x∗ ) - 0 : I Անհրաժեշտությունը հետ ում է թեորեմ 1.2.1-ից:

Ապացուցենք բավարարությունը: Օգտվելով ու ուցիկ ֆունկցայի հիմնական անհավասարությունից՝ ստանում ենք f (x) − f (x∗ ) ≥ (f 0 (x∗ ), x − x∗ ) - 0, ∀ x ∈ Rn :

Այստեղից հետ ում է, որ վրա:

x∗ -ը f -ի

մինիմումի կետ է

Rn -ի

J

Թեորեմ 1.2.3 (Էքստրեմումի երկրորդ կարգի անհըրաժեշտ պայմանը): Դիցուք x∗ -ը f ֆունկցիայի լոկալ մինիմումի (լոկալ մաքսիմումի) կետ է Rn -ի վրա f -ը երկու անգամ դիֆերենցելի է այդ կետում:

Այդ դեպքում H(x∗ )-ը դրական կիսաորոշյալ է (բացասական կիսաորոշյալ է), այսինքն H(x∗ ) ≥ 0 (H(x∗ ) ≤ 0) :

Քանի որ x∗ -ը լոկալ մինիմումի (լոկալ մաքսիմումի) կետ է, իսկ f -ը երկու անգամ դիֆերենցելի է այդ կետում, ապա կամայական հ ∈ Rn վեկտորի բավականաչա

ոքր α թվերի համար ունենք I

0 ≤ f (x∗ Է αհ) − f (x∗ ) - 1/2(H(x∗ )αհ, αհ) Է օ(α2 ) :

Բաժանելով այս անհավասարության երկու մասերը α2 թվի վրա ձգտեցնելով α-ն զրոյի՝ կստանանք պահանջվող անհավասարությունը: J

Թեորեմ 1.2.4 (Էքստրեմումի երկրորդ կարգի բավարար պայմանները): Դիցուք f (x) ֆունկցիան երկու անգամ դիֆերենցելի է x∗ կետում տեղի ունեն հետ յալ պայմանները՝ f 0 (x∗ ) - 0, H(x∗ ) » 0 (H(x∗ ) Հ 0) :

Այդ դեպքում x∗ -ը f -ի լոկալ մինիմումի (լոկալ մաքսիմումի) կետ է Rn -ի վրա:

I Ենթադրենք հակա ակը: Դա նշանակում է, որ գոյություն ունի {xk } հաջորդականություն, որր բավարարում է հետ յալ պայմաններին. xk → x∗ , f (xk ) Հ f (x∗ ) (f (xk ) » f (x∗ )) :

Նշանակելով αk - kxk − x∗ k,

հk - (xk − x∗ )/αk , կունենանք

xk - x∗ Է αk հk :

Քանի որ kհk k - 1, ապա ընդհանրությունը չխախտելով կարող ենք ենթադրել, որ հk → հ0 6- 0 : Հաշվի ա նելով թեորեմի ենթադրության f 0 (x∗ ) - 0 պայմանը՝ կունենանք 0 ≥ f (xk ) − f (x∗ ) - 1/2(H(x∗ )αk հk , αk հk ) Է օ(αk2 ) :

Բաժանելով այս անհավասարություն երկու մասերը վրա անցնելով սահմանի՝ կստանանք

αk2 -ի

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

որը հակասում է թեորեմի ենթադրությանը: J

Պարզագույն դեպքերում էքստրեմումի ա աջին երկրորդ կարգի անհրաժեշտ ու բավարար պայմանները էֆեկտիվ միջոցներ են ֆունկցիայի էքստրեմումի կետերը ճշգրիտ գտնելու համար: Օրինակ: Գտնել f (x) - x31 Է x22 Է x23 Է x2 x3 − 3x1 Է 6x2 Է 2

ֆունկցիայի էքստրեմումի կետերը R3 -ի վրա: Լու ում: Ըստ մինիմումի անհրաժեշտ պայմանի՝ ունենք fx0 1 - 3x21 −3 - 0, fx0 ո - 2x2 Էx3 Է6 - 0, fx0 3 - 2x3 Էx2 - 0 :

Լու ելով այս համակարգը, կստանանք երկու ստացիոնար կետ՝ x1 - (1, −4, 2)

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

Ունենք նա , որ fx001 x1 - 6x1 , fx001 xո - 0, fx001 x3 - 0, fx00ո xո - 2, fx00ո x3 - 1, fx003 x3 - 2 :

Այժմ յուրաքանչյուր ստացիոնար կետի համար կարելի է կազմել հեսիանը ստուգել նրա նշանը: x1 կետի համար հեսիանը ունի հետ յալ տեսքը. 

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

Քանի որ ∆1 - 6, ∆2 -

6 0 0 6

- 12 » 0, ∆3 - 18 » 0,

ապա x1 -ը լոկալ մինիմումի կետ է: Ուսումնասիրենք x2 կետը: Այդ կետում հեսիանը ունի հետ յալ տեսքը. 

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

Քանի որ ∆1 - −6 Հ 0, ∆2 - −12 Հ 0, ∆3 - −18 Հ 0, ապա էքստրեմումի բավարար պայմանները տեղի չունեն: Ստուգենք երկրորդ կարգի անհրաժեշտ պայմանները: Ա աջին կարգի գլխավոր մինորներն են՝ −6, 2, 2 թվերը: Երկրորդ կարգի գլխավոր մինորներն են՝ 3, −12, −12: Երրորդ կարգի գլխավոր մինորը հավասար է ∆3 -ի, որը բացասական է: Այսպիսով, x2 կետում էքստրեմումի երկրորդ կարգի անհրաժեշտ պայմանները չեն կատարվում: Հետ աբար, x2 կետը էքստրեմումի կետ չէ:

ԽՆԴԻՐՆԵՐ

1. Գտնել f (x) ֆունկցիայի էքստրեմումի կետերը. f (x) - x31 Է x22 Է x23 − 4x1 x2 Է 3x1 Է 2x3 → ext7 :

2. Ստուգել, արդյոք (1, 1) կետը հետ յալ ֆունկցիայի էքստրեմումի կետ է, թե ոչ. f (x) - (x2 − x1 )2 Է (1 − x1 )2 Է 10(x2 − 1)2 :

Գլուխ 2

Գրադիենտային մեթոդը Գրադիենտային մեթոդը դասվում է դիֆերենցելի ֆունկցիաների մինիմիզացիայի թվային հիմնական մեթոդների շարքին: Այդ մեթոդի էությունը շատ պարզ է: Եթե f (x) ֆունկցիան դիֆերենցելի է, ապա նրա հակագրադիենտը՝ հ - −f 0 (x) վեկտորը, յուրաքանչյուր x կետում ցույց է տալիս ֆունկցիայի նվազման ուղղությունը: Դա հիմք է տալիս ենթադրել, որ կամայական սկզբնական x կետից սկսվող xk+1 - xk − αk f 0 (xk ) (αk » 0) եկուրենտ ա նչությամբ կա ուցվա հաջորդականության անդամները մե k ինդեքսների դեպքում մոտ կլինեն f -ի մինիմումի կետին: Այստեղ այս ենթադրությունը հիմնավորվում է որոշ դասի ֆունկցիաների αk թվերի հատուկ եղանակներով ընտրությունների դեպքերում: Ֆունկցիայի մինիմիզացիայի բազմազան ալգորիթմների նրանց պրակտիկ իրականացումների հետ կարելի է անոթանալ |3, 4, 6 | աշխատանքներում:

2.1

Fունկցիայի մինիմիզացիայի գրադիենտային եղանակների ընդհանուր նկարագրությունը

Սահմանում 2.1.1: հ վեկտորը կոչվում է f ֆունկցիայի նվազման ուղղություն x կետում, եթե բավականաչա

ոքր դրական α թվերի համար տեղի ունի f (x Է αհ) Հ f (x)

անհավասարությունը:

Այլ խոսքով, հ-ը այն վեկտորն է, որի ուղղությամբ բավականաչա

ոքր շարժվելիս կարելի է ֆունկցիայի արժեքները ոքրացնել: Լեմմա 2.1.1: Դիցուք f -ը դիֆերենցելի է x կետում հ-ն այնպիսի վեկտոր է, որ տեղի ունի (f 0 (x), հ) Հ 0

անհավասարությունը: Այդ դեպքում հ-ը f -ի նվազման ուղղություն է x կետում : I

Քանի որ f -ը դիֆերենցելի է, ապա

f (x Է αհ) - f (x) Է α|(f 0 (x), հ) Է

օ(α) |: α

Այստեղից, բավականաչա

ոքր դրական α թվերի համար միջակ ակագ երում գրա արտահայտությունը դա նում է բացասական: Այնպես որ կստանանք f (x Է αհ) Հ f (x) : J

Դիտողություն: Մասնավորապես, որպես նվազման ուղղու-

թյուն կարելի է վերցնել

հ - −f 0 (x),

որը կոչվում է հա-

կագրադիենտի ուղղություն: Կարելի է ցույց տալ, որ հակագրադիենտը տալիս է ֆունկցիայի ամենաարագ նվազման ուղղությունը: Գրադիենտային վայրէջքի մեթոդները կա ուցվում են հետ յալ կերպ: Ընտրվում է կամայական x0 կետ Rn տարա ությունից կա ուցվում է xk+1 - xk Է αk հk , k - 0, 1, 2, ...

(2.1.1)

եկուրենտ ա նչությունը: Այստեղ հk - −f 0 (xk ), իսկ αk թվերը կոչվում են քայլեր, որոնք ընտրվում են որոշակի րինաչա ությամբ: Հայտնի են քայլի ընտրության մի քանի եղանակներ, որոնք ներկայացվում են ստոր : 1. Քայլի ընտրության ապրիորի եղանակը: Այս դեպքում αk քայլերը դրական թվեր են, որոնք բավարարում են հետ յալ պայմաններին. Տ

αk - Է∞,

Տ

αk2 Հ Է∞ :

Մասնավորապես, այս պայմաններին բավարարում են αk -

lո(k Է 1) , αk , k - 0, 1, 2, ... kԷ1 kԷ1

թվային հաջորդականությունները: 2. Քայլի ընտրության ամենաարագ վայրէռքի եղանակը: Այս դեպքում αk » 0 քայլերը ընտրվում են հետ յալ կերպ: Կազմում են ց(α) ≡ f (xk Է αհk ) ֆունկցիան գտնում նրա մինիմումի կետը (0, ∞) միջակայքի վրա: Այն կետը, որտեղ մինիմումը հասանելի է համարվում է αk , այսինքն՝ αk ≡ a7ց min ց(α) : αմ0

Որոշ դասի ֆունկցիաների համար կարելի է ստանալ անալիտիկ բանաձ եր αk քայլերի որոշման համար, ինչպես հետ յալ րինակում: Օրինակ: Դիցուք f (x) - 1/2(Ճx, x) Է (Ե, x), որտեղ Ճ-ն (ո × ո) չա անի սիմետրիկ, դրական որոշյալ մատրից է, իսկ Ե-ն ո չա անի վեկտոր է: Կարելի է ցույց տալ, որ f -ը ու ուցիկ է, ունի միակ մինիմումի կետ Rn -ի վրա նրա գրադիենտը որոշվում է հետ յալ բանաձ ով. f 0 (x) - ՃxԷԵ : Այս դեպքում ունենք ց(α) ≡ f (xk Է αհk ) - 1/2|Ճ(xk Է αհk ), xk Է αk հk )|Է Է(Ե, xk Է αk հk ) - α2 |1/2(Ճհk , հk )|Է Էα(Ճxk Է Ե, հk ) Է (1/2Ճxk Է Ե, xk ) :

Դժվար չէ նկատել, որ ստացվա քա ակուսային ե անդամը հասնում է իր ոքրագույն արժեքին Rn -ի վրա հետ յալ կետում. αk - −

(f 0 (xk ), հk ) (Ճxk Է Ե, հk ) − ≥0 (Ճհk , հk ) (Ճհk , հk )

(2.1.2)

կետում: Հետ աբար, f (xk Է αk հk ) - min f (xk Է αհk ) - minՇ f (xk Է αհk ) : α≥0

α∈R

3. Քայլի ընտրության կիսման եղանակը: Ֆիքսում ենք որ է դրական ε թիվ (0, 1) միջակայքից α - 1 թվի համար ստուգում ենք f (xk − αf 0 (xk )) − f (xk ) ≤ −εαkf 0 (xk )k2

(2.1.3)

անհավասարությունը: Եթե այն տեղի ունի, ապա αk -ն համարում ենք հավասար α-ի: Հակա ակ դեպքում α-ն կիսում

ենք նորից ստուգում (2.1.3) անհավասարությունը այսպես շարունակ: Եթե որ է ք-րդ քայլում բավարարվում է (2.1.3) անհավասարությունը, ապա αk - 21 : p

ԽՆԴԻՐՆԵՐ

1. Գտնել հետ յալ ֆունկցիաների էքստրեմումի կետերը ամենաարագ վայրէջքի մեթոդով: Սկզբնական x0 կետից սկսա կա ուցել {xk } հաջորդականությունը (2.1.1) եկուրենտ ա նչությամբ քայլերի ընտրությունը կատարել (2.1.2) բանաձ ով: Եթե kf 0 (xk )k Հ ε0 , ապա պրոցեսն ավարտել xk -ն համարել ֆունկցիայի էքստրեմումի կետ: Այստեղ ε0 » 0 թիվը նախապես տրվա ճշտությունն է: ա)

f (x1 , x2 ) - 5x21 Է5x22 −6x1 x2 → ոոո, x0 - (1, 1), ε0 - 0.01:

բ)

−3x21 − 2x22 Է x2 Է 6x2 − 15 → ոax, x0 - (0, 1), ε0 - 0.1:

գ)

x21 Է x22 Է 2x1 x2 Է x2 → ոոո, x0 - (1, 0), ε0 - 0.01 :

2. Դիցուք f -ը երկու անգամ դիֆերենցելի է x կետում (f 0 (x), հ) - 0, (f 00 (x), հ) Հ 0 :

Ապացուցել, որ հ-ը ղություն է:

f

ֆունկցիայի նվազման ուղ-

3. Դիցուք

H(x) - f 00 (x) f 0 (x) 6- 0: Ապացուցել,

հեսիանը դրական որոշյալ է որ

հ - −H(x)−1 f 0 (x)

վեկտորը f ֆունկցիայի նվազման ուղղություն է: Ա առադրանք 1: Գրել րագիր, որը մինիմիզացնում է f (x) - 1/2(Ճx, x) Է (Ե, x) ֆունկցիան Rn -ի վրա: Այստեղ Ճ-ն (ո × ո) չա անի սիմետրիկ, դրական որոշյալ մատրից է, իսկ Ե-ն ո չա անի վեկտոր է: Մուտքի տվյալներն են Ճ, Ե, x0 , ո, ε, ε0 պարամետրերը: Այստեղ ε0 -ն ճշտությունն է: Կա ուցել {xk } հաջորդականությունը գրադիենտային իջեցման երեք մեթոդներով համեմատել դրանք քայլերի քանակի տեսակետից: Եթե kf 0 (xk )k Հ ε0 , ապա պրոցեսն ավարտել համարել xk -ն մինիմումի կետ: Համեմատել ստացվա արդյունքները x∗ - Ճ−1 Ե վեկտորի հետ, որը f -ի մինիմումի կետն է :

2.2

Քայլի կիսման եղանակի զուգամիտության թեորեմը

Լեմմա 2.2.1: Դիցուք f ֆունկցիայի համար իշտ են հետ յալ պայմանները. 1) f ֆունկցիայի գրադիենտը բավարարում է Լիպշիցի պայմանին, այսինքն գոյություն ունի այնպիսի L » » 0 հաստատուն, որ kf 0 (x) − f 0 (y)k ≤ Lkx − yk ∀x, y ∈ Rn :

2) f -ը ներք ից սահմանա ակ է, այսինքն՝ գոյություն ունի այնպիսի ո » 0 թիվ, որ տեղի ունի f (x) ≥ ո ∀x ∈ Rn

անհավասարությունը: Այդ դեպքում քայլի կիսման եղանակով վերջավոր քայլերի ընթացքում ընտրվում է αk -ն αk » (1 − ε)/L » 0, k - 0, 1, 2, ... :

Դիցուք հk - −f 0 (xk ): Համաձայն Լագրանժի միջին արժեքի վերաբերյալ թեորեմի՝ գոյություն ունի θ ∈ (0, 1) հաստատուն այնպիսին, որ եթե α » (1 − ε)/L, ապա I

f (xk Է αհk ) − f (xk ) - (f 0 (xk Է αθհk ), αհk ) - (f 0 (xk Է αθհk ) − f 0 (xk ), αհk ) Է α(f 0 (xk ), հk ) ≤ ≤ kLαθհk kkαհk 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

Թեորեմ 2.2.1: Դիցուք f ֆունկցիան բավարարում է լեմմա 2.2.1-i բոլոր պայմաններին {xk }-ն կիսման մեթոդով կա ուցվա հաջորդականությունն է: Այդ դեպքում f 0 (xk ) → 0, երբ k → ∞ : I

Ունենք

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

(2.2.1)

Այստեղից հետ ում է, որ f (xk+1 ) ≤ f (xk ): Այսինքն, {f (xk )} հաջորդականությունը մոնոտոն նվազող է ներք ից սահմանա ակ է: Հետ աբար, հաջորդականությունը զուգամետ է, այսինքն՝ f (xk ) − f (xk+1 ) → 0 :

(2.2.1)-ից հետ ում է, որ kf 0 (xk )k2 ≤

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

Այստեղից, քանի որ, ըստ լեմմա 2.2.1-ի, αk » (1−ε)/L » » 0, ապա f 0 (xk ) → 0 : J

Թեորեմ 2.2.2: Ենթադրենք գոյություն ունեն այնպիսի դրական D » 0, d » 0 հաստատուններ, որ Dkհk2 ≥ (f 00 (x)հ, հ) ≥ dkհk2 ∀x, հ ∈ Rn :

(2.2.2)

Այդ դեպքում կիսման եղանակով կա ուցվա {xk } հաջորդականությունը զուգամիտում է f -ի միակ x∗ մինիմումի կետին երկրաչա ական պրոգրեսիայի արագությամբ: Այսինքն՝ գոյություն ունեն Շ » 0 q ∈ (0, 1), հաստատուններ այնպիսին, որ kxk − x∗ k ≤ Շq k , k - 0, 1, ... :

I

Քանի որ f 0 (x∗ ) - 0, ապա, ըստ Թեյլորի բանաձ ի,

f (x) − f (x∗ ) - (f 00 (x∗ Է θ(x − x∗ ))(x − x∗ ), x − x∗ ),

որտեղ θ ∈ (0, 1): Այստեղից, հաշվի ա նելով հավասարությունը, ստանում ենք D d kx − x∗ k2 ≤ f (x) − f (x∗ ) ≤ kx − x∗ k :

(2.2.2)

ան-

(2.2.3)

Հաշվի ա նելով այս պայմանը ներկայացնելով f ֆունկցիան Թեյլորի բանաձ ի տեսքով x կետում՝ կունենանք 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 :

Այստեղից կստանանք f (x) − f (x∗ ) ≤ kf 0 (x)kkx − x∗ k − d/2kx − x∗ k2 : (2.2.4)

Հաշվի ա նելով նա (2.2.3) անհավասարության ձախ մասը՝ (2.2.4)-ից կստանանք d kx − x∗ k2 ≤ kf 0 (x)kkx − x∗ k − d/2kx − x∗ k2 :

Հետ աբար, kx − x∗ k ≤

kf 0 (x)k : d

(2.2.5)

Օգտվելով (2.2.3)-(2.2.5) անհավասարություններից՝ ստանում ենք kf 0 (x)k2 f (x) − f (x ) ≤ − d/D(f (x) − f (x∗ )) : d ∗

Այստեղից kf 0 (x)k2 ≥ d(1 Է d/D)(f (x) − f (x∗ )) :

(2.2.6)

Կիրա ելով (2.2.6) անհավասարությունը կիսման մեթոդի f (xk+1 ) − f (xk ) ≤ −εαk kf 0 (xk )k2

անհավասարությունում՝ կստանանք f (xk+1 ) − f (x∗ ) ≤ |1 − εαk d(1 Է d/D)|((f (xk ) − f (x∗ )) :

Այստեղից, հաշվի ա նելով αk » անհավասարությունը, կստանանք

ᾱ ≡ (1 − ε)/L » 0

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

որտեղ

(2.2.7)

q̄ - 1 − εαd(1 Է d/D) :

Վերջապես, գտվելով թյունից, կստանանք r kxk − x∗ k ≤

որտեղ

r Շ-

(2.2.3)

(2.2.7)

անհավասարու-

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

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

J

Քայլի կիսման եղանակի պրակտիկ իրականացումների ժամանակ սովորաբար գտվում են նրա հետ յալ մոդիֆիկացվա տարբերակից: k-րդ քայլում որպես ֆունկցիայի նվազման ուղղություն վերցնում են հk - −

f 0 (xk ) kf 0 (xk )k

վեկտորը, իսկ αk քայլի երկարությունը ընտրվում է կիսման եղանակի հետ յալ պայմանից. f (xk Է αհk ) − f (xk ) ≤ −αεkf 0 (xk )k :

(2.2.8)

Հաջորդ xk+1 կետը կա ուցվում է xk+1 - xk Է αk հk

(2.2.9)

եկուրենտ ա նչությամբ: Այժմ քայլի կիսման եղանակը մեկնաբանենք հետ յալ պարզ րինակի միջոցով: Օրինակ: Քայլի կիսման եղանակով գտնել f (x1 , x2 ) - 4x21 Է 4x22 Է 6x1 x2

ֆունկցիայի մինիմումի կետը R2 -ի վրա: Որպես սկզբնական մոտավորություն վերցնել x0 - (−2, 1) կետը: ε պարամետրի արժեքը վերցնել հավասար 0.5-ի: Կատարել իտերացիայի մեկ քայլ: Լու ում: Քայլի կիսման եղանակի իտերացիայի (2.2.9) բանաձ ը այս խնդրի համար ունի հետ յալ տեսքը. x

k+1

 -

xk+1 xk+1



 -

xk1 xk2



 Է αk

հk1 հk2

 :

(2.2.10)

Մասնակի ա անցյալների գրադիենտի նորմի համար ունենք հետ յալ բանաձ երը. fx0 1 (x1 , x2 ) - 8x1 Է 6x2 , fx0 ո (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 , հ − : kf 0 (xk )k kf 0 (xk )k Ա աջին իտերացիայում k - 0: Օգտագոր ելով (2.2.10) − (2.2.13) բանաձ հk1 - −

նանք

(2.2.13)

երը՝ կստա-

fx0 1 (x01 , x02 ) - 8x01 Է 6x02 - 8(−2) Է 6 - −10,

fx0 ո (x01 , x02 ) - 6x01 Է 8x02 - −4, kf 0 (x0 )k -

p (−10)2 Է (−4)2 ≈ 10.77, հ01 հ02 -

≈ 0.93, 10.77

≈ 0.37 : 10.77

Դիցուք α - 1: Այդ դեպքում, հաշվի ա նելով այս արդյունքները, մեկնարկային (−2, 1) արժեքը (2.2.10)-ը, կստանանք  x≡

−2



 −

0.93 0.37

Ա աջին իտերացիայի համար մանը ունի հետ յալ տեսքը.



α0

 -

−1.07 1.63

 :

քայլի ընտրության պայ-

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

Կատարելով համապատասխան հաշվարկներ՝ նկատում ենք, որ այս անհավասարության ձախ մասը մոտավորապես հավասար է −1.6-ի, իսկ աջ մասը հավասար է −5.4-ի: Հետ աբար, այն տեղի չունի: Այժմ կիսենք α թիվը նորից ստուգենք անհավասարությունը: Այս դեպքում x - (−1.58, 1.18) :

Քանի որ f (x0 ) - 8, f (x) ≈ 4.16, ապա անհավասարության ձախ մասը հավասար է 4.16−8 - −3.84, իսկ աջ մասը, հեշտ է նկատել, որ հավասար է −2.69-ի: Այսպիսով, նշվա անհավասարությունը տեղի ունի հետ աբար՝ α0 - 0.5, x1 - (−1.54, 1.18) :

ԽՆԴԻՐՆԵՐ

Քայլի կիսման եղանակով լու ել հետ յալ էքստրեմումի խնդիրները: Վերցնել x0 - (1, 1), ε - 0.5 : Կատարել իտերացիայի մեկ քայլ: 1. 2x21 Է 2x22 Է 4x1 Է 6x2 − 2x1 x2 → ոոո : 2.

2.3

−2x21 − 2x22 − 2x1 x2 Է 2 → ոax :

G այնացման մեթոդը

Դիտարկենք պայմանական պտիմիզացիայի հետ յալ խնդիրը. f (x) → ոոո, x ∈ 1 :

(2.3.1)

Այս խնդրում f -ը դիֆերենցելի ու ուցիկ ֆունկցիա է, իսկ 1 ⊂ Rn -ը կոմպակտ ու ուցիկ բազմություն է: Տանք գ այնացման մեթոդի համա ոտ նկարագրությունը: Ընտրում ենք կամայական x0 կետ 1 բազմությունից կա ուցում ենք {xk } հաջորդականությունը xk+1 - xk Է αk հk , k - 0, 1, ...

եկուրենտ ա նչությամբ: Այստեղ հk վեկտորը f -ի այնպիսի նվազման ուղղություն է xk ∈ 1 կետում, որ բավականաչա

ոքր αk քայլերի դեպքում xk+1 ∈ 1 : հk վեկտորի որոշման համար k-րդ քայլում լու ում ենք հետ յալ միջանկյալ խնդիրը. (f 0 (xk ), x − xk ) → ոոո, x ∈ 1 :

Ենթադրենք x̄k -ն այդ խնդրի որ է լու ում է: Նշանակենք ηk - (f 0 (xk ), x̄k − xk ), հk - x̄k − xk :

վեկտորը կոչվում է պայմանական հակագրադիենտ: Ակնհայտ է, որ ηk ≤ 0: Իրոք, հk

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

Եթե ηk Հ 0 , ապա ընտրում ենք αk քայլը կիսման մեթոդով: Վերցնում ենք α - 1 ստուգում f (xk Է αհk ) − f (xk ) ≤ αεηk

(2.3.2)

անհավասարությունը: Եթե այն տեղի ունի, ապա համարում ենք αk - 1, հակա ակ դեպքում α-ն կիսում ենք նորից ստուգում նշվա անհավասարությունը այսպես շարունակ: Երբ ա աջին անգամ տեղի ունենա (2.3.2) անհավասարությունը, ապա այդ α-ն համարվում է αk -ի արժեք ցիկլը ավարտվում է: Այնուհետ կա ուցում ենք xk+1 կետը

եկուրենտ ա ընչությամբ. xk+1 - xk Է αk հk :

Թեորեմ 2.3.1: Դիցուք

ա) 1 ⊂ Rn -ը ու ուցիկ կոմպակտ է, բ) f (x)-ը դիֆերենցելի է

ու ուցիկ 1 -ի վրա,

գ) f 0 (x) գրադիենտը 1 բազմության վրա բավարարում է Լիպշիցի պայմանին: Այդ դեպքում 1) եթե որ է k-րդ քայլում ηk - 0, ապա xk -ն (2.3.1) խնդրի լու ումն է ալգորիթմն ավարտվում է,

2) եթե ηk Հ 0, k - 0, 1, 2, ..., ապա f (xk ) → min f (x) : x∈M

Դիցուք ηk - 0: Ըստ ու ուցիկ ֆունկցիայի հիմնական անհավասարության՝ ունենք I

f (x) − f (xk ) ≥ (f 0 (xk ), x − xk ) ≥ ηk - 0 ∀x ∈ 1,

այսինքն xk -ն (2.3.1) խնդրի լու ումն է: Ցույց տանք, որ հk ուղղությամբ բավականաչա

ոքր շարժվելիս մնում ենք 1 բազմության մեջ: Իրոք, քանի որ 1 -ը ու ուցիկ է, ապա xk Էαհk - xk Էα(x̄k −xk ) - (1−α)xk Էαx̄k ∈ 1, ∀α ∈ |0, 1| :

Քանի որ f -ի գրադիենտը 1 կոմպակտի վրա բավարարում է Լիպշիցի պայմանին xk ∈ 1 , ապա կարելի է ցույց տալ, որ վերջավոր քայլերից հետո (2.3.2) անհավասարությունը տեղի ունի հետ աբար αk քայլը ընտրվում է: Միաժամանակ գոյություն ունի այնպիսի ᾱ » 0 թիվ, որ αk » ᾱ » 0, k - 0, 1, ... (տենս, րինակ՝ |8|, լեմմա 3.1, էջ 229): Այժմ ապացուցենք, որ f (xk ) → min f (x) : x∈M

Համաձայն (2.3.2) անհավասարության՝ ունենք f (xk+1 ) ≤ f (xk ) Է εαk ηk :

(2.3.3)

Գումարելով (2.3.3) անհավասարությունները k ∈ |0 : ո − ինդեքսների համար՝ կստանանք

− 1|

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

m−1 Տ k-0

αk η k :

Այստեղից հետ ում է, որ բացասական անդամներով αk ηk շարքը զուգամետ է: Հետ աբար, նրա ընդհանուր անդամը ձգտում է զրոյի՝

-

αk ηk → 0 :

(2.3.4)

Քանի որ αk » ᾱ » 0, ապա (2.3.4)-ից հետ ում է, որ ηk → 0: Այստեղից, ընտրելով xk → x∗ ∈ 1 զուգամետ ենթահաջորդականությունը գտվելով ու ուցիկ ֆունկցիայի հիմնական անհավասարությունից, կստանանք՝ j

f (x) − f (xkj ) ≥ (f 0 (xkj ), x − xkj ) ≥ ηkj ∀x ∈ 1 : (2.3.5) → x∗ , ապա (2.3.5) xk Քանի որ ηk → 0 անհավասարությունում անցնելով սահմանի, կստանանք՝ j

j

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

այսինքն, x∗ -ը f -ի մինիմումի կետն է 1 բազմության վրա: Այսպիսով, ապացուցվեց, որ {f (xk )} հաջորդականության {f (xk )} ենթահաջորդականությունը զուգամիտում է minx∈M f (x): Մյուս կողմից, քանի որ {f (xk )} հաջորդականությունը մոնոտոն նվազող է, ապա այն նույնպես կզուգամիտի minx∈M f (x)-ին: j

J

ԽՆԴԻՐՆԵՐ

1. Ապացուցել պնդումները հետ յալ խնդրի համար. (Ը, x) → ոոո, x ∈ 1 :

ա) Եթե 1 - {x ∈ Rn /kx − x0 k ≤ 7}, ապա x∗ - x0 Է

վեկտորը խնդրի լու ումն է:

Ը kԸk

բ) Եթե 1 - {x ∈ Rn /aj ≤ xj ≤ Եj , j ∈ |1 : ո|}, ապա  aj , եթե Ըj ≥ 0, ∗ xj Եj , եթե Ըj Հ 0 կոորդինատներով վեկտորը խնդրի լու ումն է: 2. Գտնել f (x) - x21 Է x22 ֆունկցիայի պայմանական հակագրադիենտը x - (2, 3) կետում 1 - {x ∈ ∈ R2 /x1 Է x2 ≤ 6, x1 ≥ 0, x2 ≥ 0} բազմության վրա: Ա առադրանք 2: Կազմել րագիր, որը իրականացնում

է f (x) - 1/2(Ճx, x) Է (Ե, x) ֆունկցիայի մինիմիզացիան 1 - {x ∈ Rn /Cx ≤ d, x ≥ 0} բազմության վրա պայմանական գրադիենտի մեթոդով: Այստեղ Ճ-ն (ո × ո) չա անի սիմետրիկ դրական որոշյալ մատրից է, իսկ C-ն (ո × ո) չա անի մատրից է: k-րդ քայլում գտագոր ելով սիմպլեքս ալգորիթմը՝ ստանալ

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

խնդրի որ է լու ում: Ալգորիթմի կանգա ի համար ընդունել |ηk | Հ ε0 պայմանը, որտեղ ε0 » 0 նախապես տրվա

ճշտություն է: Եթե նշվա պայմանը կատարվում է, ապա xk վեկտորը համարել խնդրի լու ում ավարտել ալգորիթմը: Սկզբնական x0 ∈ 1 կետի ընտրությունը նույնպես կատարել սիմպլեքս ալգորիթմով:

2.4

Ապրիորի մեթոդի զուգամիտությունը

Թեորեմ 2.4.1: Դիցուք f -ը ու ուցիկ ֆունկցիա է՝ որոշվա Rn -ի վրա 1 ∗ -ը նրա մինիմումի կետերի բազմությունն է Rn -ի վրա: Ենթադրենք 1 ∗ 6- ∅: Դիցուք {xk }-ն հետ յալ եկուրենտ ա նչությամբ կա ուցվա

հաջորդականություն է.

n

x ∈R , x

k+1

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

որտեղ αk -երը դրական թվեր են՝ բավարարող Տ

պայմաններին: Այդ դեպքում

αk - Է∞,

Տ

αk2 Հ Է∞ :

(2.4.2)

xk → x̄ ∈ 1 ∗ :

Այսինքն՝ {xk } հաջորդականությունը զուգամիտում է f -ի որ է x մինիմումի կետի: I Նշանակենք v k - f 0 (xk ): Վերցնենք որ է x∗ ∈ 1 ∗ կետ հաշվենք նրա հե ավորությունը {xk } հաջորդականության

անդամներից: Ունենք

kxk+1 − x∗ k2 - kxk − x∗ k2 Է

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

Քանի որ x∗ -ը f -ի մինիմումի կետ է 1 -ի վրա, ապա (v k , x∗ − xk ) ≤ f (x∗ ) − f (xk ) ≤ 0 :

Հաշվի ա նելով այս պայմանը (2.4.3)-ը՝ կստանանք kxk+1 − x∗ k2 ≤ kxk − x∗ k2 Է

m−1 Տ

α42 :

(2.4.4)

4-0

Քանի որ αk 2 շարքը զուգամետ է, ապա (2.4.4) անհավասարությունից հետ ում է, որ {xk }-ն սահմանա ակ հաջորդականություն է: Այստեղից հետ ում է, որ սահմանա ակ կլինի նա {vk } հաջորդականությունը: Այսինքն, գոյություն ունի Շ » 0 թիվ այնպիսին, որ -

kv k k ≤ Շ :

(2.4.5)

Ցույց տանք, որ գոյություն ունի ինդեքսների այնպիսի {ks } ենթահաջորդականություն, որ (v ks , x∗ − xks ) → 0,

երբ ks → ∞ :

(2.4.6)

Ենթադրենք հակա ակը: Այդ դեպքում գոյություն ունի այնպիսի N » 0 թիվ, որ ինչ-որ K համարից սկսա տեղի ունի (f 0 (xk ), x∗ − xk ) Հ −N Հ 0, ∀k » K

(2.4.7)

անհավասարությունը: Օգտվելով (2.4.3)-(2.4.7) անհավասարություններից՝ կըստանանք kxk+1 − x∗ k2 ≤ kx0 − x∗ k2 −

k k Տ 2N Տ α4 Է α42 : (2.4.8) Շ 4-0 4-0

Այս անհավասարության մեջ անցնելով սահմանի, երբ k → ∞, կստանանք, որ նրա աջ մասը ձգտում է −∞, իսկ ձախ մասը ոչ բացասական թիվ է, ինչը հակասություն է: Այժմ {xk } ենթահաջորդականության կետերի համար, կիրա ելով ու ուցիկ ֆունկցիայի հիմնական անհավասարությունը, կունենանք՝ s

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

Այստեղ անցնելով սահմանի, երբ ks → ∞ հաշվի ա նելով նա (2.4.6)-ը, կստանանք f (xks ) → f (x∗ ) - min f (x) : x∈M

Քանի որ {xk }-ը սահմանա ակ հաջորդականություն է, ապա նրանից կարելի է անջատել զուգամետ ենթահաջորդականություն: Ընդհանրությունը չխախտելով, ենթադրենք որ xk → x̄: Այստեղից, գտվելով f -ի անընդհատությունից, կստանանք s

s

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

այսինքն՝

x̄ ∈ 1 ∗ :

Ցույց տանք, որ xk → x̄ : Քանի որ xk → x̄, ապա կամայական ε » 0 թվի համար գոյություն ունի այնպիսի K համար, որ երբ ks » K, ապա տեղի ունի s

kxks − x̄k2 Հ

ε

(2.4.9)

անհավասարությունը: Կարող ենք նա համարել, որ ցանկացա ք համարի համար տեղի ունի ks +p−1

Տ

α42 Հ

4-ks

ε

(2.4.10)

անհավասարությունը: Օգտվելով (2.4.3) (2.4.9)-(2.4.10) անհավասարություններից՝ ստանում ենք, որ երբ ks » K , ապա ցանկացա ք բնական թվի համար տեղի ունի հետ յալ անհավասարությունը՝ ks +p−1

kք

ks +p

ks

− x̄k ≤ kx − x̄k Է

Տ

α42 Հ

4-ks

ε ε Է -ε: 2 2

Իսկ սա նշանակում է, որ xk → x̄ : J

ԽՆԴԻՐՆԵՐ

Ապրիորի մեթոդով լու ել հետ յալ խնդիրները: Վերցնել x0 - (1, 1), αk - 1/k Է 1, k - 0, 1, 2, ... : Կատարել իտերացիայի երկու քայլ: 1. 3x21 Է x22 Է 11x2 Է 3x1 → ոոո : 2.

2.Տ

−2x21 − x22 Է 8x1 Է 6x2 − 25 → ոax :

Gրադիենտի պրոյեկտման մեթոդը

Դիցուք 1 ⊆ Rn -ը ակ ու ուցիկ բազմություն է: Նշանակենք ΠM (a)-ով a վեկտորի պրոյեկցիան 1 բազմության վրա: Այսինքն՝ ΠM (a)-ն 1 բազմության ամենամոտիկ կետն է a վեկտորից: Ճշմարիտ է հետ յալ պնդումը (տենս, րինակ՝ |8|):

Լեմմա 2.5.1: ΠM պերատորը բավարարում է Լիպշիցի պայմանին L - 1 հաստատունով, այսինքն՝ kΠM (x) − ΠM (y)k ≤ kx − yk ∀ x, y ∈ Rn :

(2.5.1)

Դիտարկենք մաթեմատիկական րագրավորման հետ յալ խնդիրը՝ f (x) → ոոո, x ∈ 1 :

Այստեղ f (x)-ը դիֆերենցելի ֆունկցիա է, իսկ 1 -ը ու ուցիկ բազմություն է: Գրադիենտի պրոյեկման մեթոդով այս խնդրի լու ման համար կա ուցվում է {xk } հաջորդականություն հետ յալ եկուրենտ ա նչությամբ. x0 ∈ 1, xk+1 - ΠM (xk − αk f 0 (xk )), k - 0, 1, 2, ... :

Ուսումնասիրենք այն պայմանները, որոնց դեպքում այս հաջորդականությունը կզուգամիտի f -ի որ է մինիմումի կետի: Լեմմա 2.5.2: Դիցուք f -ը θ հաստատունով ուժեղ ու ուցիկ ֆունկցիա է 1 ու ուցիկ բազմության վրա: Այդ դեպքում տեղի ունի հետ յալ անհավասարությունը. (f 0 (x) − f 0 (y), x − y) ≥ 2θkx − yk2 ∀ x, y ∈ 1 : (2.5.2) I ըստ f ֆունկցիայի ուժեղ ու ուցիկության (1.1.2) սահմանման՝ կամայական x, y ∈ 1 կետերի համար ունենք՝ f (x) − f (y) ≥ (f 0 (x), x − y) Է θkx − yk2 , f (y) − f (x) ≥ (f 0 (y), y − x) Է θkx − yk2 :

Գումարելով այս երկու անհավասարությունները՝ կստանանք (2.5.2) անհավասարությունը: J

Հենվելով այս արդյունքների վրա՝ ապացուցենք պրոյեկման մեթոդի զուգամիտության հետ յալ թեորեմը: Թեորեմ 2.5.1: Դիցուք f -ը θ հաստատունով ուժեղ ու ուցիկ ֆունկցիա է 1 ակ ու ուցիկ բազմության վրա: Ենթադրենք նա , որ f 0 գրադիենտը բավարարում է Լիպշիցի պայմանին 1 բազմության վրա L » 0 հաստատունով, այսինքն kf 0 (x) − f 0 (y)k ≤ Lkx − yk ∀x, y ∈ 1 :

Այդ դեպքում, եթե պրոյեկման մեթոդում որպես αk քայլեր վերցնենք մի նույն հաստատունը (0, L4θո ) միջակայքից, ապա {xk } հաջորդականությունը կզուգամիտի f -ի միակ մինիմումի կետին երկրաչա ական պրոգրեսիայի արագությամբ: I

Դիտարկենք հետ յալ պերատորը՝ Ճα : 1 → 1, Ճα (x) ≡ ΠM (x − αf 0 (x)) :

Ցույց տանք, որ այն սեղմող պերատոր է: Օգտագոր ելով (2.5.1) − (2.5.2) անհավասարությունները՝ կունենանք. kՃα (x) − Ճα (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)

Ընտրենք α այպես, որ q≡

√ 1 − 4αθ Է α2 L2

թիվը ոքր լինի մեկից: Եթե α ∈ (0, L4θ ), ապա q Հ 1 հետ աբար Ճα պերատորը կլինի սեղմող: Դիցուք x∗ -ը նրա անշարժ կետն է 1 բազմության վրա, այսինքն՝ ո

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

(2.5.4)

Ցույց տանք, որ այդ անշարժ կետը f -ի մինիմումի կետն է: Իրոք, քանի որ պրոյեկտման պերատորը բավարարում է (ΠM (a) − a, x − ΠM (a)) ≥ 0 ∀a ∈ Rn , ∀x ∈ 1

(2.5.5)

անհավասարությանը (տենս, րինակ՝ |8|), ապա այստեղ տեղադրելով a - x∗ − αf 0 (x∗ ), ΠM (a) - x∗ հաշվի ա նելով (2.5.4)-ը, կստանանք՝ (x∗ − x∗ Է αf 0 (x∗ ), x − x∗ ) ≥ 0 ⇒ ⇒ (f 0 (x∗ ), x − x∗ ) ≥ 0 ∀ x ∈ 1 :

(2.5.6)

Վերջապես, հաշվի ա նելով նա ու ուցիկ ֆունկցիայի հիմնական անհավասարությունը, (2.5.6)-ից կունենանք f (x) − f (x∗ ) ≥ (f 0 (x∗ , x − x∗ ) ≥ 0 ∀x ∈ 1,

այսինքն x∗ -ը f -ի մինիմումի կետն է: Բացի դրանից (2.5.3)-ից հետ ում է, որ kxk+1 − x∗ k - kՃα xk − Ճα x∗ k ≤ qkxk − x∗ k ≤ ... ≤ q k+1 kx0 − x∗ k :

Իսկ սա նշանակում է, որ {xk } հաջորդականությունը զուգամիտում է x∗ կետին երկրաչա ական պրոգրեսիայի արագությամբ: J

ԽՆԴԻՐՆԵՐ

1. Դիցուք a ∈ Rn կամայական կետ է: Ապացուցել, որ եթե ա)

1 - {x ∈ Rn /kx − x0 k ≤ 7},

ապա

ΠM (a) - x0 Է

a − x0 7: ka − x0 k

բ) եթե 1 - {x ∈ Rn /Եj ≤ xj ≤ Ըj , ապա   Եj , aj , (ΠM (a))j  Ըj ,

գ) եթե 1 - {x ∈ Rn /xj ≥ 0, ապա

j ∈ |1 : ո|},

եթե aj Հ Եj եթե Եj ≤ aj ≤ Ըj եթե aj » Ըj : j ∈ |1 : ո|},

ΠM (a) - (ոax(0, a1 ), ..., ոax(0, an )) :

Ա առադրանք 3: Կազմել րագիր, որը գրադիենտի պրո-

յեկտման մեթոդով կիրականացնի

f (x) - 1/2(Ճx, x) Է (Ե, x)

քա ակուսային ֆունկցիայի մինիմիզացիան գնդի զուգահե անիստի վրա: Որպես պրոյեկտման պերատորներ վերցնել վեր ում նշվա բանաձ երը: L հաստատունը վերցնել Ճ մատրիցի նորմը, ուժեղ ու ուցիկության θ հաստատունը վերցնել մատրիցի մինիմալ սե ական արժեքը, իսկ 2θ : L2 kxk+1 − xk k Հ ε0

αk -

Կանգա ի քայլ համարել նախապես տրվա ճշտություն է:

ε0 » 0

պայմանը, որտեղ

Գլուխ 3

Ու ուցիկ անաոից Ու ուցիկ անալիզը մաթեմատիկական անալիզի բաժին է, որն ուսումնասիրում է ու ուցիկ բազմությունների ու ուցիկ ֆունկցիաների հատկությունները: Ու ուցիկ անալիզի գաղա արները աստերը ֆունդամենտալ նշանակություն ունեն պտիմիզացիայի թվային մեթոդների տեսությունում: Դրանք լայն կիրա ություններ ու նեն նա կիրա ական մաթեմատիկայի այնպիսի բնագավա ներում ինչպիսիք են՝ խաղերի տեսությունը, գոր ույթների հետազոտումը, մաթեմատիկական էկոնոմիկան այլն: Այս գլուխը կարելի է դիտարկել որպես ու ուցիկ անալիզի ներա ություն: Այստեղ բերվա

աստերը պնդումները գտագոր վում են հետագայում մաթեմատիկական րագրավորման խնդիրներում Լագրանժի անորոշ գոր ակիցների մեթոդը հիմնավորելու համար: Նշենք, որ կան նա լրացուցիչ

աստեր, որոնք ձ ակերպվա են խնդիրների տեսքով: Հարկ ենք համարում նշել, որ ու ուցիկ անալիզի ժամանակակից մեթոդներին կարելի է անոթանալ |5, 7, 11 | աշխատանքներում:

3.1

Oւ ուցիկ բազմությունների անռատման թեորեմները

Սահմանում 3.1.1: Դիցուք ք ∈ Rn -ն ոչ զրոյական վեկտոր է, իսկ α-ն իրական թիվ է: H - {x ∈ Rn /(ք, x) - α}

բազմությունը կոչվում է հիպերհարթություն, իսկ H+ - {x ∈ Rn /(ք, x) ≥ α}, H− - {x ∈ Rn /(ք, x) ≤ α}

բազմությունները՝ այդ հիպերհարթությամբ նվա կիսատարա ություններ: Սահմանում 3.1.2: 11 , 12 ⊆ Rn բազմությունները կոչվում են անjաtvoղ հipելհալթowթյամb, եթե գոյություն ունի այնպիսի ք 6- 0 վեկտոր, որ (ք, x) ≤ (ք, y) ∀x ∈ 11 , ∀y ∈ 12 :

Սա նշանակում է, որ գոյություն ունի այնպիսի պերհարթություն, որ

H

հի-

11 ⊆ H− , 12 ⊆ H+ :

Թեորեմ 3.1.1: Դիցուք 11 , 12 ⊆ Rn այնպիսի ու ուցիկ բազմություններ են, որ 11 ∩ 12 - ∅: Այդ դեպքում նրանք անջատվում են հիպերհարթությամբ: I

Թեորեմի ապացույցը հենվում է հետ յալ երկու պընդումների վրա: Լեմմա 3.1.1: Եթե 1 -ը ակ ու ուցիկ բազմություն է a∈ / 1, ապա այդ կետը հիպերհարթությամբ անջատվում է 1 բազմությունից: I

Գտնենք a կետի պրոեկցիան 1 բազմության վրա: Ցույց տանք, որ այն գոյություն ունի միակն է: Վերցնենք a կենտրոնով 7 ≡ ոոfx∈M ka − xk Է ε շա ավղով Br (a) գունդը, որտեղ ε » 0 ֆիքսա թիվ է: Քանի, որ գունդը ակ սահմանա ակ բազմությունն է, ապա 1 ∩ Br (a) հատումը կոմպակտ է: Հետ աբար, a կետի հե ավորությունը այդ հատումից հասանելի է: Դժվար չէ համոզվել, որ այդ կետը ամենամոտիկն է նա 1 բազմությունից, այսինքն դա ΠM (a) կետն է : Ցույց տանք ΠM (a)-ի միակությունը: Ենթադրենք գոյություն ունի երկու ամենամոտիկ կետ: Դիցուք դրանք Ե, Ը կետերն են: Եթե a, Ե, Ը կետերը ե անկյուն են կազմում, ապա այն հավասարասրուն է, որի սրունքը հավասար է d ≡ inf x∈M kx − ak, իսկ հիմքը |Ը, Ե| հատվա ն է: Քանի, որ 1 ու ուցիկ է, ապա |Ը, Ե| ∈ 1 : Հետ աբար a գագաթից տարա բարձության հիմքը |Ը, Ե| հատվա ի միջնակետն է: Քանի որ բարձությունը ոքր է սրունքից սրունքը մինիմալ հե ավորությունն է, ապա ստացանք հակասություն: Նշենք նա a, Ե, Ը կետերը մի նույն գ ի վրա գտնվել չեն կարող, քանի որ a ∈/ 1 : Այժմ |ΠM (a), a| հատվա ի ց միջնակետով տանենք հիպերհարթություն, որի նորմալը a − ΠM (a) վեկտորն է: Ցույց տանք, որ այդ հիպերհարթությունը անջատում է a կետը 1 բազմությունից: Դիցուք H+ այն կիսատարա ությունն է, որը պարունակում է a կետը, իսկ H−

կիսատարա ությունը չի պարունակում a-ն: Ցույց տանք, որ 1 ⊂ H− :

Նախ պարզ է, որ ց կետի պրոեկցիան 1 բազմության վրա ΠM (a) կետն է: Ենթադրենք, որ գոյություն ունի e ∈ 1 ∩ H− : Այդ դեպքում ց, ΠM (a), e գագաթներով ե անկյան մեջ ց գագաթից տարվա բարձրության հիմքը կպատկանա |ΠM (a), e| ⊆ 1 հատվա ին այդ բարձրությունը ոքր է |ց, ΠM (a)| հատվա ի երկարությունից, որը հակասություն է, քանի որ այն ց կետի մինիմալ հե ավորությունն է 1 բազմությունից: J

Լեմմա 3.1.2: Դիցուք 1 ու ուցիկ բազմություն է, իսկ a ∈ / 1 : Այդ դեպքում a կետը հիպերհարթությամբ անջատվում է 1 բազմությունից:

Եթե a ∈/ 1 , ապա հանգում ենք նախորդ դեպքին, քանի որ այս դեպքում a կետը կարելի է հիպերհարթությամբ անջատել 1 բազմությունից հետ աբար՝ 1 բազմությունից: Այժմ ենթադրենք, որ a-ն 1 -ի եզրային կետ է: Այդ դեպքում գոյություն ունի այնպիսի {xk } ∈/ 1 հաջորդականություն, որ xk → a : Համաձայն լեմմա 3.1.1-ի յուրաքանչյուր xk կետ կարելի է անջատել 1 բազմությունից հիպերհարթությամբ: Դա նշանակում է, որ գոյություն ունեն այնպիսի քk միավոր վեկտորներ, որ I

(քk , x) ≤ (քk , xk ) ∀x ∈ 1 :

սահմանա ակելով ընդհանրությունը, կարելի է ենթադրել, որ քk → ք0 6- 0 : Անցնելով սահմանի՝ կստանանք (ք0 , x) ≤ (ք0 , a) ∀x ∈ 1,

ինչը նշանակում է a կետի հիպերհարթությամբ:

բազմության անջատում

J

Այժմ անցնենք թեորեմի ապացույցին: Նշանակենք 1 ≡ ≡ 11 − 12 : 1 -ը ու ուցիկ է քանի որ 11 ∩ 12 - ∅, ապա 0 ∈/ 1 : Համաձայն լեմմա 3.1.2-ի՝ 0 կետը կարելի է անջատել 1 բազմությունից: Դա նշանակում է, որ գոյություն ունի այնպիսի ք 6- 0 վեկտոր, որ (ք, x − y) ≤ 0 ∀x ∈ 11 , ∀y ∈ 12 :

Այստեղից, (ք, x) ≤ (ք, y) ∀x ∈ 11 , ∀y ∈ 12 : J

Հետ անք 3.1.1: Դիցուք 1 ⊆ Rn -ը ու ուցիկ բազմություն է, իսկ a-ն նրա եզրային կետը: Այդ դեպքում a կետով կարելի է տանել այնպիսի հիպերհարթություն, որ 1 բազմությունը ընկա լինի այդ հիպերհարթությամբ

նվա կիսատարա ություններից որ է մեկում: Այդպիսի հիպերհարթությունը կոչվում է հենման հիպերհարթություն: Սահմանում 3.1.3: Դիցուք 11 12 ⊆ Rn : Կասենք, որ այդ բազմությունները xist են անջատվում հիպերհարթությամբ, եթե գոյություն ունեն այնպիսի ք վեկտոր ε » 0 թիվ, որ (ք, x) ≤ (ք, y) − ε ∀x ∈ 11 , ∀y ∈ 12 :

Հետագա դասախոսությունների որոշ թեորեմների, մասնավորապես Լագրանժի անորոշ գոր ակիցների մեթոդի, հիմնավոր շարադրման համար կար որ է հետ յալ պնդումը, որը բերում ենք ա անց ապացույցի (տենս, րինակ՝ |7-8|):

Թեորեմ 3.1.2: Դիցուք 11 ⊂ Rn ակ ու ուցիկ բազմություն է, իսկ 12 ⊂ Rn ու ուցիկ կոմպակտ է 11 ∩ 12 - ∅ :

Այդ դեպքում այս բազմությունները խիստ անջատվում են հիպերհարթությամբ:

ԽՆԴԻՐՆԵՐ

1. Գրել այն հիպերհարթության հավասարումը, որն անջատում է (−1, 2, 1, −3) կետը 1 ⊆ R4 բազմությունից, որը տրվում է անհավասարությունների հետ յալ համակարգով.  5x1 Է x2 − 5x3 − 3x4 ≤ 1,    −3x2 − 2x2 Է 5x3 Է x4 ≤ 2, 3x2 Է x3 Է 2x4 ≤ 0,    x1 Է x2 Է 3x3 − x4 ≤ 9 :

2. Ապացուցել հետ յալ պնդունը: Որպեսզի 1 ⊆ Rn

ակ բազմությունը լինի ու ուցիկ, անհրաժեշտ է բավարար, որ ցանկացա Ե ∈/ 1 կետ խիստ անջատվի հիպերհարթությամբ 1 բազմությունից: 3. Դիցուք ու ուցիկ բազմության տրվա կետով կարելի է տանել երկու հենման հիպերհարթություն: Ապացուցել, որ այդ կետով անցնում են անթիվ բազմության հենման հիպերհարթություններ:

4. Դիցուք 11 , 12 ⊂ մություններ են, որ

Rn

ոոt12 6- ∅

այնպիսի ու ուցիկ բազ-

11 ∩ ոոt12 - ∅ :

Ապացուցել, որ 11 12 բազմություները անջատվում են հիպերհարթությամբ:

3.2

Կարաթեոդորի թեորեմը

Սահմանում 3.2.1: Դիցուք 1 -ը Rn -ի ենթաբազմություն է: Այդ բազմության ow owciց թաղանթ կոչվում է հետ յալ բազմությունը. n

Ըօոv1 ≡ {y ∈ R /y -

k Տ

α4 x4 , x4 ∈ 1,

4-1 k Տ

α4 - 1, α4 ≥ 0, ո ∈ |1 : k|, k - 1, 2, ...} :

4-1

Լեմմա 3.2.1: Դիցուք ոչ զրոյական x ∈ Rn վեկտորը ներկայացվում է Ճ - {x1 , x2 , ... , xm } համախմբի վեկտորների գ ային ոչ բացասական կոմբինացիայով (գ ային կոմբինացիայի գոր ակիցները ոչ բացասական թվեր են): Այդ դեպքում x-ը ներկայացվում է նա այդ համակարգի գ որեն անկախ մի ենթահամակարգի վեկտորների գ ային ոչ բացասական կոմբինացիայի միջոցով: I

Դիցուք

x-

m Տ

α4 x4 , α4 ≥ 0, ո ∈ |1 : ո| :

4-1

Եթե Ճ համախմբի վեկտորները գ որեն անկախ են, ապա պնդումն ապացուցվա է: Դիցուք այժմ Ճ համախմբի վեկտորները գ որեն կախվա են: Այդ դեպքում գոյություն ունեն λ1 , λ2 , ..., λm թվեր, որոնցից գոնե մեկը զրո չէ այնպիսին, որ x-

m Տ

λ4 x4 :

4-1

Կարող ենք ենթադրել, որ այդ գոր ակիցնեից որ է մեկը դրական է: Նշանակենք αs α4 : λi մ0 λ4 λs

α0 ≡ min

Ունենք՝ x-

m Տ 4-1

α4 x − α0

m Տ

λ4 x -

m Տ

4-1

(α4 − α0 λ4 )x4 :

4-1

Ակնհայտ է, որ α s − α 0 λs - 0

α4 − α0 λ4 ≥ 0 ∀ո :

Այստեղից հետ ում է, որ x վեկտորը ներկացվում է Ճ -ի ինչ-որ վեկտորների ոչ բացասական կոմբինացիայով, որոնց քանակը ոքր է ո-ից: Այսպես շարունակելով՝ կհանգենք գ որեն անկախ համակարգի: J

Թեորեմ 3.2.1: Դիցուք x ∈ Rn վեկտորը ներկայացվում է հետ յալ տեսքով. x-

m Տ

λ4 x4 , λ4 ≥ 0, ո ∈ |1 : ո|,

4-1

m Տ

λ4 - 1, ո » ո :

4-1

(3.2.1)

Այդ դեպքում Ճ - {x1 , ..., xm } համախմբի մեջ գոյություն ունի այնպիսի մի {x41 , x4ո , ..., x4Շ+1 } ենթահամախումբ ոչ բացասական α41 ≥ 0, α4ո ≥ 0, ... α4Շ+1 ≥ 0 թվեր, որ n+1 j-1

α4j - 1

x-

n+1 Տ

α 4 j x4 j :

j-1

Դիտարկենք ունենք I

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

m Տ

վեկտորը: Ըստ (3.2.1)-ի՝

λ4 (x4 , 1) :

4-1

Համաձայն լեմմա 3.2.1-ի՝ գոյություն ունեն վեկտորների գ որեն անկախ այնպիսի {x4 , x4 , ..., x4 } համախումբ ոչ բացասական թվեր α4 , α2 , , ..., α4 , որ

ո

(x, 1) -

»

»

k Տ

α4j (x4j , 1) :

j-1

Այսինքն՝ x-

k Տ

4j

α4j x , α41 ≥ 0, α4ո ≥ 0, ..., α4» ≥ 0,

j-1

k Տ

α4j - 1 :

j-1

(3.2.2)

Բայց, քանի որ ո Է 1 չա անի տարա ությունում գ որեն անկախ համակարգի վեկտորների քանակը ոԷ1-ից ավել չէ , ապա k ≤ ոԷ1 : Եթե k - ոԷ1, ապա թեորեմն ապացուցվա

է: Եթե k Հ ո Է 1, ապա ավելացնելով զրոյական անդամներ (3.2.2) գումարի անդամների քանակը դարձնում ենք ո Է 1 : J

Հետ անք 3.2.1 (Կարաթեոդորի թեորեմ): Դիցուք 1 -ը R -ի ենթաբազմություն է: Այդ դեպքում՝ n

Ըօոv1 - {y ∈ Rn /y -

n+1 Տ

α4 x4 , x4 ∈ 1,

4-1 n+1 Տ

α4 - 1, α4 ≥ 0, ո ∈ |1 : ո Է 1|} :

4-1

ԽՆԴԻՐՆԵՐ

1. Գտնել հետ յալ բազմությունների ու ուցիկ թաղանթները: ա) 1 - {(x1 , x2 ) ∈ R2 /x1 x2 - 1}: բ) 1 - {(x1 , x2 ) ∈ R2 /x2 - 6xք(−x1 )}: գ) 1 - {(x1 , x2 ) ∈ R2 /x1 , x2 ∈ |0, 1|} ∪ {(x1 , x2 ) ∈ ∈ R2 /x2 - x1 } :

2. Ապացուցել, որ բաց բազմության ու ուցիկ թաղանթը բաց բազմություն է: 3. Ապացուցել, որ կոմպակտ բազմության ու ուցիկ թաղանթը կոմպակտ Է: 4. Անջատվում է արդյոք (1, −1, 0) կետը 1 - Ըօոv{(−1, 1, 2), (2, −1, −3), (−2, 3, −1), (−5, −1, 3)}

բազմությունից հիպերհարթությամբ:

5. Ապացուցել, որ Ըօոv1 -ը մինիմալ այն ու ուցիկ բազմությունն է, որը պարունակում է 1 -ը: 6. Ապացուցել հետ յալ պնդումը: Որպեսզի 1 ⊆ Rn բազմությունը լինի ու ուցիկ, անհրաժեշտ է բավարար, որ Ըօոv1 - 1 :

7. Դիցուք 1 - Ըօոv{x1 , x2 , ..., xm }, իսկ f (x)-ը ու ուցիկ ֆունկցիա է, որոշվա 1 բազմության վրա: Ապացուցել, որ max f (x) - max f (x4 ) : x∈M

4∈11:m|

Ցուցում: Օգտվել Յենսենի անհավասարությունից:

8. Գտնել f (x1 , x2 ) - 25(x1 − 2)2 Է (x2 − 2)2 ֆունկցիայի մե ագույն արժեքը հետ յալ բազմության վրա.   x1 Է x2 ≥ 2, x1 − x2 ≥ −2, x1 Է x2 ≤ 6, x1 − 3x2 ≤ 2,  x1 , x 2 ≥ 0

3.3

:

Հելլիի թեորեմը

Թեորեմ 3.3.1 ( ադոն): Դիցուք տրվա է վեկտորների Ճ - {x1 , x2 , ..., xk } (k ≥ ո Է 2) համախումբը Rn -ում: Այդ դեպքում այդ բազմությունը կարելի է տրոհել երկու ենթաբազմությունների՝ Y Z այնպիսին, որ ԸօոvY ∩ ԸօոvZ 6- ∅ :

I

Դիտարկենք վեկտորների {x2 − x1 , x3 − x1 , ..., xk − x1 }

համախումբը: Քանի որ այս բազմության վեկտորների քանակը մե կամ հավասար է ո Է 1, ապա նրանք գ որեն կախվա են: Հետ աբար, գոյություն ունեն α2 , α3 , ..., αk թվեր, որոնցից գոնե մեկը հավասար չէ զրոյի այնպիսին, որ k Տ

(x4 − x1 ) - 0 ⇒

4-2

k Տ

α4 x4 - 0,

որտեղ α1 - −

4-1

k Տ

α4 :

4-2

Այսպիսով, գոյություն ունեն այնպիսի α1 , ..., αk գոր ակիցներ, որոցից գոնե մեկը հավասար չէ զրոյի այնպիսին, որ k Տ

α4 x - 0,

k Տ

4-1

α4 - 0 :

(3.3.1)

4-1

Այն α4 գոր ակիցները, որոնք հավասար են զրոյի դեն գցենք ընդհանրությունը չխախտելով ենթադրենք, որ α1 » 0, ..., αk0 » 0, αk0 +1 Հ 0, ..., αk Հ 0 :

Նշանակենք ν-

k Տ

k Տ

α4 - −

α4 :

4-k0 +1

4-1

(3.3.1)-ից կստանանք

k Տ α4 4-1

ν

x -

k Տ 4-k0 +1

−

α4 4 x : ν

(3.3.2)

Նշանակելով

Y - {x1 , ..., xk },

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

(3.3.2)-ից կստանանք

x≡

k Տ α4 4-1

ν

x -

k Տ

−

4-k0 +1

α4 4 x ∈ ԸօոvՃ ∩ ԸօոvY : ν

J

Թեորեմ 3.3.2 (Ճելլի): Եթե {Aα }-ն Rn տարա ության կոմպակտ ու ուցիկ ենթաբազմությունների այնպիսի ընտանիք Է, որ նրա ցանկացա ո Է 1 քանակով բազմությունների հատումը դատարկ չէ, ապա \

Aα 6- ∅ :

α

Քանի, որ Aα բազմությունները կոմպակտ են, ապա բավական է ցույց տալ, որ այդ ընտանիքի ցանկացա վերջավոր քանակով բազմությունների հատումը դատարկ չէ: Ապացույցը կատարենք ինդուկցիայով՝ ըստ բազմությունների քանակի: Դիցուք A1 , A2 , ..., Ak (k » ոԷ1) բազմություններ են ընտանիքից այդ բազմություններից ցանկացա k − 1-ի հատումը դատարկ չէ: Ապացուցենք, որ I

k \

A4 6- ∅ :

4-1

Նշանակենք D4 - A1 ∩ A2 ∩ ... ∩ A4−1 ∩ A4+1 ... ∩ Ak , ո ∈ |1 : k| : (3.3.3)

Ըստ ենթադրության՝ D4 , ո ∈ |1 : k| բազմությունները դատարկ չեն: Ընտրենք կամայական x4 ∈ D4 էլեմենտներ ձ ավորենք Ճ - {x1 , x2 , ..., xk } համախումբը: Ըստ ադոնի թեորեմի՝ այդ համախումբը կարելի է տրոհել S T այնպիսի երկու մասերի, որ Ճ - Y Z, Y Z - ∅ ԸօոvY

\

ԸօոvZ 6- ∅ :

Ենթադրենք

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

Ցույց տանք, որ եթե x ∈ ԸօոvY

ապա x∈

k \

ԸօոvZ,

A4 :

4-1

Ունենք

x-

\

k Տ

k Տ

λ4 x ,

4-1

λ4 - 1,

λ4 ≥ 0, ո ∈ |1 : k 0 | :

4-1

Այստեղից, քանի որ

x ∈

k \

Aj , ∀ո ≤ k 0

j-k0 +1

Aj , j ∈ |1 : k|

բազմությունները ու ուցիկ են, ապա x∈

k \ j-k0 +1

Aj :

Մյուս կողմից, քանի որ x-

k Տ

λ j xj ,

j-k0 +1

ապա

x∈

k \

Aj :

j-1

Այսպիսով, x∈

k \

Aj :

j-1

J

ԽՆԴԻՐՆԵՐ

1. Դիցուք R2 հարթության ո հատ կետեր բավարարում են հետ յալ պայմանին. նրանցից ցանկացա երեքը գտնվում են միավոր շա ավղով ինչ-որ շրջանի ներսում: Ապացուցել, որ բոլոր կետերն են գտնվում միավոր շա ավղով մի նույն շրջանի ներսում: Ցուցում: Դիցուք a1 , a2 , ..., an -ը տրվա կետերն են: Դիտարկել A4 - {x ∈ R2 /kx − a4 k ≤ 1}, ո ∈ |1 : ո|

շրջանների բազմությունը այդ ընտանիքի նկատմամբ կիրա ել Հելլիի թեորեմը:

2. Դիցուք 1 ⊂ Rn ու ուցիկ կոմպակտ բազմությունը

ա կվա է բաց կիսատարա ությունների ընտանիքով: Ապացուցել, որ այդ ընտանիքից կարելի է ընտրել ո Է 1 հատ կիսատարա ություններ, որոնք նույնպես ա կում են 1 -ը: 3. Դիցուք 1 ⊂ R2 -ը d տրամագ ով կոմպակտ √ բազմություն է: Ապացուցել, որ գոյություն ունի d/ 3 շա ավղով շրջան, որը պարունակում է 1 -ը: Ցուցում: Նախ ցույց տալ, որ այդ բազմության √ ցանկացա երեք կետերի համար գոյություն ունի d/ 3 շա ավղով շրջան, որը պարունակում է այդ կետերը: Այնուհետ այդ շրջանների նկատմամբ կիրա ել Հելլիի թեորեմը: Նշենք, որ Հելլիի թեորեմի բազմաթիվ կիրա ություններին կարելի է անոթանալ |9|-ում:

3.4

Oւ ուցիկ ֆունկցիայի սուբդիֆերենցիալը

Սահմանում 3.4.1: Դիցուք f -ը ու ուցիկ ֆունկցիա է՝ որոշվա Rn -ի վրա: v վեկտորը կոչվում է սուբգրադիենտ x0 կետում, եթե տեղի ունի f (x) − f (x0 ) ≥ (v, x − x0 ) ∀x ∈ Rn

(3.4.1)

անհավասարությունը: f -ի սուբգրադիենտների բազմությունը x0 կետում կոչվում է sowbdifելենciալ նշանակվում է ∂f (x0 ) սիմվոլով:

Թեորեմ 3.4.1: ∂f (x0 ) բազմությունը ոչ դատարկ ու ուցիկ կոմպակտ է:

I Նախ ցույց տանք ∂f (x0 )-ի ուուցիկությունը: Եթե v1 ∈ ∂f (x0 ), v2 ∈ ∂f (x0 ), ապա

f (x)−f (x0 ) ≥ (αv 1 Է(1−α)v 2 , x−x0 ) ∀x ∈ Rn , ∀α ∈ |0, 1|,

որտեղից հետ ում է ∂f (x0 )-ի ու ուցիկությունը: ∂f (x0 ) բազմության ակությունը ակնհայտ Է: Ապացուցենք, որ այն դատարկ չէ: Դիտարկենք f ֆունկցիայի վերգրաֆիկը՝ eքո(f ) - {(β, x) ∈ Rn+1 /β ≥ f (x)} :

Քանի որ այս բազմությունը ակ է ու ուցիկ, ապա նրա եզրային (f (x ), x ) կետից կարելի է տանել հենման հիպերհարթություն: Դա նշանակում է, որ գոյություն ունի այնպիսի ոչ զրոյական (Ը, v) ∈ Rn+1 վեկտոր, որ Ըβ Է (v, x) ≥ Ըf (x0 ) Է (v, x0 ) ∀(β, x) ∈ eքո(f ) :

(3.4.2)

Եթե Ը - 0 , ապա (3.4.2)-ից ստանում ենք (v, x − x0 ) ≥ 0 ∀x ∈ Rn :

անհավասարությունը: Այստեղից հետ ում է, որ v - 0, որը հակասություն է, քանի որ (Ը, v) 6- 0 : Ցույց տանք, որ Ը » 0: (3.4.2) անհավասարությունը x - x0 դեպքում ունի Ը(β − f (x0 )) ≥ 0

տեսքը, որտեղից անմիջականորեն հետ ում է, որ Ը » 0 : Այժմ (3.4.2) անհավասարության երկու մասերը բաժանենք Ը » 0 թվի վրա այնուհետ տեղադրելով β - f (x) կստանանք v f (x) − f (x0 ) ≥ (− , x − x0 ), Ը

որտեղից հետ ում է, որ v − ∈ ∂f (x0 ) : Ը

Ապացուցենք, որ ∂f (x0 ) բազմությունը սահմանա ակ է: Ենթադրենք հակա ակը: Այդ դեպքում գոյություն կունենա այնպիսի {vk } (vk ∈ ∂f (x0 )) հաջորդականություն, որ kv k k → ∞ : (3.4.1) անհավասարությունում տեղադրելով x - x0 Է v k /kv k k, կստանանք f (x) − f (x0 ) ≥ kv k k :

(3.4.3)

Քանի որ f -ը անընդհատ է, ապա (3.4.3) անհավասարության ձախ մասը սահմանա ակ է, իսկ աջ մասը ձգտում է անվերջության, երբ k → ∞, ինչը հակասություն է: J

Ֆունկցիայի մինիմիզացիայի ալգորիթմների մշակման համար կար որ է նկարագրել հաշվել ֆունկցիայի նվազման ուղղությունները յուրաքանչյուր կետում: Դիֆերենցելիության դեպքում այդ հարցը մեխանիկորեն լու վում է՝ նվազման ուղղությունը հակագրադիենտի ուղղությունն է: Սակայն երբ ֆունկցիան դիֆերենցելի չէ այդ խնդիրը բարդ է: Բայց ու ուցիկ որոշ դասի ֆունկցիաների համար սուբգրադիենտի գնությամբ հնարավոր է նկարագրել ֆունկցիաների նվազման ուղղությունները կա ուցել մինիմիզացիայի ալգորիթմներ: Ստոր բերվա պնդումները նկարագրում են այդ ֆունկցիաները նրանց նվազման ուղղությունները: Ճիշտ են հետ յալ պնդումները (տենս, րինակ՝ |4, 7|):

Թեորեմ 3.4.2: Դիցուք f1 (x), f2 (x), ..., fk (x) դիֆերենցելի ու ուցիկ ֆունկցիաներ են: Nշանակենք f (x) ≡ max f4 (x) : 4∈11:k|

Այդ դեպքում ∂f (x) - Ըօոv{f40 (x), ո ∈ I(x)},

որտեղ I(x) - {ո ∈ |1 : k|/f4 (x) - f (x)} : Թեորեմ 3.4.3: Դիցուք տեղի ունեն թեoլեմ 3.4.2-i պայմանները 0∈ / ∂f (x) :

Այդ դեպքում հ-−

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

վեկտորը f ֆունկցիայի նվազման ուղղությունն է x կետում:

Վերը նշվա թեորեմները հնարավորություն են տալիս ամենաարագ վայրէջքի մեթոդով որոշ դեպքերում գտնելու ու ուցիկ ոչ դիֆերենցելի ֆունկցիայի մինիմումի կետերը: Մեկնաբանենք դա րինակի միջոցով: Օրինակ: Դիցուք f (x1 , x2 ) ≡ max f4 (x1 , x2 ), 4∈11:3|

որտեղ f1 (x1 , x1 ) - 2x1 Է x2 , f2 (x1 , x2 ) - −x1 − 2x2 , f3 (x1 , x2 ) - −x1 Է x2 − 3 :

Պետք է գտնել f -ի մինիմումի կետը R2 -ի վրա: Որպես սկզբնական մոտավորություն վերցնենք x0 - (0, 0) կետը: Քանի որ f1 (x0 ) - f2 (x0 ) - 0, f3 (x0 ) - −3,

ապա I(x0 ) կունենանք՝

հետ աբար, ըստ թեորեմ 3.4.2-ի,

- {1, 2}

∂f (x0 ) - Ըօոv{f10 (0, 0), f20 (0, 0)} - Ըօոv{(2, 1), (−1, −2)}.

Պարզ է, որ

0∈ / ∂f (x0 ),

ուստի ըստ թեորեմ 3.4.3-ի՝

√ 2 2 , ) հ - (− 2 2 √

վեկտորը կլինի f -ի նվազման ուղղությունը x0 կետում: Այժմ ամենաարագ վայրէջքի մեթոդով գտնենք α0 քայլի երկարությունը կա ուցենք x1 կետը հետ յալ բանաձ ով. x1 - x0 Է α0 հ0 :

Ունենք

√

√ 2 √ ց(α) ≡ f (x Է αհ ) - ոax{− α, − α, α − 3} 2

√ -

Այստեղից

√ ոax{−α, 2α − 3 2} :

α0 - a7ց

min f (x0 Է αհ0 ) α∈(0,+∞)

√

2:

Հետ աբար, x1 - x0 Է α0 հ0 - (−1, 1) : Քանի որ

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

ապա I(x1 ) - {1, 2, 3} : Հետ աբար, ∂f (x1 ) - Ըօոv{f10 (x1 ), f20 (x1 ), f30 (x1 )} - Ըօոv{(2, 1) (−1, −2) (−1, −1)} :

Հեշտ է նկատել, որ 0 ∈ ∂f (x1 ): Այստեղից հետ ում է, որ x1 վեկտորը f ու ուցիկ ֆունկցիայի մինիմումի կետ է: Ինչպես եր ում է թեորեմ 3.4.3-ից ու ուցիկ ֆունկցիայի նվազման ուղղությունները գտնելու համար կար որ խնդիր է որոշել 0 կետի պրոյեկցիան ու ուցիկ կոմպակտի վրա: Նկարագրենք մի իտերացիոն ալգորիթմ, որի միջոցով ցանկացա ճշտությամբ կարելի է գտնել 0 կետի պրոյեկցիան ու ուցիկ բազմանիստի վրա: Դիցուք տրվա է ո չա անի վեկտորների Ճ - {x1 , x2 , ..., xm } համախումբը: Պետք է գտնել 0 կետի պրոյեկցիան 1 - ԸօոvՃ բազմության վրա, այսինքն՝ ΠM (0)-ն: Կա ուցում ենք {vk } հաջորդականությունը հետ յալ կերպ. »

Որպես v0 սկզբնական մոտավորություն վերցնում ենք այն վեկտորը Ճ համախմբից, որը բավարարում է հետ յալ պայմանին. (v 0 , v 0 ) - min (x4 , x4 ) : 4∈11:m|

»

Ենթադրենք արդեն ունենք vk ∈ 1 վեկտորը: Նկարագրենք vk+1 կա ուցման ալգորիթմը: Ընտրում

ենք Ճ համախմբից այն xk վեկտորը, որը բավարարում է (xk , v k ) - min (v k , x4 ) : 4∈11:m|

հավասարությանը: Այնուհետ հաշվում ենք δ(v k ) ≡ (v k − xk , v k ), tk -

δ(v k ) kxk − v k k

մե ությունները: վեկտորը կա ուցում ենք հետ յալ եկուրենտ ա նչությամբ.

» v k+1

v k+1 - v k Է tk (xk − v k ) :

Ճշմարիտ է հետ յալ պնդումը, որը բերում ենք ա անց ապացույցի (տենս, րինակ՝ |4|): Թեորեմ 3.4.4: Դիցուք {v k } հաջորդականությունը կա ուցվել է վերը նշվա ալգորիթմով: Այդ դեպքում v k → ΠM (0), երբ k → ∞ : Ա առադրանք 4: Կատարել վերը նշվա ալգորիթմի

րագրային իրականացումը Շ ++ լեզվով: Գտնել ΠM (0) վեկտորը, եթե ˙ 1.5, 1), (2, 3, 4)} : 1 - Ըօոv{(1, 1, 1), (2, 2, 2), (1,

ԽՆԴԻՐՆԵՐ

1. Դիցուք f ու ուցիկ ֆունկցիան դիֆերենցելի է x0 կետում: Ապացուցել, որ ∂f (x0 ) - {f 0 (x0 )} :

2. Դիցուք f (x) - kxk : Ցույց տալ, որ ∂f (0) - B1 (0) :

3. Հաշվել հետ յալ ու ուցիկ ֆունկցիաների սուբդիֆերենցիալները: ա)

f (x) - |x − 1| Է |x Է 1|,

բ)

f (x) - ոax{4x Է 1, x − 2},

գ)

f (x1 , x2 ) - |x1 − 1/2|x2 | Է x2 |,

դ)

f (x1 , x2 ) - |x1 Է x2 |,

ե)

f (x1 , x2 ) - ||x1 | Է x2 − 1| :

4. Ապացուցել հետ յալ պնդումը: Որպեսզի x0 կետը լինի f ու ուցիկ ֆունկցիայի մինիմումի կետ Rn -ի վրա, անհրաժեշտ է բավարար, որ 0 ∈ ∂f (x0 ) :

5.

պարամետրերի բոլոր արժեքների դեպքում լու ել հետ յալ խնդիրները. Ը

ա) բ) 6.

kxk − (Ը, x) → ոոո, x ≥ 0, x ∈ Rn , kxk2

Է kx − Ըk → ոոո, x ∈ Rn ,

f (x1 , x2 ) - x21 Է x1 x2 Է x22 Է 3|x1 Է x2 − 2| → ոոո :

Լու ում: Որպեսզի (x1 , x2 ) կետը լինի f -ի մինիմումի կետ,

անհրաժեշտ է

Մ ∈ ∂ց(x1 , x2 )

բավարար, որ գոյություն ունենա այնպիսի վեկտոր, որ

0 ∈ ∂f (x1 , x2 ) ⇔ (2x1 Է x2 , 2x2 Է x1 ) Է 3Մ - 0,

(3.4.3)

որտեղ ց(x1 , x2 ) ≡ |x1 Է x2 − 2|: Դժվար չէ տեսնել, որ   (1, 1), (−1, −1), ∂ց(x1 , x2 )  Ըօոv{(1, 1), (−1, −1)},

եթե x1 Է x2 » 2 եթե x1 Է x2 Հ 2 եթե x1 Է x2 - 2 :

Եթե x1 Է x2 » 2, ապա (3.4.3) պայմանից կստանանք 

2x1 Է x2 Է 3 - 0, 2x2 Է x1 Է 3 - 0,

⇒ x1 Է x2 - −2,

այսինքն համակարգը համատեղելի չէ: Եթե x1 Է x2 Հ 2, ապա համակարգը նույնպես լու ում չունի: Եթե x1 Է x2 - 2, ապա   2x1 Է x2 Է 3α - 0, 2x2 Է x1 Է 3α - 0,  α ∈ |−1, 1|,

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

այսինքն (1, 1) կետը խնդրի լու ումն է: 7. x21 Է x22 Է 2ոax(x1 , x2 ) → ոոո :

8.

x21 Է x22 Է 2

9.

x21 Է x22 Է 4|x1 Է x2 − 1| → ոոո :

p

(x1 − 1)2 Է (x2 − 2)2 → ոոո :

10. Ամենաարագ վայրէջքի մեթոդով գտնել f (x1 , x2 ) ≡ max f4 (x1 , x2 ) 4∈11:3|

ֆունկցիայի մինիմումի կետը: Կատարել իտերացիայի երկու քայլ: Այստեղ f1 (x1 , x1 ) - x1 Է x2 , f2 (x1 , x2 ) - −x1 − x2 , f3 (x1 , x2 ) - −x1 Է x2 − 5 :

3.Տ

Կուն-Tակկերի թեորեմը

Դիցուք f4 (x), ո ∈ |0 : ո|, ֆունկցիաները ու ուցիկ են R -ի վրա: Դիտարկենք f0 (x) ֆունկցիայի մինիմիզացիայի խնդիրը 1 ≡ {x ∈ Rn /f4 (x) ≤ 0, ո ∈ |1 : ո|} բազմության վրա. n

f0 (x) → ոոո, x ∈ 1 :

(3.5.1)

Հեշտ է ցույց տալ, որ 1 -ը ու ուցիկ բազմություն է: (3.5.1) խնդիրը կոչվում է ու ուցիկ րագրավորման խնդիր: f0 (x) ֆունկցիայի մինիմումի կետերը 1 բազմության վրա կոչվում են (3.5.1) խնդրի լու ումներ: Կազմենք Լագրանժի ֆունկցիան ՝ L(x, λ) - λ0 f0 (x) Է λ1 f1 (x) Է ... Է λm fm (x),

որտեղ λ - (λ0 , λ1 , ..., λm ) ∈ Rm+1 :

Թեորեմ 3.5.1 (Կուն-Տակկեր: Անհրաժեշտությունը): Դիցուք x∗ կետը հանդիսանում է (3.5.1) խնդրի լու ում: Այդ դեպքում գոյություն ունեն λ0 ≥ 0, λ1 ≥ 0, ..., λm ≥ 0 թվեր, որոնցից գոնե մեկը զրո չէ այնպիսին, որ

1) L(x, λ) ≥ L(x∗ , λ) ∀x ∈ Rn , 2) λ4 f4 (x∗ ) - 0, ո ∈ |1 : ո|:

սահմանա ակելով ընդհանրությունը, կարելի է ենթադրել, որ f0 (x∗ ) - 0 : Հակա ակ դեպքում կդիտարկենք f˜0 (x) - f0 (x) − f0 (x∗ ) ֆունկցիան, որը նույնպես ու ուցիկ է f˜0 (x∗ ) - 0 : Դիտարկենք հետ յալ բազմությունը. I

Շ - {(µ0 , µ1 , ..., µm ) ∈ Rm+1 /∃x ∈ Rn : f0 (x) Հ µ0 , f4 (x) ≤ µ4 , ո ∈ |1 : ո|} :

Այս բազմությունը ու ուցիկ է: Այն անմիջապես հետ ում է սահմանումից: Շ -ն դատարկ չէ: Իսկապես, քանի որ f0 (x∗ ) Հ 1, f4 (x∗ ) ≤ 1, ո ∈ |1 : ո|,

ապա (1, 1, ..., 1) ∈ Շ :

Ակնհայտ է նա , որ 0 ∈/ Շ, քանի որ հակա ակ դեպքում գոյություն կունենար այնպիսի x կետ, որ f0 (x) Հ 0, f4 (x) ≤ 0, ո ∈ |1 : ո|,

ինչը հակասություն է: 0 կետը անջատենք հիպերհարթությամբ Շ ու ուցիկ բազմությունից: Դա նշանակում է, որ գոյություն ունեն

λ4 , ո ∈ |0 : ո|,

որ

m Տ

թվեր, որոնցից գոնե մեկը զրո չէ, այնպիսին,

λ4 µ4 ≥ 0 ∀(µ0 , µ1 , ..., µm ) ∈ Շ :

(3.5.2)

4-0

Ցույց տանք, որ λ4 ≥ 0, ո ∈ |0 : ո| : Ենթադրենք, որ ինչ-որ ո0 ինդեքսի համար տեղի ունի λ4 Հ 0 անհավասարությունը: Ակնհայտ է, որ ցանկացա δ » 0 µ4 » 0 թվի համար µ ≡ (δ, 0, .., µ4 , 0, ..0) ∈ Շ : Տեղադրելով µ վեկտորի կոորդինատները (3.5.2) անհավասարությունում՝ կստանանք

δλ0 Է µ40 λ40 ≥ 0 :

(3.5.3))

Այստեղ անցնելով սահմանի, երբ δ → 0 µ4 → Է∞ կստանանք, որ (3.5.3) անհավասարության ձախ մասը ձգտում է −∞, իսկ աջ մասը զրո է, որը հակասություն է: Այժմ ապացուցենք թեորեմի երկրորդ պնդումը: (3.5.2) անհավասարությունում տեղադրելով

µ0 - δ » 0, µ1 - 0, ..., µ4 - f4 (x∗ ), µ4+1 - 0, .., µm - 0,

թվերը կստանանք՝ δλ0 Է λ4 f4 (x∗ ) ≥ 0 :

Այստեղ անցնելով սահմանի, երբ δ ձգտի զրոյի՝ կստանանք λ4 f4 (x∗ ) ≥ 0 :

Բայց, քանի որ λ4 ≥ 0 է, որ

(2.5.4)

f4 (x∗ ) ≤ 0, ապա (2.5.4)-ից հետ λ4 f4 (x∗ ) - 0 :

ում

(3.5.5)

Այժմ ապացուցենք թեորեմի եզրակացության ա աջին կետը: Իրոք, ցանկացա x ∈ Rn -ի համար (3.5.3) անհավասարությունում տեղադրելով µ0 - δ Է f0 (x), µ1 - f1 (x), ..., µm - fm (x)

կոորդինատներով µ վեկտորը, կստանանք λ0 (δ Է f0 (x)) Է λ1 f1 (x) Է ... Է λm fm (x) ≥ 0 :

Անցնելով սահմանի, երբ δ → 0, կստանանք՝ λ0 f0 (x) Է λ1 f1 (x) Է ... Է λm fm (x) ≥ 0 ∀x ∈ Rn

(3.5.6)

(3.5.5)-(3.5. 6)-ից հետ ում է որ L(x, λ) -

m Տ

λ4 f4 (x) ≥ 0 -

4-0

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

Թեորեմ 3.5.2 (Կուն-Տակկեր: Bավարարությունը): Դիցուք x∗ կետը բավարարում է (3.5.1) խնդրի բոլոր սահմանա ակումներին՝ f4 (x∗ ) ≤ 0, ո ∈ |1 : ո|,

գոյություն ունեն այնպիսի λ0 » 0, λ1 ≥ 0, λ2 ≥ ≥ 0, ..., λm ≥ 0 թվեր, որ տեղի ունեն թեորեմ 3.5.1-ի 1)-2) պայմանները: Այդ դեպքում x∗ վեկտորը (3.5.1) խնդրի լու ում է:

սահմանա ակելով ընդհանրությունը, կարող ենք ենթադրել, որ λ0 - 1 : Այդ դեպքում, հաշվի ա նելով 1) 2) պայմանները, կունենանք՝ I

f0 (x)Է

m Տ

λ4 f4 (x) ≥ f0 (x∗ )Է

4-1

m Տ

λ4 f4 (x∗ ) - f0 (x∗ ) ∀x ∈ Rn :

4-1

(3.5.7)

Եթե x վեկտորը այնպիսին է, որ f4 (x) ≤ 0 ∀ո ∈ |1 : ո|, ապա (3.5.7) անհավասարությունից կստանանք f0 (x) ≥ f0 (x∗ ) : J

պայմանը (3.5.1) խնդրում հետ յալն է. գոյություն ունի այնպիսի x̄ վեկտոր, որ եգուլյարության

պայմանը: Այս

f4 (x̄) Հ 0, ո ∈ |1 : ո| :

Ցույց տանք, որ այս պայմանի դեպքում λ0 գոր ակիցը կարելի է վերցնել հավասար մեկի: Իրոք, եթե λ0 - 0, ապա թեորեմ 3.5.1-ի 1) 2) եզրակացություններից հետ ում է, որ m Տ

λ4 f4 (x̄) ≥ 0,

4-1

որը հակասություն է, քանի որ m Տ

λ4 f4 (x̄) Հ 0 :

4-1

Նշենք, որ եթե f4 (x), ո ∈ |1 : ո|, ֆունկցիաները անընդհատ են, ապա եգուլյարության պայմանը ու ուցիկ րագրավորման խնդրում նշանակում է, որ 1 բազմությունը ունի ներքին կետ: J

Հետ անք 3.5.1: Դիցուք 1 - {x ∈ Rn /aj ≤ xj ≤ Եj ,

j ∈ |1 : ո|},

որտեղ −∞ ≤ aj Հ Եj ≤ Է∞, j ∈ |1 : ո| : Որպեսզի x∗ ∈ 1 կետը լինի ու ուցիկ դիֆերենցելի f (x) ֆունկցիայի մինիմումի կետ 1 բազմության վրա, անհրաժեշտ է բավարար, որ կամայական j ∈ |1 : ո| համար   - 0, եթե aj Հ x∗j Հ Եj , ∗ fxj (x ) ≥ 0, եթե x∗j - aj 6- −∞,  ≤ 0, եթե x∗j - Եj 6- Է∞ :

Քանի որ Կուն-Տակկերի թեորեմը մինիմումի անհրաժեշտ բավարար պայման է, ապա որոշ դեպքերում այն թույլ է տալիս բացահայտ տեսքով գտնել անհավասարության տիպի սահմանա ակումներով մաթեմատիկական րագրավորման խնդիրների լու ումները: Օրինակ 1: Լու ել հետ յալ խնդիրը. f (x1 , x2 ) - 2x21 Է x1 x2 Է x22 → ոոո, −1 ≤ x1 ≤ 1, x2 ≥ 2 :

Քանի որ f -ը ուժեղ ու ուցիկ ֆուկցիա է, իսկ սահմանա ակումներով տրվող բազմությունը ակ է ու ուցիկ, ապա այս խնդիրն ունի միակ լու ում այն բավարարում է հետ յալ երկու պայմաններին.   - 0, եթե − 1 Հ x1 Հ 1, ≥ 0, եթե x1 - −1, fx (x1 , x2 ) - 4x1 Է x2  ≤ 0, եթե x1 - 1:

fx0 ո (x1 , x2 )

 - x1 Է 2x2

- 0, ≥ 0,

եթե x2 » 2, եթե x2 - 2 :

Այժմ այս պայմաններից կարելի կազմել վեց համակարգեր լու ել դրանք: Սակայն դժվար չէ համոզվել, որ 

− 1 Հ x1 Հ 1, x2 - 2

4x1 Է x2 - 0, x1 Է 2x2 ≥ 0,

համակարգը համատեղելի է (−1/2, 2) վեկտորը նրա լու ումն է: Հետ աբար այդ վեկտորը նա մինիմիզացիայի խնդրի միակ լու ումն է : Օրինակ 2: Լու ել հետ յալ խնդիրը. x21 Է (x2 − 2)2 → ոոո, x21 Է x22 − 1 ≤ 0, x1 ≥ 0, x2 ≥ 0 :

Քանի որ թույլատրելի արժեքների բազմությունը ունի ներքին կետ, ապա Լագրանժի ֆունկցիայում λ0 գոր ակիցը կարելի է վերցնել հավասար մեկի: Կիրա ելով Կուն-Տակկերի թեորեմը՝ կստանանք.  0 Lx1 (x, λ) - 2x1 Է 2λ1 x1 − λ2 - 0,      L0xո (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)

Դիտարկենք հետ յալ դեպքերը: 1)

λ1 - 0, λ2 - 0, λ3 - 0: Այդ դեպքում (3.5.8) համակարգից ստանում ենք x1 - 0, x2 - 2, որը չի բավարարում x21 Է x22 − 1 ≤ 0 անհավասարությանը:

2)

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

Այս դեպքում(3.5.8)

համակարգից կստանանք  2  x1 Է x22 − 1 - 0, 2x1 (1 Է λ1 ) - 0,  2(x2 − 2) Է 2λ1 x2 - 0 :

Եթե λ1 - −1, ապա երրորդ հավասարումը տեղի չունի: Եթե λ1 6- −1, ապա կստանանք x1 - 0, x2 - 1, λ1 - 1, λ2 - 0 :

Քանի որ մինիմիզացվող ֆունկցիան ուժեղ ու ուցիկ է, իսկ թույլատրելի վեկտորների բազմությունը ակ է ու ուցիկ, ապա (0, 1) կետը խնդրի միակ լու ումն է:

ԽՆԴԻՐՆԵՐ

1. Կուն-Տակկերի թեորեմի գնությամբ լու ել հետեվյալ խնդիրները. ա) (x1 Է 1)2 Է (x2 − 4)2 Է 1 → ոոո, 2x1 − x2 − 2 ≤ 0, x1 ≥ 0 x2 ≥ 0 :

բ)

(x1 Է 2)2 Է (x2 Է 2)2 → ոոո, x21 Է x22 ≤ 0, x1 ≥ 0, x2 ≥ 0 :

գ) դ)

x21 Է x22 → ոոո, 2x21 Է (x2 − 4)2 ≤ 1 : 4x21 − x1 x2 Է 4x22 → ոոո, 4 ≤ x1 ≤ 8, −1 ≤ x2 ≤ ≤2:

2. Ստուգել, արդյոք (0, 4) վեկտորը հետ յալ խնդրի լու ումն է, թե ոչ. x21 Է (x2 − 2)2 → ոոո, x21 Է 2(x2 − 2)2 ≤ 8, x21 Է 2x22 ≤ 32 :

3. Ստուգել, արդյոք (0, 1) վեկտորը հետ յալ խնդրի լու ումն է, թե ոչ. 6xք(x1 − x2 ) → ոոո, x1 Է x2 ≤ 1, x1 ≥ 0, x2 ≤ 0 :

Գլուխ 4

Լագրանժի անորոշ գոր ակիցների մեթոդը Լագրանժի անորոշ գոր ակիցների մեթոդը պտիմիզացիայի այն հիմնարար սկզբունքներից է, որի միջոցով պայմանական պտիմիզացիայի խնդիրները բերվում են ոչ պայմանական պտիմիզացիայի խընդիրների: Մասնավորապես, այս գլխում դիտարկվում են մաթեմատիկական րագրավորման այնպիսի խնդիրներ, որոնցում սահմանա ակումները տրվում են հավասարություններով անհավասարություններով: Ենթադրվում է, որ նպատակային ֆունկցիան սահմանա ակումները ներկայացնող ֆունկցիաները ողորկ են: Ցույց է տրվում, որ այդպիսի խնդիրների էքստրեմալները գտնվում են Լագրանժի ֆունկցիայի ստացիոնար կետերի բազմության մեջ: Վերջին ժամանակներս, որձ է արվում հիմնավորել Լագրանժի մեթոդը մաթեմատիկական րագ81

րավորման ոչ ողորկ խնդիրների համար: Նման ուսումնասիրություններին կարելի է անոթանալ |7, 11| աշխատանքներում:

4.1

Օպտիմալության ա առին պայմանները

երկրորդ կարգի

Սահմանում 4.1.1: հ ∈ Rn վեկտորը կոչվում է 1 բազմությանը x∗ ∈ 1 կետում oա oղ, եթե գոյություն ունի այնպիսի ϕ : |−1, 1| → Rn , ϕ(α) - օ(α)

արտապատկերում, որ բավականաչա

ոքր α » 0 թվերի համար տեղի ունի հետ յալ պայմանը՝ x∗ Է αհ Է ϕ(α) ∈ 1 :

սիմվոլով նշանակենք 1 բազմությանը x∗ կետում տարվա շոշա ող վեկտորների բազմությունը: KM (x∗ )

Սահմանում 4.1.2: Եթե K -ն կոն է, ապա K ∗ ≡ {y ∈ Rn /(y, x) ≥ 0 ∀x ∈ K}

բազմությունը կոչվում է K -ի համալու կոն: Թեորեմ 4.1.1 (Լյուստերնիկի թեորեմը շոշա ող հարթության մասին): Դիցուք 1 - {x ∈ Rn /f4 (x) - 0, ո ∈ |1 : ո|},

որտեղ f4 , ո ∈ |1 : ո|, ֆունկցիաները անընդհատ դիֆերենցելի են: Դիցուք x∗ ∈ 1 ենթադրենք, որ f40 (x∗ ), ո ∈ |1 : ո|, գրադիենտները գ որեն անկախ են: Այդ դեպքում KM (x∗ ) - H ≡ {հ ∈ Rn / (f40 (x∗ ), հ) - 0, ո ∈ |1 : ո|} :

Այսինքն H ենթատարա ությունը շոշա ող կոն է 1 բազմության համար x∗ կետում: I Ցույց տանք, որ H հարթության կամայական վեկտորը շոշա ող վեկտոր է: Նշանակենք  (x∗ ) (x∗ )... f1x (x∗ ) f1x f1x Շ ո  f2x (x∗ ) f2x (x∗ )... f2x (x∗ )  Շ ո  Ճ-   (x∗ ) fmx (x∗ ) fmx (x∗ )... fmx Շ ո 

Կազմենք հավասարումների հետ յալ համակարգը՝ ց4 (α, 7) - f4 (x∗ Է αհ Է Ճ> 7) - 0, ո ∈ |1 : ո|, (4.1.1)

որտեղ 7-ը ո չա անի վեկտոր է: Ցույց տանք, որ այս համակարգը բավարարում է անբացահայտ ֆունկցիայի վերաբերյալ թեորեմի բոլոր պայմաններին: Իրոք, ց4 (0, 0) - 0, ց4α (0, 0) - (f40 (x∗ ), հ) - 0, ո ∈ |1 : ո| :

Ակնհայտ է նա , որ ֆունկցիոնալ մատրիցը

{ց4r } j (0, 0)

կոորդինատներով կետում հավասար

է B ≡ ՃՃ> մատրիցին, որն ունի հակադարձ: Հետ աբար, գոյություն ունի 7(α) արտապատկերում, որոշվա զրո կետի ինչ-որ շրջակայքում, այնպիսին, որ այն այդ շրջակայքում բավարարում է (4.1.1) համակարգին 7(0) - 0, 70 (0) - −B −1 ցα0 (0, 0) - 0,

որտեղ ցα0 (0, 0) - (ց1α (0, 0), ..., ցmα (0, 0)) :

Հետ աբար՝ lim

α→0

7(α) − 7(0) 7(α) - lim - 70 (0) - 0 : α→0 α α

(4.1.2)

Նշանակելով ϕ(α) - Ճ> 7(α), (4.1.1)-(4.1. 2) պայմաններից կստանանք ϕ(α) - օ(α)

ց4 (x∗ Է αհ Է ϕ(α)) - 0 ∀ո ∈ |1 : ո| :

Իսկ սա նշանակում է, որ հ ∈ KM (x∗ ) : Այսպիսով ապացուցվեց, որ H ⊆ KM (x∗ ) : Այժմ ցույց տանք, որ KM (x∗ ) ⊆ H : Դիցուք հ ∈ ∈ KM (x∗ ): Ըստ շոշա ող վեկտորի սահմանման գոյություն ունի այնպիսի ϕ(α) - օ(α) արտապատկերում, որ բավականաչա

ոքր դրական α թվերի համար f4 (x∗ Է αհ Է ϕ(α)) - 0, ո ∈ |1 : ո| :

Այստեղից, համաձայն դիֆերենցելիության պայմանի, կամայական ո-ի դեպքում կունենանք 0 - f4 (x∗ ԷαհԷϕ(α))−f4 (x∗ ) - α|(f40 (x∗ ), հ)Է

օ(α) |: α

Ուստի (f40 (x∗ ), հ) Է

օ(α) - 0 ⇒ (f40 (x∗ ), հ) - 0 ⇒ հ ∈ H : α

J

Դիտարկենք պայմանական պտիմիզացիայի ընդհանուր խնդիրը. f (x) → ոոո, x ∈ 1 :

(4.1.3)

Թեորեմ 4.1.2 (Մինիմումի ընդհանուր անհրաժեշտ պայմանը): Դիցուք f ֆունկցիան դիֆերենցելի է, իսկ x∗ ∈ 1 կետը (4.1.3) խնդրի լու ում է: Այդ դեպքում ∗ f 0 (x∗ ) ∈ KM (x∗ ) :

I

Ենթադրենք ∗ (x∗ ) : f 0 (x∗ ) ∈ / KM

Այդ դեպքում գոյություն ունի այնպիսի հ ∈ KM (x∗ ) վեկտոր, որ (f 0 (x∗ ), հ) Հ 0: Այստեղից քանի որ f -ը դիֆերենցելի է, ապա բավականաչա

ոքր α » 0 թվերի համար կունենանք f (x∗ Է αհ) - f (x∗ ) Է α|(f 0 (x∗ ), հ) Է

օ(α) | Հ f (x∗ ) : α

Սա հակասություն է, քանի որ x∗ -ն մինիմումի կետ է 1 բազմության վրա: J

f -ի

լոկալ

Թեորեմ 4.1.3 (Ճամալու կոնի կա ուցումը): Դիցուք տեղի ունեն թեoլեմ 4.1.1-i պայմանները: Այդ դեպքում՝ ∗ KM (x∗ )

⊥

n

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

m Տ

λ4 f40 (x∗ ),

4-1

λ4 ∈ R, ո ∈ |1 : ո|} : I Նախ, քանի որ H -ը KM (x∗ ) - H , ապա

ենթատարա ություն է

∗ KM (x∗ ) - H ⊥ :

Այժմ ցույց տանք, որ A ⊆ H⊥ :

Իրոք, դիցուք ∀հ ∈ H, ∀y ∈ A ⇒ y -

m Տ

λ4 f40 (x∗ ) ⇒

4-1

⇒ (y, հ) -

m Տ

λ4 (f40 (x∗ ), հ) - 0 ⇒ y ∈ H ⊥ :

4-1

Այժմ ենթադրենք, որ գոյություն ունի այնպիսի Ե ∈ ∈ H ⊥ վեկտոր, որ Ե ∈ / A : Քանի որ f40 (x∗ ), ո ∈ ∈ |1 : ո| գրադիենտները գ որեն անկախ են, ապա A-ն ո չա անի ենթատարա ություն է, որը ակ ու ուցիկ բազմություն է: Անջատենք այն Ե կետից: Համաձայն խիստ անջատման թեորեմ 3.1.2-ի՝ գոյություն ունեն այնպիսի ք վեկտոր ε » 0 թիվ, որ (ք, a) ≤ (ք, Ե) − ε ∀ a ∈ A :

(4.1.4)

Ցույց տանք, որ (ք, a) - 0 ∀a ∈ A :

Եթե որ է a ∈ A-ի համար (ք, a) » 0, ապա տեղադրելով αa ∈ A (α ≥ 0) վեկտորները (4.1.4) անհավասարության մեջ ձգտեցնելով α-ն անվեջության կստանանք հակասություն, քանի որ անհավասարության ձախ մասը կձգտի Է∞, իսկ աջ մասը վերջավոր թիվ է: Եթե (ք, a) Հ 0, ապա կատարելով նույն դատողությունները, նորից կգանք հակասության: Այսպիսով, (ք, a) - 0 ∀a ∈ A : Այստեղից (f40 (x∗ ), ք) - 0, ո ∈ |1 : ո| ⇒ ք ∈ H ⇒ (ք, Ե) - 0 : (4.1.5)

Բայց (4.1.4) անհավասարությունից հետ ում է, որ (ք, Ե) » ε » 0, ինչը հակասում է (4.1.5)-ին : Այսպիսով, ապացուցվեց, որ ∗ KM (x∗ ) - H ⊥ - A :

J

Այժմ դիտարկենք հավասարության տիպի սահմանա ակումներով պայմանական պտիմիզացիայի հետեվյալ խնդիրը՝ f0 (x) → ext7, f4 (x) - 0, ո ∈ |1 : ո| :

(4.1.6)

Ենթադրվում է, որ f4 , ո ∈ |0 : ո|, ֆունկցիաները անընդհատ դիֆերենցելի են Rn -ի վրա: Պահանջվում է գտնել f0 (x) ֆունկցիայի էքստրեմումի կետերը 1 ≡ {x ∈ Rn / f4 (x) - 0, ո ∈ |1 : ո|}

բազմության վրա: Այդ կետերը կոչվում են (4.1.6) խընդրի լու ումներ: 1 բազմության կետերը կոչվում են (4.1.6) խնդրի թույլատրելի կետեր: Դիցուք λ - (λ0 , ..., λm ) ∈ Rm+1 : Կազմենք Լագրանժի ֆունկցիան՝ L(x, λ) -

m Տ

λ4 f4 (x) :

4-0

Թեորեմ 4.1.4 (Լագրանժի անորոշ գոր ակիցների մեթոդը): Դիցուք x∗ կետը (4.1.6) խնդրի լու ումն է: Այդ դեպքում գոյություն ունեն λ0 , λ1 , λ2 , ..., λm թվեր, որոնցից գոնե մեկը զրոյից տարբեր է այնպիսին , որ m Տ

λ4 f40 (x∗ ) - 0,

4-0

կամ որ նույնն է L0x (x∗ , λ) - 0 ⇔ L0xi (x∗ , λ) - 0, ո ∈ |1 : ո| :

(4.1.7)

λ0 , λ1 , . . . , λm թվերը կոչվում են Լագրանժի բազ-

մապատկիչներ կամ անորոշ գոր ակիցներ:

Ենթադրենք, որ x∗ կետը (4.1.6) խնդրում լոկալ մինիմումի կետ է (լոկալ մաքսիմումի դեպքը քննարկվում է անալոգ ձ ով): Եթե f40 (x∗ ), f20 (x∗ ), .., fm0 (x∗ ) գրադիենտները գ որեն անկախ են, ապա, ըստ մինիմումի ընդհանուր անհրաժեշտ պայմանի թեորեմ 4.1.3-ի, կունենանք I

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

- {y/y -

m Տ

λ4 f40 (x∗ ), λ4 ∈ R, ո ∈ |1 : ո|} :

4-1

Այստեղից անմիջականորեն հետ ում է, որ գոյություն ունեն λ1 , λ2 , ..., λm թվեր, այնպիսին, որ f00 (x∗ )

-

m Տ

λ4 f40 (x∗ ) :

4-1

Այս դեպքում թեորեմի պնդումը ապացուցվա է: Եթե f40 (x∗ ), f20 (x∗ ), .., fm0 (x∗ ) գրադիենտները գ որեն կախվա են, ապա գոյություն կունենան գոր ակիցներ λ4 , ո ∈ |1 : ո|, որոցից գոնե մեկը զրո չէ այնպիսին, որ m Տ

λ4 f40 (x∗ ) - 0 :

4-1

Այստեղից հետ ում է, որ 0f00 (x∗ )

Է

m Տ

λ4 f40 (x∗ ) - 0 :

4-1

J

Այժմ ենթադրենք, որ (4.1.6) խնդրում բոլոր ֆունկցիաները երկու անգամ անընդհատ դիֆերենցելի են: Ճիշտ է հետ յալ պնդումը (տենս, րինակ՝ |4|): Թեորեմ 4.1.5 (Էքստրեմումի երկրորդ կարգի անհրաժեշտ պայմանը): Դիցուք x∗ -ը (4.1.6) խնդրում լոկալ մինիմումի (լոկալ մաքսիմումի) կետ է f10 (x∗ ), f20 (x∗ ), ..., fm (x∗ ) վեկտորները գ որեն անկախ են: Այդ դեպքում գոյություն ունեն

λ0 - 1, λ1 , ..., λm թվեր այնպիսին, որ տեղի ունի

հետ յալ պայմանը.

(L00xx (x∗ , λ)հ, հ) ≥ 0 ((L00xx (x∗ , λ)հ, հ) ≤ 0) ∀հ ∈ H - {հ ∈ Rn /(f40 (x∗ ), հ) - 0, ո ∈ |1 : ո|} :

Թեորեմ 4.1.6 (Երկրորդ կարգի բավարար պայմանը): Դիցուք x∗ -ը (4.1.6) խնդրի թույլատրելի կետ է գոյություն ունի այնպիսի λ ∈ Rm+1 վեկտոր, որ տեղի ունեն հետ յալ պայմանները.

1) λ0 - 1, 2) L0xi (x∗ , λ) - 0, ո ∈ |1 : ո|, 3) կամայական ոչ զրոյական հ ∈ H վեկտորի համար տեղի ունի (L00xx (x∗ , λ)հ, հ) » 0 ((L00xx (x∗ , λ)հ, հ) Հ 0) (4.1.8)

անհավասարությունը:

Այդ դեպքում x∗ -ը (4.1.6) խնդրում լոկալ մինիմումի (լոկալ մաքսիմումի) կետ է: I

Եթե x∗ կետը 1 բազմության ա անձնացվա

կետ է, ապա թեորեմի եզրակացությունը տրիվիալ է: Դիցուք այժմ x∗ -ը 1 բազմության սահմանային կետ է այն խնդրում լոկալ մինիմումի կետ չէ: Այդ դեպքում գոյություն կունենա այնպիսի {xk } հաջորդականություն, որը բավարարում է հետ յալ պայմաններին. xk ∈ 1, xk → x∗ , f0 (xk ) Հ f0 (x∗ ) :

(4.1.9)

xk

-ն ներկայացնենք հետ յալ տեսքով. xk - x∗ Է αk հk ,

որտեղ հk - (xk − x∗ )/αk :

Քանի որ, kհk k - 1, ապա ընդհանրությունը չսահմանա ակելով կարող ենք ենթադրել, որ հk → հ 6- 0 :

Հաշվի ա նելով (4.1.9) պայմանը՝ ունենք 0 - f4 (xk )−f4 (x∗ ) - (f40 (x∗ ), αk հk )Էօ(αk ), ո ∈ |1 : ո| :

Բաժանելով այս ա նչությունները անցնելով սահմանի՝ կստանանք

αk -ի

վրա

(f40 (x∗ ), հ) - 0, ո ∈ |1 : ո| :

Այսինքն՝ հ ∈ H : Քանի որ, ըստ ենթադրության, λ0 - 1, ապա (4.1.9)-ից ստանում ենք m Տ

L(xk , λ) - f0 (xk ) Է

λ4 f4 (xk ) ≤ f0 (xk ) ≤

4-1

≤ f0 (x∗ ) - f0 (x∗ ) Է

m Տ

λ4 f4 (x∗ ) - L(x∗ , λ) : (4.1.10)

4-1

Թեորեմի պայմաններից հետ ում է, որ L(x, λ) Լագրանժի ֆունկցիան երկու անգամ դիֆերենցելի է x∗ կետում: Հետ աբար, ներկայացնելով այդ ֆունկցիան, ըստ Թեյլորի բանաձ ի, x∗ կետում, ստանում ենք L(xk , λ) - L(x∗ , λ) Է (L0x (x∗ , λ), αk հk )Է

Է (L00xx (x∗ , λ)(αk հk ), αk հk ) Է օ(αk2 ) : որ, ըստ ենթադրության, L0x (x∗ , λ) - 0,

Քանի այստեղից է, որ

ապա (4.1.10) անհավասարությունից հետ ում

αk2 00 ∗ (L (x , λ)հk , հk )) Է օ(αk2 ) ≤ 0 : 2 xx

Այս անհավասարության երկու մասերը բաժանելով αk2 թվի վրա անցնելով սահմանի՝ կստանանք (L00xx (x∗ , λ)հ, հ) ≤ 0,

որը հակասում է թեորեմի (4.1.8) պայմանին: J

Պարզագույն դեպքերում Լագրանժի անորոշ գոր ակիցների մեթոդը թույլ է տալիս բացահայտ տեսքով գտնել մաթեմատիկական րագրավորման խնդիրների լու ումները հավասարությունների տիպի սահմանա ակումների դեպքում: Դրա համար պետք է կատարել հետ յալ քայլերը. » »

» »

Կազմել Լագրանժի ֆունկցիան: Գրել էքստրեմումի ա աջին կարգի անհրաժեշտ պայմանը Լագրանժի ֆունկցիայի համար ստանալ հավասարումների համակարգ, որով բնութագրվում է խնդրի ստացիոնար կետերի բազմությունը: Գտնել ստացվա համակարգի լու ումները: Էքստրեմումի երկրորդ կարգի բավարար պայմանների միջոցով այդ լու ումներից անջատել էքստրեմումի կետերը:

Այս ալգորիթմը մեկնաբանենք րինակներով: Օրինակ 1: Լու ել հետ յալ խնդիրը. f0 (x) - x21 Է x22 → ext7, f1 (x) - (x1 − 1)2 Է x22 − 4 - 0 :

Լու ում: Կազմենք Լագրանժի ֆունկցիան L(x, λ) - λ0 f0 (x) Է λ1 f1 (x) - λ0 (x21 Է x22 ) Է λ1 ((x1 − 1)2 Է x22 − 4) :

Ըստ (4.1.7) անհրաժեշտ պայմանի՝ ունենք  0  Lx1 (x, λ0 , λ1 ) - 2λ0 x1 Է 2λ1 (x1 − 1) - 0, L0 (x, λ0 , λ1 ) - 2λ0 x2 Է 2λ1 x2 - 0,  xո f1 (x) - (x1 − 1)2 Է x22 − 4 - 0 : (4.1.11) Եթե, λ0 - 0, ապա (4.1.11) համակարգից ստանում ենք 2λ1 (x1 − 1) - 0, 2λ1 x2 - 0, (x1 − 1)2 Է x22 − 4 - 0 : (4.1.12)

Քանի որ λ0 , λ1 գոր ակիցները միաժամանակ զրո չեն, ապա λ1 6- 0 : Հետ աբար, (4.1.12) համակարգի ա աջին երկու պայմաններից կստանանք x1 - 1, x2 - 0,

որը չի բավարարում երրորդ հավասարմանը: Այսպիսով, λ0 6- 0: Ընդհանրությունը չսահմանա ակելով,

կարող ենք ենթադրել, որ λ0 - 1 : Այդ դեպքում (4.1.11) համակարգը կընդունի հետ յալ տեսքը՝   2x1 Է 2λ1 (x1 − 1) - 0, 2x2 Է 2λ1 x2 - 0,  (x1 − 1)2 Է x2 − 4 - 0 :

(4.1.13)

Դիտարկենք այս համակարգի երկրորդ հավասարումը: Եթե x2 - 0, ապա երրորդից կստանանք x1 - 3, x1 - −1, իսկ ա աջին հավասարումից՝ λ1 - −3/2 : Եթե x2 6- 0, ապա երկրորից կունենանք λ1 - −1 : Այդ դեպքում ա աջին հավասարումը տեղի չունի, այսինքն (4.1.13) համակարգը համատեղելի չէ: Այսպիսով ստանում ենք երկու ստացիոնար կետեր՝ x∗1 - 3, x∗2 - 0, λ1 - − 32 :

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

Ստուգենք երկրորդ կարգի (4.1.8) բավարար պայմանները այդ կետերի համար: Ունենք՝ (L00xx հ, հ) - 2(1 Է λ1 )հ21 Է 2(1 Է λ1 )հ22 , հ ∈ H - {հ - (հ1 , հ2 ) ∈ R2 /2(x∗1 − 1)հ1 Է 2x∗2 հ2 - 0 :

Այստեղից հեշտ է տեսնել, որ տեղի ունի

A(3, 0)

կետի համար

(L00xx հ, հ) Հ 0 ∀հ ∈ H, հ 6- 0,

անհավասարությունը: Ուստի, A-ն լոկալ մաքսիմումի կետ է: Նման ձ ով համոզվում ենք, որ B(−1, 0)-ն լոկալ մինիմումի կետ է: Մյուս կողմից, քանի որ f0

ֆունկցիան հասնում է իր մե ագույն ու ոքրագույն արժեքներին, ապա B կետը գլոբալ մինիմումի կետ է, իսկ A-ն գլոբալ մաքսիմումի կետ է: Օրինակ 2: Լու ել հետ յալ խնդիրը. f0 (x) - x21 Է x22 Է x23 → ոոո, f1 (x) - x21 Է x22 − x3 - 0, f2 (x) - x1 Է x2 Է x3 − 4 - 0 :

Ըստ (4.1.7) անհրաժեշտ պայմանի՝ ունենք՝  0 Lx1 (x, λ) - 2λ0 x1 Է 2λ1 x1 Է λ2 - 0,      L0xո (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 :

Եթե, λ0 - 0, ապա կստանանք հավասարումների հետ յալ համակարգը.  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)

Եթե λ1 - 0, ապա (4.1.14) համակարգի երրորդ հավասարումից հետ ում է, որ λ2 - 0, որը հնարավոր չէ, որովհետ բոլոր գոր ակիցները միաժամանակ զրո չեն: Եթե λ1 6- 0, ապա (4.1.14) համակարգի ա աջին երեք հավասարումներից ստանում ենք x1 - x2 - − :

Տեղադրելով այս արժեքները համակարգի վերջին երկու հավասարումների մեջ՝ ստանում ենք հակասություն: Այսպիսով, λ0 6- 0: Ընդունենք λ0 - 1: Այդ դեպքում համակարգը կընդունի հետ յալ տեսքը.  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) համակարգը ունի հետ յալ երկու լու ումները. : 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

Ստուգենք երկրորդ կարգի (4.1.8) բավարար պայմանները A(1, 1, 2) B(−2, −2, 8) կետերի համար: Ունենք (L00xx հ, հ) - 2(1 Է λ1 )հ21 Է 2(1 Է λ1 )հ22 Է 2հ2 հ3 , հ ∈ H - {հ ∈ R3 /2x∗1 հ1 Է 2x∗2 հ2 − հ3 - 0, հ1 Է հ2 Է հ3 - 0} :

Այստեղից A(1, 1, 2) կետի համար կստանանք հ1 - −հ2 , հ3 - 0 ⇒ (L00xx հ, հ) -

10 2 հ » 0 ∀հ 6- 0 : 3 2

Այսինքն՝ A-ն լոկալ մինիմումի կետ է: Նույն ձ ով ստանում ենք, որ B(−2, −2, 8)-ն լոկալ մաքսիմումի կետ է:

ԽՆԴԻՐՆԵՐ

1. Լու ել հետ յալ խնդիրը. x21 Է x22 → ոոո, x21 Է x22 − 8 - 0 :

2. Լու ել հետ յալ խնդիրը. x21 Է x22 → ոոո, x21 Է 2x22 − 8 - 0 :

3. Ստուգել, արդյոք լու ումն է, թե ոչ:

(0, 2)

կետը հետ յալ խնդրի

x21 Է x22 → ոոո, x2 Է x21 − 2 - 0 :

4. Ստուգել, արդյոք լու ումն է, թե ոչ:

(−2, 2)

կետը հետ յալ խնդրի

x1 x2 → ոոո, x21 Է x22 − 8 - 0 :

5. Լու ել հետ յալ խնդիրը. 2x21 Է x22 Է 2x23 → ext7, 2x1 Է x2 Է 2x3 - 12, x1 Է 2x2 Է x3 - 10 :

6. Լու ել հետ յալ խնդիրը. x21 − x22 Է x23 → ոax, x1 Է 2x22 − x3 - 4, 2x1 Է 2x2 Է x3 - 14 :

4.2

Լագրանժի անորոշ գոր ակիցների մեթոդը (խա ը սահմանա ակումների դեպքը)

Այժմ դիտարկենք պայմանական պտիմիզացիայի ընդհանուր խնդիրը, որտեղ սահմանա ակումները տրվում են հավասարություններով անհավասարություններով՝ f0 (x) → ext7,

f4 (x) - 0, ո ∈ |1 : k|, f4 (x) ≤ 0, ո ∈ |k Է 1 : ո| : (4.2.1) Այստեղ ենթադրվում է, որ f4 (x), ո ∈ |0 : ո|, ֆունկցիաները անընդհատ դիֆերենցելի են Rn -ի

վրա:

կետը կոչվում է թույլատրելի, եթե այն բավարարում է (4.2.1) խնդրի բոլոր սահմանա ակումներին: x∗ ∈ Rn կետը կոչվում է (4.2.1) խնդրի լու ում, եթե այն f0 (x) ֆունկցիայի էքստրեմումի կետ է x ∈ Rn

1 ≡ {x ∈ Rn / f4 (x) - 0, ո ∈ |1 : k|, f4 (x) ≤ 0, ո ∈ |k Է 1 : ո|}

բազմության վրա: Սահմանում 4.2.1: Դիցուք x̄ թույլատրելի կետ է (4.2.1) խնդրում: f4 (x) ≤ 0 (ո ∈ |k Է 1 : ո|) սահմանա ակումը կոչվում է ակտիվ այդ կետում, եթե f4 (x̄) - 0: Եթե f4 (x̄) Հ 0, ապա այդ սահմանա ակումը կոչվում է պասիվ:

սիմվոլով նշանակենք x̄ կետում ակտիվ սահմանա ակումների ինդեքսների բազմությունը՝ Iա (x̄)

Iա (x̄) - {ո ∈ |k Է 1, ո|/ f4 (x̄) - 0} :

Ճիշտ են հետ յալ պնդումները (տենս, րինակ՝ |4, 6|): Թեորեմ 4.2.1 (Էքստրեմումի ա աջին կարգի անհրաժեշտ պայմանը): Դիցուք x∗ կետը (4.2.1) խնդրում լոկալ մինիմումի (լոկալ մաքսիմումի) կետ է: Այդ դեպքում գոյություն ունեն λ0 , ..., λm թվեր, որոնցից գոնե մեկը զրոյից տարբեր է այնպիսին, որ

ա) L0xi (x∗ ) - 0, ո ∈ |1 : ո|, որտեղ L(x, λ) -

m Տ

λ4 f4 (x),

4-0

բ) λ4 ≥ 0 (λ4 ≤ 0), ո ∈ |k Է 1 : ո|, գ) λ4 f4 (x∗ ) - 0, ո ∈ |k Է 1 : ո| :

գ) պայմանը կոչվում է պասիվ-ակտիվ սահմանա ակումների պայման: Թեորեմ 4.2.2 (Ա աջին կարգի բավարար պայմանը): Դիցուք x∗ վեկտորը բավարարում է հետ յալ պայմաններին.

1) x∗ - ը (4.2.1) խնդրի թույլատրելի կետ է, 2) գոյություն ունի λ - (λ0 , λ1 , ..., λm ) վեկտոր λ0 - 1 պայմանով այնպիսին, որ (x∗ , λ) զույգը բավարարում է թեորեմ 4.2.1-ի ա), բ), գ) պայմաններին, 3) x∗ կետում (4.2.1) խնդրի ակտիվ սահմանա ակումների հավասարությունների քանակների գումարը հավասար է ո-ի:

Այդ դեպքում, եթե λ4 » 0, ո ∈ Iա (x∗ ), ապա x∗ -ը (4.2.1) խնդրում լոկալ մինիմումի կետ է, եթե λ4 Հ 0, ո ∈ Iա (x∗ ), ապա x∗ -ը (4.2.1) խնդրում լոկալ մաքսիմումի կետ է:

Այժմ ձ ակերպենք քայլերի այն հերթականությունը, որոնց միջոցով կարելի է լու ել խա ը սահմանա ակումներով մաթեմատիկական րագրավորման խնդիրները: » »

»

» »

Կազմել Լագրանժի ֆունկցիան: Գրել էքստրեմումի ա աջին կարգի անհրաժեշտ պայմանը Լագրանժի ֆունկցիայի համար ստանալ հավասարումների համակարգ, որով բնութագրվում է խնդրի ստացիոնար կետերի բազմությունը: Գրել պասիվ-ակտիվ սահմանա ակումների պայմանները անհավասարություններին համապատասխանող Լագրանժի գոր ակիցների ոչ բացասական (ոչ դրական) լինելու պայմանները: Լու ել ստացվա համակարգերը՝ հաշվի ա նելով Լագրանժի գոր ակիցների նշանները: Օպտիմալության ա աջին կարգի բավարար պայմանների միջոցով այդ լու ումներից անջատել էքստրեմումի կետերը:

Այս ալգորիթմը մեկնաբանենք րինակի միջոցով: Օրինակ: Լու ել հետ յալ խնդիրը. x1 − x22 → ext7, x1 − x2 − 1 - 0, x21 Է x22 − 5 ≤ 0 :

Կազմենք Լագրանժի ֆունկցիան L(x, λ) - λ0 (x1 −x22 )Էλ1 (x1 −x2 −1)Էλ2 (x21 Էx22 −5) :

Ըստ Էքստրեմումի անհրաժեշտ պայմանի՝ ունենք հավասարումների անհավասարումների հետ յալ համակարգը. (ա) (բ) (ց) (դ) (ե)

L0x1 (x, λ) - λ0 Է λ1 Է 2λ2 x1 - 0, L0xո (x, λ) - −2λ0 x2 − λ1 Է 2λ2 x2 - 0, x1 − x2 − 1 - 0, x21 Է x22 − 5 ≤ 0, λ2 ≥ 0, λ2 (x21 Է x22 − 5) - 0 :

Դիտարկենք երկու դեպք. 1) 2)

λ0 - 0,

λ0 6- 0:

Ա աջին դեպքում համակարգի (ա) սարումներից կստանանք 

λ1 Է 2λ2 x1 - 0, −λ1 Է 2λ2 x2 - 0

(բ) հավա(4.2.2)

համակարգը: Եթե λ2 - 0, ապա (4.2.2) համակարգից կստանանք λ1 - 0, այսինքն բոլոր բոլոր գոր ակիցները զրո են, որը հակասություն է: Եթե λ2 6- 0, ապա (գ) (ե) պայմաններից կստանանք 

x21 Է x22 − 5 - 0, x1 − x2 − 1 - 0 :

համակարգը: Այս համակարգը ունի երկու լու ում. 

կամ



x1 - 2, x2 - 1

(4.2.3)

x1 - −1, x2 - −2 :

(4.2.4)

Գումարելով (4.2.2) համակարգի հավասարումները՝ կստանանք 2λ2 (x1 Է x2 ) ⇒ x1 - −x2 ,

որը հակասում է (4.2.3) (4.2.4) համակարգերին: Հետ աբար, ա աջին դեպքը հնարավոր չէ: Դիտարկենք երկրորդ դեպքը. λ0 6- 0: Ընդունելով λ0 - 1՝ (ա)-( բ) պայմաններից կստանանք 

1 Է λ1 Է 2λ2 x1 - 0, −2x2 − λ1 Է 2λ2 x2 - 0 :

Եթե λ2 - 0, ապա (4.2.5) համակարգից հավասարությունից կստանանք

(4.2.5)

(գ)

  1 Է λ1 - 0, −2x2 − λ1 - 0,  x1 − x2 − 1 - 0 :

Լու ելով այս համակարգը՝ ստանում ենք ստացիոնար հետ յալ կետը. A(3/2, 1/2), λ1 - −1, λ2 - 0 :

λ2 6- 0

դեպքում ունենք  2 x Է x22 − 5,    1 x1 − x2 − 1 - 0, 1 Է λ1 Է 2λ2 x1 - 0,    −2x2 − λ1 Է 2x2 - 0 :

համակարգը: Լու ելով այս համակարգը՝ ստանում ենք ս երկու ստացիոնար կետեր. B(2, 1), λ1 - −5/3, λ2 - 1/6, Շ(−1, −2), λ1 - 2/3, λ2 - 5/6 :

Այս երեք կետերի համար ստուգենք էքստրեմումի ա աջին կարգի բավարար պայմանները: B կետի համար ակտիվ է x21 Է x22 − 5 ≤ 0 սահմանա ակումը նրան համապատասխան Լագրանժի գոր ակիցը դրական է: Մյուս կողմից, ակտիվ սահմանա ակումների հավասարությունների քանակների գումարը հավասար է երկուսի, որը անհայտների թիվն է: Նշանակում է B -ն լոկալ մինիմումի կետ է: Նույն ձ ով՝ Շ -ն լոկալ մինիմումի կետ է: Բայց քանի որ խնդրի սահմանա ակումների բազմությունը կոմպակտ է, ապա նպատակային ֆունկցիան ունի գլոբալ մինիմումի մաքսիմումի կետեր: Հաշվելով ստացվա կետերում նպատակային ֆունկցիայի արժեքները՝ պարզում ենք, որ A կետը գլոբալ մաքսիմումի կետ է, Շ -ն գլոբալ մինիմումի կետ է, իսկ B -ն լոկալ մինիմումի կետ է:

ԽՆԴԻՐՆԵՐ

1. Լու ել խա ը սահմանա ակումներով հետ յալ խնդիրը. x21 − x2 → ոոո, x1 Է x2 − 6 - 0, 1 − x1 ≤ 0, x21 Է x22 − 26 ≤ 0 :

2. Լու ել խա ը սահմանա ակումներով հետ յալ խնդիրը. x21 Է x22 Է x23 → ոոո, 2x1 − x2 Է x3 ≤ 5, x1 Է x2 Է x3 - 3 :

3. Գտնել շոշա ող KM (x) կոնը 1 բազմության համար x կետում: ա) 1 - {(x1 , x2 ) ∈ R2 \ոոt(R+2 ) : x21 Է x22 ≤ 1}, x - (0, 1):

բ) գ) դ)

) : x21 Է x22 ≤ 1}, 1 - {(x1 , x2 ) ∈ R2 \ոոt(R+ x - (0, 0):

1 - {(x1 , x2 )/x21 ≤ x32 }, x - (0, 0): 1 - {0, 1, , ..., , ...}, x - 0: ո 1 - {0, 1, , ..., n , ...}, x - 0 :

ե) 4. Ապացուցել հետ յալ պնդումը: Որպեսզի K ⊆ Rn կոնը լինի ու ուցիկ, անհրաժեշտ է բավարար, որ ∀x, y ∈ K ⇒ x Է y ∈ K : 5. Դիցուք K ⊆ Rn ակ ու ուցիկ կոն է: Ապացուցել, որ K ∗∗ - K :

6. Դիցուք K1 , K2 ⊆ Rn -ը ակ ու ուցիկ կոներ են: Ապացուցել, որ ա) (K1 Է K2 )∗ - K1∗ ∩ K2∗ : բ) (K1 ∩ K2 )∗ - K1∗ Է K2∗ : Լու ում: Ունենք (K1 ∩ K2 )∗ - (K1∗∗ ∩ K2∗∗ )∗ - ((K1∗ Է K2∗ )∗ )∗ - (K1∗ Է K2∗ )∗∗ - K1∗ Է K2∗ :

Գլուխ 5

Վարիացիոն hաշիv Վարիացիոն հաշիվը պտիմիզացիայի բաժին է, որտեղ ուսումնասիրվում են ինտեգրալային տիպի ֆունկցիոնալների մինիմիզացիայի խնդիրները որոշ ֆունկցիոնալ տարա ություններում: Այս գլխում դիտարկվում է Ֆx1 I(y) -

L(x, y, y 0 ) dx

x0

տիպի ֆունկցիոնալի մինիմիզացիայի (մաքսիմիզացիայի) խնդիրը Շ 1 |x0 , x1 | ֆունկցիոնալ տարա ության վրա: Ցույց է տրվում, որ այդ ֆունկցիոնալի էքստրեմումները բավարարում են եզրային պայմաններով երկրորդ կարգի մի դիֆերենցիալ հավասարմանը, որը կոչվում է Էյլերի հավասարում: Այդ հավասարումով կապ է ստեղ վում վարիացիոն հաշվի դիֆերենցիալ հավասարումների տեսություն106

ների միջ : Այդ իսկ պատճա ով վարիացիոն հաշվի մեթոդները գտագոր ում են եզրային պայմաններով դիֆերենցիալ հավասարումների լու ումների գոյության ապացույցներում: Այս գլխում վարիացիոն հաշվի պարզագույն խնդիրների էքստրեմալների բնորոշման համար տրվում են որոշ բավարար պայմաններ: Վարիացիոն հաշվի տեսության ավելի խորը ուսումնասիրություններին կարելի է անոթանալ |1-2, 12-13| աշխատանքներում:

Տ.1

Էյլերի հավասարումը

Դիցուք L(x, y, y0 ) որպես երեք ո ոխականի ֆունկցիա երկու անգամ անընդհատ դիֆերենցելի է R3 -ի վրա: Պահանջվում է գտնել այնպիսի y(x) ∈ Շ 1 |x0 , x1 | ֆունկցիա, որը բավարարի y(x0 ) - y0 , y(x1 ) - y1 եզրային պայմաններին Rx հանդիսանա I(y) ≡ L(x, y, y0 ) dx ֆունկցիոնալի x լոկալ մինիմումի (լոկալ մաքսիմումի) կետ Շ 1 |x0 , x1 | տարա ության նորմի իմաստով: Այս խնդիրը ձ ակերպվում է հետ յալ կերպ.

Ֆx1 I(y) ≡

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

(5.1.1)

x0

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

որը կոչվում է ամրացվա եզրերով վարիացիոն խնդիր: Այն վարիացիոն հաշվի պարզագույն խնդիրն է: Այժմ տանք I ֆունկցիոնալի լոկալ մինիմումի (լոկալ

մաքսիմումի) սահմանումը նորմի իմաստով:

Շ 1 |x0 , x1 |

տարա ության

Սահմանում 5.1.1: Դիցուք 1 ≡ {y ∈ Շ 1 |x0 , x1 |/y(x0 ) - y0 , y(x1 ) - y1 } : y ∗ ∈ 1 կոչվում է I ֆունկցիոնալի լոկալ մինիմումի (լոկալ մաքսիմումի) կետ 1 բազմության վրա, եթե գոյություն ունի δ » 0 թիվ այնպիսին, որ բոլոր y ∈ ∈ 1 ֆունկցիաների համար, որոնք բավարարում են ky − y ∗ k1 Հ δ պայմանին, տեղի ունի I(y) ≥ I(y ∗ ) (I(y) ≤ I(y ∗ ) :

անհավասարությունը: y ∗ -ը կոչվում է նա (5.1.1) խնդրի լու ում: Թեորեմ 5.1.1: Եթե y ∗ (x) ֆունկցիան (5.1.1) խնդրի լու ումն է, ապա այն բավարարում է −

d 0 L 0 Է L0y - 0, dx y

(5.1.2)

դիֆերենցիալ հավասարմանը, որը կոչվում է յլելi հաvաsալowմ:

Ենթադրենք, որ y∗ -ը (5.1.1) խնդրում լոկալ մինիմումի կետ է (լոկալ մաքսիմումի դեպքը քըննարկվում է անալոգ ձ ով): Դիցուք հ(·) ∈ Շ01 |x0 , x1 |: Այսինքն I

հ(·) ∈ Շ 1 |x0 , x1 |

հ(x0 ) - 0, հ(x1 ) - 0 :

Դիտարկենք մեկ ո ոխականի հետ յալ ֆունկցիան. Ֆx1 ϕ(α) -

L(x, y ∗ (x) Է αհ(x), (y ∗ (x))0 Է αհ0 (x)) dx :

x0

(5.1.3)

Քանի որ y∗ -ը I ֆունկցիոնալի լոկալ մինիմումի կետ է, ապա բավականաչա

ոքր α թվերի համար տեղի ունի ϕ(α) ≥ ϕ(0)

անհավասարությունը: Այսինքն՝ 0 կետը ϕ ֆունկցիայի լոկալ մինիմումի կետ է: Հետ աբար՝ ϕ0 (0) - 0 :

Այստեղից, ըստ պարամետրից կախվա ինտեգրալի ա անցման կանոնի, կունենանք Ֆx1 ϕ0 (0) - (L0y հ Է L0y0 հ0 ) dx - 0 :

(5.1.4)

x0

Կատարեենք մասերով ինտեգրում, հաշվի ա նելով հ(x0 ) - 0, հ(x1 ) - 0 պայմանները, կստանանք Ֆx1

Ֆx1

L0y0 հ0 dx - L0y0 (հ(x1 ) − հ(x0 )) −

x0

x0

Ֆx1 -−

d 0 L 0 հ dx : dx y

x0

d 0 L 0 հ dx dx y

Այստեղից (5.1.4)-ից կստանանք Ֆx1 d (L0y − L0y0 )հ(x) dx - 0 ∀հ(x) ∈ Շ 1 |x0 , x1 |, dx x0

հ(x0 ) - 0, հ(x1 ) - 0 :

(5.1.5)

Այժմ ցույց տանք, որ (5.1.5) պայմանից հետ ում է Էյլերի հավասարումը: Նշանակենք a(x) ≡ L0y (x, y ∗ , (y ∗ )0 ) −

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

Ցույց տանք, որ a(x) - 0 ∀x ∈ |x0 , x1 | :

Ենթադրենք, որ ինչ-որ ξ ∈ |x0 , x1 | կետում a(ξ) 66- 0: Ընդհանրությունը չխախտելով, ենթադրենք, որ a(ξ) » 0: Քանի որ a(x)-ը անընդհատ ֆունկցիա է, ապա գոյություն կունենա ξ կետի մի շրջակայք՝ (ξ − δ, ξ Է δ) ⊆ |x0 , x1 |, այնպիսին, որ a(x) » 0 ∀x ∈ (ξ − δ, ξ Է δ) :

Դիցուք

ք - ξ − δ, q - ξ Է δ :

Այժմ դիտարկենք հետ յալ հ(x) ֆունկցիան.   0, (x − ք)2 (x − q)2 , հ(x)  0,

եթե x ∈ |x0 , ք| եթե x ∈ |ք, q| եթե x ∈ |q, x1 |

Պարզ է, որ հ(·) ∈ Շ 1 |x0 , x1 | Ունենք

հ(x0 ) - հ(x1 ) - 0 :

Ֆq

Ֆx1 a(x)հ(x)dx x0

a(x)հ(x) dx » 0, p

որը հակասում է (5.1.5)-ին: J

Օրինակ (Էյլերի հավասարման լու ումը հանդիսա-

նում է լոկալ մինիմումի կետ): Ֆ0 I(y) ≡

(y 0 )2 dx → ոոո, y(0) - 0, y(1) - 1 :

Կազմենք Էյլերի հավասարումը d 3(y 0 )2 - 0 ⇒ 3(y 0 )2 - Շ ⇒ y 0 - Ըօոst ⇒ dx ⇒ y(x) - Շ1 x Է Շ2 :

Հաշվի ա նելով խնդրի եզրային պայմանները՝ կստանանք y∗ (x) - x, որը խնդրի միակ էքստրեմալն է: Ցույց տանք, որ այն լոկալ մինիմումի կետ է: Դիցուք հ(·) ∈ Շ01 |0, 1| :

Այդ դեպքում ∗

Ֆ1

I(y Է հ) -

0 3

Ֆ1 dx Է 3

(1 Է հ ) dx 0

Ֆ1

հ0 dxԷ

Ֆ1 Է

0 2

∗

Ֆ1

(հ ) (3 Է հ ) dx - I(y ) Է

(հ0 )2 (3 Է հ0 ) dx :

Այստեղից, ակնհայտ է, որ եթե kհk1 Հ 3, ապա 3 Է հ(x) » 0 ∀x ∈ |0, 1| :

Հետ աբար՝

I(y ∗ Է հ) ≥ I(y ∗ ),

այսինքն՝ y∗ (·)-ը լոկալ մինիմումի կետ է:

ԽՆԴԻՐՆԵՐ

1. Լու ել վարիացիոն հաշվի հետ յալ պարզագույն խնդիրները: ա)

Ֆ1

((y 0 )2 Է y 2 ) dx → ոոո, y(0) - 0, y(1) - 1 :

բ)

Ֆ0

(12xy − (y 0 )2 )dx → ոոո, y(−1) - 1, y(0) - 0 :

−1

գ)

Ֆπ/2 ((y 0 )2 − y 2 ) dx → ոոո, y(0) - 1, y(π/2) - 0 :

դ)

Ֆ1

(y 2 Է (y 0 )2 Է 2y 6xք(x)) dx → ոոո, y(0) -

- 0, y(1) - 1 :

ե)

Ֆ3/2 ((y 0 )2 Է 2y) dx → ոոո, y(0) - 0, y(3/2) - 1 :

զ)

Ֆ1

(4y Տin x − y 2 − (y 0 )2 ) dx → ոax, y(0) - y(1) -

-0:

է)

Ֆπ/2 (6y Տin 2x Է y 2 − (y 0 )2 ) dx → ոax, y(0) 0

- y(π/2) - 0 :

2. Ամենաարագ վայրէռքի խնդիրը: Ուղղաձիգ հարթության մեջ մի նույն ուղղաձիգի վրա չգտնվող Օ(0, 0) B(x1 , y1 ) կետերը միացնել այնպիսի ողորկ կորով (գտնել հավասարումը), որով անրության ուժի ազդեցությամբ շարժվող նյութական կետը վեր ի Օ կետից ա անց սկզբնական արագության կհասնի ներք ի B կետ ամենակարճ ժամանակում: Լու ում: Դիցուք y(x) ողորկ կոր է, որը միացնում է Օ B կետերը: Դիցուք 1 (x, y(x)) կամայական կետ է կորի վրա: Ըստ էներգիայի պահպանման րենքի՝ ունենք ոv 2 /2 - ոցy(x),

որտեղ ո-ը նյութական կետի մասսան է, իսկ v-ն՝ արագությունը 1 կետում, ց-ն՝ ազատ անկման արագացումը: Այստեղից կստանանք v-

p 2ցy(x) :

Մյուս կողմից, ունենք ds vdt

p

1 Է (y 0 )2 dy , dt

որտեղ ds-ը էլեմենտար աղեղի երկարությունն է: Հետ աբար, 7 (y) - √ 2ց

Ֆx1 p 1 Է (y 0 (x))2 p dx, y(x)

որտեղ 7 (y)-ը այն ժամանակամիջոցն է, որի ընթացքում կետը տրվա

կորով A կետից հասնում է B √ կետ: Քանի որ 1/ 2ց » 0 հաստատուն է, ապա 7 (y) ֆունկցիոնալի մինիմիզացիայի խնդրում կարելի է այն հաշվի չա նել: Վերջնականորեն կստանանք էքստրեմումի հետ յալ խնդիրը. Ֆx1 p 1 Է (y 0 (x))2 dx → ոոո, I(y) ≡ y(x)

(5.1.6)

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

Կազմենք Էյլերի հավասարումը: Քանի որ (5.1.6)-ում ենթաինտեգրալ L ֆունկցիոնալը բացահայտ կախվա

չէ x ո ոխականից, ապա Էյլերի հավասարումն ունի հետ յալ տեսքը. L − y 0 L0y0 - Շ (տենս,

րինակ՝ |2|) :

Այստեղից մեր րինակի համար կունենանք L − y 0 L0y0 -

1 Է (y 0 )2 y0 − y0 p -Շ: √ y 1 Է (y 0 )2 y

Պարզեցնելուց հետո կստանանք y(1 Է (y 0 )2 ) -

Նշանակենք y 0 - Ըtցt ⇒ y -

- Շ1 : Շ2

Շ1 - Շ1 sոո2 t ⇒ 1 Է (Ըtցt)

⇒ dy - 2Շ1 sոոtԸօstdt :

Այստեղից կստանանք dx -

dy 2Շ1 sոոtԸօstdt - 2Շ1 sոո2 tdt ⇒ y Ըtցt

⇒ x(t) - Շ1 /2(2t − sոո2t) Է Շ2 :

Քանի որ y(0) - 0, ապա Շ2 - 0: Նշանակելով ք - 2t՝ կստանանք ցիկլոիդների ընտանիք x - Շ1 /2(ք − sոոք), y - Շ1 /2(1 − Ըօsք) :

հաստատունը որոշվում է այն պայմանից, որ ցիկլոիդը պետք է անցնի B կետով: 3. Բոլոր ողորկ կորերի մեջ, որոնք միացնում են հարթության A(2, 1) B(1, 0) կետերը, գտել այն կորը, որով v - x արագությամբ շարժվող նյութական կետը A կետից կհասնի B կետ ամենակարճ ժամանակում: Շ1

Տ.2

Լագրանժի մեթոդը վարիացիոն հաշվի խնդիրներում

Դիտարկենք հետ յալ խնդիրը. Ֆx1 I0 (y) ≡

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

x0

(5.2.1)

Ֆx1 I4 (y) -

f4 (x, y, y 0 ) dx - α4 , ո ∈ |1 : ո|,

(5.2.2)

x0

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

(5.2.3)

Այս խնդիրը կոչվում է վարիացիոն հաշվի իզոպերիմետրիկ խնդիր: Ենթադրվում է, որ f4 , ո ∈ ∈ |0 : ո| ֆունկցիաները, որպես երեք ո ոխականի ֆունկցիաներ, երկու անգամ անընդհատ դիֆերենցելի են R3 -ի վրա, Իսկ α1 , α2 , ..., αm հաստատունները տրվա թվեր են: y ∗1 |x0 , x1 | ֆունկցիան կոչվում է թույլատրելի, եթե այն բավարարում է (5.2. 2)-(5.2.3) պայմաններին: Սահմանում 5.2.1: Կասենք, որ թույլատրելի y ∗ ֆունկցիան (5.2.1)-(5.2.3) խնդրում լոկալ մինիմում է (լոկալ մաքսիմում է), եթե գոյություն ունի δ » 0 թիվ այնպիսին, որ բոլոր թույլատրելի y ֆունկցիաների համար, որոնք բավարարում են ky − y ∗ k1 Հ δ պայմանին, տեղի ունի I0 (y) ≥ I0 (y ∗ ) (I0 (y) ≤ I0 (y ∗ )

անհավասարությունը:

Կազմենք Լագրանժի ֆունկցիան՝ L(x, y, y 0 , λ) ≡ λ0 f0 (x, y, y 0 ) Է λ1 f1 (x, y, y 0 ) Է ...Է Էλm fm (x, y, y 0 ),

որտեղ λ - (λ0 , λ1 , ..., λm ) ∈ Rm+1 :

Թեորեմ 5.2.1: Դիցուք y ∗ (x) ֆունկցիան (5.2.1) խնդրի լու ում է: Այդ դեպքում գոյություն ունեն λ0 , ..., λm թվեր, որոնցից գոնե մեկը զրո չէ այնպիսին, որ y ∗ (x)-ը բավարարում է −

d 0 L 0 Է L0y - 0 dx y

դիֆերենցիալ հավասարմանը y(x0 ) - y0 , y(x1 ) - y1 եզրային պայմաններով: I Դիցուք y ∗ ֆունկցիան (5.2.1)-(5.2.3) խնդրում լոկալ մինիմում է (լոկալ մաքսիմումի դեպքը քննարկվում է անալոգ ձ ով): Նշանակենք δI4 (y ∗ , հ) ≡ lim α↓0

I4 (y ∗ Է αհ) − I4 (y ∗ ) : α

Հեշտ է ցույց տալ, որ Ֆx1 d δI4 (y , հ) - (− f4y0 0 Է f4y0 )հ(x) dx, ո ∈ |0 : ո| : dx ∗

x0

Այստեղից հետ ում է, որ δI4 (y∗ , հ) ֆունկցիոնալը հ-ի նկատմամբ գ ային է: Դիտարկենք հետ յալ գ ային պերատորը. A : Շ01 → Rm+1 ,

Aհ ≡ (δI0 (y ∗ , հ), δI1 (y ∗ , հ), ..., δIm (y ∗ , հ)) : IոA-ով

նշանակենք A պերատորի պատկերը: Հնարավոր է երկու դեպք. 1)

IոA ⊂ Rm+1 ,

2)

IոA - Rm+1 :

Ա աջին դեպքում IոA-ը Rm+1 -ի սե ական ենթատարա ությունն է: Հետ աբար, գոյություն ունի ոչ զրոյական այնպիսի λ - (λ0 , ..., λm+1 ) վեկտոր, որը ուղղահայաց է այդ ենթատարա ությանը, այսինքն՝ (λ, Aհ) - 0 ⇒ λ0 δI0 (y ∗ , հ) Է ... Է λm δIm (y ∗ , հ) - 0 ∀հ ∈ Շ01 :

Այստեղից կստանանք Ֆx1 d (− L0y0 Է L0 y)հ(x) dx - 0 ∀հ ∈ Շ01 : dx

(5.2.2)

x0

Ինչպես պարզագույն խնդրում, այստեղ նույնպես կարելի է ցույց տալ, որ (5.2.2)-ից հետ ում է, որ −

d 0 Ly0 Է L0 y - 0 : dx

Դիտարկենք երկրորդ դեպքը: Դիցուք {e0 , ..., em } համակարգը բազիս է կազմում Rm+1 տարա ությունում: Ընտրենք հ0 , հ1 , ..., հm ֆունկցիաները այնպիսին, որ  1, եթե ո - j: ∗ δIj (y , հ4 ) 0, եթե ո 6- j : Կազմենք հավասարումների հետ յալ համակարգը.  -m  ϕ0 (β0 , ..., βm ) ≡ I0 (y ∗ Է j-0 βj հj ) - I0 (y ∗ ) − ε, 

ϕ4 (β0 , ..., βm ) ≡ I4 (y ∗ Է

-m

j-0

βj հj ) - α4 , ո ∈ |1 : ո| : (5.2.3)

Այս համակարգում ε-ը պարամետր է: Ունենք ∂ϕ4 (0) - δI4 (y ∗ , հj ) : ∂βj

Այստեղից հետ ում է, որ (5.2.3) համակարգը բավարարում Է հակադարձ արտապատկերումների մասին թեորեմի բոլոր պայմաններին (տենս, րինակ՝ |2|, էջ 31): Դա նշանակում է, որ գոյություն ունի վեկտոր ֆունկցիա՝ β(ε) ≡ (β0 (ε), ..., βm (ε)), որ որոշվա են զրո կետի ինչ որ մի շրջակայքում, այնպիսին, որ այդ շրջկայքում նա բավարարում է (5.2.3) համակարգին β(ε) → 0, երբ β → 0 : Հետ աբար, եթե ε պարամետրը դրական է, ապա կստանանք հակասություն, քանի որ y∗ -ը (5.2.1) խնդրի լոկալ մինիմումի կետ է: J

Օրինակ (Էյլերի հավասարման լու ումը իզոպերի-

մետրիկ խնդրում գլոբալ մինիմումի կետ է): Ֆ1 I0 (y) -

(y 0 )2 → ոոո,

Ֆ1 I1 (y) -

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

Լու ում: Կազմենք Լագրանժի ֆունկցիան L - λ0 (y 0 )2 Է λ1 y :

Էյլերի հավասարումը այս ֆունկցիայի համար հետ յալն է. −

d 0 L 0 Է L0y - 0 ⇒ −2λ0 y 00 Է λ1 - 0 : dx y

Եթե λ0 - 0, ապա λ1 - 0 Լագրանժի բոլոր գոր ակիցները հավասար են զրոյի: Այդ դեպքում թույլատրելի էքստրեմալներ չկան: Էյլերի հավասարման մեջ տեղադրենք λ0 - 1: Այդ դեպքում այդ հավասարման ընդհանուր լու ումը կլինի y(x) - Շ1 x2 Է Շ2 x Է Շ3 ֆունկցիան: Շ1 , Շ2 , Շ3 անորոշ գոր ակիցները որոշենք եզրային իզոպերիմետրիայի հետ յալ պայմաններից.  y(0) - 0 ⇒ Շ3 - 0,    y(1) - 1 ⇒ Շ Է Շ - 1, R R    ydx - 0 ⇒ (Շ1 x2 Է Շ2 x) dx - 0 ⇒

⇒ Շ1 /3 Է Շ2 /2 - 0 :

Այստեղից կստանանք միակ թույլատրելի էքստրեմալը՝ y ∗ (x) - 3x2 − 2x :

Ապացուցենք, որ այն գլոբալ մինիմումի կետ է: Դիցուք y(·) թույլատրելի ֆունկցիա է: Այդ դեպքում ∗

y(·) − y (·) - հ(·) ∈

Շ01 |0, 1|

Ֆ1 հ dx - 0 :

Ունենք՝ ∗

Ֆ1

I0 (y(·))−I0 (y (·)) -

∗ 0

Ֆ1

0 2

((y ) Էհ ) dx−

Ֆ1 -

∗ 0

Ֆ1

0 2

Ֆ1

(հ ) dx ≥ 2

2(y ) հdx Է

((y ∗ )0 )2 dx -

(y ∗ )0 հ0 dx :

Կատարելով մասերով ինտեգրում՝ կստանանք Ֆ1

∗ 0 0

Ֆ1

(y ) հ dx 0

∗

(y ) dհ - y

∗

հ|10

Ֆ1 −

(y ∗ )00 հ dx -

Ֆ1 - −6

հ dx - 0 :

Այսպիսով,

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

ցանկացա թույլատրելի y(·) ֆունկցիայի համար: Օրինակ (Դիդոնայի խնդիրը մաքսիմալ մակերեսով սեղանակերպի մասին): Տրվա է f (x) ֆունկցիան |−x0 , x0 | հատվա ի վրա: Գրաֆիկը ներկայացնող կորի երկարությունը հաստատուն է: Գտնել գրաֆիկի տեսքը այնպես, որ կորագի սեղանի մակերեսը լինի մե ագույն: Այս խնդիրը ձ ակերպվում է հետ յալ կերպ. Ֆx0 y(x) dx → ոax, −x0

Ֆx0 p

1 Է (y 0 )2 dx - l, y(−x0 ) - y(x0 ) - 0 :

−x0

Լու ում: Կազմենք Լագրանժի ֆունկցիան L(y, y 0 , λ) - λ0 y Է λ1

p 1 Է (y 0 )2 :

Քանի, որ Լագրանժի ֆունկցիան բացահայտ կախվա

չէ x ո ոխականից, ապա Էյլերի հավասարումը ունի հետ յալ տեսքը. −λ1 : L − y 0 L0y0 - Շ ⇒ λ0 y − Շ - p 1 Է (y 0 )2

(5.2.4)

Այստեղից հետ ում է, որ եթե λ0 - 0, ապա կամ կամ y0 - 0: Ա աջին դեպքը հնարավոր չէ, որովհետ Լագրանժի գոր ակիցները միաժամանակ զրո լինել չեն կարող: Երկրորդ դեպքում, հաշվի ա նելով եզրային իզոպերիմետրայի պայմանները, կունենանք λ1 - 0,

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

Եթե λ0 - 1, ապա նշանակելով կստանանք՝

y 0 - tցt,

y(t) − Շ - −λ1 cՕՏ t :

(5.2.4)-ից (5.2.5)

Մյուս կողմից, ունենք dy dy - tցt ⇒ dx ⇒ x(t) − Շ1 - λ1 Տin t : (5.2.6) dx tցt

(5.2.5)-(5.2.6) հավասարություններից հետ ում է, որ (x − Շ1 )2 Է (y − Շ)2 - λ21 :

Եզրային պայմաններից ստանում ենք, որ Շ1 - 0: Այսպիսով, եթե l Հ 2x0 , ապա խնդիրը լու ում չունի: Եթե l - 2x0 , ապա y∗ (x) ≡ 0 : Եթե l » 2x0 խնդիրը ունի պտիմալ լու ում, ապա նրա գրաֆիկը

պետք է ունենա շրջանագ ային աղեղի տեսք: Այդ շրջանագի ը անցնում է (−x0 , 0) (x0 , 0) կետերով, իսկ նրա կենտրոնը գտնվում է ՕY ա անցքի վրա: Կարելի է ցույց տալ, որ եթե l » πx0 , ապա խնդիրը պտիմալ լու ում չունի:

ԽՆԴԻՐՆԵՐ

Լագրանժի գոր ակիցների մեթոդով լու ել վարիացիոն հաշվի հետ յալ իզոպերիմետրիկ խնդիրները: ա)

Ֆ1

0 2

Ֆ1

(y ) dx → ոոո,

y dx - 0, y(0) - 0, y(1) 0

բ)

-1: Ֆ1 Ֆ1 0 2 (y ) dx → ոոո, xydx - 0, y(0) - y(1) -

գ)

-0: Ֆπ Ֆπ (y 0 )2 dx → ոոո, ysոոx dx - 0, y(0) -

դ)

- y(π) - 1 : Ֆπ Ֆπ 0 2 (y ) dx → ոոո, yԸօsxdx - π/2, y(0) -

- 1, y(π) - −1 :

ե)

Ֆπ

Ֆπ ysոոx dx → ոոո,

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

- 1, y(π) - π :

Տ.3

Վարիացիոն հաշվի դասական իզոպերիմետրիկ խնդիրը

Խնդիր: Ապացուցել, որ l երկարության կտոր ա

կտոր ողորկ, պարզ հարթ ակ կորերի մեջ ամենամե

մակերեսը զբաղեցնում է շրջանագի ը: Լու ում: Դիցուք x - x(s), y - y(s), s ∈ |0, l|

կորի պարամետրական հավասարումներն են: Հաշվի ա նելով ո ոխական աղեղի երկարության դիֆերենցիալի մակերեսի հայտնի բանաձ երը՝ կարելի է տալ խնդրի հետ յալ մաթեմատիկական ձ ակերպումը. Ֆլ S(x, y) -

x(s)

dy dx dy ds → ոax, ( )2 Է ( )2 - 1 : ds ds ds

x(s)

շարքով՝

y(s)

ֆունկցիաները ներկայացնենք Ֆուրիեի

∞ Տ 2πո 2πո x(s) - a0 Է (an cՕՏ s Է Եn Տin s), (5.3.1) l l n-1 ∞ Տ 2πո 2πո y(s) - Ը0 Է (Ըn cՕՏ s Է dn Տin s) (5.3.2) : l l n-1

Այստեղից այս ֆունկցիաների ա անցիալների համար կունենանք հետ յալ բանաձ երը. ∞

2πո 2πո 2πո dx Տ 2πո (− an Տin sԷ Եn cՕՏ s), ds l l l l n-1 (5.3.3) ∞ Տ dy 2πո 2πո 2πո 2πո (− Ըn Տin sԷ dn cՕՏ s: ds n-1 l l l l (5.3.4) Հայտնի է նա , որ եթե αn , βn , ո - 0, 1, 2, ... թվերը f ֆունկցիայի Ֆուրիեի գոր ակիցներն են, իսկ γn , δn , ո - 0, 1, 2, ... թվերը՝ ϕ-ի գոր ակիցներն են,

ապա

l

Ֆլ

l

Ֆլ

∞

α2 Տ 2 f (s)ds - 0 Է (αn Է βn2 ), 4-1

∞ Տ f (s)ϕ(s)ds - α0 γ0 Է (αn γn Է βn δn ) : n-1

Այստեղից, նկատի ունենալով նա (5.3.3)-(5.3.4) բանաձ երը, հարթ պատկերի մակերեսի համար կստանանք հետ յալ բանաձ ը. S-π

∞ Տ

ո(an dn − Եn Ըn ) :

n-1

Քանի որ

Ֆլ ((

dy dx 2 ) Է ( )2 ) ds - l, ds ds

(5.3.5)

ապա, հաշվի ա նելով նա ա անցիալների (5.3.3)-(5.3.5) բանաձ երը, կստանանք, որ կորի l երկարությունը պետք է բավարարի հետ յալ հավասարմանը. ∞ 2π 2 Տ 2 2 ո (an Է Ե2n Է Ը2n Է d2n ) : ll n-1

Մակերեսի (5.3.5) կորի երկարության նաձ երից հետ ում է, որ

(5.3.6) (5.3.6)

բա-

∞ πՏ l2 −S ((ոan − dn )2 Է (ոԵn Է Ըn )2 Է 4π 2 n-1

Է(ո2 − 1)(Ը2n Է d2n )) ≥ 0 :

(5.3.7)

Այսպիսով ստացանք հանհրահայտ հետ յալ իզոպերիմետրիկ անհավասարությունը. S≤

l2 : 4π

Պարզ է, որ (5.3.7) անհավասարությունը կվերա վի հավասարության, երբ a1 - d1 , Ե1 Է Ը1 - 0, an - Եn - Ըn - dn - 0, ո - 2, 3, ... :

Այստեղից

այսինքն՝

x - a0 Է a1 cՕՏ s Է Ե1 Տin s, y - Ը0 − Ե1 cՕՏ s Է a1 Տin s,

l2 (x − a0 )2 Է (y − Ը0 )2 - a21 Է Ե21 : 4π

ԽՆԴԻՐՆԵՐ

1. Դիցուք ունենք երկու ու ուցիկ քա անկյուններ, որոնց կողերի երկարությունները մի նույն a, Ե, Ը, d թվերն են: Ենթադրենք նրանցից մեկին կարելի է արտագ ել շրջանագի : Ապացուցել, որ նրա մակերեսը մե է կամ հավասար մյուս քա անկյան մակերեսից: 2. Տրվա պարագ ով ու ուցիկ ո- անկյուն բազմանկյունների մեջ գտնել այն բազմանկյունը, որի մակերեսն ամենամե ն է: 3. Տրվա շրջանին ներգ ել ամենամե մակերեսով ո- անկյուն բազմանկյուն: 4. Դիտարկենք l երկարությամբ բոլոր այն հարթ ողորկ կորերը, որոնց A սկզբնակետը B վերջնակետը գտնվում են հարթության տրվա

L ուղղի վրա, իսկ կորերը ընկա են L ուղղի մի նույն կիսահարթության մեջ (տարբեր կորերի համար A B կետերը կարող են լինել տարբեր): Գտնել այն կորը, որով |A, B| հատվա ով սահմանա ակվա պատկերի մակերեսը լինի մե ագույն:

Տ.4

Էքստրեմումի բավարար պայմանները վարիացիոն հաշվի խնդիրներում

Այժմ բերենք վարիացիոն հաշվի պարզագույն խընդրի րինակ, ըստ որի Էյլերի հավասարումը ունի միակ

լու ում, որը էքստրեմում չէ: Այսինքն՝ Էյլերի հավասարումը էքստրեմումի միայն անհրաժեշտ պայման է: Դիտարկենք հետ յալ խնդիրը. 3π/2 Ֆ

((y 0 )2 −y 2 ) dx → ոոո, y(0) - y(3π/2) - 0 :

I(y) ≡

Էյլերի հավասարումը ունի հետ յալ տեսքը. y 00 Է y - 0 ⇒ y(x) - Շ1 Տin x Է Շ2 cՕՏ x :

Հաշվի ա նելով խնդրի եզրային պայմանները՝ կստանանք y∗ (x) ≡ 0 : Դիտարկենք ֆունկցիաների yn (x) -

2x Տin( ) ո

հաջորդականությունը: Ակնհայտ է, որ այս ֆունկցիաները թույլատրելի են C1

yn (·) → y ∗ (·) :

Մյուս կողմից ունենք I(yn ) - −

5π Հ 0 - I(y ∗ ), ո2

այսինքն y∗ -ը լոկալ մինիմումի կետ չէ: Այժմ բերենք բավարար մի պայման, որով ստուգվում է, թե երբ Էյլերի հավասարման լու ումը կլինի լոկալ մինիմումի կետ: Դիցուք y∗ (x)-ը վարիացիոն հաշվի պարզագույն խնդրի Էյլերի հավասարման լու ում է: Նշանակենք 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 ) :

Կազմենք հետ յալ դիֆերենցիալ հավասարումը, որը կոչվում է Յակոբիի հավասարում. d dհ (P ) − Qհ - 0 : dx dx

(5.4.1)

Դիցուք y∗ (x) էքստրեմալը բավարարում է հետ յալ երկու պայմաններին. » y ∗ (x)-ը

բավարարում է Yակոբիի պայմանին, եթե (5.4.1) հավասարումը սկզբնական հ(x0 ) - 0 պայմանով ունի ոչ տրիվիալ այնպիսի հ(x) լու ում, որ հ(x) 6- 0 ∀ x ∈ (x0 , x1 | :

» y ∗ (x)-ը

եթե

բավարարում է Լեժանդրի պայմանին, P (x) » 0 ∀x ∈ |x0 , x1 | :

Ճշմարիտ է հետ յալ պնդումը (տենս, րինակ՝ |1-2|): Թեորեմ 5.4.1: Դիցուք y ∗ (x)-ը (5.1.1) վարիացիոն հաշվի պարզագույն խնդրի Էյլերի հավասարման լու ումն է բավարարվում են Yակոբիի Լեժանդրի պայմանները: Այդ դեպքում y ∗ (x)-ը (5.1.1) խնդրում լոկալ մինիմումի կետ է:

Օրինակ (Կարճագույն ճանապարհի խնդիրը): Ֆ1 p

1 Է (y 0 )2 dx → ոոո, y(0) - 0, y(1) - 1 :

(5.4.2)

Լու ում: Քանի որ այստեղ L ֆունկցիան բացահայտ

կախվա չէ x ո ոխականից, ապա Էյլերի հավասարումը ունի հետ յալ տեսքը. L − y 0 L0y0 - Շ ⇒

p (y 0 )2 1 Է (y 0 )2 − p -Շ⇒ 1 Է (y 0 )2

⇒ y(x) - Շ1 x Է Շ2 :

Հաշվի ա նելով (5.4.2) եզրային պայմանները՝ կստանանք y∗ (x) - x : Ստուգենք Յակոբիի պայմանը: Ունենք d 00 L 0 ≡ 0, dx yy - √ : P (x) - p 2 2 1 Է ((y ∗ )0 )2 Q(x) - L00yy −

Յակոբիի հավասարումը ունի հետ յալ տեսքը. d2 հ -0: dx2

Այստեղից հետ ում է, որ հ(x) - Շ1 x Է Շ2 :

Ուստի հ(x) - Շ1 x, Շ1 6- 0 ֆունկցիան հ(0) - 0 սկզբնական պայմանով Յակոբիի հավասարման ոչ

տիիվիալ լու ում է, որը զրո չի դա նում (0, 1| կիսաբաց միջակայքի ոչ մի կետում: Հետ աբար, Յակոբիի բավարար պայմանը տեղի ունի: Լեժանդրի √պայմանը նույնպես տեղի ունի, քանի որ P (x) ≡ 1/2 2 » 0 : Այսպիսով, y∗ (x) - x ֆունկցիան կարճագույն ճանապարհի խնդրի լու ումն է:

ԽՆԴԻՐՆԵՐ

Օգտագոր ելով Յակոբիի Լեժանդրի պայմանները՝ լու ել վարիացիոն հաշվի հետ յալ խնդիրները: ա)

Ֆπ/2 ((y 0 )2 − y 2 ) dx → ոոո, y(0) - 0, y(π/2) - 1 :

բ)

Ֆπ/2 ((y 0 )2 − y 2 Է 4yԸօsx) dx → ոոո, y(0) -

գ)

- 0, y(π/2) - π/2 : Ֆ 1 ((y 0 )2 Է y 2 Է 4ysհ(x))dx → ոոո, y(0) -

դ)

- −1, y(1) - 0 : Ֆπ/2 ((y 0 )2 − 4y 2 ) dx → ոոո, y(0) - 0, y(π/4) - 1 :

ե)

Ֆπ/2 (y 2 − 2(y 0 )2 Է 2y) dx → ոոո, y(0) - y(π/2) 0

-0:

Գrաkանուyուն [1|

8.Խ. Ճոåճñååâ, 8. Խ. Ղոõօìոքօâ, Օ. 8. Փօìոո, ÎïòèìàëՈíîå óïքàâëåíèå, էàóêà, Խ., 19/9.

[2|

8.Խ. Ճոåճñååâ, Ý.Խ. Լոոååâ, 8.Խ. Ղոõօìոքօâ, ÑՇîքíèê 3àäàՎ ïî îïòèìè3àöèè, էàóê, Խ., 1984.

[3|

È. Մ. Ճճóոո÷, ԽàòåìàòèՎåñêèå ïքîãքàììèքîâàíèå â ïքèìåքàõ è 3àäàՎàõ, Թûñոàո ոêîëà, Խ., 1986.

[4|

Փ. Լ. 8ոñոոüåâ, ×èñëåííûå ìåòîäû քåոåíèո ՏêñòքåìàëՈíûõ 3àäàՎ, էàóêà, Խ., 1980.

[5|

Ք.Օ. Լօոօâոոճոո Ք.Օ., Խ. 8. Áոոոøօâ, Ýëåìåíòû âûïóêëîãî è ñèëՈíî âûïóêëîãî àíàëè3à, ôè3ìàòëèò, Խ., 2004.

[6|

Ճ. 8. Լոո6åոååâ, Ղ.Ճ. Մå6օâո, Խåòîäû îïòèìè3àöèè â ïքèìåքàõ è 3àäàՎàõ, Թûñոàո ոêîëà, Խ., 2002.

Á.Í. Լøåոո÷ոûé, Թûïóêëûé àíàëè3 è ՏêñòքåìàëՈíûå 3àäàՎè, էàóêà, Խ., 1980.

[8|

Ճ. Լ. Օóõոքåâ, Ճ.8. Ղոìօõօâ, 8.8. ՓåՊåքօâ, Êóքñ ìåòîäîâ îïòèìè3àöèè, էàóêà, Խ., 1986.

[9|

Ê. Մåéõ6âåéñ, Թûïóêëûå ìíîæåñòâà, էàóêà, Խ., 1985.

[10|

8. 8. 8օåâօՊոո, Ëèíåéíàո àëãåՇքà, էàóêà, Խ., 198/.

[11|

Խ.T. Խօckքfellքւ , J.B. Խօgeւ, Varտatտoոal Aոalտsտs,

SprտոջՆr-VՆrlaջ,

BՆrlտո,

HՆտdՆlbՆrջ,

1998.

|12| Վ. Ավետիսյան, Մ. Pողոսյան, Վարիացիոն հաշիվ պտիմալ կա ավարում (դասախոսություններ), ԵՊՀ հրատ., Եր ան, 2008: |13| Վ. . Bարսեղյան, Վարիացիոն հաշիվ, ԵՊՀ հրատ., Եր ան, 2011:

. .

. . .

60x841/16: 8.375

.

.

, 0025,

. 100:

:

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

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