Frank–Wolfe algorithm
ફ્રેન્ક-વોલ્ફ અલ્ગોરિધમ એ મર્યાદિત બહિર્મુખ ઓપ્ટિમાઇઝેશન માટે પુનરાવર્તિત પ્રથમ ક્રમ ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ છે. શરતી ઢાળ પદ્ધતિ, ઘટાડેલા ઢાળ અલ્ગોરિધમ અને બહિર્મુખ સંયોજન અલ્ગોરિધમ તરીકે પણ ઓળખાતી આ પદ્ધતિ મૂળરૂપે માર્ગુરેટ ફ્રેન્ક અને ફિલિપ વોલ્ફ દ્વારા 1956માં પ્રસ્તાવિત કરવામાં આવી હતી. દરેક પુનરાવર્તનમાં, ફ્રેન્ક-વોલ્ફ અલ્ગોરિધમ ઉદ્દેશ્ય કાર્યના રેખીય અંદાજને ધ્યાનમાં લે છે, અને આ રેખીય કાર્ય (સમાન ડોમેન પર લેવામાં આવે છે) ના લઘુતમ તરફ આગળ વધે છે. સમસ્યાનું નિવેદન ધારો કે વેક્ટર સ્પેસમાં કોમ્પેક્ટ કન્વેક્સ સેટ છે અને તે કન્વેક્સ, ડિફરન્સિએબલ રિયલ-વેલ્યુડ ફંક્શન છે. ફ્રેન્ક-વોલ્ફ અલ્ગોરિધમ ઓપ્ટિમાઇઝેશન સમસ્યાનું નિરાકરણ કરે છે. એલ્ગોરિધમ ઇનિશિયલાઈઝેશનઃ ચાલો, અને કોઈપણ બિંદુને અંદર આવવા દો. પગલું 1. દિશા-શોધવાની પેટા સમસ્યાઃ સમસ્યાનું નિરાકરણ શોધો વિષયને આધિન લઘુતમ કરો (અર્થઘટનઃ પ્રથમ ક્રમના ટેલર અંદાજ દ્વારા આપવામાં આવેલી સમસ્યાના રેખીય અંદાજને ઓછો કરો જે અંદર રહેવા માટે મર્યાદિત છે.) પગલું 2. પગલું કદ નિર્ધારણઃ સેટ કરો, અથવા વૈકલ્પિક રીતે શોધો કે જે ન્યૂનતમ કરે છે. પગલું 3. અપડેટઃ ચાલો, ચાલો અને પગલું 1 પર જાઓ. ગુણધર્મો જ્યારે મર્યાદિત ઓપ્ટિમાઇઝેશન માટે ગ્રેડિયન્ટ ડિસેન્ટ જેવી સ્પર્ધાત્મક પદ્ધતિઓને દરેક પુનરાવર્તનમાં શક્ય સેટ પર પ્રક્ષેપણ પગલું પાછું લેવાની જરૂર હોય છે, ત્યારે ફ્રેન્ક-વોલ્ફ અલ્ગોરિધમને ફક્ત દરેક પુનરાવર્તનમાં સમાન સેટ પર રેખીય સમસ્યાના ઉકેલની જરૂર હોય છે, અને તે આપમેળે શક્ય સેટમાં રહે છે. ફ્રેન્ક-વોલ્ફ અલ્ગોરિધમનો અભિસરણ સામાન્ય રીતે સબલીનિયર છેઃ ઓબ્જેક્ટિવ ફંક્શનમાં મહત્તમમાં ભૂલ k પુનરાવર્તનો પછી થાય છે, જ્યાં સુધી ગ્રેડિયન્ટ અમુક ધોરણોના સંદર્ભમાં સતત લિપશિટ્ઝ હોય. સમાન અભિસરણ દર પણ દર્શાવી શકાય છે જો પેટા-સમસ્યાઓ માત્ર આશરે હલ કરવામાં આવે. અલ્ગોરિધમનોના પુનરાવર્તનને હંમેશા શક્ય સમૂહના આત્યંતિક બિંદુઓના વિરલ બહિર્મુખ સંયોજન તરીકે રજૂ કરી શકાય છે, જેણે મશીન લર્નિંગ અને સિગ્નલ પ્રોસેસિંગ સમસ્યાઓમાં વિરલ લોભી ઓપ્ટિમાઇઝેશન માટે અલ્ગોરિધમનોની લોકપ્રિયતામાં મદદ કરી છે, તેમજ ઉદાહરણ તરીકે પરિવહન નેટવર્કમાં લઘુત્તમ-ખર્ચ પ્રવાહનું ઓપ્ટિમાઇઝેશન. જો શક્ય સમૂહ રેખીય અવરોધોના સમૂહ દ્વારા આપવામાં આવે છે, તો પછી દરેક પુનરાવર્તનમાં હલ કરવાની પેટા સમસ્યા એક રેખીય પ્રોગ્રામ બની જાય છે. જ્યારે સાથે સૌથી ખરાબ-કેસ કન્વર્જન્સ દર સામાન્ય રીતે સુધારી શકાતો નથી, ત્યારે ખાસ સમસ્યા વર્ગો માટે ઝડપી કન્વર્જન્સ મેળવી શકાય છે, જેમ કે કેટલીક મજબૂત બહિર્મુખ સમસ્યાઓ. ઉકેલ મૂલ્ય પર નીચલી સીમાઓ, અને પ્રાથમિક-દ્વૈત વિશ્લેષણ કારણ કે બહિર્મુખ છે, આપણી પાસેના કોઈપણ બે બિંદુઓ માટેઃ આ (અજ્ઞાત) શ્રેષ્ઠ ઉકેલ માટે પણ લાગુ પડે છે. એટલે કે,. પછીની ઓપ્ટિમાઇઝેશન સમસ્યા ફ્રેન્ક-વોલ્ફ અલ્ગોરિધમનો દરેક પુનરાવર્તનમાં હલ કરવામાં આવે છે, તેથી-th પુનરાવર્તનની દિશા-શોધવાની પેટા સમસ્યાના ઉકેલનો ઉપયોગ સેટિંગ દ્વારા દરેક પુનરાવર્તન દરમિયાન નીચી સીમાઓ વધારવા માટે કરી શકાય છે અને અજ્ઞાત શ્રેષ્ઠ મૂલ્ય પરની આવી નીચી સીમાઓ વ્યવહારમાં મહત્વપૂર્ણ છે કારણ કે તેનો ઉપયોગ અટકાવવાના માપદંડ તરીકે થઈ શકે છે, અને હંમેશાથી દરેક પુનરાવર્તનમાં અંદાજિત ગુણવત્તાનું કાર્યક્ષમ પ્રમાણપત્ર આપે છે. એવું દર્શાવવામાં આવ્યું છે કે આ અનુરૂપ દ્વૈત અંતર, એટલે કે અને નીચલા બાઉન્ડ વચ્ચેનો તફાવત, સમાન અભિસરણ દર સાથે ઘટે છે, એટલે કે. નોંધો ગ્રંથસૂચિ (ઝાંખી પેપર) ફ્રેન્ક-વોલ્ફ અલ્ગોરિધમ વર્ણન. બાહ્ય કડીઓ https://conditional-gradients.org: ફ્રેન્ક-વોલ્ફ અલ્ગોરિધમ્સનું સર્વેક્ષણ. માર્ગુરેટ ફ્રેન્ક અલ્ગોરિધમનો ઇતિહાસ વ્યક્તિગત રીતે વર્ણવે છે પ્રોક્સિમલ ગ્રેડિયન્ટ પદ્ધતિઓ પણ જુઓ ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ્સ અને પદ્ધતિઓ પુનરાવર્તિત પદ્ધતિઓ પ્રથમ ક્રમ પદ્ધતિઓ ગ્રેડિયન્ટ પદ્ધતિઓ