Ellipsoid method
ریاضیاتی اصلاح میں، ایلیپسائڈ طریقہ کنویکس افعال کو کم سے کم کرنے کے لیے ایک تکراری طریقہ ہے۔ جب عقلی ڈیٹا کے ساتھ قابل عمل لکیری اصلاح کے مسائل کو حل کرنے میں مہارت حاصل ہوتی ہے، تو ایلیپسائڈ طریقہ ایک الگورتھم ہوتا ہے جو ان پٹ سائز میں کثیر الجہتی کئی مراحل میں ایک بہترین حل تلاش کرتا ہے۔ ایلیپسائڈ طریقہ ایلیپسائڈز کی ایک ترتیب پیدا کرتا ہے جس کا حجم ہر قدم پر یکساں طور پر کم ہوتا ہے، اس طرح کنویکس فنکشن کا ایک منی مائیزر منسلک ہوتا ہے۔ ایلیپسائڈ طریقہ کار کی ایک طویل تاریخ ہے۔ ایک تکراری طریقہ کے طور پر، ایک ابتدائی ورژن نوم زیڈ شور نے متعارف کرایا تھا۔ 1972 میں، حقیقی کنویکس کم سے کم کرنے کے لیے ایک تخمینہ الگورتھم کا مطالعہ ارکاڈی نیمیرووسکی اور ڈیوڈ بی یوڈن (جوڈن) نے کیا تھا۔ عقلی ڈیٹا کے ساتھ لکیری پروگرامنگ کے مسائل کو حل کرنے کے لیے ایک الگورتھم کے طور پر، ایلیپسائڈ الگورتھم کا مطالعہ لیونڈ کھچیان نے کیا تھا ؛ کھچیان کی کامیابی لکیری پروگراموں کی کثیر الجہتی وقت کی حل پذیری کو ثابت کرنا تھی۔ نظریاتی نقطہ نظر سے یہ ایک قابل ذکر قدم تھا: اس وقت لکیری مسائل کو حل کرنے کے لیے معیاری الگورتھم سمپلیکس الگورتھم تھا، جس کا ایک رن ٹائم ہوتا ہے جو عام طور پر مسئلے کے سائز میں لکیری ہوتا ہے، لیکن ایسی مثالیں موجود ہیں جن کے لیے یہ مسئلہ کے سائز میں ایکسپونینشل ہے۔ اس طرح، ایک الگورتھم ہونا جو تمام معاملات کے لیے کثیر الجہتی ہونے کی ضمانت دیتا ہے ایک نظریاتی پیشرفت کی طرح لگتا تھا۔ کھچیاں کے کام نے پہلی بار دکھایا کہ لکیری پروگراموں کو حل کرنے کے لیے الگورتھم ہو سکتے ہیں جن کا رن ٹائم کثیر الجہتی ثابت ہو سکتا ہے۔ تاہم، عملی طور پر، الگورتھم کافی سست اور بہت کم عملی دلچسپی کا حامل ہے، حالانکہ اس نے بعد کے کام کے لیے تحریک فراہم کی جو کہ بہت زیادہ عملی استعمال کا ثابت ہوا۔ خاص طور پر، کرمارکر کا الگورتھم، ایک اندرونی نقطہ طریقہ، عملی طور پر ایلیپسائڈ طریقہ سے بہت تیز ہے۔ کرمارکر کا الگورتھم بھی بدترین صورت میں تیز ہے۔ ایلیپسائڈل الگورتھم پیچیدگی تھیوریسٹوں کو (بدترین صورت میں) حدود حاصل کرنے کی اجازت دیتا ہے جو مسئلہ کے طول و عرض اور ڈیٹا کے سائز پر منحصر ہے، لیکن قطاروں کی تعداد پر نہیں، لہذا یہ کئی سالوں تک مشترکہ اصلاح کے نظریہ میں اہم رہا۔ صرف اکیسویں صدی میں اسی طرح کی پیچیدگی کی خصوصیات کے ساتھ اندرونی نقطہ الگورتھم نمودار ہوئے ہیں۔ تفصیل ایک کنویکس کم سے کم کرنے کا مسئلہ درج ذیل اجزاء پر مشتمل ہوتا ہے۔ ایک کنویکس فنکشن جسے ویکٹر پر کم سے کم کیا جانا چاہیے (جس میں n متغیرات ہوتے ہیں) ؛ شکل کی کنویکس عدم مساوات کی رکاوٹیں، جہاں افعال کنویکس ہوتے ہیں ؛ یہ رکاوٹیں ایک کنویکس سیٹ کی وضاحت کرتی ہیں۔ شکل کی لکیری مساوات کی رکاوٹیں۔ ہمیں ایک ابتدائی ایلیپسائڈ بھی دیا جاتا ہے جس کی تعریف ایک منیائزر پر مشتمل ہوتی ہے، جہاں اور اس کا مرکز ہے۔ آخر میں، ہمیں کنویکس سیٹ کے لیے علیحدگی اوریکل کے وجود کی ضرورت ہوتی ہے۔ ایک نقطہ کو دیکھتے ہوئے، اوریکل کو دو جوابات میں سے ایک جواب دینا چاہیے: "نقطہ اندر ہے"، یا-"نقطہ اندر نہیں ہے، اور اس کے علاوہ، یہاں ایک ہائپرپلین ہے جو الگ ہوتا ہے"، یعنی ایک ویکٹر جو سب کے لیے ہے۔ ایلیپسائڈ طریقہ کار کی پیداوار یا تو یہ ہے: پولیٹوپ میں کوئی بھی نقطہ (یعنی کوئی قابل عمل نقطہ)، یا-ایک ایسا ثبوت جو خالی ہو۔ کسی فنکشن کی عدم مساوات سے محدود کم سے کم کرنا جو ہر جگہ صفر ہے کسی بھی قابل عمل نقطہ کی محض شناخت کے مسئلے سے مطابقت رکھتا ہے۔ یہ پتہ چلتا ہے کہ کسی بھی لکیری پروگرامنگ کے مسئلے کو لکیری فزیبلٹی کے مسئلے تک کم کیا جا سکتا ہے (جیسے۔ کچھ لکیری عدم مساوات اور مساوات کی رکاوٹوں کے تابع صفر فنکشن کو کم سے کم کریں)۔ ایسا کرنے کا ایک طریقہ یہ ہے کہ ابتدائی اور دوہری لکیری پروگراموں کو ایک ساتھ ایک پروگرام میں ملایا جائے، اور اضافی (لکیری) رکاوٹ کو شامل کیا جائے کہ ابتدائی حل کی قیمت دوہری حل کی قیمت سے بدتر نہیں ہے۔ دوسرا طریقہ یہ ہے کہ لکیری پروگرام کے مقصد کو ایک اضافی رکاوٹ کے طور پر سمجھا جائے، اور زیادہ سے زیادہ قیمت تلاش کرنے کے لیے بائنری سرچ کا استعمال کیا جائے۔ غیر محدود کم سے کم الگورتھم کے k-th تکرار پر، ہمارے پاس ایک ایلیپسائڈ کے مرکز میں ایک نقطہ ہوتا ہے۔ ہم ایک ویکٹر حاصل کرنے کے لیے کٹنگ پلین اوریکل سے استفسار کرتے ہیں کہ اس طرح ہم یہ نتیجہ اخذ کرتے ہیں کہ ہم اوپر بیان کردہ نصف ایلیپسائڈ پر مشتمل کم سے کم حجم کا ایلیپسائڈ مقرر کرتے ہیں اور حساب کرتے ہیں۔ اپ ڈیٹ اس طرح دیا جاتا ہے کہ رکنے کا معیار اس خاصیت کے ذریعہ دیا گیا ہے کہ عدم مساوات سے محدود کم سے کم کرنا محدود کم سے کم کرنے کے لیے الگورتھم کے k-th تکرار پر، ہمارے پاس پہلے کی طرح ایلیپسائڈ کے مرکز میں ایک نقطہ ہے۔ ہمیں اب تک کے قابل عمل تکرار کی سب سے چھوٹی معروضی قدر کو ریکارڈ کرنے والی اقدار کی فہرست بھی برقرار رکھنی چاہیے۔ اس بات پر منحصر ہے کہ نقطہ قابل عمل ہے یا نہیں، ہم دو میں سے ایک کام انجام دیتے ہیں: اگر ممکن ہو تو، بنیادی طور پر وہی اپ ڈیٹ انجام دیں جو غیر پابند صورت میں ہوتا ہے، ایک ذیلی میلان کا انتخاب کرکے جو مطمئن کرتا ہے اگر ناقابل عمل ہے اور جے-تھ رکاوٹ کی خلاف ورزی کرتا ہے، تو ایلیپسائڈ کو فزیبلٹی کٹ کے ساتھ اپ ڈیٹ کریں۔ ہماری فزیبلٹی کٹ ایک ذیلی میلان ہو سکتا ہے جس کو تمام قابل عمل z کے لیے پورا کرنا چاہیے۔ کارکردگی ایلیپسائڈ طریقہ کم جہتی مسائل پر استعمال ہوتا ہے، جیسے کہ پلینر لوکیشن کے مسائل، جہاں یہ عددی طور پر مستحکم ہے۔ یہاں تک کہ "چھوٹے" سائز کے مسائل پر، یہ عددی عدم استحکام اور عملی طور پر ناقص کارکردگی کا شکار ہے۔ تاہم، ایلیپسائڈ طریقہ امتزاج کی اصلاح میں ایک اہم نظریاتی تکنیک ہے۔ کمپیوٹیشنل پیچیدگی کے نظریہ میں، ایلیپسائڈ الگورتھم پرکشش ہے کیونکہ اس کی پیچیدگی کالموں کی تعداد اور کوفیشنٹس کے ڈیجیٹل سائز پر منحصر ہوتی ہے، لیکن قطاروں کی تعداد پر نہیں۔ اکیسویں صدی میں، اسی طرح کی خصوصیات کے ساتھ اندرونی نقطہ الگورتھم نمودار ہوئے ہیں۔ مزید پڑھنے کے نوٹ دمتریس الیراس اور منفریڈ ڈبلیو پیڈبرگ، لکیری آپٹیمائزیشن اینڈ ایکسٹینشنز: مسائل اور ایکسٹینشنز، یونیورسی ٹیکسٹ، سپرنگر-ورلاگ، 2001۔ (حل کے ساتھ پیڈبرگ کے مسائل۔) V. چندرو اور M.R.Rao، لکیری پروگرامنگ، الگورتھم اینڈ تھیوری آف کمپیوٹیشن ہینڈ بک میں باب 31، M.J.Atallah کے ذریعہ ترمیم شدہ، CRC پریس 1999، 31-1 سے 31-37۔ V. چندرو اور M.R.Rao، انٹیجر پروگرامنگ، الگورتھم میں باب 32 اور کمپیوٹیشن ہینڈ بک کا نظریہ، M.J.Atallah کے ذریعہ ترمیم شدہ، CRC پریس 1999، 32-1 سے 32-45۔ جارج بی ڈینٹزگ اور مکند این تھاپا۔ 1997۔ لکیری پروگرامنگ 1: تعارف۔ سپرنگر-ورلاگ۔ جارج بی ڈینٹزگ اور مکند این تھاپا۔ 2003 میں۔ لکیری پروگرامنگ 2: تھیوری اور ایکسٹینشنز۔ سپرنگر-ورلاگ۔ ایل لووز: این الگورتھمک تھیوری آف نمبرز، گرافز، اینڈ کنویکسٹی، سی بی ایم ایس-این ایس ایف ریجنل کانفرنس سیریز ان اپلائیڈ میتھمیٹکس 50، ایس آئی اے ایم، فلاڈیلفیا، پنسلوانیا، 1986 کٹا جی مورٹی، لکیری پروگرامنگ، ولی، 1983۔ ایم پیڈبرگ، لکیری آپٹیمائزیشن اینڈ ایکسٹینشنز، سیکنڈ ایڈیشن، سپرنگر-ورلاگ، 1999۔ کرسٹوس ایچ پاپاڈیمیٹریو اور کینتھ اسٹیگلٹز، مشترکہ اصلاح: الگورتھم اور پیچیدگی، ایک نئے پیش لفظ کے ساتھ درست جمہوریہ، ڈوور۔ الیگزینڈر شریجور، تھیوری آف لینیر اینڈ انٹیجر پروگرامنگ۔ جان ولی اینڈ سنز، 1998، بیرونی روابط EE364b، ایک اسٹینفورڈ کورس کا ہوم پیج مشترکہ اصلاح کنویکس اصلاح لکیری پروگرامنگ