Ֆունկցիան մուտքագրելու կանոններ
IN ամենադաժան վայրէջքի մեթոդըՈրպես որոնման ուղղություն ընտրվում է վեկտորը, որի ուղղությունը հակառակ է ▽f(x) ֆունկցիայի գրադիենտ վեկտորի ուղղությանը: Սկսած մաթեմատիկական վերլուծությունՀայտնի է, որ f(x)=▽f(x) վեկտորը բնութագրում է ֆունկցիայի ամենաարագ աճի ուղղությունը (տես ֆունկցիայի գրադիենտ): Հետևաբար, կոչվում է վեկտորը՝ grad f (X) = -▽f(X): հակագրադիենտև նրա ամենաարագ նվազման ուղղությունն է։ Կրկնվող կապը, որով իրականացվում է ամենադաժան վայրէջքի մեթոդը, ունի X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
որտեղ λ k >0 քայլի չափն է: Կախված քայլի չափի ընտրությունից, կարող եք ստանալ տարբեր տարբերակներ գրադիենտ մեթոդ. Եթե օպտիմիզացման գործընթացում քայլի չափը λ ամրագրված է, ապա մեթոդը կոչվում է գրադիենտ մեթոդ՝ դիսկրետ քայլով։ Օպտիմալացման գործընթացը առաջին կրկնություններում կարող է զգալիորեն արագացվել, եթե λ k ընտրվի λ k =min f(X k + λS k) պայմանից:
λ k-ն որոշելու համար օգտագործվում է ցանկացած միաչափ օպտիմալացման մեթոդ։ Այս դեպքում մեթոդը կոչվում է ամենից կտրուկ վայրէջքի մեթոդ: Որպես կանոն, մեջ ընդհանուր դեպքԳործառույթի նվազագույնին հասնելու համար մեկ քայլը բավարար չէ, գործընթացը կրկնվում է այնքան ժամանակ, մինչև հետագա հաշվարկները թույլ տան արդյունքի բարելավում:
Եթե որոշ փոփոխականներում տարածությունը շատ երկարաձգված է, ապա ձևավորվում է «կիրճ»: Որոնումը կարող է դանդաղել և զիգզագով անցնել «կիրճի» հատակով։ Երբեմն լուծումը հնարավոր չէ ստանալ ընդունելի ժամկետներում:
Մեթոդի մեկ այլ թերություն կարող է լինել դադարեցման չափանիշը ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
Օրինակ. Սկսելով x k =(-2, 3) կետից՝ որոշեք x k +1 կետը, օգտագործելով ամենադաժան վայրէջքի մեթոդը՝ ֆունկցիան նվազագույնի հասցնելու համար:
Որպես որոնման ուղղություն, ընտրեք գրադիենտ վեկտորը ընթացիկ կետում 
Եկեք ստուգենք կանգառի չափանիշը. Մենք ունենք 
Հաշվարկենք ֆունկցիայի արժեքը սկզբնական կետում f(X 1) = 35. Եկեք անենք.
քայլեք հակագրադիենտ ուղղությամբ
Հաշվարկենք ֆունկցիայի արժեքը նոր կետում
f(X 2) = 3(-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1)(3-8λ 1) - 4(-2 + 19λ 1)
Եկեք գտնենք այնպիսի քայլ, որ այս ուղղությամբ օբյեկտիվ ֆունկցիան հասնի նվազագույնի: Ֆունկցիայի էքստրեմումի գոյության անհրաժեշտ պայմանից
f’(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 - 304 λ 1) – 4*19
կամ f’(X 2) = 2598 λ 1 – 425 = 0:
Մենք ստանում ենք քայլ λ 1 = 0,164
Այս քայլն ավարտելը կհանգեցնի կետին 
որում գրադիենտ արժեքը 
, ֆունկցիայի արժեքը f(X 2) = 0,23: Ճշգրտությունը չի ստացվում, այն պահից, երբ մենք քայլ ենք անում հակագրադիենտի ուղղությամբ:
f(X 2) = 3(1.116 – 1.008λ 1) 2 + (1.688-2.26λ 1) 2 - (1.116 – 1.008λ 1)(1.688-2.26λ 1) - 4(1.116 – 1.008λ)
f’(X 2) = 11,76 – 6,12λ 1 = 0
Մենք ստանում ենք λ 1 = 0,52 
Խնդրի ձևակերպում
Թող ֆունկցիան տրվի f(x) Rn
Պահանջվում է f(x) X = Rn
Որոնման ռազմավարություն
x k
} , k = 0.1,...,
այնպիսին է, որ 
, k = 0,1,...
. Հերթական կետեր ( x k
) հաշվարկվում են ըստ կանոնի
որտեղ է կետը x 0 օգտագործողի կողմից սահմանված; քայլի չափը tk որոշվում է յուրաքանչյուր արժեքի համար կ վիճակից
Խնդիրը (3) կարող է լուծվել՝ օգտագործելով անհրաժեշտ նվազագույն պայմանը, որին հաջորդում է բավարար նվազագույն պայմանի ստուգումը: Այս ուղին կարող է օգտագործվել կամ բավականաչափ պարզ գործառույթով, որպեսզի նվազագույնի հասցվի, կամ բավականաչափ նախնական մոտավորությամբ բարդ գործառույթ 
բազմանդամ P(t k)
(սովորաբար երկրորդ կամ երրորդ աստիճանի), իսկ հետո պայմանը փոխարինվում է պայմանով, իսկ պայմանը պայմանով. 
Հերթականություն (xk)
ավարտվում է կետով x k
, որի համար , որտեղ ε
- տրված փոքր դրական թիվ, կամ k ≥ Մ
, Որտեղ Մ
- կրկնությունների սահմանափակ թվով կամ երկու անհավասարությունների միաժամանակյա կատարմամբ 
, 
Որտեղ ε 2
- փոքր դրական թիվ: Հարցն այն է, թե արդյոք կարող է մի կետ x k
համարել որպես ցանկալի տեղական նվազագույն կետի հայտնաբերված մոտարկում x*
, լուծվում է լրացուցիչ հետազոտության միջոցով։
Մեթոդի երկրաչափական մեկնաբանությունը համար n=2 Նկ. 4.
Կոորդինատիվ ծագման մեթոդ
Խնդրի ձևակերպում
Թող ֆունկցիան տրվի f(x) , սահմանափակված ներքևում նկարահանման հրապարակում Rn և ունենալով շարունակական մասնակի ածանցյալներ իր բոլոր կետերում:
f(x) իրագործելի լուծումների հավաքածուի վրա X = Rn , այսինքն. գտնել այնպիսի կետ, որ
Որոնման ռազմավարություն
Խնդիրը լուծելու ռազմավարությունը կետերի հաջորդականություն կառուցելն է ( x k
} , k = 0.1,...,
այնպիսին է, որ , k = 0,1,...
. Հերթական կետեր ( x k
) հաշվարկվում են ցիկլերով՝ կանոնին համապատասխան
(4)
Որտեղ ժ - հաշվարկային ցիկլի համարը; j = 0,1,2,...; կ - կրկնության համարը օղակի ներսում, k = 0,1,... ,n - 1; e k +1, k = 0,l,...,n - 1 - միավորի վեկտոր, (k+1) -որի պրոյեկցիան հավասար է 1-ի; կետ x 00 օգտագործողի կողմից սահմանված, քայլի չափը tk ընտրված է պայմանից
կամ 
.
Եթե ընտրված պայմանը ընթացիկ tk
չի կատարվում, քայլը կիսով չափ կրճատվել է և ժամկետը 
կրկին հաշվարկվում է. Հեշտ է տեսնել, որ ֆիքսված j-ի համար թվի հետ մեկ կրկնություն կ
կետի միայն մեկ պրոյեկցիա է փոխվում x jk
, ունենալով համար k+1
, և ամբողջ ցիկլի ընթացքում թվով ժ
, այսինքն. սկսած k = 0
և վերջ k = n -1
, կետի բոլոր n կանխատեսումները փոխվում են x j0
. Այս կետից հետո x j n
համարը նշանակված է x j + 1.0
, և այն ընդունվում է որպես ելակետ հաշվարկների համար j+1
ցիկլը. Հաշվարկն ավարտվում է կետում x jk
երբ հաշվառման ավարտի երեք չափանիշներից առնվազն մեկը բավարարված է. 
, կամ , կամ անհավասարությունների կրկնակի կատարում։
Հաշվարկների արդյունքում ստացված միավորները կարելի է գրել որպես հաջորդականության տարրեր (xl), Որտեղ l=n*j+k - կետի հերթական համարը,
n = 2-ի մեթոդի երկրաչափական մեկնաբանությունը ներկայացված է Նկ. 5.
4. Ֆրանկ-Վուլֆի մեթոդ .
Ենթադրենք, մենք պետք է գտնենք գոգավոր ֆունկցիայի առավելագույն արժեքը
Պայմաններով
Այս խնդրի բնորոշ առանձնահատկությունն այն է, որ նրա սահմանափակումների համակարգը պարունակում է միայն գծային անհավասարություններ: Այս հատկանիշը հիմք է հանդիսանում ուսումնասիրվող կետի շրջակայքում ոչ գծայինը փոխարինելու համար օբյեկտիվ գործառույթգծային, որի շնորհիվ սկզբնական խնդրի լուծումը վերածվում է գծային ծրագրավորման խնդիրների հաջորդական լուծման։
Խնդրի լուծում գտնելու գործընթացը սկսվում է խնդրի իրագործելի լուծումների տարածաշրջանին պատկանող կետի բացահայտմամբ։
270
ամառանոցներ Թող սա լինի կետը X(k)
ապա այս պահին հաշվարկվում է ֆունկցիայի գրադիենտը (57):
Եվ կառուցիր գծային ֆունկցիա
Այնուհետև գտեք այս ֆունկցիայի առավելագույն արժեքը (58) և (59) սահմանափակումներով: Թող այս խնդրի լուծումը որոշվի կետով Z(k)
. Այնուհետև կետի կոորդինատները վերցվում են որպես սկզբնական խնդրի նոր իրագործելի լուծում X(k+1)
:
Որտեղ λk - որոշակի թիվ, որը կոչվում է հաշվարկման քայլ և փակվում է զրոյի և մեկի միջև (0<λk < 1). Это число λk կամայականորեն կամ որոշված
այնպես, որ ֆունկցիայի արժեքը կետում X (k +1) f(X (k +1)) , կախված λk , առավելագույնն էր։ Դա անելու համար հարկավոր է գտնել հավասարման լուծում և ընտրել դրա ամենափոքր արմատը: Եթե դրա արժեքը մեկից մեծ է, ապա պետք է դնել λk=1 . Թիվը որոշելուց հետո λk գտնել կետի կոորդինատները X(k+1) հաշվարկել դրա մեջ գտնվող օբյեկտիվ ֆունկցիայի արժեքը և որոշել նոր կետ տեղափոխվելու անհրաժեշտությունը X(k+2) . Եթե կա նման անհրաժեշտություն, ապա հաշվարկեք կետում X(k+1) օբյեկտիվ ֆունկցիայի գրադիենտ, անցի՛ր համապատասխան գծային ծրագրավորման խնդրին և գտիր դրա լուծումը։ Որոշե՛ք կետի կոորդինատները և X(k+2) և ուսումնասիրել հետագա հաշվարկների անհրաժեշտությունը: Վերջնական թվով քայլերից հետո սկզբնական խնդրի լուծումը ստացվում է պահանջվող ճշգրտությամբ:
Այսպիսով, Ֆրանկ-Վուլֆի մեթոդով (57) - (59) խնդրի լուծում գտնելու գործընթացը ներառում է հետևյալ փուլերը.:
1. Որոշել խնդրի սկզբնական իրագործելի լուծումը:
2. Գտե՛ք (57) ֆունկցիայի գրադիենտը թույլատրելի լուծման կետում:
3. Կառուցեք ֆունկցիան (60) և գտեք դրա առավելագույն արժեքը (58) և (59) պայմաններում:
4. Որոշեք հաշվարկի քայլը:
5. Օգտագործելով (61) բանաձևերը, գտնում են նոր իրագործելի լուծման բաղադրիչները:
6. Ստուգեք հաջորդ իրագործելի լուծմանը անցնելու անհրաժեշտությունը: Անհրաժեշտության դեպքում անցեք 2-րդ փուլին, հակառակ դեպքում գտնվում է սկզբնական խնդրի ընդունելի լուծում:
Տուգանքների գործառույթների մեթոդ.
Դիտարկենք գոգավոր ֆունկցիայի առավելագույն արժեքը որոշելու խնդիրը
f (x 1, x 2, .... x n)պայմաններով g i (x 1, x 2, .... x n) ≤ b i (i=l, m) , x j ≥ 0 (j=1, n) , Որտեղ g i (x 1, x 2, .... x n) - ուռուցիկ գործառույթներ.
Այս խնդիրը ուղղակիորեն լուծելու փոխարեն գտե՛ք ֆունկցիայի առավելագույն արժեքը F(x 1, x 2, ...., x n)= f(x 1, x 2, ...., x n) +H(x 1, x 2, ...., x n) որը խնդրի օբյեկտիվ ֆունկցիայի և որոշ ֆունկցիայի գումարն է
H(x 1, x 2, ...., x n), սահմանվել է սահմանափակումների համակարգով եւ կոչվել տուգանային գործառույթ. Տուգանքի գործառույթը կարող է կառուցվել տարբեր ձևերով. Այնուամենայնիվ, ամենից հաճախ դա կարծես
Ա a i > 0
- որոշ հաստատուն թվեր, որոնք ներկայացնում են կշռման գործակիցները:
Օգտագործելով տուգանային ֆունկցիան, նրանք հաջորդաբար տեղափոխվում են մի կետից մյուսը, մինչև ստանան ընդունելի լուծում: Այս դեպքում բանաձևով հայտնաբերվում են հաջորդ կետի կոորդինատները
Վերջին կապից հետևում է, որ եթե նախորդ կետը գտնվում է սկզբնական խնդրի իրագործելի լուծումների շրջանում, ապա քառակուսի փակագծերում երկրորդ անդամը հավասար է զրոյի, և հաջորդ կետին անցումը որոշվում է միայն նպատակի գրադիենտով. ֆունկցիան։ Եթե նշված կետը չի պատկանում թույլատրելի լուծումների շրջանին, ապա այս տերմինի շնորհիվ հետագա կրկնություններում ձեռք է բերվում վերադարձ դեպի թույլատրելի լուծումների շրջան.
որոշումները. Միեւնույն ժամանակ, այնքան քիչ ա i
, որքան արագ է գտնվում ընդունելի լուծումը, բայց դրա որոշման ճշգրտությունը նվազում է։ Հետևաբար, կրկնվող գործընթացը սովորաբար սկսվում է համեմատաբար փոքր արժեքներից ա i
և, շարունակելով այն, այդ արժեքներն աստիճանաբար աճում են։
Այսպիսով, ուռուցիկ ծրագրավորման խնդրի լուծում գտնելու գործընթացը տուգանքի ֆունկցիայի մեթոդով ներառում է հետևյալ քայլերը.
1. Որոշեք նախնական իրագործելի լուծումը:
2. Ընտրեք հաշվարկի քայլը:
3. Բոլոր փոփոխականների համար գտեք օբյեկտիվ ֆունկցիայի և ֆունկցիաների մասնակի ածանցյալները, որոնք որոշում են խնդրի իրագործելի լուծումների շրջանակը:
4. Օգտագործելով (72) բանաձևը, գտնվում են խնդրի հնարավոր նոր լուծումը որոշող կետի կոորդինատները:
5. Ստուգեք, արդյոք գտնված կետի կոորդինատները բավարարում են խնդրի սահմանափակումների համակարգին: Եթե ոչ, ապա անցեք հաջորդ փուլ: Եթե գտնված կետի կոորդինատները որոշում են խնդրի թույլատրելի լուծումը, ապա ուսումնասիրվում է հաջորդ թույլատրելի լուծմանն անցնելու անհրաժեշտությունը: Անհրաժեշտության դեպքում անցեք 2-րդ փուլին, հակառակ դեպքում գտնվել է սկզբնական խնդրի ընդունելի լուծում:
6. Սահմանեք կշռման գործակիցների արժեքները և անցեք 4-րդ քայլին:
Arrow-Hurwitz մեթոդ.
Տուգանային ֆունկցիայի մեթոդով ոչ գծային ծրագրավորման խնդիրների լուծումներ գտնելիս մենք ընտրել ենք արժեքները ա i , կամայականորեն, ինչը հանգեցրել է իրագործելի լուծումների շրջանից որոշված կետերի հեռավորության զգալի տատանումների։ Այս թերությունը վերացվում է Arrow-Hurwitz մեթոդով խնդիրը լուծելիս, ըստ որի հաջորդ քայլում թվերը. a i (k) հաշվարկված բանաձևով
Որպես սկզբնական արժեքներ a i (0) վերցնել կամայական ոչ բացասական թվեր.
ՕՐԻՆԱԿ ԼՈՒԾՄԱՆ
Օրինակ 1.
Գտեք ֆունկցիայի տեղական նվազագույնը
Կետի սահմանում x k
1. Եկեք սահմանենք.
2. Դնենք k = 0 .
երեսուն. Եկեք հաշվարկենք
4 0 . Եկեք հաշվարկենք 
. Անցնենք 5-րդ քայլին:
50 . Եկեք ստուգենք վիճակը 
. Անցնենք 6-րդ քայլին:
6 0 . Եկեք սահմանենք t0 = 0,5 .
7 0 . Եկեք հաշվարկենք
8 0 . Եկեք համեմատենք 
. Մենք ունենք 
. Եզրակացություն՝ պայման k = 0
չի կատարվում։ Եկեք սահմանենք t0 = 0,25
, շարունակեք կրկնել 7, 8 քայլերը:
7 01. Եկեք հաշվարկենք.
8 01. Եկեք համեմատենք f (x 1) և f (x 0) . Եզրակացություն: f (x 1)< f (x 0) . Անցնենք 9-րդ քայլին:
9 0 . Եկեք հաշվարկենք
Եզրակացություն՝ մենք հավատում ենք k =1 և անցեք 3-րդ քայլին:
3 1. Եկեք հաշվարկենք
4 1. Եկեք հաշվարկենք 
. Անցնենք 5-րդ քայլին:
5 1. Եկեք ստուգենք վիճակը k ≥ M: k = 1< 10 = M . Անցնենք 6-րդ քայլին:
6 1. Եկեք սահմանենք t 1 = 0,25:
7 1. Եկեք հաշվարկենք
8 1. Եկեք համեմատենք f (x 2) f (x 1) հետ . Եզրակացություն: f (x 2)< f (х 1). Անցնենք 9-րդ քայլին:
9 1. Եկեք հաշվարկենք
Եզրակացություն՝ մենք հավատում ենք k = 2 և անցեք 3-րդ քայլին:
3 2. Եկեք հաշվարկենք
4 2 . Եկեք հաշվարկենք. Անցնենք 5-րդ քայլին:
5 2. Եկեք ստուգենք վիճակը k ≥ Մ : k = 2< 10 = М , անցեք 6-րդ քայլին։
6 2. Եկեք սահմանենք t 2 =0,25 .
7 2. Եկեք հաշվարկենք
8 2. Եկեք համեմատենք f (x 3) Եվ f (x 2) . Եզրակացություն: f (x 3)< f (х 2) .Անցեք 9-րդ քայլին:
9 2. Եկեք հաշվարկենք 
Եզրակացություն՝ մենք հավատում ենք k = 3 և անցեք 3-րդ քայլին:
3 3 . Եկեք հաշվարկենք
4 3 . Եկեք հաշվարկենք. Անցնենք 5-րդ քայլին:
5 3. Եկեք ստուգենք վիճակը k ≥ Մ : k = 3<10 = М , անցեք 6-րդ քայլին։
6 3. Եկեք սահմանենք t 3 = 0,25:
7 3. Եկեք հաշվարկենք
8 3. Եկեք համեմատենք f (x 4) Եվ f (x 3) : f (x 4)< f (х 3) .
9 3. Եկեք հաշվարկենք 
Պայմանները բավարարվում են, երբ k = 2,3 . Հաշվարկ
ավարտված. Կետը գտնվեց
Նկ. Ստացված 3 կետերը միացված են կետագծով։
II. Կետերի վերլուծություն x 4 .
Գործառույթ 
կրկնակի տարբերակելի է, ուստի մենք կետում կստուգենք նվազագույնի բավարար պայմանները x 4
. Դա անելու համար եկեք վերլուծենք Հեսսիական մատրիցը:
Մատրիցը հաստատուն է և դրական որոշակի (այսինքն. . H > 0
) քանի որ նրա երկու անկյունային փոքրերը դրական են: Հետեւաբար, կետը 
տեղական նվազագույն կետի և արժեքի հայտնաբերված մոտարկումն է 
արժեքի հայտնաբերված մոտարկումն է f (x *) =0
. Նշենք, որ պայմանը H > 0
, միաժամանակ կա ֆունկցիայի խիստ ուռուցիկության պայման 
. Հետևաբար, գտնվել են գլոբալ նվազագույն կետի մոտարկումներ f(x)
և դրա նվազագույն արժեքը Ռ 2
. ■
Օրինակ 2
Գտեք ֆունկցիայի տեղական նվազագույնը
I. Կետի սահմանում x k, որում բավարարված է հաշվարկները լրացնելու չափանիշներից առնվազն մեկը։
1. Եկեք սահմանենք.
Եկեք կամայական կետում գտնենք ֆունկցիայի գրադիենտը
2. Դնենք k = 0 .
երեսուն. Եկեք հաշվարկենք
4 0 . Եկեք հաշվարկենք . Անցնենք 5-րդ քայլին:
50 . Եկեք ստուգենք վիճակը 
. Անցնենք 6-րդ քայլին:
6° Հաջորդ կետը հայտնաբերվում է բանաձևով
Ստացված արտահայտությունները փոխարինենք կոորդինատներով
Գտնենք ֆունկցիայի նվազագույնը f(t 0) Ըստ t 0 օգտագործելով անհրաժեշտ պայմանները անվերապահ ծայրահեղության համար.
Այստեղից t 0 = 0,24
. Որովհետեւ 
, գտնված քայլի արժեքը ապահովում է ֆունկցիայի նվազագույնը f(t 0)
Ըստ t 0
.
Եկեք սահմանենք 
7 0 . Մենք կգտնենք
8°. Եկեք հաշվարկենք
Եզրակացություն՝ մենք հավատում ենք k = 1 և անցեք 3-րդ քայլին:
3 1. Եկեք հաշվարկենք
4 1. Եկեք հաշվարկենք 
5 1. Եկեք ստուգենք վիճակը k ≥ 1: k = 1< 10 = М.
6 1. Եկեք սահմանենք
7 1. Մենք կգտնենք 
:
8 1. Եկեք հաշվարկենք
Մենք հավատում ենք k = 2 և անցեք 3-րդ քայլին:
3 2. Եկեք հաշվարկենք
4 2 . Եկեք հաշվարկենք
5 2. Եկեք ստուգենք վիճակը k ≥ M: k = 2< 10 = M .
6 2. Եկեք սահմանենք
7 2. Մենք կգտնենք 
8 2. Եկեք հաշվարկենք
Մենք հավատում ենք k =3 և անցեք 3-րդ քայլին:
3 3 . Եկեք հաշվարկենք
4 3 . Եկեք հաշվարկենք.
Հաշվարկն ավարտված է։ Կետը գտնվեց
II. Կետերի վերլուծություն x 3 .
Օրինակ 1.1-ում (Գլուխ 2 §1) ցույց է տրվել, որ ֆունկցիան f(x) խիստ ուռուցիկ է և, հետևաբար, 3 կետերում գլոբալ նվազագույն կետի հայտնաբերված մոտարկումն է X* .
Օրինակ 3.
Գտեք ֆունկցիայի տեղական նվազագույնը
I. Կետի սահմանում xjk , որում բավարարված է հաշվարկները լրացնելու չափանիշներից առնվազն մեկը։
1. Եկեք սահմանենք
Եկեք կամայական կետում գտնենք ֆունկցիայի գրադիենտը 
2. Եկեք սահմանենք j = 0:
երեսուն. Եկեք ստուգենք՝ արդյոք պայմանը բավարարված է
4 0 . Եկեք սահմանենք k = 0:
50 . Եկեք ստուգենք՝ արդյոք պայմանը բավարարված է
6 0 . Եկեք հաշվարկենք
7 0 . Եկեք ստուգենք վիճակը 
8 0 . Եկեք սահմանենք
9 0 . Եկեք հաշվարկենք 
, Որտեղ
100 . Եկեք ստուգենք վիճակը
Եզրակացություն. մենք ենթադրում ենք և անցնում 9-րդ քայլին:
9 01. Եկեք հաշվարկենք x 01 ավելացումներով
10 01. Եկեք ստուգենք վիճակը 
11 0 . Եկեք ստուգենք պայմանները
Մենք հավատում ենք k =1 և անցեք 5-րդ քայլին:
5 1. Եկեք ստուգենք վիճակը
6 1. Եկեք հաշվարկենք
7 1. Եկեք ստուգենք վիճակը
8 1. Եկեք սահմանենք
9 1. Եկեք հաշվարկենք
10 1. Եկեք ստուգենք վիճակը 
:
11 1. Եկեք ստուգենք պայմանները
Մենք հավատում ենք k = 2 , անցեք 5-րդ քայլին։
5 2. Եկեք ստուգենք վիճակը: Եկեք սահմանենք, անցնենք 3-րդ քայլին:
3 1. Եկեք ստուգենք վիճակը
4 1. Եկեք սահմանենք k = 0:
5 2. Եկեք ստուգենք վիճակը
6 2. Եկեք հաշվարկենք
7 2. Եկեք ստուգենք վիճակը
8 2. Եկեք սահմանենք
9 2. Եկեք հաշվարկենք
10 2. Եկեք ստուգենք վիճակը 
11 2. Եկեք ստուգենք պայմանները
Մենք հավատում ենք k =1 և անցեք 5-րդ քայլին:
5 3. Եկեք ստուգենք վիճակը
6 3. Եկեք հաշվարկենք
7 3. Եկեք ստուգենք պայմանները
8 3. Եկեք սահմանենք
9 3. Եկեք հաշվարկենք
10 3. Եկեք ստուգենք վիճակը 
11 3. Եկեք ստուգենք պայմանները
Եկեք սահմանենք k = 2 և անցեք 5-րդ քայլին:
5 4 . Եկեք ստուգենք վիճակը 
Մենք հավատում ենք j = 2, x 20 = x 12 և անցեք 3-րդ քայլին:
3 2. Եկեք ստուգենք վիճակը
4 2 . Եկեք սահմանենք k =0 .
5 4 . Եկեք ստուգենք վիճակը
6 4. Եկեք հաշվարկենք
7 4. Եկեք ստուգենք վիճակը
8 4. Եկեք սահմանենք
9 4. Եկեք հաշվարկենք
10 4. Եկեք ստուգենք վիճակը և անցնենք 11-րդ քայլին:
11 4. Եկեք ստուգենք պայմանները
Պայմանները բավարարվում են թվերով երկու հաջորդական ցիկլերում j = 2 Եվ j -1= 1 . Հաշվարկն ավարտված է, կետը գտնվել է
Նկ. Ստացված 6 կետերը միացված են կետագծով։
Կոորդինատային վայրէջքի մեթոդով մենք իջնում ենք կոտրված գծով, որը բաղկացած է կոորդինատային առանցքներին զուգահեռ ուղիղ հատվածներից։
II. x21 կետի վերլուծություն.
Օրինակ 1.1-ում ցույց է տրվել, որ ֆունկցիան f(x)
խիստ ուռուցիկ է, ունի եզակի նվազագույն և, հետևաբար, կետ 
գլոբալ նվազագույն կետի հայտնաբերված մոտարկումն է։
Վերը քննարկված բոլոր գրադիենտ մեթոդներում կետերի հաջորդականությունը (xk) համընկնում է ֆունկցիայի անշարժ կետին f(x) այս ֆունկցիայի հատկությունների վերաբերյալ բավականին ընդհանուր առաջարկություններով: Մասնավորապես, թեորեմը ճիշտ է.
Թեորեմ. Եթե f(x) ֆունկցիան սահմանափակված է ստորև, նրա գրադիենտը բավարարում է Լիպշիցի պայմանը () և արժեքի ընտրությունը: tn արտադրված վերը նկարագրված մեթոդներից մեկով, այնուհետև ինչ էլ որ լինի ելակետը x 0 :
ժամը .
Սխեմայի գործնական իրականացման մեջ
k =1, 2, … n.
կրկնությունները դադարում են, եթե բոլորի համար i, i = 1, 2, ..., n , այնպիսի պայմաններ, ինչպիսիք են
,
որտեղ է նվազագույնը գտնելու ճշգրտությունը բնութագրող որոշակի թիվ:
Թեորեմի պայմաններում գրադիենտ մեթոդը ապահովում է ֆունկցիայի կամ ճշգրիտ ստորին սահմանի կոնվերգենցիան (եթե ֆունկցիան f(x) չունի նվազագույն; բրինձ. 7), կամ ինչ-որ անշարժ կետում ֆունկցիայի արժեքին, որը հաջորդականության սահմանն է (x k). Դժվար չէ օրինակներ բերել, երբ այս պահին իրականացվում է թամբ, և ոչ թե նվազագույն: Գործնականում գրադիենտ վայրէջքի մեթոդները վստահորեն շրջանցում են թամբի կետերը և գտնում են օբյեկտիվ ֆունկցիայի մինիմումներ (ընդհանուր դեպքում՝ տեղական):
ԵԶՐԱԿԱՑՈՒԹՅՈՒՆ
Գրադիենտ անսահմանափակ օպտիմալացման մեթոդների օրինակներ քննարկվեցին վերևում: Կատարված աշխատանքի արդյունքում կարելի է անել հետևյալ եզրակացությունները.
1. Սահմանափակումների առկայության դեպքում էքստրեմում գտնելու քիչ թե շատ բարդ խնդիրները պահանջում են հատուկ մոտեցումներ և մեթոդներ։
2. Սահմանափակված խնդիրների լուծման շատ ալգորիթմներ ներառում են անսահմանափակ նվազագույնիացում՝ որպես որոշ քայլ:
3. Տարբեր մեթոդներվայրէջքները տարբերվում են միմյանցից իջնելու ուղղությունը և այս ուղղությամբ քայլի երկարությունը ընտրելու ձևով:
4. Դեռևս չկա տեսություն, որը հաշվի կառնի խնդրի ձևակերպումը նկարագրող գործառույթների որևէ առանձնահատկություն: Նախապատվությունը պետք է տրվի այն մեթոդներին, որոնք ավելի հեշտ են կառավարվում խնդրի լուծման գործընթացում։
Իրական կիրառական օպտիմալացման խնդիրները շատ բարդ են: Ժամանակակից մեթոդներՕպտիմալացումները միշտ չէ, որ հաղթահարում են իրական խնդիրներն առանց մարդկային օգնության:
ՄԱՏԵՆԱԳՐՈՒԹՅՈՒՆ
1. Կոսորուկով Օ.Ա. Գործողությունների հետազոտություն. Դասագիրք. 2003 թ
2. Պանտլեև Ա.Վ. Օպտիմալացման մեթոդները օրինակներում և խնդիրներում. Դասագիրք. Օգուտ. 2005թ
3. Շիշկին Է.Վ. Գործողությունների հետազոտություն: Դասագիրք. 2006թ
4. Ակուլիչ Ի.Լ. Մաթեմատիկական ծրագրավորում օրինակներով և խնդիրներով. 1986 թ
5. Վենցել Է.Ս. Գործառնությունների հետազոտություն. 1980 թ
6. Վենցել Է.Ս., Օվչարով Լ.Ա. Հավանականությունների տեսությունը և դրա ինժեներական կիրառությունները: 1988 թ
©2015-2019 կայք
Բոլոր իրավունքները պատկանում են դրանց հեղինակներին: Այս կայքը չի հավակնում հեղինակության, այլ տրամադրում է անվճար օգտագործումը.
Էջի ստեղծման ամսաթիվը՝ 2017-07-02
Անոտացիա: Այս դասախոսությունը լայնորեն ընդգրկում է այնպիսի բազմապարամետրային օպտիմիզացման մեթոդներ, ինչպիսիք են ամենից կտրուկ վայրէջքի մեթոդը և Դեյվիդոն-Ֆլետչեր-Փաուելի մեթոդը: Բացի այդ, կատարվում է վերը նշված մեթոդների համեմատական վերլուծություն՝ ամենաարդյունավետը որոշելու, դրանց առավելություններն ու թերությունները պարզելու նպատակով. և նաև դիտարկում է օպտիմիզացման բազմաչափ խնդիրներ, ինչպիսիք են հեղեղատային մեթոդը և բազմածայրահեղ մեթոդը:
1. Ամենաշերտ վայրէջքի մեթոդ
Էությունը այս մեթոդըայն է, որ օգտագործելով նախկինում նշվածը կոորդինատային ծագման մեթոդհետախուզում է իրականացվում տրված կետառանցքներից մեկին զուգահեռ ուղղությամբ, այդ ուղղությամբ նվազագույն կետով: Այնուհետեւ որոնումը կատարվում է մյուս առանցքին զուգահեռ ուղղությամբ եւ այլն: Ուղղությունները, իհարկե, ամրագրված են։ Խելամիտ է թվում փորձել փոփոխել այս մեթոդը, որպեսզի յուրաքանչյուր փուլում նվազագույն կետի որոնումն իրականացվի «լավագույն» ուղղությամբ: Պարզ չէ, թե որ ուղղությունն է «լավագույնը», բայց հայտնի է, որ գրադիենտ ուղղությունֆունկցիայի ամենաարագ աճի ուղղությունն է։ Հետևաբար, հակառակ ուղղությունը ֆունկցիայի ամենաարագ նվազման ուղղությունն է։ Այս գույքը կարող է հիմնավորվել հետևյալ կերպ.
Ենթադրենք, որ մենք շարժվում ենք x կետից հաջորդ կետ x + hd, որտեղ d-ը որոշակի ուղղություն է, իսկ h-ը որոշակի երկարության քայլ է։ Հետևաբար, շարժումը կատարվում է կետից (x 1, x 2, ..., x n) կետից (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Որտեղ
Գործառույթների արժեքների փոփոխությունը որոշվում է հարաբերություններով
| (1.3) |
Մինչև առաջին կարգի zx i, մասնակի ածանցյալները հաշվարկվում են x կետում: Ինչպե՞ս պետք է ընտրվեն d i ուղղությունները, որոնք բավարարում են (1.2) հավասարումը, որպեսզի ստացվի df ֆունկցիայի փոփոխության ամենամեծ արժեքը: Այստեղ է, որ առաջանում է սահմանափակումով մաքսիմալացման խնդիր: Կիրառենք Լագրանժի բազմապատկիչների մեթոդը, որի օգնությամբ որոշում ենք ֆունկցիան
Սահմանափակումը (1.2) բավարարող df արժեքը հասնում է առավելագույնին, երբ ֆունկցիան
Հասնում է առավելագույնին. Դրա ածանցյալը
Հետևաբար,
 |
(1.6) |
Այնուհետև di ~ df/dx i և d ուղղությունը զուգահեռ է V/(x) ուղղությանը x կետում։
Այսպիսով, ամենամեծ տեղական աճըՏրված փոքր քայլի h ֆունկցիան տեղի է ունենում, երբ d-ը Vf(x) կամ g(x) ուղղությունն է: Հետևաբար, ամենից կտրուկ վայրէջքի ուղղությունը ուղղությունն է
Ավելի շատ պարզ ձևովհավասարումը (1.3) կարելի է գրել հետևյալ կերպ.
Որտեղ է անկյունը Vf(x) և dx վեկտորների միջև: Համար տրված արժեք dx մենք նվազագույնի ենք հասցնում df-ը՝ ընտրելով, որ dx-ի ուղղությունը համընկնում է -Vf(x) ուղղության հետ:
Մեկնաբանություն. Գրադիենտ ուղղությունՈւղղահայաց է հաստատուն մակարդակի գծի ցանկացած կետի, քանի որ այս գծի երկայնքով ֆունկցիան հաստատուն է: Այսպիսով, եթե (d 1, d 2, ..., d n) փոքր քայլ է մակարդակի գծի երկայնքով, ապա
Եւ, հետեւաբար
 |
(1.8) |
Կարող եք նաև որոնել ոչ թե գրադիենտի ուղղությամբ լավագույն կետը, այլ ավելի լավը, քան ներկայիսը:
Տեղական օպտիմիզացման բոլոր մեթոդներից ամենահեշտը կիրառելը: Ունի բավականին թույլ պայմաններկոնվերգենցիա, բայց կոնվերգենցիայի արագությունը բավականին ցածր է (գծային): Գրադիենտ մեթոդի քայլը հաճախ օգտագործվում է որպես օպտիմալացման այլ մեթոդների մաս, ինչպիսին է Ֆլետչեր–Ռիվզ մեթոդը։
Նկարագրություն [ | ]
Բարելավումներ[ | ]
Գրադիենտ վայրէջքի մեթոդը պարզվում է, որ շատ դանդաղ է կիրճով շարժվելիս, և քանի որ օբյեկտիվ ֆունկցիայի փոփոխականների թիվը մեծանում է, մեթոդի այս վարքագիծը դառնում է բնորոշ: Այս երեւույթի դեմ պայքարելու համար այն օգտագործվում է, որի էությունը շատ պարզ է. Գրադիենտ վայրէջք կատարելով երկու քայլ և ձեռք բերելով երեք կետ, երրորդ քայլը պետք է կատարվի առաջին և երրորդ կետերը միացնող վեկտորի ուղղությամբ՝ ձորի հատակի երկայնքով:
Քառակուսայինին մոտ ֆունկցիաների համար արդյունավետ է կոնյուգացիոն գրադիենտ մեթոդը։
Կիրառում արհեստական նեյրոնային ցանցերում[ | ]
Գրադիենտ վայրէջքի մեթոդը, որոշակի փոփոխություններով, լայնորեն կիրառվում է պերցեպտրոնի ուսուցման համար և հայտնի է արհեստական նեյրոնային ցանցերի տեսության մեջ որպես հետտարածման մեթոդ։ Պերցեպտրոնի տիպի նեյրոնային ցանցը վարժեցնելիս անհրաժեշտ է փոխել ցանցի կշռման գործակիցները՝ նվազագույնի հասցնելու համար. միջին սխալնեյրոնային ցանցի ելքում, երբ ուսուցման մուտքային տվյալների հաջորդականությունը մատակարարվում է մուտքին: Ֆորմալ կերպով, գրադիենտ վայրէջքի մեթոդով ընդամենը մեկ քայլ անելու համար (ցանցի պարամետրերում ընդամենը մեկ փոփոխություն կատարեք), անհրաժեշտ է հաջորդաբար ներկայացնել վերապատրաստման տվյալների բացարձակ ամբողջ փաթեթը ցանցի մուտքագրմանը, հաշվարկել սխալը յուրաքանչյուր օբյեկտի համար: վերապատրաստման տվյալները և հաշվարկեք ցանցի գործակիցների անհրաժեշտ ուղղումը (բայց մի արեք այս ուղղումը), և բոլոր տվյալները ներկայացնելուց հետո հաշվարկեք յուրաքանչյուր ցանցի գործակցի ճշգրտման գումարը (գրադիենտների գումարը) և շտկեք գործակիցները «մեկ քայլ» . Ակնհայտ է, որ վերապատրաստման տվյալների մեծ հավաքածուի դեպքում ալգորիթմը կաշխատի չափազանց դանդաղ, ուստի գործնականում ցանցի գործակիցները հաճախ ճշգրտվում են յուրաքանչյուր ուսումնական տարրից հետո, որտեղ գրադիենտ արժեքը մոտավորվում է ծախսերի ֆունկցիայի գրադիենտով, որը հաշվարկվում է միայն մեկ մարզման վրա: տարր. Այս մեթոդը կոչվում է ստոխաստիկ գրադիենտ ծագում կամ գործառնական գրադիենտ վայրէջք . Ստոխաստիկ գրադիենտ վայրէջքստոխաստիկ մոտարկման ձևերից է։ Ստոխաստիկ մոտարկումների տեսությունը պայմաններ է ապահովում ստոխաստիկ գրադիենտ ծագման մեթոդի կոնվերգենցիայի համար։
Հղումներ [ | ]
- Ջ.Մեթյուզ.Մոդուլ ամենից կտրուկ վայրէջքի կամ գրադիենտ մեթոդի համար: (անհասանելի հղում)
գրականություն [ | ]
- Ակուլիչ Ի.Լ.Մաթեմատիկական ծրագրավորում օրինակներով և խնդիրներով. - Մ.: Բարձրագույն դպրոց, 1986. - P. 298-310:
- Գիլ Ֆ., Մյուրեյ Վ., Ռայթ Մ.Գործնական օպտիմալացում = Գործնական օպտիմիզացում: - Մ.: Միր, 1985:
- Կորշունով Յու. Մ., Կորշունով Յու. Մ.Կիբեռնետիկայի մաթեմատիկական հիմունքները. - Մ.: Էներգոատոմիզդատ, 1972:
- Մաքսիմով Յու.Ա., Ֆիլիպովսկայա Է.Ա.Ոչ գծային ծրագրավորման խնդիրների լուծման ալգորիթմներ. - M.: MEPhI, 1982:
- Մաքսիմով Յու.Ա.Գծային և դիսկրետ ծրագրավորման ալգորիթմներ. - M.: MEPhI, 1980:
- Կոռն Գ., Կոռն Թ.Մաթեմատիկայի ձեռնարկ գիտնականների և ճարտարագետների համար. - M.: Nauka, 1970. - P. 575-576:
- Ս. Յու. Գորոդեցկի, Վ.Ա. Գրիշագին.Ոչ գծային ծրագրավորում և բազմաէքստրեմալ օպտիմալացում: - Նիժնի ՆովգորոդՆիժնի Նովգորոդի համալսարանի հրատարակչություն, 2007 թ. - էջ 357-363:
Յուրաքանչյուր կրկնության ժամանակ ամենադաժան վայրէջքի մեթոդն օգտագործելիս՝ քայլի չափը Ա կ ընտրվում է ֆունկցիայի նվազագույն պայմանից f(x)վայրէջքի ուղղությամբ, այսինքն.
f(x[կ] -ա կ f» (x[կ])) = f(x[k] -af» (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 ես [k+ 1]= x ես [կ] -Ա կ զ" ես (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)լավ պայմանավորված. Հիշեցնենք, որ սեփական արժեքներես, ես =1, …, n, մատրիցները բնորոշ հավասարման արմատներն են
Այնուամենայնիվ, գործնականում, որպես կանոն, նվազագույնի հասցվող գործառույթներն ունեն երկրորդ ածանցյալների վատ պայմանավորված մատրիցներ. (տ/մ<< 1). Որոշ ուղղությունների երկայնքով նման գործառույթների արժեքները փոխվում են շատ ավելի արագ (երբեմն մի քանի մեծության կարգով), քան այլ ուղղություններով: Նրանց հարթ մակերեսները ամենապարզ դեպքում խիստ երկարաձգված են (նկ. 2.10), իսկ ավելի բարդ դեպքերում դրանք թեքվում են և նմանվում ձորերի։ Նման հատկություններով ֆունկցիաները կոչվում են հեղեղատ.Այս ֆունկցիաների հակագրադիենտի ուղղությունը (տե՛ս նկ. 2.10) էապես շեղվում է ուղղությունից մինչև նվազագույն կետ, ինչը հանգեցնում է կոնվերգենցիայի արագության նվազմանը։
Բրինձ. 2.10.
Գրադիենտ մեթոդների կոնվերգենցիայի արագությունը նույնպես զգալիորեն կախված է գրադիենտ հաշվարկների ճշգրտությունից: Ճշգրտության կորուստը, որը սովորաբար տեղի է ունենում նվազագույն կետերի մոտակայքում կամ հեղեղատային իրավիճակում, ընդհանուր առմամբ կարող է խաթարել գրադիենտ վայրէջքի գործընթացի մերձեցումը: Ելնելով վերը նշված պատճառներից՝ խնդրի լուծման սկզբնական փուլում գրադիենտ մեթոդները հաճախ օգտագործվում են այլ՝ ավելի արդյունավետ մեթոդների հետ համատեղ։ Այս դեպքում կետը Xհեռու է նվազագույն կետից, և հակագրադիենտի ուղղությամբ քայլերը հնարավորություն են տալիս հասնել ֆունկցիայի զգալի նվազման։
