Գրադիենտ վայրէջք. Անվերապահ օպտիմալացում

Կարող եք նաև որոնել ոչ թե գրադիենտի ուղղությամբ լավագույն կետը, այլ ավելի լավը, քան ներկայիսը:

Տեղական օպտիմիզացման բոլոր մեթոդներից ամենահեշտը կիրառելը: Ունի բավականին թույլ պայմաններկոնվերգենցիա, բայց կոնվերգենցիայի արագությունը բավականին ցածր է (գծային): Գրադիենտ մեթոդի քայլը հաճախ օգտագործվում է որպես օպտիմալացման այլ մեթոդների մաս, ինչպիսին է Ֆլետչեր–Ռիվզ մեթոդը։

Նկարագրություն [ | ]

Բարելավումներ[ | ]

Գրադիենտ վայրէջքի մեթոդը պարզվում է, որ շատ դանդաղ է կիրճով շարժվելիս և փոփոխականների քանակի ավելացմամբ օբյեկտիվ գործառույթմեթոդի այս վարքագիծը դառնում է բնորոշ: Այս երեւույթի դեմ պայքարելու համար այն օգտագործվում է, որի էությունը շատ պարզ է. Գրադիենտ վայրէջք կատարելով երկու քայլ և ձեռք բերելով երեք կետ, երրորդ քայլը պետք է կատարվի առաջին և երրորդ կետերը միացնող վեկտորի ուղղությամբ՝ ձորի հատակի երկայնքով:

Քառակուսայինին մոտ ֆունկցիաների համար արդյունավետ է կոնյուգացիոն գրադիենտ մեթոդը։

Կիրառում արհեստական ​​նեյրոնային ցանցերում[ | ]

Գրադիենտ վայրէջքի մեթոդը, որոշակի փոփոխություններով, լայնորեն կիրառվում է պերցեպտրոնի ուսուցման համար և հայտնի է արհեստական ​​նեյրոնային ցանցերի տեսության մեջ որպես հետտարածման մեթոդ։ Պերցեպտրոնի տիպի նեյրոնային ցանցը վարժեցնելիս անհրաժեշտ է փոխել ցանցի կշռման գործակիցները՝ նվազագույնի հասցնելու համար. միջին սխալնեյրոնային ցանցի ելքում, երբ ուսուցման մուտքային տվյալների հաջորդականությունը մատակարարվում է մուտքին: Ֆորմալ կերպով, գրադիենտ վայրէջքի մեթոդով ընդամենը մեկ քայլ անելու համար (ցանցի պարամետրերում ընդամենը մեկ փոփոխություն կատարեք), անհրաժեշտ է հաջորդաբար ներկայացնել վերապատրաստման տվյալների բացարձակ ամբողջ փաթեթը ցանցի մուտքագրմանը, հաշվարկել սխալը յուրաքանչյուր օբյեկտի համար: վերապատրաստման տվյալները և հաշվարկեք ցանցի գործակիցների անհրաժեշտ ուղղումը (բայց մի արեք այս ուղղումը), և բոլոր տվյալները ներկայացնելուց հետո հաշվարկեք յուրաքանչյուր ցանցի գործակցի ճշգրտման գումարը (գրադիենտների գումարը) և շտկեք գործակիցները «մեկ քայլ» . Ակնհայտ է, որ վերապատրաստման տվյալների մեծ հավաքածուի դեպքում ալգորիթմը կաշխատի չափազանց դանդաղ, ուստի գործնականում ցանցի գործակիցները հաճախ ճշգրտվում են յուրաքանչյուր ուսումնական տարրից հետո, որտեղ գրադիենտ արժեքը մոտավորվում է ծախսերի ֆունկցիայի գրադիենտով, որը հաշվարկվում է միայն մեկ մարզման վրա: տարր. Այս մեթոդը կոչվում է ստոխաստիկ գրադիենտ ծագում կամ գործառնական գրադիենտ վայրէջք . Stochastic gradient descent-ը ստոխաստիկ մոտարկման ձև է: Ստոխաստիկ մոտարկումների տեսությունը պայմաններ է ապահովում ստոխաստիկ գրադիենտ ծագման մեթոդի կոնվերգենցիայի համար։

Հղումներ [ | ]

• Ջ.Մեթյուզ.Մոդուլ ամենից կտրուկ վայրէջքի կամ գրադիենտ մեթոդի համար: (անհասանելի հղում)

գրականություն [ | ]

• Ակուլիչ Ի.Լ.Մաթեմատիկական ծրագրավորում օրինակներով և խնդիրներով. - Մ.: Բարձրագույն դպրոց, 1986. - P. 298-310:
• Գիլ Ֆ., Մյուրեյ Վ., Ռայթ Մ.Գործնական օպտիմալացում = Գործնական օպտիմիզացում: - Մ.: Միր, 1985:
• Կորշունով Յու. Մ., Կորշունով Յու. Մ.Կիբեռնետիկայի մաթեմատիկական հիմունքները. - Մ.: Էներգոատոմիզդատ, 1972:
• Մաքսիմով Յու.Ա., Ֆիլիպովսկայա Է.Ա.Ոչ գծային ծրագրավորման խնդիրների լուծման ալգորիթմներ. - M.: MEPhI, 1982:
• Մաքսիմով Յու.Ա.Գծային և դիսկրետ ծրագրավորման ալգորիթմներ. - M.: MEPhI, 1980:
• Կոռն Գ., Կոռն Թ.Մաթեմատիկայի ձեռնարկ գիտնականների և ճարտարագետների համար. - M.: Nauka, 1970. - P. 575-576:
• Ս. Յու. Գորոդեցկի, Վ.Ա. Գրիշագին.Ոչ գծային ծրագրավորում և բազմաէքստրեմալ օպտիմալացում: - Նիժնի ՆովգորոդՆիժնի Նովգորոդի համալսարանի հրատարակչություն, 2007 թ. - էջ 357-363:

