Sum-of-squares optimization
ஒரு கூட்டுத்தொகை சதுர உகப்பாக்கம் திட்டம் என்பது ஒரு நேரியல் செலவு செயல்பாடு மற்றும் முடிவு மாறிகளில் ஒரு குறிப்பிட்ட வகை கட்டுப்பாடு கொண்ட ஒரு உகப்பாக்கம் சிக்கலாகும். இந்த கட்டுப்பாடுகள் சில பல்லுறுப்புக்கோவைகளில் முடிவு மாறிகள் குணகங்களாகப் பயன்படுத்தப்படும்போது, அந்த பல்லுறுப்புக்கோவைகள் பல்லுறுப்புக்கோவை SOS பண்பைக் கொண்டிருக்க வேண்டும். சம்பந்தப்பட்ட பல்லுறுப்புக்கோவைகளின் அதிகபட்ச அளவை நிர்ணயிக்கும் போது, கூட்டுத்தொகை-சதுர உகப்பாக்கம் அரை வரையறுக்கப்பட்ட நிரலாக்கத்தில் தளர்வுகளின் லேசர் படிநிலை என்றும் அழைக்கப்படுகிறது. கட்டுப்பாட்டுக் கோட்பாடு (குறிப்பாக, பல்லுறுப்புக்கோவை திசையன் புலங்களால் விவரிக்கப்படும் இயக்கவியல் அமைப்புகளுக்கான பல்லுறுப்புக்கோவை லியாபுனோவ் செயல்பாடுகளைத் தேடுவதற்கு), புள்ளிவிவரங்கள், நிதி மற்றும் இயந்திர கற்றல் உள்ளிட்ட பல்வேறு பகுதிகளில் கூட்டுத்தொகை சதுர உகப்பாக்கம் நுட்பங்கள் பயன்படுத்தப்பட்டுள்ளன. டான், டபிள்யூ., பேக்கார்ட், ஏ., 2004. "சதுர நிரலாக்கத்தின் கூட்டுத்தொகையைப் பயன்படுத்தி கட்டுப்பாட்டு லியாபுனோவ் செயல்பாடுகளைத் தேடுகிறது". இல்ஃ அலெர்டன் கான்ஃப். கம்யூனிகேஷன், கன்ட்ரோல் அண்ட் கம்ப்யூட்டிங். பிபி. 210-219. </ref> A. சக்ரவர்த்தி, பி. செய்லர் மற்றும் ஜி. பாலாஸ், "எஃப்/ஏ-18 விமானக் கட்டுப்பாட்டாளர்களின் வீழ்ச்சி-இலை முறைக்கு சஸ்பெக்டிபிலிட்டிஃ நான்லீனியர் அனாலிசிஸ்", ஏ. ஐ. ஏ. ஏ ஜர்னல் ஆஃப் கைடென்ஸ், கண்ட்ரோல் அண்ட் டைனமிக்ஸ், தொகுதி. 34 இல்லை. 1 (2011), பக். 73-85. உகப்பாக்கம் சிக்கல் ஒரு திசையன் மற்றும் பல்லுறுப்புக்கோவைகளைப் பொறுத்தவரை, ஒரு கூட்டுத்தொகை வர்க்க உகப்பாக்கம் சிக்கல் இவ்வாறு எழுதப்படுகிறது இங்கே "SOS" என்பது கூட்டுத்தொகை வர்க்கங்களின் (SOS) பல்லுறுப்புக்கோவைகளின் வகுப்பைக் குறிக்கிறது. அளவுகள் முடிவு மாறிகள் ஆகும். SOS நிரல்களை SOS பல்லுறுப்புக்கோவை நிரலின் இரட்டைத்தன்மையைப் பயன்படுத்தி அரை வரையறுக்கப்பட்ட நிரல்களாக (SDP கள்) மாற்றலாம் மற்றும் நேர்மறை-அரை வரையறுக்கப்பட்ட மேட்ரிக்ஸ்களைப் பயன்படுத்தி கட்டுப்படுத்தப்பட்ட பல்லுறுப்புக்கோவை உகப்பாக்கலுக்கான தளர்வு, பின்வரும் பகுதியைப் பார்க்கவும். இரட்டை சிக்கல்ஃ கட்டுப்படுத்தப்பட்ட பல்லுறுப்புக்கோவை உகப்பாக்கம் நம்மிடம் ஒரு-மாறுபட்ட பல்லுறுப்புக்கோவை உள்ளது என்று வைத்துக்கொள்வோம், மேலும் இந்த பல்லுறுப்புக்கோவை ஒரு துணைக்குழுவில் குறைக்க விரும்புகிறோம் என்று வைத்துக்கொள்வோம். மேலும், துணைக்குழுவில் உள்ள கட்டுப்பாடுகள் அதிகபட்சமாக டிகிரியின் பல்லுறுப்புக்கோவை சமத்துவங்களைப் பயன்படுத்தி குறியிடப்படலாம் என்று வைத்துக்கொள்வோம், ஒவ்வொரு வடிவமும் அதிகபட்சமாக டிகிரியின் பல்லுறுப்புக்கோவை ஆகும். இந்த ஆப்டிமைசேஷன் சிக்கலுக்கான இயற்கையான, பொதுவாக கன்வெக்ஸ் அல்லாத நிரல் பின்வருமாறுஃ டிகிரியில் ஒவ்வொரு மோனோமியலுக்கும் ஒரு உள்ளீட்டைக் கொண்ட-பரிமாண திசையன் எங்கே, இதனால் ஒவ்வொரு மல்டிசெட்டுக்கும், நாம் குறைக்க விரும்பும் பல்லுறுப்புக்கோவையின் குணகங்களின் அணி, மற்றும் பல்லுறுப்புக்கோவையின் குறியீட்டின் குணகங்களின் அணி-இது துணைக்குழுவில் உள்ள-th கட்டுப்பாட்டைக் குறிக்கிறது. நமது தேடல் இடத்தில் கூடுதல், நிலையான மாறிலி குறியீடு, பல்லுறுப்புக்கோவைகளை எழுதுவதற்கும் மேட்ரிக்ஸ் பிரதிநிதித்துவத்திற்கும் வசதியாக சேர்க்கப்படுகிறது. இந்த நிரல் பொதுவாக கன்வெக்ஸ் அல்லாதது, ஏனெனில் கட்டுப்பாடுகள் () கன்வெக்ஸ் அல்ல. இந்த மினிமைசேஷன் சிக்கலுக்கான ஒரு சாத்தியமான குவிந்த தளர்வு செமிடிஃபைனைட் நிரலாக்கத்தைப் பயன்படுத்தி மாறிகளின் ரேங்க்-ஒன் மேட்ரிக்ஸை பாசிட்டிவ்-செமிடிஃபைனைட் மேட்ரிக்ஸுடன் மாற்றுகிறதுஃ அளவின் ஒவ்வொரு மோனோமியலையும் பெரும்பாலான குறியீடுகளின் பல தொகுப்புகளால் குறியிடுகிறோம். அத்தகைய ஒவ்வொரு மோனோமியலுக்கும், நிரலில் ஒரு மாறியை உருவாக்குகிறோம், மேலும் மேட்ரிக்ஸை உருவாக்க மாறிகளை ஏற்பாடு செய்கிறோம், அங்கு உண்மையான மேட்ரிக்ஸின் தொகுப்பு, அதன் வரிசைகள் மற்றும் நெடுவரிசைகள் அதிகபட்ச அளவிலிருந்து உறுப்புகளின் பல தொகுப்புகளுடன் அடையாளம் காணப்படுகின்றன. பின்னர் பின்வரும் செமிடிஃபைனைட் நிரலை மாறிகளில் எழுதுகிறோம்ஃ இதற்கு உட்பட்டுஃ மீண்டும் நாம் குறைக்க விரும்பும் பல்லுறுப்புக்கோவையின் குணகங்களின் அணி, மற்றும் பல்லுறுப்புக்கோவையின் குறியீட்டின் குணகங்களின் அணி துணைக்குழுவில் உள்ள-th கட்டுப்பாடு. மூன்றாவது கட்டுப்பாடு மேட்ரிக்ஸுக்குள் பல முறை தோன்றும் மோனோமியலின் மதிப்பு மேட்ரிக்ஸ் முழுவதும் சமமாக இருப்பதை உறுதி செய்கிறது, மேலும் இருபடி வடிவத்தில் இருக்கும் சமச்சீர்மைகளை மதிக்க சேர்க்கப்படுகிறது. டூயலிட்டி ஒன்று மேலே உள்ள அரை வரையறுக்கப்பட்ட நிரலின் டூயலை எடுத்து பின்வரும் நிரலைப் பெறலாம்ஃ கட்டுப்பாட்டுடன் தொடர்புடைய ஒரு மாறி நம்மிடம் உள்ளது (இங்கு அனைத்து உள்ளீடுகளுடன் கூடிய மேட்ரிக்ஸ் பூஜ்ஜியத்தால் குறியிடப்பட்ட உள்ளீட்டிற்கு சேமிக்கப்படுகிறது), ஒவ்வொரு பல்லுறுப்புக்கோவை கட்டுப்பாட்டிற்கும் ஒரு உண்மையான மாறி மற்றும் பல தொகுப்புகளின் ஒவ்வொரு குழுவிற்கும், சமச்சீர் கட்டுப்பாட்டுக்கு ஒரு இரட்டை மாறி உள்ளது. நேர்மறை-சமச்சீர் வரம்பு கட்டுப்பாடு என்பது பல்லுறுப்புக்கோவைகளின் கூட்டுத்தொகையாக இருப்பதை உறுதிசெய்கிறதுஃ நேர்மறை-சமச்சீர் வரையறுக்கப்பட்ட மேட்ரிக்ஸ்களின் குணாதிசயத்தால், எந்தவொரு நேர்மறை-சமச்சீர் வரையறுக்கப்பட்ட மேட்ரிக்ஸுக்கும், நாம் திசையன்களுக்கு எழுதலாம். எனவே எதற்கும், டிகிரியின் பல்லுறுப்புக்கோவையின் குணகங்களுடன் திசையன்களை நாம் அடையாளம் கண்டுள்ளோம். இது மதிப்பு அதிகமாக இருப்பதற்கான ஒரு கூட்டுத்தொகை வர்க்க ஆதாரத்தை வழங்குகிறது. மேற்கூறியவை பல்லுறுப்புக்கோவை ஏற்றத்தாழ்வுகளால் வரையறுக்கப்பட்ட பகுதிகளுக்கும் விரிவுபடுத்தப்படலாம். Lasserre படிநிலை என்றும் அழைக்கப்படும் கூட்டுத்தொகை-சதுர படிநிலை (SOS படிநிலை) என்பது அதிகரிக்கும் சக்தி மற்றும் அதிகரிக்கும் கணக்கீட்டு செலவின் குவிந்த தளர்வுகளின் படிநிலையாகும். ஒவ்வொரு இயற்கை எண்ணுக்கும் தொடர்புடைய குவிந்த தளர்வு SOS படிநிலையின் th நிலை அல்லது-th சுற்று என்று அழைக்கப்படுகிறது. முதல் சுற்று, எப்போது, ஒரு அடிப்படை அரை வரையறுக்கப்பட்ட நிரலுடன் ஒத்திருக்கிறது, அல்லது அதிகபட்சமாக டிகிரியின் பல்லுறுப்புக்கோவைகளின் மீது கூட்டுத்தொகை-சதுர உகப்பாக்கம். படிநிலையின் முதல் மட்டத்தில் அடிப்படை குவிந்த நிரலை-th நிலைக்கு அதிகரிக்க, நிரல் அதிகபட்சமாக டிகிரி பல்லுறுப்புக்கோவைகளை கருத்தில் கொள்ள கூடுதல் மாறிகள் மற்றும் கட்டுப்பாடுகள் நிரலில் சேர்க்கப்படுகின்றன. எஸ்ஓஎஸ் வரிசைமுறை அதன் பெயரை-th மட்டத்தில் உள்ள புறநிலை செயல்பாட்டின் மதிப்பு இரட்டை வழியாக அதிகபட்சமாக டிகிரியின் பல்லுறுப்புக்கோவைகளைப் பயன்படுத்தி ஒரு கூட்டுத்தொகை-சதுர ஆதாரத்துடன் பிணைக்கப்பட்டுள்ளது என்பதிலிருந்து பெறுகிறது (மேலே உள்ள "டூயல்டிட்டி" ஐப் பார்க்கவும்). இதன் விளைவாக, அதிகபட்சமாக டிகிரி பல்லுறுப்புக்கோவைகளைப் பயன்படுத்தும் எந்த கூட்டுத்தொகை-சதுர ஆதாரமும் புறநிலை மதிப்பை பிணைக்கப் பயன்படுத்தப்படலாம், இது தளர்வுகளின் இறுக்கம் குறித்த உத்தரவாதங்களை நிரூபிக்க அனுமதிக்கிறது. பெர்க்கின் தேற்றத்துடன் இணைந்து, போதுமான பல சுற்றுகள் கொடுக்கப்பட்டால், எந்த நிலையான இடைவெளியிலும் தளர்வு தன்னிச்சையாக இறுக்கமாக இருக்கும் என்பதை இது மேலும் குறிக்கிறது. ஒரு வரம்புக்குட்பட்ட இடைவெளியில் உள்ள ஒவ்வொரு எதிர்மறை அல்லாத உண்மையான பல்லுறுப்புக்கோவையையும் அந்த இடைவெளியில் துல்லியத்திற்குள் போதுமான உயர் டிகிரியின் உண்மையான பல்லுறுப்புக்கோவைகளின் கூட்டுத்தொகையுடன் தோராயமாக மதிப்பிட முடியும் என்று பெர்க்கின் முடிவு கூறுகிறது, எனவே பல்லுறுப்புக்கோவை புறநிலை மதிப்பு புள்ளியின் செயல்பாடாக இருந்தால், சமத்துவமின்மை ஆர்வமுள்ள பிராந்தியத்தில் உள்ள அனைவருக்கும் இருந்தால், இந்த உண்மையின் கூட்டுத்தொகை-சதுர ஆதாரம் இருக்க வேண்டும். சாத்தியமான பிராந்தியத்தின் மீது புறநிலை செயல்பாட்டின் குறைந்தபட்சமாக தேர்வுசெய்தால், எங்களுக்கு முடிவு உள்ளது. கணக்கீட்டு செலவு மாறிகளில் ஒரு செயல்பாட்டை உகந்ததாக்கும் போது, படிநிலையின்-th நிலை மாறிகள் மீது அரை வரையறுக்கப்பட்ட நிரலாக எழுதப்படலாம், மேலும் நீள்வட்ட முறையைப் பயன்படுத்தி சரியான நேரத்தில் தீர்க்கப்படலாம். ஒரு பல்லுறுப்புக்கோவை என்பது அத்தகைய பல்லுறுப்புக்கோவைகள் இருந்தால் வர்க்கங்களின் கூட்டுத்தொகை (எஸ்ஓஎஸ்) ஆகும். எடுத்துக்காட்டாக, இது வர்க்கங்களின் கூட்டுத்தொகை என்பதால், வர்க்கங்களின் கூட்டுத்தொகை என்றால் அனைவருக்கும். பல்லுறுப்புக்கோவை SOS இன் விரிவான விளக்கங்கள் available.Parrilo, P. (2003) "அரை இயற்கணித சிக்கல்களுக்கான அரை வரையறுக்கப்பட்ட நிரலாக்க தளர்வுகள்" ஆகும். கணித நிரலாக்க செர். பி 96 (2), 293-320. ஒரு சமச்சீர் அணி இருக்கும் இடத்தில் நாற்கர வடிவங்களை வெளிப்படுத்தலாம். இதேபோல், டிகிரி ≤ 2d "இன் பல்லுறுப்புக்கோவைகளை திசையன் டிகிரியின் அனைத்து மோனோமியல்களையும் கொண்டிருக்கும் இடத்தில் வெளிப்படுத்தலாம். இது கிராம் மேட்ரிக்ஸ் வடிவம் என்று அழைக்கப்படுகிறது. ஒரு முக்கியமான உண்மை என்னவென்றால், அது போன்ற ஒரு சமச்சீர் மற்றும் நேர்மறை-அரை வரையறுக்கப்பட்ட அணி இருந்தால் மட்டுமே SOS ஆகும். இது SOS பல்லுறுப்புக்கோவைகள் மற்றும் நேர்மறை-அரை வரையறுக்கப்பட்ட மேட்ரிக்ஸ்களுக்கு இடையே ஒரு தொடர்பை வழங்குகிறது. மென்பொருள் கருவிகள் சாஸ்டூல்ஸ், குனு ஜிபிஎல்லின் கீழ் உரிமம் பெற்றது. குறிப்பு வழிகாட்டி arXiv: 1310.4716 [math.OC] இல் கிடைக்கிறது, மேலும் அதன் உட்புறங்களைப் பற்றிய விளக்கக்காட்சி இங்கே கிடைக்கிறது. சி. டி. சி. எஸ்-சோஸ், சி. டி. சி. எஸ்ஸின் ஒரு தொகுப்பு, பெரிய அளவிலான எஸ்ஓஎஸ் திட்டங்களைக் கையாள்வதற்கான ஒரு ஆக்மென்டட் லக்ராஞ்சியன் முறை தீர்வு. ஜூலியாவுக்கான ஜூம்பியின் சுமோஃப்ஸ்கொயர்ஸ் நீட்டிப்பு. ஜூலியாவுக்கான டி. எஸ். எஸ். ஓ. எஸ், ஸ்பார்ஸி தழுவிய தருணம்-எஸ். ஓ. எஸ் படிநிலைகளை அடிப்படையாகக் கொண்ட ஒரு பல்லுறுப்புக்கோவை உகப்பாக்கம் கருவி. கட்டுப்படுத்தப்பட்ட பல்லுறுப்புக்கோவை உகப்பாக்கத்தின் இரட்டை சிக்கலுக்கு, MATLAB/ஆக்டேவுக்கு GloptiPoly, பைத்தானுக்கு Ncpol2sdPA மற்றும் ஜூலியாவுக்கு MomentOpt. குறிப்புகள் கணித உகப்பாக்கம் உண்மையான இயற்கணித வடிவியல்