Ellipsoid method
கணித உகப்பாக்கத்தில், நீள்வட்ட முறை என்பது குவிந்த செயல்பாடுகளைக் குறைப்பதற்கான ஒரு மறு செய்கை முறையாகும். பகுத்தறிவு தரவுகளுடன் சாத்தியமான நேரியல் உகப்பாக்கம் சிக்கல்களைத் தீர்ப்பதில் நிபுணத்துவம் பெற்றிருக்கும்போது, நீள்வட்ட முறை என்பது ஒரு வழிமுறையாகும், இது உள்ளீட்டு அளவில் பல்லுறுப்புக்கோவையாக இருக்கும் பல படிகளில் உகந்த தீர்வைக் காண்கிறது. நீள்வட்ட முறை நீள்வட்டங்களின் வரிசையை உருவாக்குகிறது, அதன் அளவு ஒவ்வொரு கட்டத்திலும் ஒரே மாதிரியாக குறைகிறது, இதனால் ஒரு குவிந்த செயல்பாட்டின் மினிமைசரை இணைக்கிறது. நீள்வட்ட முறை நீண்ட வரலாற்றைக் கொண்டுள்ளது. ஒரு மறுசுழற்சி முறையாக, ஒரு ஆரம்ப பதிப்பு நௌம் இசட் ஷோர் என்பவரால் அறிமுகப்படுத்தப்பட்டது. 1972 ஆம் ஆண்டில், உண்மையான குவிந்த குறைப்புக்கான தோராயமான வழிமுறை அர்காடி நெமிரோவ்ஸ்கி மற்றும் டேவிட் பி. யூடின் (ஜூடின்) ஆகியோரால் ஆய்வு செய்யப்பட்டது. பகுத்தறிவு தரவுகளுடன் நேரியல் நிரலாக்க சிக்கல்களைத் தீர்ப்பதற்கான ஒரு வழிமுறையாக, நீள்வட்ட வழிமுறை லியோனிட் கச்சியானால் ஆய்வு செய்யப்பட்டது; நேரியல் நிரல்களின் பல்லுறுப்புக்கோவை-நேரத் தீர்க்கக்கூடிய தன்மையை நிரூபிப்பதே கச்சியானின் சாதனை. இது ஒரு கோட்பாட்டு கண்ணோட்டத்தில் ஒரு குறிப்பிடத்தக்க படியாகும்ஃ அந்த நேரத்தில் நேரியல் சிக்கல்களைத் தீர்ப்பதற்கான நிலையான வழிமுறை சிம்ப்ளக்ஸ் வழிமுறை ஆகும், இது ஒரு இயக்க நேரத்தைக் கொண்டுள்ளது, இது பொதுவாக சிக்கலின் அளவில் நேரியல், ஆனால் இதற்கு எடுத்துக்காட்டுகள் உள்ளன சிக்கலின் அளவில் அதிவேகமானது. எனவே, அனைத்து நிகழ்வுகளுக்கும் பல்லுறுப்புக்கோவை என்று உத்தரவாதம் அளிக்கப்பட்ட ஒரு வழிமுறையைக் கொண்டிருப்பது ஒரு கோட்பாட்டு திருப்புமுனையாகத் தோன்றியது. காச்சியனின் பணி, முதல் முறையாக, நேரியல் நிரல்களைத் தீர்ப்பதற்கான வழிமுறைகள் இருக்க முடியும் என்பதைக் காட்டியது, அதன் இயக்க நேரத்தை பல்லுறுப்புக்கோவை என்று நிரூபிக்க முடியும். இருப்பினும், நடைமுறையில், வழிமுறை மிகவும் மெதுவாகவும், நடைமுறை ஆர்வமும் குறைவாகவும் உள்ளது, இருப்பினும் இது பிற்காலப் பணிகளுக்கு உத்வேகம் அளித்தது, இது மிகவும் நடைமுறை பயன்பாடாக மாறியது. குறிப்பாக, கர்மார்கரின் வழிமுறை, ஒரு உட்புற-புள்ளி முறை, நடைமுறையில் நீள்வட்ட முறையை விட மிக வேகமாக உள்ளது. கர்மார்கரின் வழிமுறையும் மிக மோசமான நிலையில் வேகமானது. நீள்வட்ட வழிமுறை சிக்கலான கோட்பாட்டாளர்களை சிக்கலின் பரிமாணம் மற்றும் தரவுகளின் அளவைப் பொறுத்து (மோசமான-வழக்கு) வரம்புகளை அடைய அனுமதிக்கிறது, ஆனால் வரிசைகளின் எண்ணிக்கையைப் பொறுத்து அல்ல, எனவே இது பல ஆண்டுகளாக ஒருங்கிணைந்த உகப்பாக்கம் கோட்பாட்டில் முக்கியமானது. 21 ஆம் நூற்றாண்டில் மட்டுமே இதே போன்ற சிக்கலான பண்புகளைக் கொண்ட உட்புற-புள்ளி வழிமுறைகள் தோன்றின. விளக்கம் ஒரு குவிந்த மினிமைசேஷன் சிக்கல் பின்வரும் கூறுகளைக் கொண்டுள்ளது. திசையனின் மீது குறைக்கப்பட வேண்டிய குவிந்த செயல்பாடு (n மாறிகளைக் கொண்ட); வடிவத்தின் குவிந்த சமத்துவமின்மை கட்டுப்பாடுகள், செயல்பாடுகள் குவிந்திருக்கும் இடத்தில்; இந்த கட்டுப்பாடுகள் ஒரு குவிந்த தொகுப்பை வரையறுக்கின்றன. வடிவத்தின் நேரியல் சமத்துவக் கட்டுப்பாடுகள். ஒரு மினிமைசரைக் கொண்டிருப்பதாக வரையறுக்கப்பட்ட ஒரு ஆரம்ப நீள்வட்டமும் நமக்கு வழங்கப்படுகிறது, எங்கே மற்றும் அதன் மையமாகும். இறுதியாக, குவிந்த தொகுப்புக்கு ஒரு பிரிப்பு ஆரக்கிள் இருப்பது நமக்குத் தேவைப்படுகிறது. ஒரு புள்ளியைப் பொறுத்தவரை, ஆரக்கிள் இரண்டு பதில்களில் ஒன்றைத் திருப்ப வேண்டும்ஃ "புள்ளி உள்ளே உள்ளது", அல்லது-"புள்ளி உள்ளே இல்லை, மேலும், இங்கே ஒரு ஹைப்பர்பிளேன் இருந்து பிரிக்கப்படுகிறது", அதாவது, அனைவருக்கும் ஒரு திசையன். நீள்வட்ட முறையின் வெளியீடு பின்வருமாறுஃ பாலிடோப்பில் உள்ள எந்த புள்ளியும் (அதாவது, எந்த சாத்தியமான புள்ளியும்), அல்லது-காலியாக இருக்கும் ஒரு சான்று. எல்லா இடங்களிலும் பூஜ்ஜியமாக இருக்கும் ஒரு செயல்பாட்டின் சமத்துவமின்மை-கட்டுப்படுத்தப்பட்ட குறைத்தல் எந்தவொரு சாத்தியமான புள்ளியையும் வெறுமனே அடையாளம் காணும் சிக்கலுடன் ஒத்திருக்கிறது. எந்தவொரு நேரியல் நிரலாக்க சிக்கலையும் ஒரு நேரியல் சாத்தியக்கூறு சிக்கலாகக் குறைக்கலாம் (எ. கா. சில நேரியல் சமத்துவமின்மை மற்றும் சமத்துவக் கட்டுப்பாடுகளுக்கு உட்பட்டு பூஜ்ஜிய செயல்பாட்டைக் குறைக்கவும்). இதைச் செய்வதற்கான ஒரு வழி, முதன்மை மற்றும் இரட்டை நேரியல் நிரல்களை ஒன்றாக ஒரு நிரலாக இணைப்பதன் மூலமும், முதன்மைத் தீர்வின் மதிப்பு இரட்டைத் தீர்வின் மதிப்பை விட மோசமாக இல்லை என்ற கூடுதல் (நேரியல்) தடையை சேர்ப்பதன் மூலமும் ஆகும். மற்றொரு வழி நேரியல் நிரலின் நோக்கத்தை ஒரு கூடுதல் தடையாக கருதுவதாகும், மேலும் உகந்த மதிப்பைக் கண்டறிய பைனரி தேடலைப் பயன்படுத்துகிறது. கட்டுப்பாடற்ற மினிமைசேஷன் அல்காரிதத்தின் k-th மறு செய்கையில், ஒரு நீள்வட்டத்தின் மையத்தில் ஒரு புள்ளி உள்ளது, ஒரு திசையனைப் பெறுவதற்கு கட்டிங்-பிளேன் ஆரக்கிளை நாம் வினவுகிறோம், எனவே மேலே விவரிக்கப்பட்ட அரை நீள்வட்டத்தைக் கொண்ட குறைந்தபட்ச அளவின் நீள்வட்டமாக அமைத்துள்ளோம் என்று முடிவு செய்கிறோம். சமத்துவமின்மை-கட்டுப்படுத்தப்பட்ட மினிமைசேஷன் என்ற பண்பால் நிறுத்தும் அளவுகோல் வழங்கப்படுகிறது கட்டுப்படுத்தப்பட்ட மினிமைசேஷனுக்கான வழிமுறையின் k-th மறு செய்கையில், முன்பு போலவே நீள்வட்டத்தின் மையத்தில் ஒரு புள்ளி உள்ளது. இதுவரை சாத்தியமான மறு செய்கைகளின் மிகச்சிறிய புறநிலை மதிப்பைப் பதிவு செய்யும் மதிப்புகளின் பட்டியலையும் நாம் பராமரிக்க வேண்டும். புள்ளி சாத்தியமானதா இல்லையா என்பதைப் பொறுத்து, இரண்டு பணிகளில் ஒன்றை நாங்கள் செய்கிறோம்ஃ சாத்தியமானால், கட்டுப்பாடற்ற விஷயத்தில் உள்ள அதே புதுப்பிப்பைச் செய்யுங்கள், திருப்திப்படுத்தும் ஒரு உட்பிரிவைத் தேர்ந்தெடுப்பதன் மூலம். நமது சாத்தியக்கூறு வெட்டு ஒரு துணை சாய்வாக இருக்கலாம், இது சாத்தியமான அனைத்து z க்கும் பூர்த்தி செய்ய வேண்டும். செயல்திறன் நீள்வட்ட முறை குறைந்த பரிமாண சிக்கல்களுக்கு பயன்படுத்தப்படுகிறது, அதாவது பிளானர் இருப்பிட சிக்கல்கள், இது எண்ணியல் ரீதியாக நிலையானது. "சிறிய" அளவிலான சிக்கல்களில் கூட, இது எண்ணியல் ஸ்திரமின்மை மற்றும் நடைமுறையில் மோசமான செயல்திறன் ஆகியவற்றால் பாதிக்கப்படுகிறது. இருப்பினும், நீள்வட்ட முறை ஒருங்கிணைந்த உகப்பாக்கத்தில் ஒரு முக்கியமான தத்துவார்த்த நுட்பமாகும். கணக்கீட்டு சிக்கலான கோட்பாட்டில், நீள்வட்ட வழிமுறை கவர்ச்சிகரமானதாக இருக்கிறது, ஏனெனில் அதன் சிக்கலானது நெடுவரிசைகளின் எண்ணிக்கை மற்றும் குணகங்களின் டிஜிட்டல் அளவைப் பொறுத்தது, ஆனால் வரிசைகளின் எண்ணிக்கையைப் பொறுத்தது அல்ல. 21 ஆம் நூற்றாண்டில், ஒத்த பண்புகளைக் கொண்ட உட்புற-புள்ளி வழிமுறைகள் தோன்றியுள்ளன. டிமிட்ரிஸ் அலெவ்ராஸ் மற்றும் மான்ஃப்ரெட் டபிள்யூ. பேட்பெர்க், லீனியர் ஆப்டிமைசேஷன் அண்ட் எக்ஸ்டென்ஷன்ஸ்ஃ பிராப்ளம்ஸ் அண்ட் எக்ஸ்டென்ஷன்ஸ், யுனிவர்சிடெக்ஸ்ட், ஸ்பிரிங்கர்-வெர்லாக், 2001. (தீர்வுகளுடன் பாட்பெர்க்கில் இருந்து சிக்கல்கள்.) வி. சந்துரு மற்றும் M.R.Rao, லீனியர் புரோகிராமிங், அல்காரிதம் மற்றும் கணக்கீட்டு கையேட்டின் கோட்பாட்டில் அத்தியாயம் 31, M.J.Atallah ஆல் திருத்தப்பட்டது, சிஆர்சி பிரஸ் 1999,31-1 முதல் 31-37 வரை. வி. சந்துரு மற்றும் M.R.Rao, முழு எண் நிரலாக்கம், அல்காரிதம்ஸ் அண்ட் தியரி ஆஃப் கம்ப்யூடேஷன் கையேட்டில் அத்தியாயம் 32, M.J.Atallah ஆல் திருத்தப்பட்டது, சிஆர்சி பிரஸ் 1999,32-1 முதல் 32-45 வரை. ஜார்ஜ் பி. டான்ட்சிக் மற்றும் முகுந்த் என். தாபா. 1997 ஆம் ஆண்டு. நேரியல் நிரலாக்கம் 1: அறிமுகம். ஸ்ப்ரிங்கர்-வெர்லாக். ஜார்ஜ் பி. டான்ட்சிக் மற்றும் முகுந்த் என். தாபா. 2003 ஆம் ஆண்டு. நேரியல் நிரலாக்கம் 2: கோட்பாடு மற்றும் விரிவாக்கங்கள். ஸ்ப்ரிங்கர்-வெர்லாக். எல். லோவாஸ்ஃ எண்கள், வரைபடங்கள் மற்றும் குவியலின் ஒரு வழிமுறை கோட்பாடு, சிபிஎம்எஸ்-என்எஸ்எஃப் பிராந்திய மாநாட்டுத் தொடர் பயன்பாட்டு கணிதத்தில் 50, சியாம், பிலடெல்பியா, பென்சில்வேனியா, 1986 கட்டா ஜி. மூர்த்தி, லீனியர் புரோகிராமிங், வில்லி, 1983. எம். பேட்பெர்க், லீனியர் ஆப்டிமைசேஷன் அண்ட் எக்ஸ்டென்ஷன்ஸ், இரண்டாவது பதிப்பு, ஸ்பிரிங்கர்-வெர்லாக், 1999. கிறிஸ்டோஸ் எச். பாப்பாடிமிட்ரியோ மற்றும் கென்னத் ஸ்டெய்க்லிட்ஸ், ஒருங்கிணைந்த உகப்பாக்கம்ஃ வழிமுறைகள் மற்றும் சிக்கலானது, ஒரு புதிய முன்னுரையுடன் திருத்தப்பட்ட குடியரசு, டோவர். அலெக்சாண்டர் ஷ்ரிஜ்வர், நேரியல் மற்றும் முழு எண் நிரலாக்கத்தின் கோட்பாடு. ஜான் வில்லி & சன்ஸ், 1998, வெளிப்புற இணைப்புகள் EE364b, ஒரு ஸ்டான்போர்ட் பாடநெறி முகப்புப்பக்கம் ஒருங்கிணைந்த உகப்பாக்கம் கன்வெக்ஸ் உகப்பாக்கம் நேரியல் நிரலாக்கம்