Augmented Lagrangian method
آگمینٹڈ لاگرانجین طریقے محدود اصلاح کے مسائل کو حل کرنے کے لیے الگورتھم کی ایک مخصوص کلاس ہیں۔ ان میں جرمانے کے طریقوں سے مماثلت ہے کہ وہ ایک محدود اصلاح کے مسئلے کو غیر محدود مسائل کی ایک سیریز سے تبدیل کرتے ہیں اور مقصد میں جرمانے کی اصطلاح شامل کرتے ہیں، لیکن آگمینٹڈ لاگرانجین طریقہ ایک اور اصطلاح کا اضافہ کرتا ہے جو ایک لاگرانج ضرب کی نقل کرنے کے لیے ڈیزائن کیا گیا ہے۔ آگمینٹڈ لاگرانجین کا تعلق لاگرانج ملٹی پلیئرز کے طریقہ کار سے ہے، لیکن اس سے ملتا جلتا نہیں ہے۔ مختلف انداز سے دیکھا جائے تو، غیر محدود مقصد محدود مسئلے کا لاگرانجین ہے، جس میں اضافی جرمانے کی مدت (اضافہ) ہے۔ یہ طریقہ اصل میں ضرب کے طریقہ کار کے نام سے جانا جاتا تھا اور اس کا مطالعہ 1970 اور 1980 کی دہائی میں جرمانے کے طریقوں کے ممکنہ متبادل کے طور پر کیا گیا تھا۔ اس پر سب سے پہلے میگنس ہیسٹینس اور پھر 1969 میں مائیکل پاول نے تبادلہ خیال کیا۔ اس طریقہ کار کا مطالعہ آر ٹائرل راکفیلر نے فینچل ڈوئلٹی کے سلسلے میں کیا تھا، خاص طور پر پراکسیمل پوائنٹ طریقوں، موریو-یوسیڈا ریگولرائزیشن، اور زیادہ سے زیادہ مونوٹون آپریٹرز کے سلسلے میں۔ یہ طریقے ساختی اصلاح میں استعمال کیے گئے تھے۔ اس طریقہ کار کا مطالعہ دیمیتری برٹسیکاس نے بھی کیا تھا، خاص طور پر اپنی 1982 کی کتاب میں، جس میں غیر کواڈریٹک ریگولرائزیشن افعال (مثال کے طور پر، اینٹروپک ریگولرائزیشن) شامل ہیں۔ یہ مشترکہ مطالعہ "ضرب کے ایکسپونینشل طریقہ" کو جنم دیتا ہے جو عدم مساوات کی رکاوٹوں کو دو بار تفریق کے قابل اضافہ شدہ لاگرانجین فنکشن کے ساتھ سنبھالتا ہے۔ 1970 کی دہائی سے، سیکوینشیل کواڈریٹک پروگرامنگ (ایس کیو پی) اور انٹیر پوائنٹ میتھڈز (آئی پی ایم) پر زیادہ توجہ دی گئی ہے، جزوی طور پر اس لیے کہ وہ عددی سافٹ ویئر لائبریریوں سے اسپارس میٹرکس سبروٹینز کو زیادہ آسانی سے استعمال کرتے ہیں، اور جزوی طور پر اس لیے کہ آئی پی ایم میں خود مطابقت پذیر افعال کے نظریہ کے ذریعے ثابت شدہ پیچیدگی کے نتائج ہوتے ہیں۔ آگمینٹڈ لاگرانجین طریقہ کار کو اصلاح کے نظام LANCELOT، ALGENCAN اور AMPL کے ذریعے دوبارہ زندہ کیا گیا، جس نے بظاہر گھنے لیکن "جزوی طور پر الگ کرنے کے قابل" مسائل پر غیر معمولی میٹرکس تکنیکوں کو استعمال کرنے کی اجازت دی۔ یہ طریقہ اب بھی کچھ مسائل کے لیے مفید ہے۔ 2007 کے آس پاس، کل تغیر ڈینوائزنگ اور کمپریسڈ سینسنگ جیسے شعبوں میں آگمینٹڈ لاگرانجین طریقوں کی بحالی ہوئی۔ خاص طور پر، معیاری آگمینٹڈ لاگرانجین طریقہ کار کی ایک قسم جو جزوی اپ ڈیٹس کا استعمال کرتی ہے (لکیری مساوات کو حل کرنے کے لیے گاؤس-سیڈل طریقہ کار کی طرح) جسے ملٹی پلیئرز یا اے ڈی ایم ایم کا متبادل سمت طریقہ کہا جاتا ہے، نے کچھ توجہ حاصل کی۔ عمومی طریقہ مندرجہ ذیل محدود اصلاح کے مسئلے کو حل کرنے پر غور کریں: اس کے تابع جہاں مساوات کی رکاوٹوں کے اشارے کی نشاندہی ہوتی ہے۔ اس مسئلے کو غیر محدود کم سے کم مسائل کے سلسلے کے طور پر حل کیا جا سکتا ہے۔ حوالہ کے لیے، ہم پہلے جرمانے کے طریقہ کار کے نقطہ نظر کے kth مرحلے کو درج کرتے ہیں: جرمانے کا طریقہ اس مسئلے کو حل کرتا ہے، پھر اگلے تکرار پر یہ بڑی قیمت کا استعمال کرتے ہوئے اور پرانے حل کو ابتدائی اندازے یا "وارم اسٹارٹ" کے طور پر استعمال کرتے ہوئے مسئلہ کو دوبارہ حل کرتا ہے۔ آگمینٹڈ لاگرانجین طریقہ مندرجہ ذیل غیر محدود مقصد کا استعمال کرتا ہے: اور ہر تکرار کے بعد، اپ ڈیٹ کرنے کے علاوہ، متغیر کو بھی اس اصول کے مطابق اپ ڈیٹ کیا جاتا ہے جہاں kth مرحلے پر غیر محدود مسئلے کا حل ہے (یعنی۔ )۔ متغیر لگرینج ضرب کا تخمینہ ہے، اور اس تخمینے کی درستگی ہر قدم پر بہتر ہوتی ہے۔ طریقہ کار کا سب سے بڑا فائدہ یہ ہے کہ جرمانے کے طریقہ کار کے برعکس، اصل محدود مسئلے کو حل کرنے کے لیے یہ ضروری نہیں ہے۔ لگرینج ضرب کی اصطلاح کی موجودگی کی وجہ سے، بہت چھوٹا رہ سکتا ہے، اور اس طرح خراب حالت سے بچ سکتا ہے۔ اس کے باوجود، ایک بڑے باؤنڈڈ سیٹ (سیف گارڈز) میں پروجیکٹ ملٹی پلیئرز کے تخمینوں کے عملی نفاذ میں یہ عام ہے جو عددی عدم استحکام سے بچتا ہے اور مضبوط نظریاتی ہم آہنگی کی طرف لے جاتا ہے۔ طریقہ کار کو عدم مساوات کی رکاوٹوں سے نمٹنے کے لیے بڑھایا جا سکتا ہے۔ عملی بہتریوں پر بحث کے لیے، ریفس دیکھیں۔ ضرب کا متبادل سمت کا طریقہ ضرب کا متبادل سمت کا طریقہ (اے ڈی ایم ایم) آگمینٹڈ لاگرانجین اسکیم کا ایک متغیر ہے جو دوہری متغیرات کے لیے جزوی اپ ڈیٹس کا استعمال کرتا ہے۔ یہ طریقہ اکثر مسائل کو حل کرنے کے لیے استعمال کیا جاتا ہے جیسے، یہ محدود مسئلے کے مساوی ہے، اگرچہ یہ تبدیلی معمولی لگ سکتی ہے، لیکن اب اس مسئلے پر محدود اصلاح کے طریقوں (خاص طور پر، آگمینٹڈ لاگرانجین طریقہ) کا استعمال کرتے ہوئے حملہ کیا جا سکتا ہے، اور معروضی فنکشن x اور y میں الگ کیا جا سکتا ہے۔ دوہری اپ ڈیٹ کے لیے ایک ہی وقت میں x اور y میں قربت فنکشن کو حل کرنے کی ضرورت ہوتی ہے۔ ADMM تکنیک اس مسئلے کو تقریبا پہلے x کے لیے y فکسڈ کے ساتھ حل کرنے اور پھر x فکسڈ کے ساتھ y کے لیے حل کرنے کی اجازت دیتی ہے۔ کنورجنس (جیکوبی طریقہ کار کی طرح) تک دہرانے کے بجائے، الگورتھم براہ راست دوہری متغیر کو اپ ڈیٹ کرنے اور پھر عمل کو دہرانے کے لیے آگے بڑھتا ہے۔ یہ عین مطابق کم سے کم کرنے کے برابر نہیں ہے، لیکن طریقہ اب بھی کچھ مفروضوں کے تحت صحیح حل میں بدل جاتا ہے۔ اس تخمینہ کی وجہ سے، الگورتھم خالص آگمینٹڈ لاگرانجین طریقہ سے الگ ہے۔ اے ڈی ایم ایم کو ڈگلس-ریخفورڈ تقسیم کرنے والے الگورتھم کے اطلاق کے طور پر دیکھا جا سکتا ہے، اور ڈگلس-ریخفورڈ الگورتھم بدلے میں پراکسیمل پوائنٹ الگورتھم کی ایک مثال ہے۔ تفصیلات حوالہ میں مل سکتی ہیں۔ کئی جدید سافٹ ویئر پیکجز ہیں، جن میں YALL1 (2009)، SPARSA (2009) اور SALSA (2009) شامل ہیں، جو بنیادی تعاقب اور متغیرات کو حل کرتے ہیں اور ADMM کا استعمال کرتے ہیں۔ ایسے پیکیجز بھی ہیں جو زیادہ عام مسائل کو حل کرنے کے لیے اے ڈی ایم ایم کا استعمال کرتے ہیں، جن میں سے کچھ متعدد کمپیوٹنگ کور (جیسے، ایس این اے پی وی ایکس (2015)، پیرا اے ڈی ایم ایم (2016)) کا استحصال کر سکتے ہیں۔ اسٹوچسٹک آپٹیمائزیشن فنکشن کے شور کے نمونوں تک رسائی کے ساتھ نقصان کی تقریب کو کم سے کم کرنے کے مسئلے پر غور کرتی ہے۔ مقصد یہ ہے کہ فی نئے نمونے کے لیے بہترین پیرامیٹر (منی مائیزر) کا تخمینہ لگایا جائے۔ کچھ ترامیم کے ساتھ، اے ڈی ایم ایم کو اسٹاکسٹک آپٹیمائزیشن کے لیے استعمال کیا جا سکتا ہے۔ سٹوچسٹک ترتیب میں، میلان کے صرف شور والے نمونے قابل رسائی ہوتے ہیں، لہذا لاگرانجین کا ایک غیر درست تخمینہ استعمال کیا جاتا ہے: جہاں وقت کے لحاظ سے مختلف قدم کا سائز ہوتا ہے۔ اے ڈی ایم ایم کا اطلاق باقاعدہ مسائل کو حل کرنے کے لیے کیا گیا ہے، جہاں فنکشن کو بہتر بنانے اور باقاعدہ بنانے کو مقامی طور پر انجام دیا جا سکتا ہے اور پھر رکاوٹوں کے ذریعے عالمی سطح پر مربوط کیا جا سکتا ہے۔ ریگولیرائزڈ آپٹیمائزیشن کے مسائل اعلی جہتی نظام میں خاص طور پر متعلقہ ہیں کیونکہ ریگولیرائزیشن ایک قدرتی طریقہ کار ہے جو بد پوزیشن پر قابو پانے اور بہترین حل میں پارسمونی کی حوصلہ افزائی کرنے کے لیے ہے (مثال کے طور پر، اسپرسٹی اور لو رینک)۔ باقاعدہ مسائل کو حل کرنے کے لیے اے ڈی ایم ایم کی تاثیر کا مطلب یہ ہو سکتا ہے کہ یہ چھپے ہوئے جہتی سٹوچسٹک اصلاح کے مسائل کو حل کرنے کے لیے مفید ثابت ہو سکتا ہے۔ متبادل نقطہ نظر ترتیب وار کواڈریٹک پروگرامنگ ترتیب وار لکیری پروگرامنگ سافٹ ویئر اگمینٹڈ لاگرانجین طریقہ کار کا اوپن سورس اور غیر آزاد/تجارتی نفاذ: Accord.NET (اگمینٹڈ لاگرانجین آپٹیمائزر کا C #نفاذ) ALGLIB (C #اور C + + پری کنڈیشنڈ اگمینٹڈ لاگرانجین حل کرنے والے کا نفاذ) PENN (GPL 3، تجارتی لائسنس دستیاب) LANCELOT (مفت "اندرونی استعمال" لائسنس، ادا شدہ تجارتی اختیارات) MINOS (کچھ قسم کے مسائل کے لیے ایک اگمینٹڈ لاگرانجین طریقہ بھی استعمال کرتا ہے)۔ اپاچی 2 لائسنس یافتہ وجہ کا کوڈ آن لائن دستیاب ہے۔ ALGENCAN (حفاظتی اقدامات کے ساتھ آگمینٹڈ لاگرانجین طریقہ کار کا فورٹرن نفاذ)۔ آن لائن دستیاب ہے۔ این ایل او پی ٹی (اگمینٹڈ لاگرانجین آپٹیمائزر کا سی + + نفاذ، مختلف پروگرامنگ زبانوں سے قابل رسائی) پائ پراکسیمل (اگمینٹڈ لاگرانجین طریقہ کار کا ازگر نفاذ)۔ بیریر فنکشن انٹیر پوائنٹ طریقہ لگرینج ملٹی پلیئر پینلٹی طریقہ حوالہ جات ببلیوگرافی آپٹیمائزیشن الگورتھم اور طریقے بھی دیکھیں۔