બિંદુ પર વિભેદક કાર્ય f(x) નો ઢાળ એક્સકહેવાય છે n-પરિમાણીય વેક્ટર f(x) , જેના ઘટકો ફંક્શનના આંશિક ડેરિવેટિવ્ઝ છે f(x),બિંદુ પર ગણતરી એક્સ, એટલે કે

f"(x ) = (df(x)/ડીએચ 1 , …, df(x)/ડીએક્સ એન) ટી.

આ વેક્ટર બિંદુ દ્વારા પ્લેન પર લંબ છે એક્સ, અને ફંક્શનની લેવલ સપાટીની સ્પર્શક f(x),એક બિંદુમાંથી પસાર થવું એક્સ.આવી સપાટીના દરેક બિંદુ પર કાર્ય f(x)સમાન મૂલ્ય લે છે. ફંક્શનને વિવિધ સ્થિર મૂલ્યો C 0 , C 1 , ... સાથે સમાન કરીને, અમે તેની ટોપોલોજી (ફિગ. 2.8) ને દર્શાવતી સપાટીઓની શ્રેણી મેળવીએ છીએ.

ચોખા. 2.8. ઢાળ

ગ્રેડિયન્ટ વેક્ટર આપેલ બિંદુ પર કાર્યમાં સૌથી ઝડપી વધારો તરફ નિર્દેશિત થાય છે. ઢાળની વિરુદ્ધ વેક્ટર (-f'(x)) , કહેવાય છે વિરોધી ઢાળઅને કાર્યના સૌથી ઝડપી ઘટાડા તરફ નિર્દેશિત થાય છે. ન્યૂનતમ બિંદુ પર, કાર્યનો ઢાળ શૂન્ય છે. પ્રથમ ક્રમની પદ્ધતિઓ, જેને ઢાળ અને લઘુત્તમ પદ્ધતિઓ પણ કહેવાય છે, તે ઢાળના ગુણધર્મો પર આધારિત છે. સામાન્ય કિસ્સામાં આ પદ્ધતિઓનો ઉપયોગ કરવાથી તમે કાર્યનો સ્થાનિક લઘુત્તમ બિંદુ નક્કી કરી શકો છો.

દેખીતી રીતે, જો ત્યાં કોઈ વધારાની માહિતી નથી, તો પછી પ્રારંભિક બિંદુથી એક્સમુદ્દા પર જવાનું શાણપણ છે એક્સ, એન્ટિગ્રેડિયન્ટની દિશામાં પડેલો - કાર્યનો સૌથી ઝડપી ઘટાડો. વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએ[આર k ] વિરોધી ઢાળ - f'(x ) [કે] એક્સ[આરબિંદુ પર

], અમે ફોર્મની પુનરાવર્તિત પ્રક્રિયા મેળવીએ છીએ X[ 1] = k+[આર]-x f'(x ) , a k f"(x > 0; આર=0, 1, 2, ...

અને k

