Sum-of-squares optimization
સમ-ઓફ-સ્ક્વેર ઓપ્ટિમાઇઝેશન પ્રોગ્રામ એ રેખીય ખર્ચ કાર્ય અને નિર્ણય ચલો પર ચોક્કસ પ્રકારના અવરોધ સાથે ઓપ્ટિમાઇઝેશન સમસ્યા છે. આ અવરોધો એવા સ્વરૂપના છે કે જ્યારે નિર્ણય ચલોનો ઉપયોગ ચોક્કસ બહુપદીઓમાં ગુણાંક તરીકે થાય છે, ત્યારે તે બહુપદીઓમાં બહુપદી SOS ગુણધર્મ હોવો જોઈએ. સામેલ બહુપદીઓની મહત્તમ ડિગ્રી નક્કી કરતી વખતે, સમ-ઓફ-સ્ક્વેર ઓપ્ટિમાઇઝેશનને સેમિડિફાઇનાઇટ પ્રોગ્રામિંગમાં છૂટછાટના લેસર પદાનુક્રમ તરીકે પણ ઓળખવામાં આવે છે. સમ-ઓફ-સ્ક્વેર ઓપ્ટિમાઇઝેશન તકનીકો વિવિધ ક્ષેત્રોમાં લાગુ કરવામાં આવી છે, જેમાં નિયંત્રણ સિદ્ધાંત (ખાસ કરીને, બહુપદી વેક્ટર ક્ષેત્રો દ્વારા વર્ણવેલ ગતિશીલ સિસ્ટમો માટે બહુપદી લિયાપુનોવ વિધેયો શોધવા માટે), આંકડાશાસ્ત્ર, નાણા અને મશીન લર્નિંગનો સમાવેશ થાય છે. "સ્ક્વેર પ્રોગ્રામિંગના સરવાળાનો ઉપયોગ કરીને નિયંત્રણ લિયાપુનોવ કાર્યો માટે શોધ". માંઃ એલર્ટન કોન્ફ. કોમ., કંટ્રોલ એન્ડ કમ્પ્યુટિંગ પર. પીપી. 210-219. </રેફ> A. ચક્રવર્તી, પી. સીલર અને જી. બાલાસ, "ફોલિંગ-લીફ મોડમાં એફ/એ-18 ફ્લાઇટ કંટ્રોલર્સની સંવેદનશીલતા-બિનરેખીય વિશ્લેષણ", એ. આઈ. એ. એ. જર્નલ ઓફ ગાઇડન્સ, કંટ્રોલ એન્ડ ડાયનેમિક્સ, વોલ્યુમ. 34 નં. 1 (2011), પૃ. 73-85. ઓપ્ટિમાઇઝેશન સમસ્યા, માટે વેક્ટર અને બહુપદીઓ આપવામાં આવે તો, સમ-ઓફ-સ્ક્વેર ઓપ્ટિમાઇઝેશન સમસ્યાને આ રીતે લખવામાં આવે છે અહીં "SOS" સમ-ઓફ-સ્ક્વેર (SOS) બહુપદીઓના વર્ગને રજૂ કરે છે. જથ્થા એ નિર્ણય ચલ છે. એસ. ઓ. એસ. પ્રોગ્રામ્સને એસ. ઓ. એસ. બહુપદી પ્રોગ્રામની દ્વૈતતાનો ઉપયોગ કરીને અર્ધ-અનંત પ્રોગ્રામ્સ (એસ. ડી. પી.) માં રૂપાંતરિત કરી શકાય છે અને હકારાત્મક-અર્ધ-અનંત મેટ્રિસીસનો ઉપયોગ કરીને મર્યાદિત બહુપદી ઓપ્ટિમાઇઝેશન માટે છૂટછાટ, નીચેનો વિભાગ જુઓ. બેવડી સમસ્યાઃ મર્યાદિત બહુપદી ઓપ્ટિમાઇઝેશન ધારો કે આપણી પાસે-ચલ બહુપદી છે, અને ધારો કે આપણે આ બહુપદીને સબસેટ પર ઘટાડવા માંગીએ છીએ. વધુમાં ધારો કે સબસેટ પરના અવરોધોને મહત્તમ ડિગ્રીની બહુપદી સમાનતાનો ઉપયોગ કરીને એન્કોડ કરી શકાય છે, દરેક સ્વરૂપ જ્યાં મહત્તમ ડિગ્રીની બહુપદી હોય છે. આ ઓપ્ટિમાઇઝેશન સમસ્યા માટે એક કુદરતી, જોકે સામાન્ય રીતે નોન-કન્વેક્સ પ્રોગ્રામ નીચે મુજબ છેઃ મહત્તમ ડિગ્રીમાં દરેક મોનોમીયલ માટે એક એન્ટ્રી સાથે-ડાયમેન્શનલ વેક્ટર ક્યાં છે, જેથી દરેક મલ્ટીસેટ માટે, આપણે જે બહુપદીને ઘટાડવા માંગીએ છીએ તેના ગુણાંકનો મેટ્રિક્સ છે, અને તે બહુપદીના ગુણાંકનો મેટ્રિક્સ છે જે સબસેટ પર-th અવરોધને એન્કોડિંગ કરે છે. આપણી શોધ જગ્યામાં વધારાનો, નિશ્ચિત અચળાંક અનુક્રમણિકા, બહુપદીઓ લખવાની સુવિધા માટે અને મેટ્રિક્સ રજૂઆતમાં ઉમેરવામાં આવે છે. આ પ્રોગ્રામ સામાન્ય રીતે બિન-બહિર્મુખ હોય છે, કારણ કે અવરોધો () બહિર્મુખ નથી. આ લઘુતમ સમસ્યા માટે એક સંભવિત બહિર્મુખ છૂટછાટ, ચલોના ક્રમ-એક મેટ્રિક્સને હકારાત્મક-અર્ધ-પરિમિત મેટ્રિક્સ સાથે બદલવા માટે અર્ધ-પરિમિત પ્રોગ્રામિંગનો ઉપયોગ કરે છેઃ આપણે કદના દરેક એકસૂત્રને મોટાભાગના સૂચકાંકોના બહુવિધ સમૂહ દ્વારા અનુક્રમિત કરીએ છીએ. આવી દરેક મોનોમીયલ માટે, આપણે પ્રોગ્રામમાં ચલ બનાવીએ છીએ, અને આપણે ચલને મેટ્રિક્સ બનાવવા માટે ગોઠવીએ છીએ, જ્યાં વાસ્તવિક મેટ્રિક્સનો સમૂહ છે જેની પંક્તિઓ અને સ્તંભો મહત્તમ કદના તત્વોના બહુવિધ સમૂહો સાથે ઓળખાય છે. પછી આપણે ચલોમાં નીચેનો સેમિડિફાઇનાઇટ પ્રોગ્રામ લખીએ છીએઃ આ વિષયમાંઃ જ્યાં ફરીથી બહુપદીના ગુણાંકનો મેટ્રિક્સ છે જેને આપણે ઘટાડવા માંગીએ છીએ, અને તે બહુપદીના ગુણાંકનો મેટ્રિક્સ છે જે સબસેટ પર-th અવરોધને એન્કોડિંગ કરે છે. ત્રીજો અવરોધ એ સુનિશ્ચિત કરે છે કે મેટ્રિક્સની અંદર ઘણી વખત દેખાતી એકવિધતાનું મૂલ્ય સમગ્ર મેટ્રિક્સમાં સમાન હોય છે, અને તે દ્વિઘાત સ્વરૂપમાં હાજર સમપ્રમાણતાને માન આપવા માટે ઉમેરવામાં આવે છે. દ્વૈત એક ઉપરોક્ત અર્ધ-અનંત પ્રોગ્રામનું દ્વૈત લઈ શકે છે અને નીચેનો પ્રોગ્રામ મેળવી શકે છેઃ આપણી પાસે અવરોધને અનુરૂપ ચલ છે (જ્યાં અનુક્રમિત એન્ટ્રી માટે શૂન્ય બચેલી તમામ એન્ટ્રીઓ સાથેનું મેટ્રિક્સ છે), દરેક બહુપદી અવરોધ માટે વાસ્તવિક ચલ છે અને મલ્ટિસેટ્સના દરેક જૂથ માટે, આપણી પાસે સમપ્રમાણતા અવરોધ માટે દ્વિ ચલ છે. પોઝિટિવ-સેમાઇડફાઇનિટનેસ અવરોધ એ સુનિશ્ચિત કરે છે કે તે બહુપદીઓના વર્ગોનો સરવાળો છેઃ પોઝિટિવ-સેમાઇડફાઇનાઇટ મેટ્રિક્સના લાક્ષણિકતા દ્વારા, કોઈપણ પોઝિટિવ-સેમાઇડફાઇનાઇટ મેટ્રિક્સ માટે, આપણે વેક્ટર માટે લખી શકીએ છીએ. આમ કોઈપણ માટે, જ્યાં આપણે મહત્તમ ડિગ્રીના બહુપદીના ગુણાંક સાથે વેક્ટરને ઓળખી કાઢ્યા છે. આ વર્ગનો સરવાળો પુરાવો આપે છે કે મૂલ્ય વધી ગયું છે. ઉપરોક્તને બહુપદી અસમાનતાઓ દ્વારા વ્યાખ્યાયિત પ્રદેશોમાં પણ વિસ્તૃત કરી શકાય છે. સમ-ઓફ-સ્ક્વેર પદાનુક્રમ સમ-ઓફ-સ્ક્વેર પદાનુક્રમ (એસ. ઓ. એસ. પદાનુક્રમ), જેને લેસર વંશવેલો તરીકે પણ ઓળખવામાં આવે છે, તે વધતી શક્તિ અને વધતા કોમ્પ્યુટેશનલ ખર્ચની બહિર્મુખ છૂટછાટનો પદાનુક્રમ છે. દરેક પ્રાકૃતિક સંખ્યા માટે અનુરૂપ બહિર્મુખ છૂટછાટને એસ. ઓ. એસ. પદાનુક્રમના th સ્તર અથવા-th રાઉન્ડ તરીકે ઓળખવામાં આવે છે. પ્રથમ રાઉન્ડ, જ્યારે, મૂળભૂત સેમિડિફાઇનાઇટ પ્રોગ્રામને અનુરૂપ હોય છે, અથવા મહત્તમ ડિગ્રીના બહુપદીઓ પર સરવાળા-ના-ચોરસ ઓપ્ટિમાઇઝેશનને અનુરૂપ હોય છે. પદાનુક્રમના પ્રથમ સ્તર પર મૂળભૂત બહિર્મુખ કાર્યક્રમને-th સ્તર સુધી વધારવા માટે, કાર્યક્રમમાં વધારાના ચલ અને અવરોધો ઉમેરવામાં આવે છે જેથી કાર્યક્રમ મહત્તમ ડિગ્રીની બહુપદીઓને ધ્યાનમાં લઈ શકે. એસ. ઓ. એસ. પદાનુક્રમ તેનું નામ એ હકીકત પરથી ઉતરી આવ્યું છે કે-th સ્તર પર ઉદ્દેશ્ય કાર્યનું મૂલ્ય દ્વિ દ્વારા મહત્તમ ડિગ્રીના બહુપદીઓનો ઉપયોગ કરીને સરવાળા-વર્ગ પુરાવા સાથે બંધાયેલ છે (ઉપર "દ્વૈતતા" જુઓ). પરિણામે, કોઈપણ સમ-ઓફ-સ્ક્વેર પ્રૂફ કે જે મહત્તમ ડિગ્રીના બહુપદીઓનો ઉપયોગ કરે છે તેનો ઉપયોગ ઉદ્દેશ્ય મૂલ્યને બાંધવા માટે થઈ શકે છે, જેનાથી છૂટછાટની ચુસ્તતા પર બાંયધરી આપી શકાય છે. બર્ગના પ્રમેય સાથે જોડાણમાં, આ આગળ સૂચવે છે કે પૂરતા પ્રમાણમાં ઘણા રાઉન્ડ આપવામાં આવે તો, કોઈપણ નિશ્ચિત અંતરાલ પર છૂટછાટ મનસ્વી રીતે ચુસ્ત બને છે. બર્ગનું પરિણામ જણાવે છે કે બંધાયેલ અંતરાલની અંદર દરેક બિન-નકારાત્મક વાસ્તવિક બહુપદીને પૂરતા પ્રમાણમાં ઉચ્ચ ડિગ્રીની વાસ્તવિક બહુપદીઓના વર્ગના સરવાળા સાથે તે અંતરાલ પર ચોકસાઈની અંદર અંદાજિત કરી શકાય છે, અને આમ જો બહુપદી ઉદ્દેશ્ય મૂલ્ય બિંદુના કાર્ય તરીકે હોય, જો અસમાનતા રસના ક્ષેત્રમાં બધા માટે હોય, તો આ હકીકતનો સરવાળો-વર્ગ પુરાવો હોવો આવશ્યક છે. શક્ય ક્ષેત્ર પર વસ્તુનિષ્ઠ કાર્યનું લઘુતમ બનવાનું પસંદ કરીને, આપણી પાસે પરિણામ છે. કોમ્પ્યુટેશનલ ખર્ચ ચલમાં કાર્યને શ્રેષ્ઠ બનાવતી વખતે, પદાનુક્રમના-th સ્તરને ચલ પર અર્ધ-અનંત પ્રોગ્રામ તરીકે લખી શકાય છે, અને લંબગોળ પદ્ધતિનો ઉપયોગ કરીને સમયસર ઉકેલી શકાય છે. સમ-ઓફ-સ્ક્વેર બેકગ્રાઉન્ડ બહુપદી એ વર્ગોનો સરવાળો (એસ. ઓ. એસ.) છે જો ત્યાં આવી બહુપદીઓ અસ્તિત્વમાં હોય. ઉદાહરણ તરીકે, તે વર્ગોનો સરવાળો છે જ્યાંથી નોંધ લો કે જો તે વર્ગોનો સરવાળો છે તો બધા માટે. બહુપદી એસ. ઓ. એસ. નું વિગતવાર વર્ણન available.Parrilo, પી. (2003) "અર્ધ બીજગણિત સમસ્યાઓ માટે અર્ધ-અનંત પ્રોગ્રામિંગ છૂટછાટ" છે. ગાણિતિક પ્રોગ્રામિંગ Ser. બી 96 (2), 293-320. ચતુર્ભુજ સ્વરૂપોને સમપ્રમાણ મેટ્રિક્સ તરીકે વ્યક્ત કરી શકાય છે. તેવી જ રીતે, ડિગ્રી ≤ 2d "ની બહુપદીઓને એ રીતે વ્યક્ત કરી શકાય છે કે જ્યાં વેક્ટર ડિગ્રીની તમામ એકવિધતા ધરાવે છે. આને ગ્રામ મેટ્રિક્સ સ્વરૂપ તરીકે ઓળખવામાં આવે છે. એક મહત્વપૂર્ણ હકીકત એ છે કે જો અને માત્ર ત્યારે જ એસ. ઓ. એસ. છે જો ત્યાં આવા સપ્રમાણ અને સકારાત્મક-અર્ધ-પરિમિત મેટ્રિક્સ અસ્તિત્વમાં હોય. આ એસ. ઓ. એસ. બહુપદીઓ અને હકારાત્મક-અર્ધ-અનંત મેટ્રિસીસ વચ્ચે જોડાણ પ્રદાન કરે છે. સોફ્ટવેર ટૂલ્સ, જી. એન. યુ. જી. પી. એલ. હેઠળ લાઇસન્સ પ્રાપ્ત. સંદર્ભ માર્ગદર્શિકા arXiv: 1310.4716 [math.OC] પર ઉપલબ્ધ છે, અને તેના આંતરિક વિશેની પ્રસ્તુતિ અહીં ઉપલબ્ધ છે. સી. ડી. સી. એસ.-એસ. ઓ. એસ., સી. ડી. સી. એસ. નું એક પેકેજ છે, જે મોટા પાયે એસ. ઓ. એસ. કાર્યક્રમો સાથે વ્યવહાર કરવા માટે એક સંવર્ધિત લેગ્રેન્જિયન પદ્ધતિ ઉકેલક છે. જુલિયા માટે જે. યુ. એમ. પી. નું સુમોફસ્ક્વેર વિસ્તરણ. જુલિયા માટે ટી. એસ. એસ. ઓ. એસ., એક બહુપદી ઓપ્ટિમાઇઝેશન સાધન છે જે સ્પાર્સિટી અનુકૂલિત ક્ષણ-એસ. ઓ. એસ. પદાનુક્રમ પર આધારિત છે. મર્યાદિત બહુપદી ઓપ્ટિમાઇઝેશનની બેવડી સમસ્યા માટે, MATLAB/ઓક્ટેવ માટે ગ્લોપ્ટીપોલી, પાયથોન માટે Ncpol2sdPA અને જુલિયા માટે મોમેન્ટઓપ્ટ. સંદર્ભો ગાણિતિક ઓપ્ટિમાઇઝેશન વાસ્તવિક બીજગણિત ભૂમિતિ