Ամենակտրուկ վայրէջքի մեթոդը գրադիենտ մեթոդ է՝ փոփոխական քայլով: Յուրաքանչյուր կրկնության ժամանակ k քայլի չափը ընտրվում է f(x) ֆունկցիայի նվազագույնի պայմանից իջնելու ուղղությամբ, այսինքն.

Այս պայմանը նշանակում է, որ հակագրադիենտի երկայնքով շարժումը տեղի է ունենում այնքան ժամանակ, քանի դեռ f (x) ֆունկցիայի արժեքը նվազում է։ Մաթեմատիկական տեսանկյունից յուրաքանչյուր կրկնության ժամանակ անհրաժեշտ է լուծել միաչափ մինիմիզացիայի խնդիրը՝ ըստ ֆունկցիայի.

() = f (x (k) -f (x (k)))

Դրա համար օգտագործենք ոսկե հարաբերակցության մեթոդը:

Ամենակտրուկ վայրէջքի մեթոդի ալգորիթմը հետևյալն է.

Նշված են x (0) մեկնարկային կետի կոորդինատները:

x (k) , k = 0, 1, 2, ... կետում հաշվարկվում է f (x (k)) գրադիենտ արժեքը։

Քայլի չափը k որոշվում է միաչափ մինիմիզացիայի միջոցով՝ օգտագործելով ֆունկցիան

() = f (x (k) -f (x (k))).

x (k) կետի կոորդինատները որոշվում են.

x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.

Ստուգվում է կրկնվող գործընթացի դադարեցման պայմանը.

||զ (x (k +1))|| .

Եթե ​​այն կատարվի, ուրեմն հաշվարկները դադարում են։ Հակառակ դեպքում, մենք անցնում ենք 1-ին քայլին: Ամենակտրուկ վայրէջքի մեթոդի երկրաչափական մեկնաբանությունը ներկայացված է Նկ. 1.

Բրինձ. 2.1. Առավել կտրուկ վայրէջքի մեթոդի բլոկային դիագրամ:

Մեթոդի ներդրումը ծրագրում.

Ամենաթեժ վայրէջքի մեթոդ.

Բրինձ. 2.2. Ամենակտրուկ վայրէջքի մեթոդի իրականացում.

Եզրակացություն. Մեր դեպքում մեթոդը համընկավ 7 կրկնությունների մեջ: A7 կետը (0,6641; -1,3313) ծայրահեղ կետ է: Կոնյուգացիոն ուղղությունների մեթոդ. Քառակուսային ֆունկցիաների համար կարող եք ստեղծել գրադիենտ մեթոդ, որտեղ կոնվերգենցիայի ժամանակը կլինի վերջավոր և հավասար n փոփոխականների թվին:

Եկեք կոչենք որոշակի ուղղություն և խոնարհենք ինչ-որ դրական որոշակի Hess մատրիցի նկատմամբ H, եթե.

Այսպիսով, H միավորի համար խոնարհված ուղղությունը նշանակում է դրանց ուղղահայացը: Ընդհանուր դեպքում Հ-ն ոչ տրիվիալ է։ IN ընդհանուր դեպքզուգակցումը Հեսսի մատրիցայի կիրառումն է վեկտորի վրա, դա նշանակում է պտտել այս վեկտորը որոշակի անկյան տակ, ձգել կամ սեղմել այն:

Իսկ այժմ վեկտորը ուղղանկյուն է, այսինքն՝ խոնարհումը ոչ թե վեկտորի ուղղանկյունությունն է, այլ պտտվող վեկտորի ուղղանկյունությունը.e.i.

Բրինձ. 2.3. Կոնյուգացիոն ուղղությունների մեթոդի բլոկային դիագրամ:

Մեթոդի ներդրումը ծրագրում՝ Կոնյուգացիոն ուղղությունների մեթոդ.

Բրինձ. 2.4. Կոնյուգացիոն ուղղությունների մեթոդի իրականացում.

Բրինձ. 2.5. Կոնյուգացիոն ուղղությունների մեթոդի գրաֆիկ:

Եզրակացություն. A3 կետը (0,6666; -1,3333) գտնվել է 3 կրկնությունից և ծայրահեղ կետ է:

3. Սահմանափակումների առկայության դեպքում ֆունկցիայի նվազագույն և առավելագույն արժեքի որոշման մեթոդների վերլուծություն

Հիշեցնենք, որ ընդհանուր առաջադրանքպայմանական օպտիմալացումն այսպիսի տեսք ունի

f(x) ® min, x О W,

