Interior-point method
اندرونی نقطہ کے طریقے (جسے رکاوٹ کے طریقے یا آئی پی ایم بھی کہا جاتا ہے) الگورتھم کی ایک مخصوص کلاس ہیں جو لکیری اور غیر لکیری کنویکس اصلاح کے مسائل کو حل کرتی ہیں۔ ایک اندرونی نقطہ طریقہ 1967 میں سوویت ریاضی دان آئی آئی ڈکن نے دریافت کیا تھا اور 1980 کی دہائی کے وسط میں امریکہ میں اسے دوبارہ ایجاد کیا گیا تھا۔ 1984 میں، نریندر کرمارکر نے لکیری پروگرامنگ کے لیے ایک طریقہ تیار کیا جسے کرمارکر کا الگورتھم کہا جاتا ہے، جو ثابت شدہ کثیر الجہتی وقت میں چلتا ہے اور عملی طور پر بھی بہت موثر ہے۔ اس نے لکیری پروگرامنگ کے مسائل کے حل کو فعال کیا جو سمپلیکس طریقہ کار کی صلاحیتوں سے بالاتر تھے۔ سمپلیکس طریقہ کار کے برعکس، یہ قابل عمل علاقے کے اندرونی حصے کو عبور کر کے بہترین حل تک پہنچتا ہے۔ طریقہ کار کو کنویکس سیٹ کو انکوڈ کرنے کے لیے استعمال ہونے والے سیلف کنکورڈنٹ بیریئر فنکشن کی بنیاد پر کنویکس پروگرامنگ کے لیے عام کیا جا سکتا ہے۔ کسی بھی کنویکس آپٹیمائزیشن کے مسئلے کو ایک کنویکس سیٹ پر ایک لکیری فنکشن کو کم سے کم (یا زیادہ سے زیادہ) کرنے میں تبدیل کیا جا سکتا ہے۔ رکاوٹ کا استعمال کرتے ہوئے قابل عمل سیٹ کو انکوڈنگ کرنے اور رکاوٹ کے طریقوں کو ڈیزائن کرنے کے خیال کا مطالعہ انتھونی وی فائیکو، گارتھ پی میک کارمک اور دیگر نے 1960 کی دہائی کے اوائل میں کیا تھا۔ یہ خیالات بنیادی طور پر عمومی غیر لکیری پروگرامنگ کے لیے تیار کیے گئے تھے، لیکن بعد میں اس طبقے کے مسائل کے لیے زیادہ مسابقتی طریقوں کی موجودگی کی وجہ سے انہیں ترک کر دیا گیا۔ ترتیب وار کواڈریٹک پروگرامنگ)۔ یوری نیسٹروف اور ارکاڈی نیمیرووسکی نے اس طرح کی رکاوٹوں کی ایک خاص کلاس تیار کی جسے کسی بھی کنویکس سیٹ کو انکوڈ کرنے کے لیے استعمال کیا جا سکتا ہے۔ وہ اس بات کی ضمانت دیتے ہیں کہ الگورتھم کے تکرار کی تعداد حل کے طول و عرض اور درستگی میں کثیر الجہتی سے محدود ہے۔ کرمارکر کی پیشرفت نے اندرونی نقطہ کے طریقوں اور رکاوٹ کے مسائل کے مطالعہ کو زندہ کیا، جس سے یہ ظاہر ہوتا ہے کہ لکیری پروگرامنگ کے لیے ایک الگورتھم بنانا ممکن تھا جس کی خصوصیت کثیر الجہتی پیچیدگی تھی اور اس کے علاوہ، جو سمپلیکس طریقہ کے ساتھ مسابقتی تھا۔ پہلے سے ہی کھچیان کا ایلیپسائڈ طریقہ ایک کثیر الجہتی وقت کا الگورتھم تھا ؛ تاہم، یہ عملی دلچسپی کا حامل ہونا بہت سست تھا۔ ابتدائی-دوہری راستے کی پیروی کرنے والے اندرونی نقطہ طریقوں کی کلاس کو سب سے زیادہ کامیاب سمجھا جاتا ہے۔ مہروترا کا پیشن گوئی کرنے والا اصلاح کار الگورتھم اس طبقے کے طریقوں کے زیادہ تر نفاذ کی بنیاد فراہم کرتا ہے۔ غیر لکیری اصلاح کے لیے ابتدائی-دوہری اندرونی نقطہ کا طریقہ محدود غیر لکیری اصلاح کے لیے ابتدائی-دوہری طریقہ کے خیال کا مظاہرہ کرنا آسان ہے۔ سادگی کے لیے، عدم مساوات کی رکاوٹوں کے ساتھ درج ذیل غیر لکیری اصلاح کے مسئلے پر غور کریں: یہ عدم مساوات سے محدود اصلاح کا مسئلہ اسے ایک غیر محدود معروضی فنکشن میں تبدیل کر کے حل کیا جاتا ہے جس کی کم سے کم ہم مؤثر طریقے سے تلاش کرنے کی امید کرتے ہیں۔ خاص طور پر، (1) سے وابستہ لوگرتھمک بیریئر فنکشن یہ ہے کہ یہاں ایک چھوٹا مثبت اسکیلر ہے، جسے بعض اوقات "بیریئر پیرامیٹر" کہا جاتا ہے۔ جیسا کہ صفر میں ضم ہوتا ہے کم از کم (1) کے حل میں ضم ہونا چاہئے۔ تفریق پذیر فنکشن کے میلان کو ظاہر کیا جاتا ہے۔ اصل ("پرائمل") متغیر کے علاوہ ہم ایک لگرینج ملٹی پلیئر سے متاثر دوہری متغیر مساوات (4) متعارف کراتے ہیں جسے بعض اوقات "پرٹربڈ کمپلیمینٹریٹی" حالت کہا جاتا ہے، کیونکہ اس کی مشابہت کے کے ٹی حالات میں "تکمیلی سستی" سے ہوتی ہے۔ ہم ان کو تلاش کرنے کی کوشش کرتے ہیں جن کے لیے رکاوٹ فنکشن کا میلان صفر ہے۔ (4) سے (3) میں تبدیل کرتے ہوئے، ہمیں میلان کے لیے ایک مساوات ملتی ہے: جہاں میٹرکس رکاوٹوں کا جیکوبین ہوتا ہے۔ (5) کے پیچھے وجدان یہ ہے کہ کا میلان سب اسپیس میں ہونا چاہیے جو رکاوٹوں کے میلان سے پھیلا ہوا ہے۔ چھوٹے (4) کے ساتھ "پریشان کن تکمیل" کو اس شرط کے طور پر سمجھا جا سکتا ہے کہ حل یا تو حد کے قریب ہونا چاہیے، یا یہ کہ رکاوٹ جزو نارمل پر میلان کا تخمینہ تقریبا صفر ہونا چاہیے۔ آئیے بار بار اپ ڈیٹ کرنے کے لیے تلاش کی سمت بنیں۔ نیوٹن کے طریقہ کار کو (4) اور (5) پر لاگو کرتے ہوئے، ہمیں ایک مساوات ملتی ہے: جہاں کا ہیسیئن میٹرکس ہے، ایک اخترن میٹرکس ہے، اور اس کا اخترن میٹرکس ہے۔ (1)، (4) کی وجہ سے ہر قدم پر شرط نافذ کی جانی چاہیے۔ یہ مناسب انتخاب کر کے کیا جا سکتا ہے: افائن اسکیلنگ آگمینٹڈ لاگرانجین طریقہ بھی دیکھیں۔ چمبولی-پاک الگورتھم کرش-کوہن-ٹکر حالات جرمانہ طریقہ حوالہ جات کتاب نگاری اصلاح الگورتھم اور طریقے