Subgradient method
سب گریڈیئنٹ طریقے کنویکس کم سے کم کرنے کے مسائل کو حل کرنے کے لیے تکراری طریقے ہیں۔ اصل میں 1960 اور 1970 کی دہائیوں میں نوم زیڈ شور اور دیگر کے ذریعہ تیار کردہ، ذیلی میلان کے طریقے متغیر ہوتے ہیں جب ان کا اطلاق غیر متفرق معروضی فعل پر بھی کیا جاتا ہے۔ جب آبجیکٹیو فنکشن تفریق پذیر ہوتا ہے، تو غیر متزلزل مسائل کے لیے ذیلی میلان کے طریقے اسی تلاش کی سمت کا استعمال کرتے ہیں جو تیز ترین نزول کا طریقہ ہے۔ سب گریڈیئنٹ طریقے نیوٹن کے طریقہ کار سے سست ہوتے ہیں جب ان کا اطلاق دو بار مسلسل تفریق پذیر کنویکس افعال کو کم کرنے کے لیے کیا جاتا ہے۔ تاہم، نیوٹن کا طریقہ ان مسائل پر یکجا ہونے میں ناکام رہتا ہے جن میں غیر تفریق پذیر کنکس ہوتے ہیں۔ حالیہ برسوں میں، کنویکس کم سے کم کرنے کے مسائل کے لیے کچھ اندرونی نقطہ کے طریقے تجویز کیے گئے ہیں، لیکن سب گریڈیئنٹ پروجیکشن کے طریقے اور نزول کے متعلقہ بنڈل کے طریقے مسابقتی ہیں۔ طول و عرض کی بہت بڑی تعداد کے ساتھ کنویکس کم سے کم کرنے کے مسائل کے لیے، سب گریڈیئنٹ پروجیکشن کے طریقے موزوں ہیں، کیونکہ انہیں کم اسٹوریج کی ضرورت ہوتی ہے۔ سب گریڈیئنٹ پروجیکشن کے طریقوں کا اطلاق اکثر سڑنے کی تکنیکوں کے ساتھ بڑے پیمانے کے مسائل پر کیا جاتا ہے۔ اس طرح کے سڑنے کے طریقے اکثر کسی مسئلے کے لیے ایک سادہ تقسیم شدہ طریقہ کی اجازت دیتے ہیں۔ کلاسیکی ذیلی میلان کے اصول ڈومین کے ساتھ ایک کنویکس فنکشن ہونے دیں۔ ایک کلاسیکی سب گریڈیئنٹ طریقہ تکرار کرتا ہے جہاں at کے کسی بھی سب گریڈیئنٹ کی نشاندہی کرتا ہے، اور اس کا تکرار ہے۔ اگر تفریق قابل ہے، تو اس کا واحد ذیلی میلان خود میلان ویکٹر ہے۔ یہ ہو سکتا ہے کہ اٹ کے لیے نزول کی سمت نہ ہو۔ اس لیے ہم ایک ایسی فہرست برقرار رکھتے ہیں جو اب تک پائے جانے والے سب سے کم آبجیکٹیو فنکشن ویلیو کا سراغ رکھتی ہے، یعنی۔ مرحلہ سائز کے قواعد بہت سے مختلف قسم کے مرحلہ سائز کے قواعد ذیلی میلان کے طریقوں کے ذریعے استعمال کیے جاتے ہیں۔ اس مضمون میں پانچ کلاسیکی قدم کے سائز کے اصولوں کو نوٹ کیا گیا ہے جن کے لیے کنورجنس ثبوت معلوم ہیں: مستقل قدم کا سائز، مستقل قدم کی لمبائی، جو مربع خلاصہ دیتا ہے لیکن خلاصہ کے قابل قدم کا سائز نہیں، یعنی۔ کوئی بھی قدم سائز جو ناقابل تلافی کمی کو مطمئن کرتا ہے، یعنی۔ کوئی بھی قدم کا سائز جو ناقابل تلافی کم ہونے والے قدم کی لمبائی کو مطمئن کرتا ہے، یعنی۔ جہاں تمام پانچوں اصولوں کے لیے، مرحلہ کے سائز کا تعین "آف لائن" کیا جاتا ہے، طریقہ کار کو دہرانے سے پہلے ؛ مرحلہ کے سائز کا انحصار سابقہ تکرار پر نہیں ہوتا ہے۔ سب گریڈیئنٹ طریقوں کی یہ "آف لائن" خاصیت تفریق پذیر افعال کے لیے نزول کے طریقوں کے لیے استعمال ہونے والے "آن لائن" مرحلہ سائز کے اصولوں سے مختلف ہے: تفریق پذیر افعال کو کم سے کم کرنے کے بہت سے طریقے کنورجنس کے لیے وولف کی کافی شرائط کو پورا کرتے ہیں، جہاں مرحلہ سائز عام طور پر موجودہ نقطہ اور موجودہ تلاش کی سمت پر منحصر ہوتے ہیں۔ سب گریڈینٹ طریقوں کے لیے اسٹیپس سائز کے اصولوں پر ایک وسیع بحث، بشمول انکریمنٹل ورژن، برٹسیکاس اور برٹسیکاس، نیڈک اور اوزڈاگلر کی کتابوں میں دی گئی ہے۔ کنورجنس کے نتائج مستقل مرحلے کی لمبائی اور اسکیلڈ سب گریڈینٹس کے لیے جو ایک کے برابر یوکلیڈین معیار رکھتے ہیں، سب گریڈینٹ طریقہ کم سے کم قیمت کے من مانی طور پر قریب تخمینے میں بدل جاتا ہے، جو کہ شور کے نتیجے میں ہوتا ہے۔ یہ کلاسیکی ذیلی میلان کے طریقے ناقص کارکردگی کے حامل ہیں اور اب عام استعمال کے لیے تجویز نہیں کیے جاتے ہیں۔ تاہم، وہ اب بھی خصوصی ایپلی کیشنز میں بڑے پیمانے پر استعمال ہوتے ہیں کیونکہ وہ سادہ ہوتے ہیں اور انہیں آسانی سے مسئلے کے خصوصی ڈھانچے سے فائدہ اٹھانے کے لیے ڈھال لیا جا سکتا ہے۔ سب گریجینٹ پروجیکشن اور بنڈل کے طریقے 1970 کی دہائی کے دوران، کلاڈ لیماریچل اور فل وولف نے کنویکس کم سے کم کرنے کے مسائل کے لیے نزول کے "بنڈل طریقوں" کی تجویز پیش کی۔ اس وقت سے "بنڈل طریقوں" کی اصطلاح کے معنی نمایاں طور پر بدل گئے ہیں۔ جدید ورژن اور مکمل کنورجنس تجزیہ کیویئل نے فراہم کیے تھے۔ عصری بنڈل کے طریقے اکثر قدم کے سائز کے انتخاب کے لیے "لیول کنٹرول" کے قوانین کا استعمال کرتے ہیں، بورس ٹی پولیک (1969) کے "سب گریڈیئنٹ پروجیکشن" طریقہ سے تکنیک تیار کرتے ہیں۔ تاہم، ایسے مسائل ہیں جن پر بنڈل کے طریقے سب گریڈینٹ پروجیکشن کے طریقوں کے مقابلے میں بہت کم فائدہ پیش کرتے ہیں۔ محدود اصلاح پروجیکٹڈ سب گریڈیئنٹ سب گریڈیئنٹ طریقہ کار کی ایک توسیع پروجیکٹڈ سب گریڈیئنٹ طریقہ ہے، جو محدود اصلاح کے مسئلے کو حل کرتا ہے جس کے تابع ایک کنویکس سیٹ ہے۔ پروجیکٹڈ سب گریڈیئنٹ طریقہ تکرار کا استعمال کرتا ہے جہاں پروجیکشن آن ہوتا ہے اور عام رکاوٹوں پر اس کا کوئی بھی سب گریڈیئنٹ ہوتا ہے۔ سب گریڈیئنٹ طریقہ کو عدم مساوات کے محدود مسئلے کو حل کرنے کے لیے بڑھایا جا سکتا ہے جس کے تابع کنویکس ہوتے ہیں۔ الگورتھم وہی شکل اختیار کرتا ہے جو غیر متزلزل کیس کے طور پر ہوتا ہے جہاں ایک قدم کا سائز ہوتا ہے، اور یہ مقصد کا ذیلی میلان ہوتا ہے یا ٹیک میں رکاوٹ افعال میں سے ایک ہوتا ہے جہاں کے ذیلی تفریق کو ظاہر کرتا ہے۔ اگر موجودہ نقطہ قابل عمل ہے، تو الگورتھم ایک معروضی ذیلی میلان کا استعمال کرتا ہے۔ اگر موجودہ نقطہ ناقابل عمل ہے، تو الگورتھم کسی بھی خلاف ورزی شدہ رکاوٹ کے ذیلی میلان کا انتخاب کرتا ہے۔ حوالہ جات مزید پڑھنے کے لیے بیرونی روابط EE364A اور EE364B، سٹینفورڈ کا کنویکس آپٹیمائزیشن کورس سیکوینس۔ اصلاح کے الگورتھم اور طریقے کنویکس اصلاح