որտեղ W-ը R m-ի պատշաճ ենթաբազմություն է: Հավասարության տիպի սահմանափակումներով խնդիրների ենթադասն առանձնանում է նրանով, որ  բազմությունը սահմանվում է ձևի սահմանափակումներով.

f i (x) = 0, որտեղ f i: R m ®R (i = 1, …, k):

Այսպիսով,W = (x О R m: f i (x) = 0, i = 1, …, k):

Մեզ համար հարմար կլինի f ֆունկցիայի համար գրել «0» ինդեքս։ Այսպիսով, հավասարության տիպի սահմանափակումներով օպտիմալացման խնդիրը գրված է այսպես

f 0 (x) ® min, (3.1)

f i (x) = 0, i = 1, …, k. (3.2)

Եթե ​​մենք այժմ f-ով R m-ում նշում ենք մի ֆունկցիա R k-ի արժեքներով, որի կոորդինատային նշումը ունի f(x) = (f 1 (x), ..., f k (x) ձևը, ապա ( 3.1)–(3.2) կարող ենք գրել նաև ձևով

f 0 (x) ® min, f(x) = Q.

Երկրաչափական առումով հավասարության տիպի սահմանափակումների խնդիրը  բազմազանության վրա f 0 ֆունկցիայի գրաֆիկի ամենացածր կետը գտնելու խնդիրն է (տես նկ. 3.1):

Այն կետերը, որոնք բավարարում են բոլոր սահմանափակումները (այսինքն՝  բազմության կետերը) սովորաբար կոչվում են թույլատրելի։ Թույլատրելի x* կետը կոչվում է f 0 ֆունկցիայի պայմանական նվազագույնը f i (x) = 0, i = 1, ..., k (կամ (3.1)–(3.2) խնդրի լուծումը, եթե. բոլոր թույլատրելի կետերի համար x f 0 (x *)  f 0 (x): (3.3)

Եթե ​​(3.3)-ը բավարարվում է միայն x* կետի V x * հարևանությամբ գտնվող թույլատրելի x-ի համար, ապա մենք խոսում ենք տեղական պայմանական նվազագույնի մասին: Պայմանական խիստ տեղական և գլոբալ նվազագույն հասկացությունները սահմանվում են բնական ճանապարհով։

Գրադիենտ մեթոդի այս տարբերակում նվազագույնի հասցնելու հաջորդականությունը (X k) նույնպես կառուցված է ըստ կանոնի (2.22): Այնուամենայնիվ, a k քայլի չափը հայտնաբերվում է օժանդակ միաչափ մինիմալացման խնդրի լուծման արդյունքում

min(j k (a) | a>0 ), (2.27)

որտեղ j k (a)=f(X k - a· (X k)). Այսպիսով, հակագրադիենտի ուղղությամբ յուրաքանչյուր կրկնության ժամանակ կատարվում է սպառիչ վայրէջք. Խնդիրը (2.27) լուծելու համար կարող եք օգտագործել 1-ին բաժնում նկարագրված միաչափ որոնման մեթոդներից մեկը, օրինակ՝ բիթային որոնման մեթոդը կամ ոսկե հատվածի մեթոդը:

Եկեք նկարագրենք ամենադաժան վայրէջքի մեթոդի ալգորիթմը:

Քայլ 0.Սահմանել e>0 ճշգրտության պարամետրը, ընտրել X 0 ОE n , սահմանել k=0:

Քայլ 1.Գտե՛ք (X k) և ստուգե՛ք նշված ճշտության հասնելու պայմանը || (x k) ||£ էլ. Եթե ​​բավարարված է, ապա անցեք 3-րդ քայլին, հակառակ դեպքում՝ 2-րդ քայլին:

Քայլ 2.Լուծել խնդիրը (2.27), այսինքն. գտնել կ. Գտե՛ք հաջորդ կետը, դրե՛ք k=k+1 և անցե՛ք 1-ին քայլին։

Քայլ 3Լրացրեք հաշվարկները՝ դնելով X * = X k, f * = f(X k):

Տիպիկ օրինակ

Նվազագույնի հասցնել գործառույթը

f(x)=x 1 2 +4x 2 2 -6x 1 -8x 2 +13; (2.28)

Եկեք նախ լուծենք խնդիրը դասականմեթոդ. Եկեք գրենք հավասարումների համակարգ, որը ներկայացնում է անհրաժեշտ պայմաններըանվերապահ ծայրահեղություն

Լուծելով այն՝ ստանում ենք անշարժ կետ X*=(3;1): Հաջորդը, եկեք ստուգենք կատարումը բավարար պայման, որի համար գտնում ենք երկրորդ ածանցյալների մատրիցը

Քանի որ, ըստ Սիլվեստրի չափանիշի, այս մատրիցը դրական է որոշ «»-ի համար, ապա գտնված X* կետը f(X) ֆունկցիայի նվազագույն կետն է: Նվազագույն արժեքը f *=f(X*)=0: Սա խնդրի ճշգրիտ լուծումն է (11):

Եկեք կատարենք մեթոդի մեկ կրկնություն գրադիենտ վայրէջքհամար (2.28): Ընտրենք մեկնարկային կետը X 0 =(1;0), սահմանենք սկզբնական քայլը a=1 և l=0.5 պարամետրը։ Հաշվենք f(X 0)=8։

Գտնենք f(X) ֆունկցիայի գրադիենտը X 0 կետում

(X 0)= = (2.29)

Սահմանենք նոր կետ X=X 0 -a· (X 0)՝ հաշվարկելով դրա կոորդինատները.

x 1 =

x 2 = (2.30)

Հաշվենք f(X)= f(X 0 -a· (X 0))=200: Քանի որ f(X)>f(X 0), մենք քայլը բաժանում ենք՝ ենթադրելով a=a·l=1·0.5=0.5: Կրկին հաշվում ենք՝ օգտագործելով (2.30) բանաձևերը x 1 =1+4a=3; x 2 =8a=4 և գտի՛ր f(X)=39 արժեքը: Քանի որ f(X)>f(X 0) կրկին, մենք էլ ավելի փոքրացնում ենք քայլի չափը՝ սահմանելով a=a·l=0.5·0.5=0.25: Մենք հաշվում ենք նոր կետ x 1 =1+4·0.25=2 կոորդինատներով; x 2 =8·0.25=2 և ֆունկցիայի արժեքը այս կետում f(X)=5: Քանի որ f(X) նվազման պայմանը

Եկեք կատարենք մեկ կրկնություն՝ օգտագործելով մեթոդը ամենից կտրուկ վայրէջքհամար (2.28) նույն սկզբնական կետով X 0 =(1;0): Օգտագործելով արդեն գտնված գրադիենտը (2.29), մենք գտնում ենք

X= X 0 -a· (X 0)

եւ կառուցել j 0 (a)=f(X 0 -a· (X 0))=(4a-2) 2 +4(8a-1) 2 ֆունկցիան: Այն նվազագույնի հասցնելով՝ օգտագործելով անհրաժեշտ պայմանը

j 0 ¢(a)=8·(4a - 2)+64·(8a - 1)=0

մենք գտնում ենք քայլի չափի օպտիմալ արժեքը a 0 =5/34:

Նվազագույնի հասցնելու հաջորդականության կետի որոշում

X 1 = X 0 -a 0 · (X 0) .

f(x) տարբերակվող ֆունկցիայի գրադիենտը կետում Xկանչեց n- ծավալային վեկտոր f(x) , որի բաղադրիչները ֆունկցիայի մասնակի ածանցյալներ են f(x),հաշվարկված կետում X, այսինքն.

f» (x ) = (df(x)/դհ 1 , …, df(x)/dx n) Տ.

Այս վեկտորը ուղղահայաց է կետով անցնող հարթությանը X, և շոշափում է ֆունկցիայի մակարդակի մակերեսին f(x),անցնելով մի կետով X.Նման մակերեսի յուրաքանչյուր կետում ֆունկցիան f(x)վերցնում է նույն արժեքը: Ֆունկցիան հավասարեցնելով տարբեր հաստատուն արժեքներին C 0 , C 1 , ..., մենք ստանում ենք մի շարք մակերեսներ, որոնք բնութագրում են դրա տոպոլոգիան (նկ. 2.8):

Բրինձ. 2.8. Գրադիենտ

Գրադիենտ վեկտորն ուղղված է տվյալ կետում ֆունկցիայի ամենաարագ աճի ուղղությամբ։ Գրադիենտին հակառակ վեկտոր (-f'(x)) , կանչեց հակագրադիենտև ուղղված է ֆունկցիայի ամենաարագ նվազմանը։ Նվազագույն կետում ֆունկցիայի գրադիենտը զրո է: Առաջին կարգի մեթոդները, որոնք նաև կոչվում են գրադիենտ և նվազագույնի հասցնելու մեթոդներ, հիմնված են գրադիենտների հատկությունների վրա: Այս մեթոդների կիրառումը ընդհանուր դեպքում թույլ է տալիս որոշել ֆունկցիայի տեղական նվազագույն կետը:

Ակնհայտորեն, եթե չկա լրացուցիչ տեղեկություն, ապա ելակետից Xխելամիտ է գնալ կետին X, պառկած հակագրադիենտի ուղղությամբ՝ ֆունկցիայի ամենաարագ նվազումը։ Ընտրելով որպես վայրէջքի ուղղություն Ռ[կ] հակագրադիենտ - f'(x[k] ) կետում X[կ], մենք ստանում ենք ձևի կրկնվող գործընթաց

X[ k+ 1] = x[կ]-a k f» (x[k] ) , և կ > 0; կ=0, 1, 2, ...

Կոորդինատային ձևով այս գործընթացը գրված է հետևյալ կերպ.

x i [ կ+1]=x i[կ] - ա կf(x[k] ) /x i

i = 1, ..., n; կ= 0, 1, 2,...

Որպես կրկնվող գործընթացի դադարեցման չափանիշ՝ կա՛մ փաստարկի փոքր աճի պայմանի կատարումը || x[կ+l] -x[կ] || <= e , либо выполнение условия малости градиента

|| f'(x[կ+l] ) || <= g ,

Այստեղ e-ն և g-ն տրված են փոքր քանակությամբ:

Հնարավոր է նաև համակցված չափանիշ, որը բաղկացած է նշված պայմանների միաժամանակյա կատարումից։ Գրադիենտ մեթոդները միմյանցից տարբերվում են քայլի չափը ընտրելու եղանակով և կ.

Մշտական ​​քայլով մեթոդում բոլոր կրկնությունների համար ընտրվում է որոշակի հաստատուն քայլի արժեք: Բավականին փոքր քայլ և կկապահովի ֆունկցիայի նվազումը, այսինքն՝ անհավասարությունը

f(x[ կ+1]) = f(x[k] – a k f (x[k] )) < f(x[k] ) .

Այնուամենայնիվ, դա կարող է հանգեցնել նվազագույն կետին հասնելու համար անընդունելի մեծ թվով կրկնությունների իրականացման անհրաժեշտության: Մյուս կողմից, չափազանց մեծ քայլը կարող է առաջացնել ֆունկցիայի անսպասելի աճ կամ հանգեցնել նվազագույն կետի շուրջ տատանումների (հեծանվավազք)։ Քայլի չափն ընտրելու համար անհրաժեշտ տեղեկատվություն ստանալու դժվարության պատճառով, մշտական ​​քայլերով մեթոդները գործնականում հազվադեպ են օգտագործվում:

Գրադիենտներն ավելի խնայող են կրկնությունների քանակի և հուսալիության առումով փոփոխական քայլերի մեթոդներ,երբ, կախված հաշվարկների արդյունքներից, քայլի չափը ինչ-որ կերպ փոխվում է։ Դիտարկենք գործնականում օգտագործվող նման մեթոդների տարբերակները:

Յուրաքանչյուր կրկնության ժամանակ ամենադաժան վայրէջքի մեթոդն օգտագործելիս՝ քայլի չափը և կընտրվում է ֆունկցիայի նվազագույն պայմանից f(x)վայրէջքի ուղղությամբ, այսինքն.
f(x[կ]–a k f’(x[կ])) = f(x[k] -աֆ» (x[կ])) .

Այս պայմանը նշանակում է, որ հակագրադիենտի երկայնքով շարժումը տեղի է ունենում այնքան ժամանակ, որքան ֆունկցիայի արժեքը f(x)նվազում է. Մաթեմատիկական տեսանկյունից յուրաքանչյուր կրկնության ժամանակ անհրաժեշտ է լուծել միաչափ մինիմիզացիայի խնդիրը՝ ըստ. Ագործառույթները
ժ (ա) = f(x[կ]-աֆ» (x[կ])) .

Ամենակտրուկ վայրէջքի մեթոդի ալգորիթմը հետևյալն է.

1. Սահմանեք ելակետի կոորդինատները X.

2. Կետում X[կ], k = 0, 1, 2, ... հաշվարկում է գրադիենտ արժեքը f'(x[կ]) .

3. Քայլի չափը որոշվում է ա k, միաչափ մինիմիզացիայի միջոցով Ագործառույթներ j (ա) = f(x[կ]-աֆ» (x[կ])).

4. Որոշվում են կետի կոորդինատները X[k+ 1]:

x i [ k+ 1]= x i[կ]- a k f' i (x[կ]), i = 1,..., էջ.

5. Ստուգվում են ստերացման գործընթացի դադարեցման պայմանները. Եթե ​​դրանք կատարվեն, ուրեմն հաշվարկները դադարում են։ Հակառակ դեպքում անցեք 1-ին քայլին:

Քննարկվող մեթոդում կետից շարժման ուղղությունը X[կ] շոշափում է մակարդակի գիծը կետում x[k+ 1] (նկ. 2.9): Վայրէջքի հետագիծը զիգզագաձեւ է, հարակից զիգզագային կապերով միմյանց ուղղանկյուն: Իսկապես, քայլ ա k-ն ընտրվում է նվազագույնի հասցնելով ըստ Ագործառույթներ? (ա) = f(x[k] -աֆ» (x[կ])) . Գործառույթի մինիմումի համար անհրաժեշտ պայման դժ (ա)/դա = 0:Հաշվելով բարդ ֆունկցիայի ածանցյալը՝ մենք ստանում ենք հարևան կետերում իջնելու ուղղությունների վեկտորների ուղղանկյունության պայմանը.

դիջ (a)/da = -f’(x[k+ 1]f'(x[կ]) = 0.

Բրինձ. 2.9. Ամենից կտրուկ վայրէջքի մեթոդի երկրաչափական մեկնաբանություն

Գրադիենտային մեթոդները միանում են նվազագույնին բարձր արագությամբ (երկրաչափական առաջընթացի արագություն) հարթ ուռուցիկ ֆունկցիաների համար: Նման գործառույթներն ունեն ամենամեծը Մև ամենաքիչը մԵրկրորդ ածանցյալների մատրիցայի սեփական արժեքները (Հեսսիական մատրիցա)

քիչ են տարբերվում միմյանցից, այսինքն՝ մատրիցով N(x)լավ պայմանավորված. Հիշեցնենք, որ սեփական արժեքները l i, ես =1, …, n, մատրիցները բնորոշ հավասարման արմատներն են

Այնուամենայնիվ, գործնականում, որպես կանոն, նվազագույնի հասցվող գործառույթներն ունեն երկրորդ ածանցյալների վատ պայմանավորված մատրիցներ. (տ/մ<< 1). Որոշ ուղղությունների երկայնքով նման գործառույթների արժեքները փոխվում են շատ ավելի արագ (երբեմն մի քանի մեծության կարգով), քան այլ ուղղություններով: Նրանց հարթ մակերեսները ամենապարզ դեպքում խիստ երկարաձգված են (նկ. 2.10), իսկ ավելի բարդ դեպքերում դրանք թեքվում են և նմանվում ձորերի։ Նման հատկություններով ֆունկցիաները կոչվում են հեղեղատ.Այս ֆունկցիաների հակագրադիենտի ուղղությունը (տե՛ս նկ. 2.10) էապես շեղվում է ուղղությունից մինչև նվազագույն կետ, ինչը հանգեցնում է կոնվերգենցիայի արագության նվազմանը։

Բրինձ. 2.10. Ջրհեղեղի ֆունկցիա

Գրադիենտ մեթոդների կոնվերգենցիայի արագությունը նույնպես զգալիորեն կախված է գրադիենտ հաշվարկների ճշգրտությունից: Ճշգրտության կորուստը, որը սովորաբար տեղի է ունենում նվազագույն կետերի մոտակայքում կամ հեղեղատային իրավիճակում, ընդհանուր առմամբ կարող է խաթարել գրադիենտ վայրէջքի գործընթացի մերձեցումը: Ելնելով վերը նշված պատճառներից՝ խնդրի լուծման սկզբնական փուլում գրադիենտ մեթոդները հաճախ օգտագործվում են այլ՝ ավելի արդյունավետ մեթոդների հետ համատեղ։ Այս դեպքում կետը Xհեռու է նվազագույն կետից, և հակագրադիենտի ուղղությամբ քայլերը հնարավորություն են տալիս հասնել ֆունկցիայի զգալի նվազման։

Վերևում քննարկված գրադիենտ մեթոդները գտնում են ֆունկցիայի նվազագույն կետը ընդհանուր դեպքում միայն անսահման թվով կրկնումներում: Կոնյուգացիոն գրադիենտ մեթոդը ստեղծում է որոնման ուղղություններ, որոնք ավելի համահունչ են նվազագույնի հասցվող ֆունկցիայի երկրաչափությանը: Սա զգալիորեն մեծացնում է դրանց կոնվերգենցիայի արագությունը և թույլ է տալիս, օրինակ, նվազագույնի հասցնել քառակուսի ֆունկցիան

f(x) = (x, Hx) + (b, x) + a

սիմետրիկ դրական որոշակի մատրիցով Նվերջավոր թվով քայլերով Պ,հավասար է ֆունկցիայի փոփոխականների քանակին: Նվազագույն կետի մերձակայքում գտնվող ցանկացած հարթ ֆունկցիա կարող է լավ մոտավորվել քառակուսի ֆունկցիայով, հետևաբար ոչ քառակուսի ֆունկցիաները նվազագույնի հասցնելու համար հաջողությամբ օգտագործվում են կոնյուգացիոն գրադիենտ մեթոդներ: Այս դեպքում դրանք դադարում են լինել վերջավոր և դառնում են կրկնվող։

Ըստ սահմանման, երկու n- ծավալային վեկտոր XԵվ ժամըկանչեց խոնարհվածհարաբերական մատրիցին Հ(կամ Հ-կոնյուգատ), եթե սկալյար արտադրանքը (x, Դե) = 0:Այստեղ N -չափի սիմետրիկ դրական որոշակի մատրիցա Պ X Պ.

Կոնյուգացիոն գրադիենտ մեթոդների ամենակարևոր խնդիրներից մեկը ուղղությունների արդյունավետ կառուցման խնդիրն է: Fletcher-Reeves մեթոդը լուծում է այս խնդիրը՝ փոխակերպելով հակագրադիենտը յուրաքանչյուր քայլում -f(x[կ]) ուղղությամբ էջ[կ], Հ- միավորել նախկինում գտնված ուղղությունների հետ Ռ, Ռ, ..., Ռ[կ-1]. Եկեք նախ դիտարկենք այս մեթոդը նվազագույնի հասցնելու խնդրի հետ կապված քառակուսի ֆունկցիա.

Ուղղություններ Ռ[կ] հաշվարկվում է բանաձևերով.

p[ կ] = -f'(x[կ]) +b k-1 էջ[կ-l], կ>= 1;

p = - զ’(x) .

b արժեքներ կ-1 ընտրված են այնպես, որ ուղղությունները էջ[կ], Ռ[կ-1] էին Հ- զուգակցված :

(էջ[կ], HP[k- 1])= 0.

Արդյունքում՝ քառակուսի ֆունկցիայի համար

,

կրկնվող նվազագույնի հասցնելու գործընթացն ունի ձև

x[ կ+l] =x[կ]+a k p[կ],

Որտեղ Ռ[կ] - իջնելու ուղղությունը դեպի k-մ քայլ; և k -քայլի չափը. Վերջինս ընտրվում է ֆունկցիայի նվազագույն պայմանից f(x)Ըստ Աշարժման ուղղությամբ, այսինքն՝ միաչափ մինիմալացման խնդրի լուծման արդյունքում.

f(x[ կ] + ա կ ր[կ]) = f(x[կ] + ար [կ]) .

Քառակուսային ֆունկցիայի համար

Ֆլետչեր-Ռիվսի կոնյուգացիոն գրադիենտ մեթոդի ալգորիթմը հետևյալն է.

1. Կետում Xհաշվարկված էջ = -f'(x) .

2. Միացված k-մ քայլ, օգտագործելով վերը նշված բանաձեւերը, քայլը որոշվում է Ակ . և ժամանակաշրջան X[k+ 1].

3. Արժեքները հաշվարկված են f(x[կ+1]) Եվ f'(x[կ+1]) .

4. Եթե f'(x) = 0, ապա կետ X[կ+1] ֆունկցիայի նվազագույն կետն է f(x).Հակառակ դեպքում որոշվում է նոր ուղղություն էջ[կ+l] հարաբերությունից

և անցում է կատարվում հաջորդ կրկնությանը: Այս ընթացակարգը կգտնի քառակուսի ֆունկցիայի նվազագույնը ոչ ավելի, քան Պքայլերը. Ոչ քառակուսային ֆունկցիաները նվազագույնի հասցնելիս Ֆլետչեր-Ռիվսի մեթոդը վերջավորից դառնում է կրկնվող: Այս դեպքում, հետո (p+ 1) 1-4-րդ ընթացակարգի կրկնությունը ցիկլային կերպով կրկնվում է փոխարինմամբ Xվրա X[Պ+1] , և հաշվարկներն ավարտվում են , որտեղ տրված թիվ է: Այս դեպքում օգտագործվում է մեթոդի հետևյալ փոփոխությունը.

x[ կ+l] = x[կ]+a k p[կ],

p[ կ] = -f'(x[կ])+ բ k- 1 էջ[կ-l], կ>= 1;

p = -f'( x);

f(x[ կ] + ա կ պ[կ]) = f(x[կ] +ap[կ];

.

Այստեղ Ի- շատ ինդեքսներ. Ի= (0, n, 2 p, աշխատավարձ, ...), այսինքն՝ մեթոդը թարմացվում է ամեն անգամ Պքայլերը.

Երկրաչափական իմաստԿոնյուգացիոն գրադիենտ մեթոդը հետևյալն է (նկ. 2.11). Տրված ելակետից Xվայրէջքն իրականացվում է ուղղությամբ Ռ = -f» (x) Կետում Xորոշվում է գրադիենտ վեկտորը f» (x) Քանի որ Xֆունկցիայի նվազագույն կետն է ուղղությամբ Ռ, Դա f'(x) ուղղանկյուն դեպի վեկտոր Ռ. Այնուհետև գտնվում է վեկտորը Ռ , Հ- միացնել Ռ. Հաջորդը, մենք գտնում ենք գործառույթի նվազագույնը ուղղության երկայնքով Ռև այլն:

Բրինձ. 2.11 . Նվազման հետագիծը կոնյուգացիոն գրադիենտ մեթոդով

Կոնյուգացիոն ուղղության մեթոդներն ամենաարդյունավետներից են նվազագույնի հասցնելու խնդիրները լուծելու համար: Այնուամենայնիվ, պետք է նշել, որ նրանք զգայուն են այն սխալների նկատմամբ, որոնք տեղի են ունենում հաշվման գործընթացում: Մեծ թվով փոփոխականների դեպքում սխալը կարող է այնքան մեծանալ, որ գործընթացը պետք է կրկնվի նույնիսկ քառակուսի ֆունկցիայի համար, այսինքն՝ դրա համար գործընթացը միշտ չէ, որ տեղավորվում է Պքայլերը.

Ամենակտրուկ վայրէջքի մեթոդը (անգլերեն գրականության մեջ «մեթոդ ամենից կտրուկ վայրէջք») օպտիմալացման խնդիրների լուծման կրկնվող թվային մեթոդ է (առաջին կարգի), որը թույլ է տալիս որոշել օբյեկտիվ ֆունկցիայի ծայրահեղությունը (նվազագույնը կամ առավելագույնը).

իրական տիրույթում ֆունկցիայի փաստարկի (վերահսկվող պարամետրերի) արժեքներն են:

Համաձայն դիտարկվող մեթոդի՝ օբյեկտիվ ֆունկցիայի ծայրահեղությունը (առավելագույնը կամ նվազագույնը) որոշվում է ֆունկցիայի ամենաարագ աճի (նվազման) ուղղությամբ, այսինքն. ֆունկցիայի գրադիենտի (հակագրադիենտ) ուղղությամբ։ Գրադիենտ ֆունկցիա մի կետում վեկտոր է, որի ելքերը կոորդինատային առանցքների վրա ֆունկցիայի մասնակի ածանցյալներն են կոորդինատների նկատմամբ.

որտեղ i, j,…, n-ը կոորդինատային առանցքներին զուգահեռ միավոր վեկտորներ են:

Գրադիենտ բազային կետում մակերեսի նկատմամբ խիստ ուղղանկյուն է, և դրա ուղղությունը ցույց է տալիս ֆունկցիայի ամենաարագ աճի ուղղությունը, իսկ հակառակ ուղղությունը (հակագրադիենտ), համապատասխանաբար, ցույց է տալիս ֆունկցիայի ամենաարագ նվազման ուղղությունը։

Ամենակտրուկ վայրէջքի մեթոդն է հետագա զարգացումգրադիենտ ծագման մեթոդ. Ընդհանուր առմամբ, ֆունկցիայի էքստրեմումը գտնելու գործընթացը կրկնվող ընթացակարգ է, որը գրված է հետևյալ կերպ.

որտեղ «+» նշանն օգտագործվում է ֆունկցիայի առավելագույնը գտնելու համար, իսկ «-» նշանը՝ ֆունկցիայի նվազագույնը գտնելու համար.

Միավոր ուղղության վեկտորը, որը որոշվում է բանաձևով.

- գրադիենտ մոդուլը որոշում է ֆունկցիայի աճի կամ նվազման արագությունը գրադիենտի կամ հակագրադիենտի ուղղությամբ.

Հաստատուն, որը որոշում է քայլի չափը և նույնն է բոլոր i-րդ ուղղությունների համար:

Քայլի չափն ընտրվում է շարժման ուղղությամբ f(x) օբյեկտիվ ֆունկցիայի նվազագույնի պայմանից, այսինքն՝ գրադիենտի կամ հակագրադիենտի ուղղությամբ միաչափ օպտիմալացման խնդրի լուծման արդյունքում.

Այլ կերպ ասած, քայլի չափը որոշվում է այս հավասարումը լուծելով.

Այսպիսով, հաշվարկման քայլն ընտրվում է այնպես, որ շարժումն իրականացվում է այնքան ժամանակ, մինչև ֆունկցիան բարելավվի՝ այդպիսով ինչ-որ պահի հասնելով ծայրահեղության: Այս պահին նորից որոշվում է որոնման ուղղությունը (օգտագործելով գրադիենտ) և որոնվում է օբյեկտիվ ֆունկցիայի նոր օպտիմալ կետ և այլն։ Այսպիսով, այս մեթոդով որոնումը տեղի է ունենում ավելի մեծ քայլերով, և ֆունկցիայի գրադիենտը հաշվարկվում է ավելի փոքր թվով կետերում:

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

Շարժման հետագիծը դեպի ծայրամասային կետ՝ օգտագործելով ամենաթռիչ վայրէջքի մեթոդը, որը ցույց է տրված f(x) ֆունկցիայի հավասար մակարդակի գծի գրաֆիկում:

Օպտիմալ լուծման որոնումն ավարտվում է, երբ գտնվում է կրկնվող հաշվարկի քայլում (մի քանի չափանիշներ).

Որոնման հետագիծը մնում է ընթացիկ որոնման կետի փոքր հարևանությամբ.

Օբյեկտիվ ֆունկցիայի աճը չի փոխվում.

Օբյեկտիվ ֆունկցիայի գրադիենտը տեղական նվազագույն կետում դառնում է զրո.

Հարկ է նշել, որ գրադիենտ վայրէջքի մեթոդը կիրճի երկայնքով շարժվելիս շատ դանդաղ է ստացվում, և քանի որ օբյեկտիվ ֆունկցիայի փոփոխականների թիվը մեծանում է, մեթոդի այս վարքագիծը դառնում է բնորոշ: Ձորը իջվածք է, որի մակարդակի գծերը մոտավորապես ունեն բազմապատիկ տարբեր կիսաանցքերով էլիպսների տեսք։ Ձորի առկայության դեպքում վայրէջքի հետագիծը փոքր քայլով ստանում է զիգզագ գծի ձև, որի արդյունքում իջնելու արագությունը նվազագույնի է հասցվում: Դա բացատրվում է նրանով, որ այդ ֆունկցիաների հակագրադիենտի ուղղությունը էականորեն շեղվում է ուղղությունից մինչև նվազագույն կետ, ինչը հանգեցնում է հաշվարկի լրացուցիչ ուշացման։ Արդյունքում ալգորիթմը կորցնում է հաշվողական արդյունավետությունը։

Ջրհեղեղի ֆունկցիա

Գրադիենտ մեթոդը, իր բազմաթիվ փոփոխություններով հանդերձ, լայն տարածում ունի և արդյունավետ մեթոդուսումնասիրվող օբյեկտների օպտիմալի որոնում: Գրադիենտ որոնման թերությունն այն է, որ այն օգտագործելիս կարելի է հայտնաբերել ֆունկցիայի միայն տեղական ծայրահեղությունը։ Ուրիշներին գտնելու համար տեղական ծայրահեղություններանհրաժեշտ է փնտրել այլ ելակետերից։ Նաև կոնվերգենցիայի արագությունը գրադիենտ մեթոդներնաև զգալիորեն կախված է գրադիենտի հաշվարկների ճշգրտությունից: Ճշգրտության կորուստը, որը սովորաբար տեղի է ունենում նվազագույն կետերի մոտակայքում կամ հեղեղատային իրավիճակում, ընդհանուր առմամբ կարող է խաթարել գրադիենտ վայրէջքի գործընթացի մերձեցումը:

Հաշվարկի մեթոդ

Քայլ 1:Գործառույթի գրադիենտը հաշվարկելու համար վերլուծական արտահայտությունների սահմանում (խորհրդանշական ձևով)

Քայլ 2Սահմանեք նախնական մոտավորությունը

Քայլ 3:Որոշվում է վերջին որոնման ուղղությունը վերականգնելու ալգորիթմական ընթացակարգը վերագործարկելու անհրաժեշտությունը: Վերագործարկման արդյունքում նորից որոնողական աշխատանքներ են իրականացվում ամենաարագ վայրէջքի ուղղությամբ։