Augmented Lagrangian method
સંવર્ધિત લેગ્રેન્જિયન પદ્ધતિઓ મર્યાદિત ઓપ્ટિમાઇઝેશન સમસ્યાઓને ઉકેલવા માટે અલ્ગોરિધમ્સનો ચોક્કસ વર્ગ છે. તેઓ દંડની પદ્ધતિઓ સાથે સમાનતા ધરાવે છે જેમાં તેઓ અનિયંત્રિત સમસ્યાઓની શ્રેણી દ્વારા મર્યાદિત ઓપ્ટિમાઇઝેશન સમસ્યાને બદલે છે અને ઉદ્દેશ્યમાં દંડ શબ્દ ઉમેરે છે, પરંતુ સંવર્ધિત લેગ્રેન્જિયન પદ્ધતિ લેગ્રેન્જ ગુણકની નકલ કરવા માટે રચાયેલ અન્ય એક શબ્દ ઉમેરે છે. સંવર્ધિત લેગ્રેન્જિયન લેગ્રેન્જ મલ્ટિપ્લાયરની પદ્ધતિ સાથે સંબંધિત છે, પરંતુ તેની સાથે સમાન નથી. અલગ રીતે જોવામાં આવે તો, અનિયંત્રિત ઉદ્દેશ એ મર્યાદિત સમસ્યાનું લગ્રેન્જિયન છે, જેમાં વધારાની દંડની મુદત (વૃદ્ધિ) છે. આ પદ્ધતિ મૂળરૂપે ગુણક પદ્ધતિ તરીકે જાણીતી હતી અને 1970 અને 1980ના દાયકામાં દંડ પદ્ધતિઓના સંભવિત વિકલ્પ તરીકે તેનો અભ્યાસ કરવામાં આવ્યો હતો. તેની ચર્ચા સૌપ્રથમ મેગ્નસ હેસ્ટેન્સ અને પછી 1969માં માઇકલ પોવેલ દ્વારા કરવામાં આવી હતી. આ પદ્ધતિનો અભ્યાસ આર. ટાયરેલ રોકાફેલ્લર દ્વારા ફેન્શેલ દ્વૈતતાના સંબંધમાં કરવામાં આવ્યો હતો, ખાસ કરીને નિકટવર્તી-બિંદુ પદ્ધતિઓ, મોરેઉ-યોસિડા નિયમિતકરણ અને મહત્તમ મોનોટોન ઓપરેટરોના સંબંધમાં; આ પદ્ધતિઓનો ઉપયોગ માળખાકીય ઓપ્ટિમાઇઝેશનમાં કરવામાં આવ્યો હતો. આ પદ્ધતિનો અભ્યાસ દિમિત્રી બર્ટસેકાસ દ્વારા પણ કરવામાં આવ્યો હતો, ખાસ કરીને તેમના 1982 ના પુસ્તકમાં, બિન-ચતુષ્કોણીય નિયમિતકરણ કાર્યો (દા. ત., એન્ટ્રોપિક નિયમિતકરણ) ને સમાવતા વિસ્તરણ સાથે. આ સંયુક્ત અભ્યાસ "ગુણકોની ઘાતાંકીય પદ્ધતિ" ને જન્મ આપે છે જે બે વાર-વિભેદક સંવર્ધિત લાગ્રેન્જિયન કાર્ય સાથે અસમાનતાના અવરોધોને સંભાળે છે. 1970ના દાયકાથી, ક્રમિક ચતુર્ભુજ પ્રોગ્રામિંગ (SQP) અને આંતરિક બિંદુ પદ્ધતિઓ (IPM) પર વધુ ધ્યાન આપવામાં આવ્યું છે, કારણ કે તેઓ આંકડાકીય સોફ્ટવેર લાઈબ્રેરીઓમાંથી વિરલ મેટ્રિક્સ સબરૂટિનનો વધુ સરળતાથી ઉપયોગ કરે છે, અને અંશતઃ કારણ કે IPM સ્વ-સુસંગત કાર્યોના સિદ્ધાંત દ્વારા સાબિત જટિલતા પરિણામો ધરાવે છે. સંવર્ધિત લેગ્રેન્જિયન પદ્ધતિને LANCELOT, ALGENCAN અને AMPL ઓપ્ટિમાઇઝેશન સિસ્ટમો દ્વારા પુનર્જીવિત કરવામાં આવી હતી, જેણે દેખીતી રીતે ગાઢ પરંતુ "આંશિક રીતે અલગ કરી શકાય તેવી" સમસ્યાઓ પર વિરલ મેટ્રિક્સ તકનીકોનો ઉપયોગ કરવાની મંજૂરી આપી હતી. આ પદ્ધતિ હજુ પણ કેટલીક સમસ્યાઓ માટે ઉપયોગી છે. 2007 ની આસપાસ, કુલ વિવિધતા ડીનોઇઝિંગ અને કોમ્પ્રેસ્ડ સેન્સિંગ જેવા ક્ષેત્રોમાં સંવર્ધિત લેગ્રેન્જિયન પદ્ધતિઓનું પુનરુત્થાન થયું હતું. ખાસ કરીને, પ્રમાણભૂત સંવર્ધિત લગ્રેન્જિયન પદ્ધતિનો એક પ્રકાર કે જે આંશિક સુધારાઓનો ઉપયોગ કરે છે (રેખીય સમીકરણોને ઉકેલવા માટે ગૌસ-સીડેલ પદ્ધતિની જેમ) જે ગુણકો અથવા એ. ડી. એમ. એમ. ની વૈકલ્પિક દિશા પદ્ધતિ તરીકે ઓળખાય છે, તેણે થોડું ધ્યાન ખેંચ્યું. સામાન્ય પદ્ધતિ નીચેની મર્યાદિત ઓપ્ટિમાઇઝેશન સમસ્યાને ઉકેલવાનો વિચાર કરો જ્યાં સમાનતાના અવરોધો માટે સૂચકાંકો સૂચવે છે. આ સમસ્યાને અનિયંત્રિત લઘુતમ સમસ્યાઓની શ્રેણી તરીકે ઉકેલી શકાય છે. સંદર્ભ માટે, આપણે પહેલા પેનલ્ટી પદ્ધતિ અભિગમના kમા પગલાની યાદી બનાવીએ છીએઃ પેનલ્ટી પદ્ધતિ આ સમસ્યાનું સમાધાન કરે છે, પછી આગામી પુનરાવર્તનમાં તે મોટા મૂલ્યનો ઉપયોગ કરીને અને જૂના ઉકેલનો પ્રારંભિક અનુમાન અથવા "વોર્મ સ્ટાર્ટ" તરીકે ઉપયોગ કરીને સમસ્યાનું ફરીથી સમાધાન કરે છે. સંવર્ધિત લાગ્રેન્જિયન પદ્ધતિ નીચેના અનિયંત્રિત ઉદ્દેશનો ઉપયોગ કરે છેઃ અને દરેક પુનરાવર્તન પછી, અપડેટ કરવા ઉપરાંત, ચલ પણ નિયમ અનુસાર અપડેટ કરવામાં આવે છે જ્યાં kth પગલું (એટલે કે. ). ચલ એ લેગ્રેન્જ ગુણકનો અંદાજ છે, અને આ અંદાજની ચોકસાઈ દરેક તબક્કે સુધરે છે. પદ્ધતિનો મુખ્ય ફાયદો એ છે કે દંડની પદ્ધતિથી વિપરીત, મૂળ મર્યાદિત સમસ્યાને ઉકેલવા માટે લેવાની જરૂર નથી. લેગ્રેન્જ ગુણક શબ્દની હાજરીને કારણે, તે ઘણું નાનું રહી શકે છે, અને આમ ખરાબ સ્થિતિને ટાળી શકે છે. તેમ છતાં, મોટા બાઉન્ડેડ સેટ (સલામતી) માં પ્રોજેક્ટ મલ્ટિપ્લાયર અંદાજો માટે વ્યવહારુ અમલીકરણમાં સામાન્ય છે જે આંકડાકીય અસ્થિરતાને ટાળે છે અને મજબૂત સૈદ્ધાંતિક અભિસરણ તરફ દોરી જાય છે. અસમાનતાના અવરોધોને નિયંત્રિત કરવા માટે આ પદ્ધતિનો વિસ્તાર કરી શકાય છે. વ્યવહારુ સુધારાઓની ચર્ચા માટે, સંદર્ભો જુઓ. મલ્ટિપ્લાયરની વૈકલ્પિક દિશા પદ્ધતિ મલ્ટિપ્લાયરની વૈકલ્પિક દિશા પદ્ધતિ (એ. ડી. એમ. એમ.) એ સંવર્ધિત લગ્રેન્જિયન યોજનાનો એક પ્રકાર છે જે બેવડા ચલ માટે આંશિક સુધારાઓનો ઉપયોગ કરે છે. આ પદ્ધતિ ઘણીવાર સમસ્યાઓને ઉકેલવા માટે લાગુ કરવામાં આવે છે જેમ કે, આ મર્યાદિત સમસ્યાની સમકક્ષ છે, જો કે આ ફેરફાર તુચ્છ લાગે છે, હવે સમસ્યાને મર્યાદિત ઓપ્ટિમાઇઝેશન (ખાસ કરીને, સંવર્ધિત લેગ્રેન્જિયન પદ્ધતિ) ની પદ્ધતિઓનો ઉપયોગ કરીને હુમલો કરી શકાય છે, અને ઉદ્દેશ્ય કાર્ય x અને y માં અલગ કરી શકાય છે. બેવડા સુધારા માટે એક જ સમયે x અને y માં નિકટતા કાર્યને હલ કરવાની જરૂર છે; ADMM તકનીક આ સમસ્યાને અંદાજે x માટે y નિશ્ચિત સાથે હલ કરીને અને પછી x નિશ્ચિત સાથે y માટે હલ કરીને હલ કરવાની મંજૂરી આપે છે. અભિસરણ (જેકોબી પદ્ધતિની જેમ) સુધી પુનરાવર્તન કરવાને બદલે, અલ્ગોરિધમ સીધા દ્વિ ચલને અપડેટ કરવા અને પછી પ્રક્રિયાને પુનરાવર્તન કરવા માટે આગળ વધે છે. આ ચોક્કસ લઘુતમકરણની સમકક્ષ નથી, પરંતુ પદ્ધતિ હજુ પણ કેટલીક ધારણાઓ હેઠળ સાચા ઉકેલમાં પરિવર્તિત થાય છે. આ અંદાજને કારણે, અલ્ગોરિધમ શુદ્ધ સંવર્ધિત લેગ્રેન્જિયન પદ્ધતિથી અલગ છે. એ. ડી. એમ. એમ. ને ડગ્લાસ-રેચફોર્ડ વિભાજન અલ્ગોરિધમનો ઉપયોગ તરીકે જોઈ શકાય છે, અને ડગ્લાસ-રેચફોર્ડ અલ્ગોરિધમ પ્રોક્સિમલ પોઇન્ટ અલ્ગોરિધમનું ઉદાહરણ છે; વિગતો સંદર્ભમાં મળી શકે છે. YALL1 (2009), SPARSA (2009) અને SALSA (2009) સહિત ઘણા આધુનિક સોફ્ટવેર પેકેજો છે, જે બેઝિસ પર્સ્યુટ અને વેરિઅન્ટ્સને હલ કરે છે અને ADMM નો ઉપયોગ કરે છે. એવા પેકેજો પણ છે જે વધુ સામાન્ય સમસ્યાઓ ઉકેલવા માટે એ. ડી. એમ. એમ. નો ઉપયોગ કરે છે, જેમાંથી કેટલાક બહુવિધ કમ્પ્યુટિંગ કોર (દા. ત., એસ. એન. એ. પી. વી. એક્સ. (2015), પેરા. એ. ડી. એમ. એમ. (2016)) નો ઉપયોગ કરી શકે છે. સ્ટોકેસ્ટિક ઓપ્ટિમાઇઝેશન (ઢાળ) કાર્યના ઘોંઘાટીયા નમૂનાઓની પહોંચ સાથે નુકસાન કાર્યને ઘટાડવાની સમસ્યાને ધ્યાનમાં લે છે. ધ્યેય એ છે કે નવા નમૂના દીઠ શ્રેષ્ઠ પરિમાણ (મિનિમાઇઝર) નો અંદાજ હોવો જોઈએ. કેટલાક ફેરફારો સાથે, ADMM નો ઉપયોગ સ્ટોકેસ્ટિક ઓપ્ટિમાઇઝેશન માટે થઈ શકે છે. સ્ટોકેસ્ટિક સેટિંગમાં, ઢાળના માત્ર ઘોંઘાટીયા નમૂનાઓ જ સુલભ હોય છે, તેથી લેગ્રેન્જિયનનો અચોક્કસ અંદાજ વપરાય છેઃ જ્યાં સમય-બદલાતા પગલાનું કદ છે. એ. ડી. એમ. એમ. ને નિયમિત સમસ્યાઓ ઉકેલવા માટે લાગુ કરવામાં આવ્યું છે, જ્યાં કાર્ય ઓપ્ટિમાઇઝેશન અને નિયમિતકરણ સ્થાનિક રીતે કરી શકાય છે અને પછી અવરોધો દ્વારા વૈશ્વિક સ્તરે સંકલન કરી શકાય છે. નિયમિત ઓપ્ટિમાઇઝેશન સમસ્યાઓ ઉચ્ચ-પરિમાણીય શાસનમાં ખાસ કરીને સુસંગત છે કારણ કે નિયમિતકરણ એ ખરાબ સ્થિતિને દૂર કરવા અને શ્રેષ્ઠ ઉકેલ (દા. ત., અસ્પષ્ટતા અને નીચલા ક્રમ) માં અસ્પષ્ટતાને પ્રોત્સાહિત કરવા માટેની એક કુદરતી પદ્ધતિ છે. નિયમિત સમસ્યાઓ ઉકેલવા માટે એ. ડી. એમ. એમ. ની અસરકારકતાનો અર્થ એ હોઈ શકે કે તે છુપાવવા-પરિમાણીય સ્ટોકેસ્ટિક ઓપ્ટિમાઇઝેશન સમસ્યાઓ ઉકેલવા માટે ઉપયોગી થઈ શકે છે. વૈકલ્પિક અભિગમો અનુક્રમિક ચતુર્ભુજ પ્રોગ્રામિંગ અનુક્રમિક રેખીય પ્રોગ્રામિંગ સોફ્ટવેર ઓપન સોર્સ અને સંવર્ધિત લેગ્રેન્જિયન પદ્ધતિનો બિન-મુક્ત/વ્યાપારી અમલીકરણઃ Accord.NET (સંવર્ધિત લેગ્રેન્જિયન ઓપ્ટિમાઇઝરનું C #અમલીકરણ) ALGLIB (પૂર્વશર્ત સંવર્ધિત લેગ્રેન્જિયન સોલ્વરનું C #અને C + + અમલીકરણ) PENN (GPL 3, વ્યાપારી લાઇસન્સ ઉપલબ્ધ) LANCELOT (મફત "આંતરિક ઉપયોગ" લાઇસન્સ, ચૂકવણી કરેલ વ્યાપારી વિકલ્પો) MINOS (કેટલીક પ્રકારની સમસ્યાઓ માટે સંવર્ધિત લેગ્રેન્જિયન પદ્ધતિનો પણ ઉપયોગ કરે છે). અપાચે 2 લાઇસન્સ પ્રાપ્ત કારણ માટેનો કોડ ઓનલાઇન ઉપલબ્ધ છે. ALGENCAN (સલામતી સાથે સંવર્ધિત લેગ્રેન્જિયન પદ્ધતિનું ફોરટ્રાન અમલીકરણ). ઓનલાઈન ઉપલબ્ધ છે. એન. એલ. ઓ. પી. ટી. (વિવિધ પ્રોગ્રામિંગ ભાષાઓમાંથી સુલભ સંવર્ધિત લાગ્રેન્જિયન ઓપ્ટિમાઇઝરનું સી + + અમલીકરણ) પાયપ્રોક્સિમલ (સંવર્ધિત લાગ્રેન્જિયન પદ્ધતિનું પાયથોન અમલીકરણ). બેરિયર ફંક્શન આંતરિક-બિંદુ પદ્ધતિ લેગ્રેન્જ ગુણક દંડ પદ્ધતિ સંદર્ભો ગ્રંથસૂચિ ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ્સ અને પદ્ધતિઓ પણ જુઓ.