સંકલન સ્વરૂપમાં, આ પ્રક્રિયા નીચે મુજબ લખાયેલ છે: આર+1]=x i [[આર] - x if(x f'(x ) a k

/x i n; આર= 0, 1, 2,...

i = 1, ..., k+[આરપુનરાવર્તિત પ્રક્રિયાને રોકવા માટેના માપદંડ તરીકે, કાં તો દલીલના નાના વધારાની શરતની પરિપૂર્ણતા || +l][આર] || <= e , либо выполнение условия малости градиента

|| - એક્સ[આર f'(x ) || <= g ,

+l]

અહીં e અને g નાની માત્રામાં આપવામાં આવે છે. a k f"(x.

એક સંયુક્ત માપદંડ પણ શક્ય છે, જેમાં ઉલ્લેખિત શરતોની એક સાથે પરિપૂર્ણતાનો સમાવેશ થાય છે. તેઓ જે રીતે પગલાનું કદ પસંદ કરે છે તે રીતે ગ્રેડિયન્ટ પદ્ધતિઓ એકબીજાથી અલગ પડે છે a k f"(xસતત પગલાં સાથેની પદ્ધતિમાં, તમામ પુનરાવર્તનો માટે ચોક્કસ સ્થિર પગલું મૂલ્ય પસંદ કરવામાં આવે છે. એકદમ નાનું પગલું

ખાતરી કરશે કે કાર્ય ઘટે છે, એટલે કે, અસમાનતા આર+1]) = f(x f(x[ [કે] - f'(x )) < f(x f'(x ) .

જો કે, આ લઘુત્તમ બિંદુ સુધી પહોંચવા માટે અસ્વીકાર્ય રીતે મોટી સંખ્યામાં પુનરાવર્તનો હાથ ધરવાની જરૂરિયાત તરફ દોરી શકે છે. બીજી બાજુ, એક પગલું જે ખૂબ મોટું છે તે કાર્યમાં અણધારી વધારો કરી શકે છે અથવા લઘુત્તમ બિંદુ (સાયકલિંગ) ની આસપાસ ઓસિલેશન તરફ દોરી શકે છે. પગલાના કદને પસંદ કરવા માટે જરૂરી માહિતી મેળવવાની મુશ્કેલીને લીધે, સતત પગલાં સાથેની પદ્ધતિઓનો વ્યવહારમાં ભાગ્યે જ ઉપયોગ થાય છે.

પુનરાવર્તનોની સંખ્યા અને વિશ્વસનીયતાના સંદર્ભમાં ગ્રેડિયન્ટ વધુ આર્થિક છે ચલ પગલાં પદ્ધતિઓ,જ્યારે, ગણતરીના પરિણામોના આધારે, પગલાનું કદ અમુક રીતે બદલાય છે. ચાલો વ્યવહારમાં ઉપયોગમાં લેવાતી આવી પદ્ધતિઓના પ્રકારોને ધ્યાનમાં લઈએ.

દરેક પુનરાવૃત્તિ પર સૌથી ઊંચો વંશ પદ્ધતિનો ઉપયોગ કરતી વખતે, પગલાનું કદ a k f"(xફંક્શનની ન્યૂનતમ સ્થિતિમાંથી પસંદ કરવામાં આવે છે f(x)વંશની દિશામાં, એટલે કે.
f(x[આર]-a k f'(x[આર])) = f(x f'(x - af"(x[આર])) .

આ સ્થિતિનો અર્થ એ છે કે એન્ટિગ્રેડિયન્ટ સાથેની હિલચાલ ફંક્શનના મૂલ્ય સુધી થાય છે f(x)ઘટે છે. ગાણિતિક દૃષ્ટિકોણથી, દરેક પુનરાવૃત્તિ પર એક-પરિમાણીય લઘુત્તમીકરણની સમસ્યાને હલ કરવી જરૂરી છે એકાર્યો
j (a) = f(x[આર]-af"(x[આર])) .

સૌથી ઊંચો વંશ પદ્ધતિનો અલ્ગોરિધમ નીચે મુજબ છે.

1. પ્રારંભિક બિંદુના કોઓર્ડિનેટ્સ સેટ કરો એક્સ.

2. બિંદુ પર એક્સ[આર], k = 0, 1, 2, ... ગ્રેડિયન્ટ મૂલ્યની ગણતરી કરે છે - એક્સ[આર]) .

3. પગલાનું કદ નક્કી કરવામાં આવે છે a k, એક-પરિમાણીય લઘુત્તમીકરણ દ્વારા એકાર્યો જે (a) = f(x[આર]-af"(x[આર])).

4. બિંદુના કોઓર્ડિનેટ્સ નક્કી કરવામાં આવે છે એક્સ[X[ 1]:

x i [ X[ 1]= x i[આર]- a k f' i (x[આર]), i = 1,..., p.

5. સ્ટીરેશન પ્રક્રિયાને રોકવા માટેની શરતો તપાસવામાં આવે છે. જો તેઓ પૂરા થાય, તો ગણતરીઓ અટકી જાય છે. નહિંતર, પગલું 1 પર જાઓ.

જટિલ કાર્યના વ્યુત્પન્નની ગણતરી કર્યા પછી, અમે પડોશી બિંદુઓ પર વંશ દિશાઓના વેક્ટરની ઓર્થોગોનાલિટી માટેની સ્થિતિ મેળવીએ છીએ: ડીજે[X[ 1]- એક્સ[આર]) = 0.

(a)/da = -f’(x

ચોખા. 2.9. સૌથી ઊભો વંશ પદ્ધતિનું ભૌમિતિક અર્થઘટનસરળ બહિર્મુખ કાર્યો માટે ગ્રેડિયન્ટ પદ્ધતિઓ ઉચ્ચ ઝડપે (ભૌમિતિક પ્રગતિની ગતિ) પર ન્યૂનતમ પર એકરૂપ થાય છે. આવા કાર્યો સૌથી મહાન છે એમઅને ઓછામાં ઓછું

m બીજા ડેરિવેટિવ્ઝના મેટ્રિક્સના ઇજેન મૂલ્યો (હેસિયન મેટ્રિક્સ)એકબીજાથી થોડું અલગ છે, એટલે કે મેટ્રિક્સ N(x) =1, …, nસારી રીતે કન્ડિશન્ડ. યાદ કરો કે ઇજનવેલ્યુઝ l i,

જો કે, વ્યવહારમાં, એક નિયમ તરીકે, વિધેયોને ઘટાડી દેવામાં આવે છે તેમાં બીજા ડેરિવેટિવ્ઝના અયોગ્ય મેટ્રિસિસ હોય છે. (t/m<< 1). કેટલીક દિશાઓ સાથેના આવા કાર્યોના મૂલ્યો અન્ય દિશાઓની તુલનામાં ખૂબ ઝડપથી (ક્યારેક તીવ્રતાના કેટલાક ઓર્ડર દ્વારા) બદલાય છે. સરળ કેસમાં તેમની સ્તરની સપાટીઓ મજબૂત રીતે વિસ્તરેલી હોય છે (ફિગ. 2.10), અને વધુ જટિલ કિસ્સાઓમાં તેઓ વળાંક અને કોતરો જેવા દેખાય છે. આવા ગુણધર્મો સાથેના કાર્યો કહેવામાં આવે છે ખાડીઆ કાર્યોના એન્ટિગ્રેડિયન્ટની દિશા (જુઓ. ફિગ. 2.10) દિશાથી લઘુત્તમ બિંદુ સુધી નોંધપાત્ર રીતે વિચલિત થાય છે, જે સંપાતની ગતિમાં મંદી તરફ દોરી જાય છે.

ચોખા. 2.10. ગલી કાર્ય

ઢાળ પદ્ધતિઓનો કન્વર્જન્સ દર પણ ગ્રેડિયન્ટ ગણતરીઓની ચોકસાઈ પર નોંધપાત્ર રીતે આધાર રાખે છે. ચોકસાઈની ખોટ, જે સામાન્ય રીતે ન્યૂનતમ બિંદુઓની નજીકમાં અથવા ગલીની પરિસ્થિતિમાં થાય છે, તે સામાન્ય રીતે ગ્રેડિએન્ટ ડિસેન્ટ પ્રક્રિયાના કન્વર્જન્સને વિક્ષેપિત કરી શકે છે. એક્સઉપરોક્ત કારણોને લીધે, સમસ્યાને ઉકેલવાના પ્રારંભિક તબક્કે ઢાળ પદ્ધતિઓનો ઉપયોગ અન્ય, વધુ અસરકારક પદ્ધતિઓ સાથે સંયોજનમાં થાય છે. આ કિસ્સામાં, બિંદુ

લઘુત્તમ બિંદુથી દૂર છે, અને એન્ટિગ્રેડિયન્ટની દિશામાં પગલાઓ કાર્યમાં નોંધપાત્ર ઘટાડો પ્રાપ્ત કરવાનું શક્ય બનાવે છે.

ઉપર ચર્ચા કરાયેલી ઢાળ પદ્ધતિઓ સામાન્ય કિસ્સામાં ફંકશનનો ન્યૂનતમ બિંદુ ફક્ત અનંત સંખ્યામાં પુનરાવર્તનોમાં જ શોધે છે. સંયોજક ઢાળ પદ્ધતિ શોધ દિશાઓ જનરેટ કરે છે જે કાર્યની ભૂમિતિને ઘટાડી દેવામાં આવે છે તેની સાથે વધુ સુસંગત હોય છે. આ તેમના કન્વર્જન્સની ઝડપમાં નોંધપાત્ર વધારો કરે છે અને ઉદાહરણ તરીકે, ચતુર્ભુજ કાર્યને ઘટાડવા માટે પરવાનગી આપે છે.

f(x) = (x, Hx) + (b, x) + a સપ્રમાણ હકારાત્મક ચોક્કસ મેટ્રિક્સ સાથેએન પગલાંઓની મર્યાદિત સંખ્યામાં p,

ફંક્શન ચલોની સંખ્યા જેટલી. nન્યૂનતમ બિંદુની નજીકમાં કોઈપણ સરળ કાર્યને ચતુર્ભુજ કાર્ય દ્વારા સારી રીતે અંદાજિત કરી શકાય છે, તેથી બિન-ક્વાડ્રેટિક કાર્યોને ઘટાડવા માટે સંયોજક ઢાળ પદ્ધતિઓનો સફળતાપૂર્વક ઉપયોગ થાય છે. આ કિસ્સામાં, તેઓ મર્યાદિત થવાનું બંધ કરે છે અને પુનરાવર્તિત બને છે. એક્સવ્યાખ્યા દ્વારા, બે -પરિમાણીય વેક્ટરઅને ખાતેકહેવાય છે સંયોજિતમેટ્રિક્સ સંબંધિત સંયોજિતએચ (અથવા, -સંયુક્ત), જો સ્કેલર ઉત્પાદન(x સારું) = 0.અહીં એન -કદનું સપ્રમાણ હકારાત્મક ચોક્કસ મેટ્રિક્સ n

એક્સ પી.[આર]) સંયોજક ઢાળ પદ્ધતિઓમાં સૌથી નોંધપાત્ર સમસ્યાઓ પૈકી એક કાર્યક્ષમ રીતે દિશાઓ બાંધવાની સમસ્યા છે. ફ્લેચર-રીવ્સ પદ્ધતિ દરેક પગલા પર એન્ટિગ્રેડિયન્ટને રૂપાંતરિત કરીને આ સમસ્યાને હલ કરે છે -f(x[આર], સંયોજિત- અગાઉ મળેલી દિશાઓ સાથે સંયોજિત કરો વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએ, વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએ, ..., વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએ[આર-1].

ચાલો પ્રથમ ચતુર્ભુજ કાર્યને ઘટાડવાની સમસ્યાના સંબંધમાં આ પદ્ધતિને ધ્યાનમાં લઈએ. વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએ[આરદિશાઓ

] ની ગણતરી સૂત્રો દ્વારા કરવામાં આવે છે: આર] = -- એક્સ[આર]) p[ -f(x[આર+b k-1 આર>= 1;

-l], p = -’(અથવા) .

f આર b મૂલ્યો -f(x[આર], વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએ[આર-1 પસંદ કરવામાં આવે છે જેથી દિશાઓ સંયોજિત-1] હતા :

(-f(x[આર], -સંયુક્ત[એચપી 1])= 0.

પરિણામે, ચતુર્ભુજ કાર્ય માટે

પુનરાવર્તિત લઘુત્તમ પ્રક્રિયા ફોર્મ ધરાવે છે આર f'(x x[[આર]=x[આર],

+a k પી વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએ[આર] - જ્યાં એચપીમાટે વંશની દિશા m પગલું;અને k - પગલું કદ.બાદમાં ફંક્શનની ન્યૂનતમ સ્થિતિમાંથી પસંદ કરવામાં આવે છે એ f(x)

ખાતરી કરશે કે કાર્ય ઘટે છે, એટલે કે, અસમાનતા આર] + દ્વારા[આર]) = f(x[આર] + ચળવળની દિશામાં, એટલે કે એક-પરિમાણીય લઘુત્તમ સમસ્યાને હલ કરવાના પરિણામે: [આર]) .

a k આર

ચતુર્ભુજ કાર્ય માટે એક્સફ્લેચર-રીવ્સ કન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિનું અલ્ગોરિધમ નીચે મુજબ છે. -f(x = -- એક્સ) .

1. બિંદુ પર એચપીગણતરી કરેલ એ 2. ચાલુ . m પગલું, ઉપરોક્ત સૂત્રોનો ઉપયોગ કરીને, પગલું નક્કી કરવામાં આવે છે એક્સ[X[ 1].

k f(x[આર+1]) અને સમયગાળો - એક્સ[આર+1]) .

3. મૂલ્યોની ગણતરી કરવામાં આવે છે - એક્સ) અને એક્સ[આર 4. જો = 0, પછી બિંદુ+1] એ ફંક્શનનો ન્યૂનતમ બિંદુ છે -f(x[આર f(x).

નહિંતર, નવી દિશા નક્કી થાય છે એન -+l] સંબંધમાંથી અને આગામી પુનરાવર્તન માટે સંક્રમણ હાથ ધરવામાં આવે છે. આ પ્રક્રિયા લઘુત્તમ ક્વાડ્રેટિક ફંક્શનને વધુમાં શોધી શકશે નહીંપગલાં એક્સજ્યારે બિન-ચતુર્ભુજ કાર્યોને ઘટાડી રહ્યા હોય, ત્યારે ફ્લેચર-રીવ્ઝ પદ્ધતિ મર્યાદિતમાંથી પુનરાવર્તિત બને છે. આ કિસ્સામાં, પછી એક્સ[એન -(p+

પુનરાવર્તિત લઘુત્તમ પ્રક્રિયા ફોર્મ ધરાવે છે આર f'(x 1) પ્રક્રિયા 1-4 ની પુનરાવૃત્તિ ચક્રીય રીતે રિપ્લેસમેન્ટ સાથે પુનરાવર્તિત થાય છે[આર]=x[આર],

] ની ગણતરી સૂત્રો દ્વારા કરવામાં આવે છે: આર] પર[આર])+ +1] , અને ગણતરીઓ પર સમાપ્ત થાય છે, જ્યાં આપેલ સંખ્યા છે. આ કિસ્સામાં, પદ્ધતિમાં નીચેના ફેરફારનો ઉપયોગ થાય છે: એચપી 1 -f(x[આર+b k-1 આર>= 1;

= x k+);

ખાતરી કરશે કે કાર્ય ઘટે છે, એટલે કે, અસમાનતા આર] + = -f'(x[આર]) = f(x[આર] b[આર];

p = -f’( a k p+ap a k pઅહીં આઈ- ઘણા સૂચકાંકો: એન -= (0, n, 2

p, પગાર, ...) એક્સ, એટલે કે પદ્ધતિ દર વખતે અપડેટ થાય છે વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએ = પગલાંકન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિનો ભૌમિતિક અર્થ નીચે મુજબ છે (ફિગ. 2.11). આપેલ પ્રારંભિક બિંદુથી એક્સવંશ દિશામાં હાથ ધરવામાં આવે છે -f"(x). એક્સબિંદુએ વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએ, ઢાળ વેક્ટર નક્કી થાય છે ] વિરોધી ઢાળ -) f"(x વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએ). કારણ કે વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએ , સંયોજિતદિશામાં કાર્યનો લઘુત્તમ બિંદુ છે વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએતે વંશની દિશા તરીકે પસંદ કરી રહ્યા છીએઓર્થોગોનલ થી વેક્ટર

. પછી વેક્ટર મળે છે . - સાથે જોડવું

. આગળ, આપણે દિશા સાથે લઘુત્તમ કાર્ય શોધીએ છીએ એન -= (0, n, 2

વગેરે આ વ્યાખ્યાન વ્યાપકપણે આવી મલ્ટિપેરામીટર ઓપ્ટિમાઇઝેશન પદ્ધતિઓને આવરી લે છે જેમ કે સૌથી વધુ વંશીય પદ્ધતિ અને ડેવિડન-ફ્લેચર-પોવેલ પદ્ધતિ. વધુમાં, ઉપરોક્ત પદ્ધતિઓનું તુલનાત્મક વિશ્લેષણ હાથ ધરવામાં આવે છે જેથી કરીને સૌથી વધુ અસરકારક એક નક્કી કરવામાં આવે, તેમના ફાયદા અને ગેરફાયદા ઓળખવામાં આવે છે; અને બહુપરીમાણીય ઑપ્ટિમાઇઝેશન સમસ્યાઓને પણ ધ્યાનમાં લે છે, જેમ કે કોતર પદ્ધતિ અને મલ્ટિએક્સ્ટ્રેમલ પદ્ધતિ.

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 પર થાય છે. ફંક્શન df માં ફેરફારનું સૌથી મોટું મૂલ્ય મેળવવા માટે સમીકરણ (1.2) ને સંતોષતા હોય તેવા દિશાઓ d i કેવી રીતે પસંદ કરવી જોઈએ? આ તે છે જ્યાં અવરોધ સાથે મહત્તમકરણની સમસ્યા ઊભી થાય છે. ચાલો લેગ્રેન્જ ગુણકની પદ્ધતિ લાગુ કરીએ, જેની મદદથી આપણે કાર્ય નક્કી કરીએ

મૂલ્ય df સંતોષકારક અવરોધ (1.2) તેની મહત્તમ સુધી પહોંચે છે જ્યારે કાર્ય

મહત્તમ સુધી પહોંચે છે. તેનું વ્યુત્પન્ન

આથી,

(1.6)

પછી di ~ df/dx i અને દિશા d એ બિંદુ x પર V/(x) દિશાની સમાંતર છે.

આમ, સૌથી મોટો સ્થાનિક વધારોઆપેલ નાના પગલા h માટે કાર્ય ત્યારે થાય છે જ્યારે d એ Vf(x) અથવા g(x) ની દિશા હોય. તેથી, સૌથી ઊભો ઉતરવાની દિશા એ દિશા છે

સરળ સ્વરૂપમાં, સમીકરણ (1.3) નીચે પ્રમાણે લખી શકાય છે:

Vf(x) અને dx વેક્ટર્સ વચ્ચેનો ખૂણો ક્યાં છે. dx ની આપેલ કિંમત માટે, dx ની દિશા -Vf(x) ની દિશા સાથે એકરુપ હોય તે પસંદ કરીને અમે df ને નાનું કરીએ છીએ.

ટિપ્પણી. ઢાળ દિશાસ્થિર સ્તરની રેખા પર કોઈપણ બિંદુને લંબરૂપ, કારણ કે આ રેખા સાથે કાર્ય સ્થિર છે. આમ, જો (d 1, d 2, ..., d n) સ્તર રેખા સાથેનું નાનું પગલું છે, તો

અને તેથી

(1.8)

ફિગ.3. સૌથી ઊભો વંશ પદ્ધતિનું ભૌમિતિક અર્થઘટન. દરેક પગલા પર, તે પસંદ કરવામાં આવે છે જેથી આગામી પુનરાવર્તન એ કિરણ L પરના કાર્યનો ન્યૂનતમ બિંદુ હોય.

ઢાળ પદ્ધતિનું આ સંસ્કરણ નીચેના વિચારણાઓમાંથી પગલાની પસંદગી પર આધારિત છે. બિંદુથી આપણે એન્ટિગ્રેડિયન્ટની દિશામાં આગળ વધીશું જ્યાં સુધી આપણે આ દિશામાં ફંક્શન f ના ન્યૂનતમ સુધી પહોંચીએ, એટલે કે કિરણ પર:

બીજા શબ્દોમાં કહીએ તો, તે પસંદ કરવામાં આવે છે જેથી આગળનું પુનરાવર્તન એ કિરણ L પર ફંક્શન f નો ન્યૂનતમ બિંદુ હોય (ફિગ 3 જુઓ). ગ્રેડિયન્ટ પદ્ધતિના આ સંસ્કરણને સૌથી ઊંચો વંશ પદ્ધતિ કહેવામાં આવે છે. નોંધ કરો, માર્ગ દ્વારા, કે આ પદ્ધતિમાં નજીકના પગલાઓની દિશાઓ ઓર્થોગોનલ છે.

સૌથી ઊંચો વંશ પદ્ધતિ માટે દરેક પગલા પર એક-પરિમાણીય ઑપ્ટિમાઇઝેશન સમસ્યા હલ કરવાની જરૂર છે. પ્રેક્ટિસ બતાવે છે કે આ પદ્ધતિને સતત પગલા સાથે ઢાળ પદ્ધતિ કરતાં ઘણી વખત ઓછા ઑપરેશનની જરૂર પડે છે.

જો કે, સામાન્ય પરિસ્થિતિમાં, સૌથી ઊંચું વંશ પદ્ધતિનો સૈદ્ધાંતિક કન્વર્જન્સ રેટ સતત (શ્રેષ્ઠ) સ્ટેપ સાથેની ઢાળ પદ્ધતિના કન્વર્જન્સ દર કરતાં વધારે નથી.

સંખ્યાત્મક ઉદાહરણો

સતત પગલા સાથે ઢાળવાળી વંશ પદ્ધતિ

સતત પગલા સાથે ગ્રેડિયન્ટ ડિસેન્ટ પદ્ધતિના કન્વર્જન્સનો અભ્યાસ કરવા માટે, ફંક્શન પસંદ કરવામાં આવ્યું હતું:

પ્રાપ્ત પરિણામો પરથી, અમે નિષ્કર્ષ પર આવી શકીએ છીએ કે જો ગેપ ખૂબ મોટો હોય, તો પદ્ધતિ અલગ પડે છે, જો ગેપ ખૂબ નાનો હોય, તો તે ધીમે ધીમે કન્વર્જ થાય છે અને ચોકસાઈ વધુ ખરાબ હોય છે. તેમાંથી સૌથી મોટું પગલું પસંદ કરવું જરૂરી છે કે જેના પર પદ્ધતિ એકરૂપ થાય છે.

સ્ટેપ ડિવિઝન સાથે ગ્રેડિયન્ટ પદ્ધતિ

સ્ટેપ ડિવિઝન (2) સાથે ગ્રેડિએન્ટ ડિસેન્ટ પદ્ધતિના કન્વર્જન્સનો અભ્યાસ કરવા માટે, ફંક્શન પસંદ કરવામાં આવ્યું હતું:

પ્રારંભિક અંદાજ બિંદુ (10,10) છે.

સ્ટોપીંગ માપદંડ વપરાયેલ:

પ્રયોગના પરિણામો કોષ્ટકમાં બતાવવામાં આવ્યા છે:

અર્થ પરિમાણ	પરિમાણ મૂલ્ય	પરિમાણ મૂલ્ય	ચોકસાઈ પ્રાપ્ત કરી	પુનરાવર્તનોની સંખ્યા

પ્રાપ્ત પરિણામો પરથી, અમે પરિમાણોની શ્રેષ્ઠ પસંદગી વિશે નિષ્કર્ષ પર આવી શકીએ છીએ: , જો કે પદ્ધતિ પરિમાણોની પસંદગી માટે ખૂબ સંવેદનશીલ નથી.

સૌથી ઊભો ઉતરવાની પદ્ધતિ

સૌથી ઊંચુંનીચું થતું વંશ પદ્ધતિના કન્વર્જન્સનો અભ્યાસ કરવા માટે, નીચેનું કાર્ય પસંદ કરવામાં આવ્યું હતું:

પ્રારંભિક અંદાજ બિંદુ (10,10) છે. સ્ટોપીંગ માપદંડ વપરાયેલ:

એક-પરિમાણીય ઑપ્ટિમાઇઝેશન સમસ્યાઓ ઉકેલવા માટે, સુવર્ણ વિભાગ પદ્ધતિનો ઉપયોગ કરવામાં આવ્યો હતો.

પદ્ધતિએ 9 પુનરાવર્તનોમાં 6e-8 ની ચોકસાઈ પ્રાપ્ત કરી.

આના પરથી આપણે નિષ્કર્ષ પર આવી શકીએ છીએ કે સ્ટેપ-સ્પ્લિટ ગ્રેડિયન્ટ મેથડ અને કોન્સ્ટન્ટ-સ્ટેપ ગ્રેડિયન્ટ ડિસેન્ટ મેથડ કરતાં સ્ટીપસ્ટ ડિસેન્ટ મેથડ વધુ ઝડપથી કન્વર્જ થાય છે.

સૌથી ઊંચો વંશ પદ્ધતિનો ગેરલાભ એ છે કે તેને એક-પરિમાણીય ઑપ્ટિમાઇઝેશન સમસ્યા હલ કરવાની જરૂર છે.

જ્યારે પ્રોગ્રામિંગ ગ્રેડિયન્ટ ડિસેન્ટ પદ્ધતિઓ, તમારે પરિમાણો પસંદ કરતી વખતે સાવચેત રહેવું જોઈએ, એટલે કે

· સતત સ્ટેપ સાથે ગ્રેડિયન્ટ ડિસેન્ટ પદ્ધતિ: પગલું 0.01 કરતા ઓછું પસંદ કરવું જોઈએ, અન્યથા પદ્ધતિ અલગ પડે છે (અભ્યાસ કરવામાં આવી રહેલા કાર્યના આધારે, આવા પગલા સાથે પણ પદ્ધતિ અલગ પડી શકે છે).
સ્ટેપ ડિવિઝન સાથેની ઢાળ પદ્ધતિ પરિમાણોની પસંદગી માટે ખૂબ સંવેદનશીલ નથી. પરિમાણો પસંદ કરવા માટેના વિકલ્પોમાંથી એક:
· સૌથી ઊંચો વંશ પદ્ધતિ: સુવર્ણ ગુણોત્તર પદ્ધતિ (જ્યારે લાગુ હોય ત્યારે) એક-પરિમાણીય ઑપ્ટિમાઇઝેશન પદ્ધતિ તરીકે ઉપયોગ કરી શકાય છે.

કન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિ એ બહુપરીમાણીય જગ્યામાં બિનશરતી ઑપ્ટિમાઇઝેશન માટે પુનરાવર્તિત પદ્ધતિ છે. પદ્ધતિનો મુખ્ય ફાયદો એ છે કે તે મર્યાદિત સંખ્યામાં પગલાઓમાં ચતુર્ભુજ ઑપ્ટિમાઇઝેશન સમસ્યાને હલ કરે છે. તેથી, પ્રથમ ચતુર્ભુજ કાર્યાત્મકને ઑપ્ટિમાઇઝ કરવા માટે સંયોજક ઢાળ પદ્ધતિ વર્ણવવામાં આવે છે, પુનરાવર્તિત સૂત્રો લેવામાં આવે છે, અને કન્વર્જન્સ દરના અંદાજો આપવામાં આવે છે. આ પછી, તે બતાવવામાં આવે છે કે કેવી રીતે સંલગ્ન પદ્ધતિને મનસ્વી કાર્યાત્મક ઑપ્ટિમાઇઝ કરવા માટે સામાન્યીકરણ કરવામાં આવે છે, પદ્ધતિના વિવિધ પ્રકારો ધ્યાનમાં લેવામાં આવે છે, અને કન્વર્જન્સની ચર્ચા કરવામાં આવે છે.

ઑપ્ટિમાઇઝેશન સમસ્યાનું નિવેદન

ચાલો સેટ આપીએ અને આ સેટ પર એક ઉદ્દેશ્ય કાર્ય વ્યાખ્યાયિત કરીએ. ઑપ્ટિમાઇઝેશન સમસ્યામાં સેટ પર ઉદ્દેશ્ય કાર્યની ચોક્કસ ઉપલા અથવા ચોક્કસ નીચલા બાઉન્ડ શોધવાનો સમાવેશ થાય છે. બિંદુઓનો સમૂહ કે જેના પર ઉદ્દેશ્ય કાર્યની નીચલી સીમા પહોંચી છે તે નિયુક્ત કરવામાં આવે છે.

જો, પછી ઑપ્ટિમાઇઝેશન સમસ્યાને અનિયંત્રિત કહેવામાં આવે છે. જો, પછી ઑપ્ટિમાઇઝેશન સમસ્યાને અવરોધિત કહેવામાં આવે છે.

ચતુર્ભુજ કાર્યાત્મક માટે સંયોજિત ઢાળ પદ્ધતિ

પદ્ધતિનું નિવેદન

નીચેની ઑપ્ટિમાઇઝેશન સમસ્યાને ધ્યાનમાં લો:

અહીં એક સપ્રમાણ હકારાત્મક ચોક્કસ માપ મેટ્રિક્સ છે. આ ઑપ્ટિમાઇઝેશન સમસ્યાને ચતુર્ભુજ કહેવામાં આવે છે. તેની નોંધ લો. ફંક્શનના એક્સ્ટ્રીમમ માટેની શરત સિસ્ટમની સમકક્ષ છે. ફંક્શન સમીકરણ દ્વારા વ્યાખ્યાયિત એક બિંદુ પર તેની નીચલા બાઉન્ડ સુધી પહોંચે છે. આમ, આ ઓપ્ટિમાઇઝેશન સમસ્યા રેખીય સમીકરણોની સિસ્ટમને હલ કરવા માટે ઓછી થાય છે, સંયોજક ઢાળ પદ્ધતિનો વિચાર નીચે મુજબ છે: ચાલો આધાર બનાવીએ. પછી કોઈપણ બિંદુ માટે વેક્ટરને આધારમાં વિસ્તૃત કરવામાં આવે છે આમ, તેને ફોર્મમાં રજૂ કરી શકાય છે

દરેક અનુગામી અંદાજ સૂત્રનો ઉપયોગ કરીને ગણવામાં આવે છે:

વ્યાખ્યા. બે વેક્ટર અને સપ્રમાણ મેટ્રિક્સ B જો માટે સંયોજક હોવાનું કહેવાય છે

ચાલો સંયોજક ઢાળ પદ્ધતિમાં આધાર બાંધવાની પદ્ધતિનું વર્ણન કરીએ અમે પ્રારંભિક અંદાજ તરીકે આર્બિટરી વેક્ટર પસંદ કરીએ છીએ. દરેક પુનરાવર્તન પર નીચેના નિયમો પસંદ કરવામાં આવે છે:

આધાર વેક્ટરની ગણતરી સૂત્રોનો ઉપયોગ કરીને કરવામાં આવે છે:

ગુણાંક પસંદ કરવામાં આવે છે જેથી વેક્ટર અને A ના સંદર્ભમાં સંયોજિત હોય.

જો આપણે દ્વારા સૂચવીએ છીએ, તો પછી ઘણી સરળીકરણો પછી આપણે વ્યવહારમાં સંયોજક ઢાળ પદ્ધતિ લાગુ કરતી વખતે ઉપયોગમાં લેવાતા અંતિમ સૂત્રો મેળવીએ છીએ:

સંયોજક ઢાળ પદ્ધતિ માટે, નીચેનું પ્રમેય ધરાવે છે: પ્રમેય ચાલો, જ્યાં કદનું સપ્રમાણ હકારાત્મક નિશ્ચિત મેટ્રિક્સ છે. પછી કન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિ પગલાંઓ કરતાં વધુ નહીં અને નીચેના સંબંધો ધરાવે છે:

પદ્ધતિનું કન્વર્જન્સ

જો બધી ગણતરીઓ સચોટ હોય અને પ્રારંભિક ડેટા સચોટ હોય, તો પદ્ધતિ પુનરાવર્તિત કરતાં વધુમાં સિસ્ટમને હલ કરવા માટે કન્વર્જ થાય છે, સિસ્ટમનું પરિમાણ ક્યાં છે. વધુ શુદ્ધ પૃથ્થકરણ દર્શાવે છે કે પુનરાવૃત્તિની સંખ્યા ઓળંગતી નથી, જ્યાં મેટ્રિક્સ A ના વિવિધ ઇજનવેલ્યુની સંખ્યા છે. કન્વર્જન્સના દરનો અંદાજ કાઢવા માટે, નીચેનો (બદલે રફ) અંદાજ સાચો છે:

જો મેટ્રિક્સના મહત્તમ અને ન્યૂનતમ ઇજેનવેલ્યુ માટેના અંદાજો જાણીતા હોય, તો તે તમને કન્વર્જન્સના દરનો અંદાજ કાઢવાની મંજૂરી આપે છે, વ્યવહારમાં, નીચેના સ્ટોપિંગ માપદંડનો મોટાભાગે ઉપયોગ થાય છે:

કોમ્પ્યુટેશનલ જટિલતા

પદ્ધતિના દરેક પુનરાવર્તન પર, કામગીરી કરવામાં આવે છે. ઉત્પાદનની ગણતરી કરવા માટે આ સંખ્યાની કામગીરી જરૂરી છે - દરેક પુનરાવર્તનમાં આ સૌથી વધુ સમય લેતી પ્રક્રિયા છે. અન્ય ગણતરીઓ માટે O(n) કામગીરીની જરૂર પડે છે. પદ્ધતિની કુલ કોમ્પ્યુટેશનલ જટિલતા ઓળંગતી નથી - કારણ કે પુનરાવર્તનોની સંખ્યા n કરતાં વધુ નથી.

સંખ્યાત્મક ઉદાહરણ

ચાલો આપણે એવી સિસ્ટમને ઉકેલવા માટે કન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિ લાગુ કરીએ જ્યાં, સંયોજક ઢાળ પદ્ધતિનો ઉપયોગ કરીને, આ સિસ્ટમનો ઉકેલ બે પુનરાવર્તનોમાં મેળવવામાં આવે છે. મેટ્રિક્સના ઇજેનવેલ્યુ 5, 5, -5 છે - તેમાંથી બે અલગ અલગ છે, તેથી, સૈદ્ધાંતિક અંદાજ મુજબ, પુનરાવર્તનોની સંખ્યા બે કરતા વધી શકતી નથી

સકારાત્મક નિશ્ચિત મેટ્રિક્સ સાથે SLAE ને ઉકેલવા માટેની સૌથી અસરકારક પદ્ધતિઓમાંની એક સંયોજક ઢાળ પદ્ધતિ છે. પદ્ધતિ મર્યાદિત સંખ્યામાં પગલાઓમાં સંકલનની બાંયધરી આપે છે, અને જરૂરી ચોકસાઈ ઘણી વહેલી પ્રાપ્ત કરી શકાય છે. મુખ્ય સમસ્યા એ છે કે ભૂલોના સંચયને કારણે, બેઝિસ વેક્ટર્સની ઓર્થોગોનાલિટીનું ઉલ્લંઘન થઈ શકે છે, જે કન્વર્જન્સને બગાડે છે.

સામાન્ય રીતે સંયોજિત ઢાળ પદ્ધતિ

ચાલો હવે જ્યારે લઘુત્તમ કાર્યાત્મક ચતુર્ભુજ ન હોય તેવા કેસ માટે સંયોજક ઢાળ પદ્ધતિમાં ફેરફારને ધ્યાનમાં લઈએ: અમે સમસ્યા હલ કરીશું:

સતત વિભેદક કાર્ય. આ સમસ્યાને ઉકેલવા માટે સંયોજક ઢાળ પદ્ધતિને સંશોધિત કરવા માટે, મેટ્રિક્સ A નો સમાવેશ કરતા નથી તેવા સૂત્રો મેળવવા જરૂરી છે:

ત્રણમાંથી એક સૂત્રનો ઉપયોગ કરીને ગણતરી કરી શકાય છે:

1. - ફ્લેચર-રીવ્ઝ પદ્ધતિ

2. - પોલાક-રીબી`રે પદ્ધતિ

જો કાર્ય ચતુર્ભુજ અને સખત રીતે બહિર્મુખ હોય, તો ત્રણેય સૂત્રો સમાન પરિણામ આપે છે. જો એક મનસ્વી કાર્ય છે, તો પછી દરેક સૂત્ર સંયોજક ઢાળ પદ્ધતિના પોતાના ફેરફારને અનુરૂપ છે. ત્રીજા સૂત્રનો ભાગ્યે જ ઉપયોગ થાય છે કારણ કે તેને પદ્ધતિના દરેક પગલા પર ફંક્શન અને ફંક્શનના હેસિયનની ગણતરીની જરૂર છે.

જો ફંક્શન ચતુર્ભુજ ન હોય, તો સંયોજક ઢાળ પદ્ધતિ મર્યાદિત સંખ્યામાં પગલાંઓમાં એકરૂપ થઈ શકશે નહીં. તદુપરાંત, દરેક પગલા પર સચોટ ગણતરી ફક્ત દુર્લભ કિસ્સાઓમાં જ શક્ય છે. તેથી, ભૂલોનું સંચય એ હકીકત તરફ દોરી જાય છે કે વેક્ટર્સ હવે કાર્યના ઘટાડાની દિશા સૂચવતા નથી. પછી અમુક તબક્કે તેઓ માને છે. તમામ સંખ્યાઓનો સમૂહ કે જેના પર તે સ્વીકારવામાં આવે છે તે દ્વારા સૂચિત કરવામાં આવશે. નંબરોને મેથડ અપડેટ મોમેન્ટ્સ કહેવામાં આવે છે. વ્યવહારમાં, તે ઘણીવાર પસંદ કરવામાં આવે છે કે જગ્યાનું પરિમાણ ક્યાં છે.

પદ્ધતિનું કન્વર્જન્સ

ફ્લેચર-રીવ્ઝ પદ્ધતિ માટે, એક કન્વર્જન્સ પ્રમેય છે જે ફંક્શનને ન્યૂનતમ કરવા પર ખૂબ કડક શરતો લાદતું નથી: પ્રમેય. નીચેની શરતોને સંતોષવા દો:

વિવિધતા મર્યાદિત છે

વ્યુત્પન્ન અમુક પડોશમાં સ્થિરતા સાથે લિપ્સિટ્ઝની સ્થિતિને સંતોષે છે

સેટ M: .

પોલાક-રીબર પદ્ધતિ માટે, કન્વર્જન્સ એ ધારણા હેઠળ સાબિત થાય છે કે જે સખત રીતે બહિર્મુખ કાર્ય છે. સામાન્ય કિસ્સામાં, પોલાક-રીબર પદ્ધતિના સંકલનને સાબિત કરવું અશક્ય છે. તેનાથી વિપરીત, નીચેનું પ્રમેય સાચું છે: પ્રમેય. ચાલો ધારીએ કે પોલાક-રીબર પદ્ધતિમાં દરેક પગલા પરના મૂલ્યોની બરાબર ગણતરી કરવામાં આવે છે. પછી ત્યાં એક કાર્ય છે, અને પ્રારંભિક અનુમાન, જેમ કે.

જો કે, વ્યવહારમાં પોલાક-રીબર પદ્ધતિ વધુ સારી રીતે કામ કરે છે. વ્યવહારમાં સૌથી સામાન્ય સ્ટોપિંગ માપદંડ: ગ્રેડિયન્ટ નોર્મ ચોક્કસ થ્રેશોલ્ડ કરતા ઓછો થઈ જાય છે. m સળંગ પુનરાવર્તનો માટે ફંક્શનનું મૂલ્ય લગભગ યથાવત રહ્યું છે.

કોમ્પ્યુટેશનલ જટિલતા

પોલાક-રીબર અથવા ફ્લેચર-રીવ્સ પદ્ધતિઓના દરેક પુનરાવૃત્તિ પર, કાર્ય અને તેના ઢાળની ગણતરી એકવાર કરવામાં આવે છે, અને એક-પરિમાણીય ઑપ્ટિમાઇઝેશન સમસ્યા હલ થાય છે. આમ, કન્જુગેટ ગ્રેડિયન્ટ મેથડના એક સ્ટેપની જટિલતા એ જ ક્રમની તીવ્રતાના ક્રમની છે જેટલી સ્ટીપ ડિસેન્ટ પદ્ધતિના એક સ્ટેપની જટિલતા છે. વ્યવહારમાં, સંયોજક ઢાળ પદ્ધતિ શ્રેષ્ઠ કન્વર્જન્સ ઝડપ દર્શાવે છે.

અમે કન્જુગેટ ગ્રેડિયન્ટ મેથડનો ઉપયોગ કરીને ન્યૂનતમ ફંક્શન શોધીશું

આ ફંક્શનનું ન્યૂનતમ 1 છે અને તે બિંદુ (5, 4) પર પહોંચે છે. ઉદાહરણ તરીકે આ ફંક્શનનો ઉપયોગ કરીને, ચાલો પોલાક-રીબર અને ફ્લેચર-રીવ્ઝ પદ્ધતિઓની તુલના કરીએ. જ્યારે વર્તમાન સ્ટેપ પર ઢાળનો ચોરસ ધોરણ નાનો બને છે ત્યારે બંને પદ્ધતિઓમાં પુનરાવર્તનો બંધ થાય છે. પસંદગી માટે ગોલ્ડન રેશિયો પદ્ધતિનો ઉપયોગ થાય છે

ફ્લેચર-રીવ્ઝ પદ્ધતિ	પોલાક-રીબર પદ્ધતિ
પુનરાવર્તનોની સંખ્યા	ઉકેલ મળ્યો	કાર્ય મૂલ્ય	પુનરાવર્તનોની સંખ્યા	ઉકેલ મળ્યો	કાર્ય મૂલ્ય
		(5.01382198,3.9697932)			(5.03942877,4.00003512)
		(5.01056482,3.99018026)			(4.9915894,3.99999044)
		(4.9979991,4.00186173)			(5.00336181,4.0000018)
		(4.99898277,4.00094645)			(4.99846808,3.99999918)
		(4.99974658,4.0002358)			(4.99955034,3.99999976)

સંયોજક ઢાળ પદ્ધતિના બે સંસ્કરણો અમલમાં મૂકવામાં આવ્યા છે: ચતુર્ભુજ કાર્યાત્મકને ઘટાડવા માટે, અને મનસ્વી કાર્યને ઘટાડવા માટે. પ્રથમ કિસ્સામાં, પદ્ધતિ વેક્ટર કાર્ય દ્વારા લાગુ કરવામાં આવે છે શોધ ઉકેલ(મેટ્રિક્સ એ, વેક્ટર b) અહીં A અને b એ ચતુર્ભુજ ઑપ્ટિમાઇઝેશન સમસ્યાની વ્યાખ્યામાં સામેલ મેટ્રિક્સ અને વેક્ટર છે. મનસ્વી કાર્યક્ષમતાને ઘટાડવા માટે, તમે બેમાંથી એક ફંક્શનનો ઉપયોગ કરી શકો છો: વેક્ટર FletcherRievesMethod(int spaceSize, Function F, વેક્ટર (*GradF) (વેક્ટર )) વેક્ટર PolakRibiereMethod(int spaceSize, function F, વેક્ટર (*GradF) (વેક્ટર )) બંને કાર્યો માટેના પરિમાણો સમાન છે અને તેનો નીચેનો અર્થ છે: spaceSize - જગ્યાનું પરિમાણ (ચલોની સંખ્યા કે જેના પર ન્યૂનતમ કાર્યાત્મક આધાર રાખે છે) F - લઘુત્તમ કરવા માટેના ફંક્શન માટે એક નિર્દેશક. કાર્ય ડબલ સ્વરૂપનું હોવું જોઈએ<имя функции>(વેક્ટર ) ગ્રાડએફ - એક પરિમાણીય ઑપ્ટિમાઇઝેશન સમસ્યાને ઉકેલવા માટે બંને પદ્ધતિઓ સહાયક કાર્યનો ઉપયોગ કરે છે જે લઘુત્તમ કાર્યાત્મકના ઢાળની ગણતરી કરે છે. પ્રોગ્રામ ગોલ્ડન સેક્શન પદ્ધતિનો ઉપયોગ કરીને એક-પરિમાણીય ઑપ્ટિમાઇઝેશનનો અમલ કરે છે.

ઑપ્ટિમાઇઝેશન સમસ્યાઓ ઉકેલવા માટે ગ્રેડિયન્ટ ડિસેન્ટ પદ્ધતિઓ ખૂબ શક્તિશાળી સાધનો છે. પદ્ધતિઓનો મુખ્ય ગેરલાભ એ લાગુ કરવાની મર્યાદિત શ્રેણી છે. કન્જુગેટ ગ્રેડિયન્ટ મેથડ ગ્રેડિયન્ટ ડિસેન્ટ મેથડની જેમ જ એક બિંદુ પર ઇન્ક્રીમેન્ટના રેખીય ભાગ વિશેની માહિતીનો ઉપયોગ કરે છે. તદુપરાંત, સંયોજક ઢાળ પદ્ધતિ તમને મર્યાદિત સંખ્યામાં પગલાઓમાં ચતુર્ભુજ સમસ્યાઓ હલ કરવાની મંજૂરી આપે છે. અન્ય ઘણી સમસ્યાઓ પર, કન્જુગેટ ગ્રેડિયન્ટ મેથડ પણ ગ્રેડિયન્ટ ડિસેન્ટ મેથડ કરતાં આગળ છે. એક-પરિમાણીય ઑપ્ટિમાઇઝેશન સમસ્યાને કેટલી સચોટ રીતે હલ કરવામાં આવે છે તેના પર ઢાળ પદ્ધતિનું કન્વર્જન્સ નોંધપાત્ર રીતે આધાર રાખે છે. સંભવિત પદ્ધતિ લૂપ્સ અપડેટ્સનો ઉપયોગ કરીને ઉકેલવામાં આવે છે. જો કે, જો કોઈ પદ્ધતિ સ્થાનિક ન્યૂનતમ કાર્યમાં પ્રવેશ કરે છે, તો તે મોટે ભાગે તેમાંથી છટકી શકશે નહીં.

દરેક પુનરાવૃત્તિ પર સૌથી ઊંચો વંશ પદ્ધતિનો ઉપયોગ કરતી વખતે, પગલાનું કદ એ આર ફંક્શનની ન્યૂનતમ સ્થિતિમાંથી પસંદ કરવામાં આવે છે f(x)વંશની દિશામાં, એટલે કે.

f(x[આર] -a આર -f"(x[આર])) = f(x f'(x -af"(x[આર])) .

j (a) = f(x[આર]-af"(x[આર])) .

સૌથી ઊંચો વંશ પદ્ધતિનો અલ્ગોરિધમ નીચે મુજબ છે.

1. પ્રારંભિક બિંદુના કોઓર્ડિનેટ્સ સેટ કરો એક્સ.
2. બિંદુ પર એક્સ[આર], k = 0, 1, 2, ... ગ્રેડિયન્ટ મૂલ્યની ગણતરી કરે છે -f"(x[આર]) .
3. પગલાનું કદ નક્કી કરવામાં આવે છે a k, એક-પરિમાણીય લઘુત્તમીકરણ દ્વારા એકાર્યો જે (a) = f(x[આર]-af"(x[આર])).
4. બિંદુના કોઓર્ડિનેટ્સ નક્કી કરવામાં આવે છે એક્સ[X[ 1]:

એક્સ N(x) [X[ 1]1) પ્રક્રિયા 1-4 ની પુનરાવૃત્તિ ચક્રીય રીતે રિપ્લેસમેન્ટ સાથે પુનરાવર્તિત થાય છે N(x) [આર] -એ આર f" N(x) (એક્સ[આર]), i = 1,..., p.

વિચારણા હેઠળની પદ્ધતિમાં, બિંદુથી ચળવળની દિશા એક્સ[આર] બિંદુ પર સ્તર રેખાને સ્પર્શે છે k+[X[ 1] (ફિગ. 2.9). વંશનો માર્ગ વાંકોચૂંકો છે, જેમાં અડીને આવેલા ઝિગઝેગ એકબીજા સાથે ઓર્થોગોનલ લિંક્સ છે. ખરેખર, એક પગલું a k ને નાનું કરીને પસંદ કરવામાં આવે છે એકાર્યો? (a) = f(x f'(x -af"(x[આર])) . કાર્યના ન્યૂનતમ માટે જરૂરી શરત કાર્યના ન્યૂનતમ માટે જરૂરી શરત j ડીજટિલ કાર્યના વ્યુત્પન્નની ગણતરી કર્યા પછી, અમે પડોશી બિંદુઓ પર વંશ દિશાઓના વેક્ટરની ઓર્થોગોનાલિટી માટેની સ્થિતિ મેળવીએ છીએ:

કાર્યના ન્યૂનતમ માટે જરૂરી શરત j (a)/da = -f"(x[X[ 1]-f"(x[આર]) = 0.

ચોખા. 2.9.

સરળ બહિર્મુખ કાર્યો માટે ગ્રેડિયન્ટ પદ્ધતિઓ ઉચ્ચ ઝડપે (ભૌમિતિક પ્રગતિની ગતિ) પર ન્યૂનતમ પર એકરૂપ થાય છે. આવા કાર્યો સૌથી મહાન છે સૌથી ઊભો વંશ પદ્ધતિનું ભૌમિતિક અર્થઘટનઅને ઓછામાં ઓછું એમબીજા ડેરિવેટિવ્ઝના મેટ્રિક્સના ઇજેન મૂલ્યો (હેસિયન મેટ્રિક્સ)

એકબીજાથી થોડું અલગ છે, એટલે કે મેટ્રિક્સ બીજા ડેરિવેટિવ્ઝના મેટ્રિક્સના ઇજેન મૂલ્યો (હેસિયન મેટ્રિક્સ)સારી રીતે કન્ડિશન્ડ. યાદ કરો કે ઇજનવેલ્યુઝ l i, N(x) =1, …, n, મેટ્રિસીસ એ લાક્ષણિક સમીકરણના મૂળ છે

ચોખા. 2.10.

ઢાળ પદ્ધતિઓનો કન્વર્જન્સ દર પણ ગ્રેડિયન્ટ ગણતરીઓની ચોકસાઈ પર નોંધપાત્ર રીતે આધાર રાખે છે. ચોકસાઈની ખોટ, જે સામાન્ય રીતે ન્યૂનતમ બિંદુઓની નજીકમાં અથવા ગલીની પરિસ્થિતિમાં થાય છે, તે સામાન્ય રીતે ગ્રેડિએન્ટ ડિસેન્ટ પ્રક્રિયાના કન્વર્જન્સને વિક્ષેપિત કરી શકે છે. ઉપરોક્ત કારણોને લીધે, સમસ્યાને ઉકેલવાના પ્રારંભિક તબક્કે ઢાળ પદ્ધતિઓનો ઉપયોગ અન્ય, વધુ અસરકારક પદ્ધતિઓ સાથે સંયોજનમાં થાય છે. આ કિસ્સામાં, બિંદુ એક્સલઘુત્તમ બિંદુથી દૂર છે, અને એન્ટિગ્રેડિયન્ટની દિશામાં પગલાઓ કાર્યમાં નોંધપાત્ર ઘટાડો પ્રાપ્ત કરવાનું શક્ય બનાવે છે.

સૌથી ઊંચો વંશ પદ્ધતિ (અંગ્રેજી સાહિત્યમાં "બેહદ વંશની પદ્ધતિ") એ ઑપ્ટિમાઇઝેશન સમસ્યાઓ હલ કરવા માટે પુનરાવર્તિત સંખ્યાત્મક પદ્ધતિ (પ્રથમ ક્રમ) છે, જે તમને ઉદ્દેશ્ય કાર્યની સીમા (ન્યૂનતમ અથવા મહત્તમ) નક્કી કરવાની મંજૂરી આપે છે:

વાસ્તવિક ડોમેન પર ફંક્શન દલીલ (નિયંત્રિત પરિમાણો) ના મૂલ્યો છે.

વિચારણા હેઠળની પદ્ધતિ અનુસાર, ઉદ્દેશ્ય કાર્યની સીમા (મહત્તમ અથવા લઘુત્તમ) કાર્યના સૌથી ઝડપી વધારો (ઘટાડા) ની દિશામાં નક્કી કરવામાં આવે છે, એટલે કે. કાર્યના ઢાળ (એન્ટિ-ગ્રેડિયન્ટ) ની દિશામાં. એક બિંદુ પર ગ્રેડિયન્ટ ફંક્શન એક વેક્ટર છે જેના સંકલન અક્ષો પરના અંદાજો કોઓર્ડિનેટના સંદર્ભમાં ફંક્શનના આંશિક ડેરિવેટિવ્ઝ છે:

જ્યાં i, j,…, n એ સંકલન અક્ષોની સમાંતર એકમ વેક્ટર છે.

આધાર બિંદુ પર ઢાળ સપાટી પર સખત રીતે ઓર્થોગોનલ છે, અને તેની દિશા કાર્યમાં સૌથી ઝડપી વૃદ્ધિની દિશા બતાવે છે, અને વિરુદ્ધ દિશા (એન્ટિગ્રેડિયન્ટ), અનુક્રમે, કાર્યના સૌથી ઝડપી ઘટાડાની દિશા દર્શાવે છે.

સૌથી ઊંચો વંશ પદ્ધતિ એ ઢાળવાળી વંશ પદ્ધતિનો વધુ વિકાસ છે. સામાન્ય રીતે, ફંક્શનની સીમા શોધવાની પ્રક્રિયા એ પુનરાવર્તિત પ્રક્રિયા છે, જે નીચે પ્રમાણે લખાયેલ છે:

જ્યાં "+" ચિહ્નનો ઉપયોગ મહત્તમ કાર્ય શોધવા માટે થાય છે, અને "-" ચિહ્નનો ઉપયોગ લઘુત્તમ કાર્ય શોધવા માટે થાય છે;

એકમ દિશા વેક્ટર, જે સૂત્ર દ્વારા નક્કી થાય છે:

- ગ્રેડિયન્ટ મોડ્યુલ ગ્રેડિયન્ટ અથવા એન્ટી-ગ્રેડિયન્ટની દિશામાં ફંક્શનના વધારા અથવા ઘટાડાનો દર નક્કી કરે છે:

એક સ્થિરાંક જે પગલાનું કદ નક્કી કરે છે અને તે તમામ i-th દિશાઓ માટે સમાન છે.

ચળવળની દિશામાં લઘુત્તમ ઉદ્દેશ્ય ફંક્શન f(x) ની સ્થિતિમાંથી સ્ટેપનું કદ પસંદ કરવામાં આવે છે, એટલે કે, ઢાળ અથવા એન્ટિગ્રેડિયન્ટની દિશામાં એક-પરિમાણીય ઑપ્ટિમાઇઝેશન સમસ્યાને ઉકેલવાના પરિણામે:

બીજા શબ્દોમાં કહીએ તો, પગલાનું કદ આ સમીકરણને હલ કરીને નક્કી કરવામાં આવે છે:

આમ, ગણતરીનું પગલું એવી રીતે પસંદ કરવામાં આવે છે કે જ્યાં સુધી કાર્ય સુધરે નહીં ત્યાં સુધી ચળવળ હાથ ધરવામાં આવે છે, આમ અમુક બિંદુએ એક્સ્ટ્રીમમ સુધી પહોંચે છે. આ બિંદુએ, શોધ દિશા ફરીથી નક્કી કરવામાં આવે છે (ગ્રેડિયન્ટનો ઉપયોગ કરીને) અને ઉદ્દેશ્ય કાર્યના નવા શ્રેષ્ઠ બિંદુની માંગ કરવામાં આવે છે, વગેરે. આમ, આ પદ્ધતિમાં, શોધ મોટા પગલાઓમાં થાય છે, અને કાર્યના ઢાળની ગણતરી પોઈન્ટની નાની સંખ્યામાં થાય છે.

બે ચલોના કાર્યના કિસ્સામાં, આ પદ્ધતિમાં નીચેની ભૌમિતિક અર્થઘટન છે: બિંદુ પરથી ચળવળની દિશા બિંદુ પરની સ્તર રેખાને સ્પર્શે છે. વંશનો માર્ગ વાંકોચૂંકો છે, જેમાં અડીને આવેલા ઝિગઝેગ એકબીજા સાથે ઓર્થોગોનલ લિંક્સ છે. પડોશી બિંદુઓ પર વંશ દિશાઓના વેક્ટરની ઓર્થોગોનાલિટી માટેની સ્થિતિ નીચેની અભિવ્યક્તિ દ્વારા લખાયેલ છે:

ફંક્શન f(x) ના સમાન સ્તરની રેખાના ગ્રાફ પર દર્શાવવામાં આવેલ સૌથી ઊભો વંશ પદ્ધતિનો ઉપયોગ કરીને છેડાના બિંદુ સુધીની હિલચાલનો માર્ગ

પુનરાવર્તિત ગણતરીના પગલા (કેટલાક માપદંડો) પર શ્રેષ્ઠ ઉકેલની શોધ સમાપ્ત થાય છે:

શોધ માર્ગ વર્તમાન શોધ બિંદુના નાના પડોશમાં રહે છે:

ઉદ્દેશ્ય કાર્યનો વધારો બદલાતો નથી:

સ્થાનિક લઘુત્તમ બિંદુ પર ઉદ્દેશ્ય કાર્યનો ઢાળ શૂન્ય બને છે:

એ નોંધવું જોઈએ કે કોતર સાથે આગળ વધતી વખતે ગ્રેડિયન્ટ ડિસેન્ટ પદ્ધતિ ખૂબ જ ધીમી હોય છે, અને ઉદ્દેશ્ય કાર્યમાં ચલોની સંખ્યા વધે છે, પદ્ધતિની આ વર્તણૂક લાક્ષણિક બની જાય છે. કોતર એ ડિપ્રેશન છે, જેની સ્તર રેખાઓ લગભગ અર્ધ-અક્ષો સાથે લંબગોળ આકાર ધરાવે છે જે ઘણી વખત અલગ પડે છે. કોતરની હાજરીમાં, ઉતરતા માર્ગ નાના પગલા સાથે ઝિગઝેગ લાઇનનું સ્વરૂપ લે છે, જેના પરિણામે લઘુત્તમ સુધી ઉતરવાની પરિણામી ગતિ ઘણી ધીમી થઈ જાય છે. આ એ હકીકત દ્વારા સમજાવવામાં આવ્યું છે કે આ કાર્યોના એન્ટિગ્રેડિયન્ટની દિશા દિશાથી લઘુત્તમ બિંદુ તરફ નોંધપાત્ર રીતે વિચલિત થાય છે, જે ગણતરીમાં વધારાના વિલંબ તરફ દોરી જાય છે. પરિણામે, અલ્ગોરિધમ કોમ્પ્યુટેશનલ કાર્યક્ષમતા ગુમાવે છે.

ગલી કાર્ય

ગ્રેડિયન્ટ પદ્ધતિ, તેના અસંખ્ય ફેરફારો સાથે, અભ્યાસ હેઠળના ઑબ્જેક્ટ્સની શ્રેષ્ઠતાને શોધવા માટેની એક સામાન્ય અને અસરકારક પદ્ધતિ છે. ગ્રેડિયન્ટ શોધનો ગેરલાભ (તેમજ ઉપર ચર્ચા કરેલી પદ્ધતિઓ) એ છે કે તેનો ઉપયોગ કરતી વખતે, ફંક્શનની માત્ર સ્થાનિક સીમા શોધી શકાય છે. અન્ય સ્થાનિક એક્સ્ટ્રીમા શોધવા માટે, અન્ય પ્રારંભિક બિંદુઓથી શોધ કરવી જરૂરી છે. ઉપરાંત, ગ્રેડિયન્ટ પદ્ધતિઓનો કન્વર્જન્સ દર પણ ગ્રેડિયન્ટ ગણતરીઓની ચોકસાઈ પર નોંધપાત્ર રીતે આધાર રાખે છે. ચોકસાઈની ખોટ, જે સામાન્ય રીતે ન્યૂનતમ બિંદુઓની નજીકમાં અથવા ગલીની પરિસ્થિતિમાં થાય છે, તે સામાન્ય રીતે ગ્રેડિએન્ટ ડિસેન્ટ પ્રક્રિયાના કન્વર્જન્સને વિક્ષેપિત કરી શકે છે.

ગણતરી પદ્ધતિ

પગલું 1:કાર્યના ઢાળની ગણતરી કરવા માટે વિશ્લેષણાત્મક અભિવ્યક્તિઓ (પ્રતિકાત્મક સ્વરૂપમાં) ની વ્યાખ્યા

પગલું 2: પ્રારંભિક અંદાજ સેટ કરો

પગલું 3:છેલ્લી શોધ દિશાને ફરીથી સેટ કરવા માટે અલ્ગોરિધમિક પ્રક્રિયાને પુનઃપ્રારંભ કરવાની જરૂરિયાત નક્કી કરવામાં આવે છે. પુનઃપ્રારંભના પરિણામે, શોધ ફરીથી ઝડપી વંશની દિશામાં હાથ ધરવામાં આવે છે.

સતત પગથિયાં સાથે સૌથી ઊંચું ઉતરવાની પદ્ધતિ. સ્ટીપ ગ્રેડિયન્ટ ડિસેન્ટ પદ્ધતિ

1. સૌથી ઊભો ઉતરવાની પદ્ધતિ

સંખ્યાત્મક ઉદાહરણો