Frank–Wolfe algorithm
فرینک-وولف الگورتھم محدود کنویکس آپٹیمائزیشن کے لیے ایک تکراری فرسٹ آرڈر آپٹیمائزیشن الگورتھم ہے۔ مشروط میلان طریقہ، کم میلان الگورتھم اور کنویکس امتزاج الگورتھم کے نام سے بھی جانا جاتا ہے، یہ طریقہ اصل میں مارگوریٹ فرینک اور فلپ وولف نے 1956 میں تجویز کیا تھا۔ ہر تکرار میں، فرینک-وولف الگورتھم معروضی فنکشن کے لکیری تخمینے پر غور کرتا ہے، اور اس لکیری فنکشن (اسی ڈومین پر لیا گیا) کے کم سے کم کرنے والے کی طرف بڑھتا ہے۔ دشواری کا بیان فرض کریں کہ ویکٹر اسپیس میں ایک کمپیکٹ کنویکس سیٹ ہے اور یہ ایک کنویکس، تفریق پذیر حقیقی قدر والا فنکشن ہے۔ فرینک-وولف الگورتھم کم سے کم کے تابع اصلاح کے مسئلے کو حل کرتا ہے۔ الگورتھم انیشیئلائزیشن: چلو، اور کسی بھی نقطہ کو اندر آنے دو۔ مرحلہ 1۔ سمت تلاش کرنے کا ذیلی مسئلہ: کم سے کم موضوع کو حل کرنے کے لیے تلاش کریں (تشریح: پہلے درجے کے ٹیلر کے اندازے کے ذریعے دیے گئے مسئلے کے لکیری تخمینے کو کم سے کم کریں جو اس کے اندر رہنے کے لیے مجبور ہے۔) مرحلہ 2۔ قدم کے سائز کا تعین: سیٹ کریں، یا متبادل طور پر کم سے کم تلاش کریں۔ مرحلہ 3. اپ ڈیٹ کریں: چلو، چلو اور مرحلہ 1 پر جائیں۔ اگرچہ مسابقتی طریقوں جیسے کہ محدود اصلاح کے لیے گریڈیئنٹ ڈیسنٹ کے لیے ہر تکرار میں قابل عمل سیٹ پر ایک پروجیکشن قدم کی ضرورت ہوتی ہے، فرینک-وولف الگورتھم کو صرف ہر تکرار میں ایک ہی سیٹ پر لکیری مسئلے کے حل کی ضرورت ہوتی ہے، اور خود بخود قابل عمل سیٹ میں رہتا ہے۔ فرینک-وولف الگورتھم کا کنورجنس عام طور پر ذیلی لکیری ہوتا ہے: معروضی فنکشن میں زیادہ سے زیادہ غلطی k تکرار کے بعد ہوتی ہے، جب تک کہ میلان کسی معیار کے حوالے سے لپشیٹز مسلسل ہو۔ اسی ہم آہنگی کی شرح کو اس صورت میں بھی دکھایا جا سکتا ہے جب ذیلی مسائل کو صرف تقریبا حل کیا جائے۔ الگورتھم کے تکرار کو ہمیشہ قابل عمل سیٹ کے انتہائی نکات کے ایک غیر معمولی کنویکس امتزاج کے طور پر پیش کیا جا سکتا ہے، جس نے مشین لرننگ اور سگنل پروسیسنگ کے مسائل میں غیر معمولی لالچی اصلاح کے لیے الگورتھم کی مقبولیت میں مدد کی ہے، نیز مثال کے طور پر نقل و حمل کے نیٹ ورک میں کم سے کم لاگت کے بہاؤ کی اصلاح۔ اگر قابل عمل سیٹ لکیری رکاوٹوں کے ایک سیٹ کے ذریعے دیا جاتا ہے، تو ہر تکرار میں حل کیا جانے والا ذیلی مسئلہ لکیری پروگرام بن جاتا ہے۔ اگرچہ سب سے خراب صورت میں کنورجنس کی شرح کو عام طور پر بہتر نہیں کیا جا سکتا ہے، لیکن خاص مسئلہ کلاسوں کے لیے تیز کنورجنس حاصل کی جا سکتی ہے، جیسے کہ کچھ مضبوط کنویکس مسائل۔ حل کی قیمت پر نچلی حدود، اور ابتدائی دوہری تجزیہ چونکہ کنویکس ہے، ہمارے پاس موجود کسی بھی دو نکات کے لیے: یہ (نامعلوم) بہترین حل کے لیے بھی ہے۔ یعنی۔ مؤخر الذکر اصلاح کا مسئلہ فرینک-وولف الگورتھم کے ہر تکرار میں حل کیا جاتا ہے، لہذا-th تکرار کے سمت تلاش کرنے والے ذیلی مسئلے کا حل ترتیب کے ذریعے ہر تکرار کے دوران بڑھتی ہوئی نچلی حدود کا تعین کرنے کے لیے استعمال کیا جا سکتا ہے اور نامعلوم زیادہ سے زیادہ قدر پر اس طرح کی کم حدود عملی طور پر اہم ہیں کیونکہ انہیں روکنے کے معیار کے طور پر استعمال کیا جا سکتا ہے، اور ہمیشہ سے ہر تکرار میں تخمینہ کے معیار کا ایک موثر سرٹیفکیٹ دیتا ہے۔ یہ دکھایا گیا ہے کہ یہ متعلقہ دوہری فرق، یعنی اور نچلی حد کے درمیان فرق، اسی کنورجنس ریٹ کے ساتھ کم ہوتا ہے، یعنی۔ نوٹز ببلیوگرافی (جائزہ کاغذ) فرینک-وولف الگورتھم کی تفصیل۔ بیرونی روابط https://conditional-gradients.org: فرینک وولف الگورتھم کا ایک سروے۔ مارگوریٹ فرینک الگورتھم کی تاریخ کا ذاتی بیان دیتے ہوئے یہ بھی دیکھیں کہ پراکسیمل گریڈینٹ کے طریقے آپٹیمائزیشن الگورتھم اور طریقے تکراری طریقے فرسٹ آرڈر کے طریقے گریڈینٹ کے طریقے