Ellipsoid method
ગાણિતિક ઓપ્ટિમાઇઝેશનમાં, લંબગોળ પદ્ધતિ બહિર્મુખ કાર્યોને ઘટાડવા માટેની પુનરાવર્તિત પદ્ધતિ છે. જ્યારે તર્કસંગત માહિતી સાથે શક્ય રેખીય ઓપ્ટિમાઇઝેશન સમસ્યાઓને ઉકેલવા માટે વિશિષ્ટ હોય, ત્યારે લંબગોળ પદ્ધતિ એ એક અલ્ગોરિધમ છે જે ઇનપુટ કદમાં બહુપદી હોય તેવા સંખ્યાબંધ પગલાંઓમાં શ્રેષ્ઠ ઉકેલ શોધે છે. લંબગોળ પદ્ધતિ લંબગોળનો ક્રમ પેદા કરે છે જેનું કદ દરેક તબક્કે સમાનરૂપે ઘટે છે, આમ બહિર્મુખ કાર્યનું લઘુતમ પરિબળ બંધ કરે છે. ઇતિહાસ લંબગોળ પદ્ધતિનો લાંબો ઇતિહાસ છે. પુનરાવર્તિત પદ્ધતિ તરીકે, નૌમ ઝેડ. શોર દ્વારા પ્રારંભિક સંસ્કરણ રજૂ કરવામાં આવ્યું હતું. 1972માં, વાસ્તવિક બહિર્મુખ લઘુતમકરણ માટેના અંદાજિત અલ્ગોરિધમનો અભ્યાસ અર્કાડી નેમિરોવસ્કી અને ડેવિડ બી. યુડિન (જુડિન) દ્વારા કરવામાં આવ્યો હતો. તર્કસંગત ડેટા સાથે રેખીય પ્રોગ્રામિંગ સમસ્યાઓને ઉકેલવા માટેના અલ્ગોરિધમ તરીકે, લિયોનીદ ખાચિયાન દ્વારા લંબગોળ અલ્ગોરિધમનો અભ્યાસ કરવામાં આવ્યો હતો; ખાચિયાનની સિદ્ધિ રેખીય પ્રોગ્રામ્સની બહુપદી-સમયની ઉકેલવાની ક્ષમતાને સાબિત કરવાની હતી. સૈદ્ધાંતિક દ્રષ્ટિકોણથી આ એક નોંધપાત્ર પગલું હતુંઃ તે સમયે રેખીય સમસ્યાઓ ઉકેલવા માટેનું પ્રમાણભૂત અલ્ગોરિધમ સિમ્પ્લેક્સ અલ્ગોરિધમ હતું, જેનો રન ટાઇમ હોય છે જે સામાન્ય રીતે સમસ્યાના કદમાં રેખીય હોય છે, પરંતુ કયા ઉદાહરણો અસ્તિત્વમાં છે જેના માટે તે સમસ્યાના કદમાં ઘાતાંકીય છે. જેમ કે, એક અલ્ગોરિધમ હોવું કે જે તમામ કેસો માટે બહુપદી હોવાની બાંયધરી આપે છે તે એક સૈદ્ધાંતિક સફળતા જેવું લાગતું હતું. ખાચિયાનના કાર્યએ પ્રથમ વખત દર્શાવ્યું હતું કે, રેખીય પ્રોગ્રામ્સને ઉકેલવા માટે એલ્ગોરિધમ્સ હોઈ શકે છે, જેનો રનટાઇમ બહુપદી સાબિત થઈ શકે છે. વ્યવહારમાં, જો કે, અલ્ગોરિધમ એકદમ ધીમું અને થોડું વ્યવહારુ રસ ધરાવતું છે, જો કે તે પછીના કાર્ય માટે પ્રેરણા પૂરી પાડે છે જે વધુ વ્યવહારુ ઉપયોગમાં હોવાનું બહાર આવ્યું છે. ખાસ કરીને, કરમરકરનું અલ્ગોરિધમ, આંતરિક-બિંદુ પદ્ધતિ, વ્યવહારમાં લંબગોળ પદ્ધતિ કરતાં ઘણી ઝડપી છે. સૌથી ખરાબ સ્થિતિમાં પણ કરમરકરનું અલ્ગોરિધમ ઝડપી છે. લંબગોળ અલ્ગોરિધમ જટિલતા સિદ્ધાંતવાદીઓને (સૌથી ખરાબ સ્થિતિ) સીમાઓ હાંસલ કરવાની મંજૂરી આપે છે જે સમસ્યાના પરિમાણ અને ડેટાના કદ પર આધાર રાખે છે, પરંતુ પંક્તિઓની સંખ્યા પર નહીં, તેથી તે ઘણા વર્ષો સુધી સંયુક્ત ઓપ્ટિમાઇઝેશન સિદ્ધાંતમાં મહત્વપૂર્ણ રહ્યું. માત્ર 21મી સદીમાં જ સમાન જટિલતા ગુણધર્મો સાથે આંતરિક-બિંદુ અલ્ગોરિધમ્સ દેખાયા છે. વર્ણન બહિર્મુખ લઘુતમ સમસ્યામાં નીચેના ઘટકોનો સમાવેશ થાય છે. વેક્ટર પર લઘુતમ કરવા માટેનું બહિર્મુખ કાર્ય (જેમાં n ચલ હોય છે); સ્વરૂપની બહિર્મુખ અસમાનતાની મર્યાદાઓ, જ્યાં કાર્યો બહિર્મુખ હોય છે; આ અવરોધો બહિર્મુખ સમૂહને વ્યાખ્યાયિત કરે છે. સ્વરૂપની રેખીય સમાનતાની મર્યાદાઓ. આપણને પ્રારંભિક લંબગોળ પણ આપવામાં આવે છે જેને લઘુતમ સમાવતી તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, જ્યાં અને તેનું કેન્દ્ર છે. છેવટે, આપણે બહિર્મુખ સમૂહ માટે અલગ ઓરેકલના અસ્તિત્વની જરૂર છે. એક બિંદુને જોતાં, ઓરેકલે બેમાંથી એક જવાબ આપવો જોઈએઃ "બિંદુ અંદર છે", અથવા-"બિંદુ અંદર નથી, અને વધુમાં, અહીં એક હાયપરપ્લેન છે જે તેનાથી અલગ થાય છે", એટલે કે, બધા માટે વેક્ટર. લંબગોળ પદ્ધતિનું આઉટપુટ ક્યાં તો છેઃ પોલીટોપમાં કોઈપણ બિંદુ (એટલે કે, કોઈપણ શક્ય બિંદુ), અથવા-એક પુરાવો જે ખાલી છે. દરેક જગ્યાએ શૂન્ય હોય તેવા કાર્યનું અસમાનતા-મર્યાદિત લઘુતમકરણ કોઈપણ શક્ય બિંદુને ઓળખવાની સમસ્યાને અનુરૂપ છે. તે તારણ આપે છે કે કોઈપણ રેખીય પ્રોગ્રામિંગ સમસ્યાને રેખીય શક્યતા સમસ્યામાં ઘટાડી શકાય છે (દા. ત. કેટલીક રેખીય અસમાનતા અને સમાનતાના અવરોધોને આધિન શૂન્ય કાર્યને ઘટાડવું). આવું કરવાની એક રીત એ છે કે પ્રાઈમલ અને ડ્યુઅલ રેખીય પ્રોગ્રામ્સને એક પ્રોગ્રામમાં એકસાથે જોડીને, અને વધારાના (રેખીય) અવરોધને ઉમેરીને કે પ્રાઈમલ સોલ્યુશનનું મૂલ્ય ડ્યુઅલ સોલ્યુશનના મૂલ્ય કરતાં વધુ ખરાબ નથી. બીજી રીત એ છે કે રેખીય કાર્યક્રમના ઉદ્દેશને વધારાની અવરોધ તરીકે ગણવો, અને મહત્તમ મૂલ્ય શોધવા માટે દ્વિસંગી શોધનો ઉપયોગ કરવો. અનિયંત્રિત લઘુતમકરણ અલ્ગોરિધમનો k-th પુનરાવર્તન સમયે, આપણી પાસે લંબગોળના કેન્દ્રમાં એક બિંદુ હોય છે આપણે વેક્ટર મેળવવા માટે કટીંગ-પ્લેન ઓરેકલની પૂછપરછ કરીએ છીએ જેથી આપણે નિષ્કર્ષ કાઢીએ કે આપણે ઉપર વર્ણવેલ અર્ધ-લંબગોળ ધરાવતા ન્યૂનતમ કદના લંબગોળ તરીકે સેટ કરીએ છીએ અને ગણતરી કરીએ છીએ. અપડેટ તેના દ્વારા આપવામાં આવે છે જ્યાં અટકાવવાનો માપદંડ એ ગુણધર્મ દ્વારા આપવામાં આવે છે કે અસમાનતા-મર્યાદિત લઘુતમકરણ મર્યાદિત લઘુતમકરણ માટેના અલ્ગોરિધમનો k-th પુનરાવર્તન સમયે, આપણી પાસે પહેલાની જેમ લંબગોળની મધ્યમાં એક બિંદુ છે. આપણે અત્યાર સુધીના શક્ય પુનરાવર્તનોના સૌથી નાના ઉદ્દેશ્ય મૂલ્યને રેકોર્ડ કરતા મૂલ્યોની સૂચિ પણ જાળવવી જોઈએ. બિંદુ શક્ય છે કે નહીં તેના આધારે, અમે બેમાંથી એક કાર્ય કરીએ છીએઃ જો શક્ય હોય, તો અનિવાર્યપણે અનિયંત્રિત કેસની જેમ જ તે જ સુધારા કરો, જે સંતોષ આપે છે તે સબગ્રેડિયન્ટ પસંદ કરીને જો તે અશક્ય છે અને જે-th અવરોધનું ઉલ્લંઘન કરે છે, તો શક્યતા કટ સાથે લંબગોળને અપડેટ કરો. આપણો શક્યતા કાપ એક પેટા-અધોગતિ હોઈ શકે છે જેને તમામ શક્ય z માટે સંતોષવું આવશ્યક છે. પ્રદર્શન લંબગોળ પદ્ધતિનો ઉપયોગ નિમ્ન-પરિમાણીય સમસ્યાઓ પર થાય છે, જેમ કે સમતલીય સ્થાનની સમસ્યાઓ, જ્યાં તે આંકડાકીય રીતે સ્થિર હોય છે. "નાના" કદની સમસ્યાઓ પર પણ, તે સંખ્યાત્મક અસ્થિરતા અને વ્યવહારમાં નબળા પ્રદર્શનથી પીડાય છે. જો કે, લંબગોળ પદ્ધતિ એ સંયુક્ત ઓપ્ટિમાઇઝેશનમાં એક મહત્વપૂર્ણ સૈદ્ધાંતિક તકનીક છે. કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, લંબગોળ અલ્ગોરિધમ આકર્ષક છે કારણ કે તેની જટિલતા સ્તંભોની સંખ્યા અને ગુણાંકના ડિજિટલ કદ પર આધારિત છે, પરંતુ પંક્તિઓની સંખ્યા પર નહીં. 21મી સદીમાં, સમાન ગુણધર્મો સાથે આંતરિક-બિંદુ અલ્ગોરિધમ્સ દેખાયા છે. વધુ વાંચન નોંધો દિમિત્રીસ અલેવરાસ અને મેનફ્રેડ ડબલ્યુ. પેડબર્ગ, લીનિયર ઓપ્ટિમાઇઝેશન એન્ડ એક્સ્ટેન્શન્સઃ પ્રોબ્લેમ્સ એન્ડ એક્સ્ટેન્શન્સ, યુનિવર્સિટેક્સ્ટ, સ્પ્રિંગર-વેરલેગ, 2001. (ઉકેલો સાથે પેડબર્ગની સમસ્યાઓ.) વી. ચંદ્રુ અને M.R.Rao, લીનિયર પ્રોગ્રામિંગ, અલ્ગોરિધમ્સ અને થિયરી ઓફ કમ્પ્યુટેશન હેન્ડબુકમાં પ્રકરણ 31, M.J.Atallah દ્વારા સંપાદિત, CRC પ્રેસ 1999,31-1 થી 31-37. વી. ચંદ્રુ અને M.R.Rao, પૂર્ણાંક પ્રોગ્રામિંગ, અલ્ગોરિધમ્સ અને થિયરી ઓફ કમ્પ્યુટેશન હેન્ડબુકમાં પ્રકરણ 32, M.J.Atallah દ્વારા સંપાદિત, CRC પ્રેસ 1999,32-1 થી 32-45. જ્યોર્જ બી. ડેન્ટઝિગ અને મુકુંદ એન. થાપા. 1997. રેખીય પ્રોગ્રામિંગ 1: પરિચય. સ્પ્રિંગર-વેરલેગ. જ્યોર્જ બી. ડેન્ટઝિગ અને મુકુંદ એન. થાપા. 2003 માં. લીનિયર પ્રોગ્રામિંગ 2: થિયરી અને એક્સ્ટેન્શન્સ. સ્પ્રિંગર-વેરલેગ. એલ. લોવેઝઃ એન એલ્ગોરિધમિક થિયરી ઓફ નંબર્સ, ગ્રાફ્સ એન્ડ કન્વેક્સિટી, સીબીએમએસ-એનએસએફ રિજનલ કોન્ફરન્સ સિરીઝ ઇન એપ્લાઇડ મેથેમેટિક્સ 50, એસઆઈએએમ, ફિલાડેલ્ફિયા, પેન્સિલવેનિયા, 1986 કટ્ટા જી. મૂર્તિ, લીનિયર પ્રોગ્રામિંગ, વિલી, 1983. એમ. પેડબર્ગ, લીનિયર ઓપ્ટિમાઇઝેશન એન્ડ એક્સ્ટેન્શન્સ, સેકન્ડ એડિશન, સ્પ્રિંગર-વેરલેગ, 1999. ક્રિસ્ટોસ એચ. પાપાડિમિટ્રિયુ અને કેનેથ સ્ટીગ્લિટ્ઝ, કોમ્બિનેટોરિયલ ઓપ્ટિમાઇઝેશનઃ એલ્ગોરિધમ્સ એન્ડ કોમ્પ્લેક્સિટી, નવી પ્રસ્તાવના સાથે સુધારેલ રીપબ્લિકેશન, ડોવર. એલેક્ઝાન્ડર શ્રીજવર, થિયરી ઓફ લિનિયર એન્ડ ઇન્ટિજર પ્રોગ્રામિંગ. જ્હોન વિલી એન્ડ સન્સ, 1998, એક્સ્ટર્નલ લિંક્સ EE364b, સ્ટેનફોર્ડ કોર્સ હોમપેજ કોમ્બિનેટોરિયલ ઓપ્ટિમાઇઝેશન કન્વેક્સ ઓપ્ટિમાઇઝેશન લીનિયર પ્રોગ્રામિંગ