Ўзбекистон республикаси олий ва ўрта махсус таълим вазирлиги коракалпак давлат университети “технология” кафедраси

Градиент усуллари

Оптимумни қидиришнинг градиент мақсад функцияси R(х) ва Хосилаларини R(х)/х_j Хисоблаш ва таХлил қилишга асосланган. Мақсад функциясининг аналитик куринишини Хамма вақт Хам аниқ куринишда ёзиш мумкин эмас, ёки у жуда мураккаб булиб, ундан олинган Хосила Хам жуда мураккаб аналитик ифода куринишида булади. Бундай Холатларда мақсад функцияларининг Хосилаларини Хисоблаш учун тақрибий Хисоблаш усуллари қулланилади, яъни

R/x_j R/eқ R(х₁, х₂,..х_j+х_j,..х_n) - R(х₁, х₂,..х_j,..х_n) / х_j ;

х_j- j- узгарувчини олган усиш қиймати (ёки, ноградиент усуллари қулланилади). Градиент усулларга қуйидаги усуллар киради:

1. 
   Релаксация усули;
   
2. 
   Градиент усули;
   
3. 
   Экстремумга тез тушиш усули;
   
4. 
   «Оғир шарик» усули;
   
5. 
   Оптимумни градиент аналитик ифодаси маълум булган Холда қидириш.
   

Релаксация усули.

Оптимумни қидириш алгоритми бўйича, мақсад функциясининг энг тез ўзгариши ўқ йўналиши аниқланади. Масалан, агар оптималлик критерийсининг энг кичик қийматини топиш керак бўлса, унда функциянинг энг тез камайиш йўналиши аниқланади.

қидирувнинг бошланғич нуқтасида Хамма ўқ йўналишлар бўйича оптималлаштирилаётган функция Хосилалари Хисоблаб чиқилади. Хосиласи энг катта бўлган ўзгарувчи йўналишни, функциянинг энг тез ўзгарувчи (камаювчи) йўналиши Хисобланади.
Агар, Хосила ишораси манфий бўлса, унда шу йўналишда функция камаяди, агар мусбат бўлса, унда функция камайиши тескари йўналишда бўлади. Шу ўқ йўналиши бўйича қидирув, шу йўналиш бўйича мақсад функциясининг энг кичик қиймати топилгунча давом этади. Сўнгра, Хамма ўқ йўналишлар бўйича функция Хосиласи Хисобланиб (қидирув амалга оширилган йўналишдан ташқари), яна мақсад функциясининг энг тез камаювчи йўналиши аниқланади. Энди шу йўналиш бўйича функциянинг экстремуми қидирилади. Сўнгра, яна янги йўналиш аниқланади ва Хоказо. Хамма ўқ йўналишлар бўйича оптмаллик критерийсининг қиймати камаймай қолганда, қидирувни тўхтатиш мумкин. Баъзи Холларда оптималлик белгиси сифатида қуйидаги шарт қабул қилинади:


^п R
_( ) ²<б
^{i 1} X_i

б0 булса, бу нуқтада функция Хосиласи нольга тенг.

Бошланғич Холатдан оптимумга қараб Харакатнинг график ифодаси қуйидаги расмда берилган (33-расм). қидирув қадамини туғри қабул қилиниши, оптимумга қараб юриш тезлигини аниқлайди. Агар қадам жуда кичик бўлса, унда оптимумни Хисоблаб топгунча, мақсад функциясини қийматини жуда кўп маротаба Хисоблаш керак булади.. Агар қадам жуда катта бўлса, унда оптимум яқинида «ивирсираш» бўлиб, оптимумга қўйилган шарт бўйича яқинлашиш анча қийин булади. Одатда, ўқ йўналиши алмашганда қадам қиймати ўзгартирилиб борилади, яъни оптимумга яқинлашган сари қидирув қадами камайтириб борилади.
33-расм.
Релаксация усулини камчиликларидан бири, бу қидирув вақтини координаталар тизимсининг ориентацисига боғлиқлигидир (34-расм). Ўқларнинг бир-бирига нисбатан буралганлиги билан фарқланувчи координаталар тизимсидаги мақсад функциясининг бир хил қиймат чизиқларини кўрайлик (34-расм). Координата ўқларининг биринчи ориентациясида, 5-6 марта қидирув ўқ йўналиши Хисоблаб топилиб, сўнгра экстремум топилади. Иккинчи Холатда 2 марта йўналиш Хисоблаб топилиб экстремумга етиб келинди.

34-расм.

Агар ўзгарувчилар ўзгариш областига тенгсизлик кўринишидаги чеклама қўйилган бўлса, унда оптимумни қидириш шу чекламанинг Хамма нуқтасига келганда тўхтаб қолади.
Худди шундай, қидирувдаги қийинчиликларга мақсад функциясида мавжуд «жарлик»лар сабаб бўлиши мумкин (локал оптимум). Бунда қидирув шу «жарлик»ларда тўхтаб қолади.