Subgradient method
અધોગામી પદ્ધતિઓ બહિર્મુખ લઘુતમ સમસ્યાઓ ઉકેલવા માટેની પુનરાવર્તિત પદ્ધતિઓ છે. મૂળરૂપે 1960 અને 1970 ના દાયકામાં નૌમ ઝેડ. શોર અને અન્ય લોકો દ્વારા વિકસાવવામાં આવી હતી, જ્યારે બિન-વિભેદક ઉદ્દેશ્ય કાર્ય પર પણ લાગુ કરવામાં આવે ત્યારે સબગ્રેડિયન્ટ પદ્ધતિઓ અભિસારી હોય છે. જ્યારે ઉદ્દેશ્ય કાર્ય વિભેદક હોય છે, ત્યારે અનિયંત્રિત સમસ્યાઓ માટે પેટા-ઢાળ પદ્ધતિઓ એ જ શોધ દિશાનો ઉપયોગ કરે છે જે સૌથી તીવ્ર વંશની પદ્ધતિ છે. જ્યારે સતત બે વાર વિભેદક બહિર્મુખ કાર્યોને ઘટાડવા માટે લાગુ કરવામાં આવે છે ત્યારે અધોગામી પદ્ધતિઓ ન્યૂટનની પદ્ધતિ કરતાં ધીમી હોય છે. જો કે, ન્યુટનની પદ્ધતિ બિન-વિભેદક સંકોચન ધરાવતી સમસ્યાઓ પર અભિસરણ કરવામાં નિષ્ફળ જાય છે. તાજેતરના વર્ષોમાં, બહિર્મુખ લઘુતમ સમસ્યાઓ માટે કેટલીક આંતરિક-બિંદુ પદ્ધતિઓ સૂચવવામાં આવી છે, પરંતુ અધોગામી પ્રક્ષેપણ પદ્ધતિઓ અને વંશના સંબંધિત બંડલ પદ્ધતિઓ સ્પર્ધાત્મક રહે છે. ખૂબ મોટી સંખ્યામાં પરિમાણો સાથે બહિર્મુખ લઘુતમ સમસ્યાઓ માટે, સબગ્રેડિએન્ટ-પ્રોજેક્શન પદ્ધતિઓ યોગ્ય છે, કારણ કે તેમને ઓછા સંગ્રહની જરૂર પડે છે. અધોગામી પ્રક્ષેપણ પદ્ધતિઓ ઘણીવાર વિઘટન તકનીકો સાથે મોટા પાયે સમસ્યાઓ પર લાગુ કરવામાં આવે છે. આવી વિઘટન પદ્ધતિઓ ઘણીવાર સમસ્યા માટે સરળ વિતરણ પદ્ધતિને મંજૂરી આપે છે. ક્લાસિકલ સબગ્રેડિએન્ટ નિયમો ચાલો ડોમેન સાથે બહિર્મુખ કાર્ય હોઈએ. એક શાસ્ત્રીય સબગ્રેડિએન્ટ પદ્ધતિ પુનરાવર્તન કરે છે જ્યાં એ. ટી. ના કોઈપણ સબગ્રેડિએન્ટને સૂચવે છે, અને તે તેનું પુનરાવર્તન છે. જો ડિફરેન્શીયેબલ હોય, તો તેનો એકમાત્ર સબગ્રેડિયન્ટ પોતે ગ્રેડિયન્ટ વેક્ટર છે. એવું બની શકે છે કે જે એટ માટે ઉતરતી દિશા નથી. તેથી અમે એક યાદી જાળવીએ છીએ જે અત્યાર સુધીમાં મળેલા સૌથી ઓછા ઉદ્દેશ્ય કાર્ય મૂલ્યનો ટ્રેક રાખે છે, એટલે કે. સ્ટેપ સાઇઝના નિયમો સબગ્રેડિએન્ટ પદ્ધતિઓ દ્વારા વિવિધ પ્રકારના સ્ટેપ-સાઇઝના નિયમોનો ઉપયોગ કરવામાં આવે છે. આ લેખ પાંચ શાસ્ત્રીય પગલા-કદના નિયમોની નોંધ કરે છે, જેના માટે અભિસરણ પુરાવાઓ જાણીતા છેઃ સતત પગલાનું કદ, સતત પગલાની લંબાઈ, જે ચોરસ સરવાળો આપે છે પરંતુ સરવાળો નહીં, એટલે કે. કોઈપણ પગલાનું કદ જે અસંપાદિત ઘટાડાને સંતોષ આપે છે, એટલે કે. કોઈપણ પગલાનું કદ જે અસંબદ્ધ ઘટતા પગલાની લંબાઈને સંતોષ આપે છે, એટલે કે. જ્યાં તમામ પાંચ નિયમો માટે, પદ્ધતિનું પુનરાવર્તન થાય તે પહેલાં પગલાના કદ "ઓફ-લાઇન" નક્કી કરવામાં આવે છે; પગલાના કદ અગાઉના પુનરાવર્તનો પર આધારિત નથી. સબગ્રેડિએન્ટ પદ્ધતિઓનો આ "ઓફ-લાઇન" ગુણધર્મ અવકલનીય કાર્યો માટે ઉતરતી પદ્ધતિઓ માટે ઉપયોગમાં લેવાતા "ઓન-લાઇન" પગલું-કદના નિયમોથી અલગ છેઃ અવકલનીય કાર્યોને ઘટાડવા માટેની ઘણી પદ્ધતિઓ અભિસરણ માટે વોલ્ફની પૂરતી શરતોને સંતોષે છે, જ્યાં પગલું-કદ સામાન્ય રીતે વર્તમાન બિંદુ અને વર્તમાન શોધ-દિશા પર આધાર રાખે છે. બર્ટસેકાસ અને બર્ટસેકાસ, નેડિક અને ઓઝડાગ્લર દ્વારા પુસ્તકોમાં વૃદ્ધિશીલ આવૃત્તિઓ સહિત સબગ્રેડિએન્ટ પદ્ધતિઓ માટે સ્ટેપસાઇઝ નિયમોની વ્યાપક ચર્ચા આપવામાં આવી છે. કન્વર્જન્સ પરિણામો યુક્લિડિયન ધોરણ એકની બરાબર હોય તેવા સતત પગલા-લંબાઈ અને માપેલા પેટા-ઘટકો માટે, પેટા-ઘટ પદ્ધતિ લઘુત્તમ મૂલ્યના આપખુદ નજીકના અંદાજમાં એકરૂપ થાય છે, જે શોરના પરિણામ દ્વારા છે. આ શાસ્ત્રીય સબગ્રેડિએન્ટ પદ્ધતિઓ નબળી કામગીરી ધરાવે છે અને હવે સામાન્ય ઉપયોગ માટે ભલામણ કરવામાં આવતી નથી. જો કે, તેઓ હજુ પણ વિશિષ્ટ કાર્યક્રમોમાં વ્યાપકપણે ઉપયોગમાં લેવાય છે કારણ કે તેઓ સરળ છે અને હાથમાં રહેલી સમસ્યાના વિશેષ માળખાનો લાભ લેવા માટે તેમને સરળતાથી અનુકૂલિત કરી શકાય છે. સબગ્રેડિએન્ટ-પ્રોજેક્શન અને બંડલ પદ્ધતિઓ 1970ના દાયકા દરમિયાન, ક્લાઉડ લેમરેચલ અને ફિલ વોલ્ફે બહિર્મુખ લઘુતમીકરણની સમસ્યાઓ માટે વંશની "બંડલ પદ્ધતિઓ" પ્રસ્તાવિત કરી હતી. ત્યારથી "બંડલ પદ્ધતિઓ" શબ્દનો અર્થ નોંધપાત્ર રીતે બદલાઈ ગયો છે. આધુનિક આવૃત્તિઓ અને સંપૂર્ણ અભિસરણ વિશ્લેષણ કિવીએલ દ્વારા પ્રદાન કરવામાં આવ્યા હતા. સમકાલીન બંડલ-પદ્ધતિઓ ઘણીવાર પગલાં-કદ પસંદ કરવા માટે "સ્તર નિયંત્રણ" નિયમોનો ઉપયોગ કરે છે, બોરિસ ટી. પોલિયાક (1969) ની "સબગ્રેડિએન્ટ-પ્રોજેક્શન" પદ્ધતિમાંથી તકનીકો વિકસાવે છે. જો કે, એવી સમસ્યાઓ છે કે જેના પર બંડલ પદ્ધતિઓ સબગ્રેડિએન્ટ-પ્રોજેક્શન પદ્ધતિઓ કરતાં થોડો ફાયદો આપે છે. કન્સ્ટ્રેઈન્ડ ઓપ્ટિમાઇઝેશન પ્રોજેક્ટેડ સબગ્રેડિએન્ટ સબગ્રેડિએન્ટ પદ્ધતિનું એક વિસ્તરણ એ પ્રોજેક્ટેડ સબગ્રેડિએન્ટ પદ્ધતિ છે, જે કન્સ્ટેઈન્ડ ઓપ્ટિમાઇઝેશન સમસ્યાનું નિરાકરણ કરે છે, જ્યાં બહિર્મુખ સમૂહ છે. અંદાજિત સબગ્રેડિયન્ટ પદ્ધતિ પુનરાવર્તનનો ઉપયોગ કરે છે જ્યાં પ્રક્ષેપણ ચાલુ હોય છે અને તે સામાન્ય અવરોધો પર કોઈપણ સબગ્રેડિયન્ટ હોય છે સબગ્રેડિયન્ટ પદ્ધતિને અસમાનતા મર્યાદિત સમસ્યાને ઉકેલવા માટે વિસ્તૃત કરી શકાય છે, જ્યાં બહિર્મુખ હોય તેને આધિન ઘટાડે છે. અલ્ગોરિધમ અનિયંત્રિત કેસ જેવું જ સ્વરૂપ લે છે જ્યાં એક પગલાનું કદ હોય છે, અને તે ઉદ્દેશ્યનો સબગ્રેડિએન્ટ છે અથવા ટેક ખાતેના કન્સ્ટ્રેઇનટ ફંક્શન્સમાંથી એક છે જ્યાં ના સબડિફરેન્શિયલને સૂચવે છે. જો વર્તમાન બિંદુ શક્ય હોય, તો અલ્ગોરિધમ એક ઉદ્દેશ્ય સબગ્રેડિએન્ટનો ઉપયોગ કરે છે; જો વર્તમાન બિંદુ અવ્યવહારુ હોય, તો અલ્ગોરિધમ કોઈપણ ઉલ્લંઘન કરેલ અવરોધનો સબગ્રેડિએન્ટ પસંદ કરે છે. સંદર્ભો વધુ વાંચન બાહ્ય કડીઓ EE364A અને EE364B, સ્ટેનફોર્ડનો બહિર્મુખ ઓપ્ટિમાઇઝેશન કોર્સ ક્રમ. ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ્સ અને પદ્ધતિઓ કન્વેક્સ ઓપ્ટિમાઇઝેશન