Convex optimization
کنویکس آپٹیمائزیشن ریاضیاتی اصلاح کا ایک ذیلی میدان ہے جو کنویکس سیٹوں پر کنویکس افعال کو کم سے کم کرنے کے مسئلے کا مطالعہ کرتا ہے (یا، مساوی طور پر، کنویکس سیٹوں پر کنکیو افعال کو زیادہ سے زیادہ کرنا)۔ کنویکس آپٹیمائزیشن کے مسائل کی بہت سی کلاسیں کثیر الجہتی وقت کے الگورتھم کو تسلیم کرتی ہیں، جبکہ ریاضیاتی اصلاح عام طور پر این پی ہارڈ ہوتی ہے۔ کنویکس آپٹیمائزیشن میں مختلف شعبوں میں ایپلی کیشنز ہیں، جیسے خودکار کنٹرول سسٹم، تخمینہ اور سگنل پروسیسنگ، مواصلات اور نیٹ ورک، الیکٹرانک سرکٹ ڈیزائن، ڈیٹا تجزیہ اور ماڈلنگ، فنانس، شماریات (زیادہ سے زیادہ تجرباتی ڈیزائن)، اور ساختی اصلاح، جہاں تخمینہ کا تصور موثر ثابت ہوا ہے۔ کمپیوٹنگ اور اصلاح کے الگورتھم میں حالیہ پیشرفتوں کے ساتھ، کنویکس پروگرامنگ تقریبا اتنی ہی سیدھی ہے جتنی کہ لکیری پروگرامنگ۔ تعریف کنویکس آپٹیمائزیشن کا مسئلہ ایک اصلاح کا مسئلہ ہے جس میں آبجیکٹیو فنکشن ایک کنویکس فنکشن ہے اور قابل عمل سیٹ ایک کنویکس سیٹ ہے۔ انٹو کے کچھ ذیلی سیٹ کی نقشہ سازی کرنے والا فنکشن کنویکس ہوتا ہے اگر اس کا ڈومین کنویکس ہے اور اس کے ڈومین میں موجود تمام لوگوں کے لیے درج ذیل شرط ہوتی ہے: ایک سیٹ S کنویکس ہے اگر تمام اراکین اور سب کے لیے، ہمارے پاس یہ ہے۔ خاص طور پر، کنویکس آپٹیمائزیشن کا مسئلہ کچھ حصول تلاش کرنے کا مسئلہ ہے، جہاں آبجیکٹیو فنکشن کنویکس ہے، جیسا کہ ممکن سیٹ ہے۔ اگر ایسا نقطہ موجود ہے، تو اسے ایک بہترین نقطہ یا حل کہا جاتا ہے ؛ تمام بہترین نکات کے سیٹ کو بہترین سیٹ کہا جاتا ہے۔ اگر نیچے غیر محدود ہے یا لامحدود حاصل نہیں کیا جاتا ہے، تو اصلاح کا مسئلہ غیر محدود کہا جاتا ہے۔ بصورت دیگر، اگر خالی سیٹ ہے، تو مسئلہ کو ناقابل عمل کہا جاتا ہے۔ ایک کنویکس آپٹیمائزیشن کا مسئلہ معیاری شکل میں ہوتا ہے اگر اسے اس طرح لکھا جائے کہ: اصلاح متغیر ہے ؛ معروضی فنکشن ایک کنویکس فنکشن ہے ؛ عدم مساوات کی رکاوٹ کے افعال، کنویکس فنکشن ہیں ؛ مساوات کی رکاوٹ کے افعال، افائن ٹرانسفارمیشن ہیں، یعنی شکل کے:، جہاں ایک ویکٹر ہے اور ایک اسکیلر ہے۔ یہ اشارے تلاش کرنے کے مسئلے کو بیان کرتا ہے جو تمام اطمینان بخش میں کم سے کم ہوتا ہے، اور،۔ فنکشن مسئلہ کا معروضی فنکشن ہے، اور افعال اور رکاوٹ افعال ہیں۔ اصلاح کے مسئلے کا قابل عمل سیٹ ان تمام نکات پر مشتمل ہوتا ہے جو رکاوٹوں کو پورا کرتے ہیں۔ یہ سیٹ کنویکس ہے کیونکہ کنویکس ہے، کنویکس افعال کے ذیلی سطح کے سیٹ کنویکس ہیں، افائن سیٹ کنویکس ہیں، اور کنویکس سیٹوں کا چوراہا کنویکس ہے۔ کنویکس آپٹیمائزیشن کے مسئلے کا حل کسی بھی نقطہ کو حاصل کرنا ہے۔ عام طور پر، کنویکس آپٹیمائزیشن کے مسئلے میں صفر، ایک یا بہت سے حل ہو سکتے ہیں۔ اصلاح کے بہت سے مسائل کو اس معیاری شکل میں مساوی طور پر وضع کیا جا سکتا ہے۔ مثال کے طور پر، کنکیو فنکشن کو زیادہ سے زیادہ کرنے کے مسئلے کو کنویکس فنکشن کو کم سے کم کرنے کے مسئلے کے مساوی طور پر دوبارہ تشکیل دیا جا سکتا ہے۔ کنویکس سیٹ پر کنکیو فنکشن کو زیادہ سے زیادہ کرنے کے مسئلے کو عام طور پر کنویکس آپٹیمائزیشن کا مسئلہ کہا جاتا ہے۔ خصوصیات کنویکس آپٹیمائزیشن کے مسائل کی مفید خصوصیات درج ذیل ہیں: ہر مقامی کم از کم عالمی کم از کم ہے ؛ زیادہ سے زیادہ سیٹ کنویکس ہے ؛ اگر آبجیکٹیو فنکشن سختی سے کنویکس ہے، تو مسئلہ میں زیادہ سے زیادہ ایک زیادہ سے زیادہ نقطہ ہوتا ہے۔ ان نتائج کو فنکشنل تجزیہ (ہلبرٹ خالی جگہوں میں) جیسے ہلبرٹ پروجیکشن تھیوریم، علیحدگی ہائپرپلین تھیوریم، اور فرکاس لیما سے ہندسی تصورات کے ساتھ کنویکس منیمائزیشن کے نظریہ کے ذریعے استعمال کیا جاتا ہے۔ ایپلی کیشنز مندرجہ ذیل دشواری کی کلاسیں تمام کنویکس آپٹیمائزیشن کے مسائل ہیں، یا سادہ تبدیلیوں کے ذریعے کنویکس آپٹیمائزیشن کے مسائل تک کم کی جا سکتی ہیں: کم سے کم مربع لکیری پروگرامنگ کنویکس کواڈریٹک منیمائزیشن لکیری رکاوٹوں کے ساتھ کنویکس کواڈریٹک رکاوٹوں کے ساتھ کواڈریٹک منیمائزیشن کونک آپٹیمائزیشن جیومیٹرک پروگرامنگ سیکنڈ آرڈر کون پروگرامنگ سیمیڈفائنٹ پروگرامنگ اینٹروپی میکسمائزیشن مناسب رکاوٹوں کے ساتھ کنویکس آپٹیمائزیشن میں درج ذیل کے لیے عملی ایپلی کیشنز ہیں۔ پورٹ فولیو کی اصلاح۔ بدترین صورت میں خطرے کا تجزیہ۔ بہترین تشہیر۔ شماریاتی رجعت کی تغیرات (بشمول باقاعدگی اور مقداری رجعت)۔ ماڈل فٹنگ (خاص طور پر ملٹی کلاس درجہ بندی)۔ بجلی کی پیداوار کو بہتر بنانا۔ مشترکہ اصلاح۔ غیر یقینی صورتحال کا غیر ممکنہ ماڈلنگ۔ وائرلیس سگنلز کا استعمال کرتے ہوئے لوکلائزیشن لگرینج ملٹی پلیئرز لاگت فنکشن اور عدم مساوات کی رکاوٹوں کے ذریعہ معیاری شکل میں دیئے گئے کنویکس منیمائزیشن کے مسئلے پر غور کریں۔ پھر ڈومین یہ ہے: مسئلہ کے لیے لاگرانجین فنکشن یہ ہے کہ اس میں ہر نقطہ کے لیے جو کم سے کم ہوتا ہے، وہاں حقیقی اعداد موجود ہوتے ہیں جنہیں لاگرانج ملٹی پلیئرز کہا جاتا ہے، جو بیک وقت ان شرائط کو پورا کرتے ہیں: کم سے کم ایک (تکمیلی سستی) کے ساتھ کم سے کم ہوتا ہے۔ اگر کوئی "سختی سے قابل عمل نقطہ" موجود ہے، یعنی ایک نقطہ تسلی بخش ہے تو اوپر دیے گئے بیان کو اس کی ضرورت کے لیے مضبوط کیا جا سکتا ہے۔ اس کے برعکس، اگر کچھ اسکیلرز کے لیے (1)-(3) کو مطمئن کرتے ہیں تو یقینی طور پر کم کرنا یقینی ہے۔ الگورتھم ان کنسٹرینڈ کنویکس آپٹیمائزیشن کو آسانی سے گریڈینٹ ڈیسنٹ (اسٹپیسٹ ڈیسنٹ کا ایک خاص معاملہ) یا نیوٹن کے طریقہ کار کے ساتھ حل کیا جا سکتا ہے، جو ایک مناسب قدم کے سائز کے لیے لائن سرچ کے ساتھ مل کر ہے۔ یہ ریاضیاتی طور پر تیزی سے یکجا ہونے کے لیے ثابت کیے جا سکتے ہیں، خاص طور پر مؤخر الذکر طریقہ۔ لکیری مساوات کی رکاوٹوں کے ساتھ کنویکس آپٹیمائزیشن کو کے کے ٹی میٹرکس تکنیک کا استعمال کرتے ہوئے بھی حل کیا جا سکتا ہے اگر آبجیکٹیو فنکشن ایک کواڈریٹک فنکشن ہے (جو نیوٹن کے طریقہ کار کی تغیر کو عام بناتا ہے، جو اس صورت میں بھی کام کرتا ہے جب ابتدائی نقطہ رکاوٹوں کو پورا نہیں کرتا ہے)، لیکن عام طور پر لکیری الجبرا کے ساتھ مساوات کی رکاوٹوں کو ختم کرکے یا دوہری مسئلے کو حل کرکے بھی حل کیا جا سکتا ہے۔ آخر میں، لکیری مساوات کی رکاوٹوں اور کنویکس عدم مساوات کی رکاوٹوں دونوں کے ساتھ کنویکس آپٹیمائزیشن کو معروضی فنکشن کے ساتھ ساتھ لوگرتھمک رکاوٹ کی شرائط پر غیر محدود کنویکس آپٹیمائزیشن تکنیک کا اطلاق کرکے حل کیا جا سکتا ہے۔ (جب ابتدائی نقطہ قابل عمل نہیں ہے-یعنی رکاوٹوں کو پورا کرنا-اس سے پہلے نام نہاد فیز I کے طریقے ہوتے ہیں، جو یا تو ایک قابل عمل نقطہ تلاش کرتے ہیں یا یہ ظاہر کرتے ہیں کہ کوئی موجود نہیں ہے۔ فیز I کے طریقے عام طور پر زیر بحث تلاش کو ایک اور کنویکس آپٹیمائزیشن مسئلے تک کم کرنے پر مشتمل ہوتے ہیں۔) کنویکس آپٹیمائزیشن کے مسائل کو مندرجہ ذیل عصری طریقوں سے بھی حل کیا جا سکتا ہے: بنڈل کے طریقے (وولف، لیماریچل، کیویئل)، اور سب گریڈینٹ پروجیکشن کے طریقے (پولیک)، اندرونی نقطہ کے طریقے، جو خود ہم آہنگ رکاوٹ افعال اور خود باقاعدہ رکاوٹ افعال کا استعمال کرتے ہیں۔ کٹنگ پلین کے طریقے ایلیپسائڈ طریقہ سب گریڈینٹ طریقہ دوہری سب گریڈینٹس اور ڈرفٹ پلس پینلٹی طریقہ سب گریڈینٹ طریقوں کو آسانی سے لاگو کیا جا سکتا ہے اور اس لیے بڑے پیمانے پر استعمال ہوتے ہیں۔ دوہری ذیلی گریڈیئنٹ طریقے ذیلی گریڈیئنٹ طریقے ہیں جو دوہری مسئلے پر لاگو ہوتے ہیں۔ ڈرفٹ پلس پینلٹی کا طریقہ دوہری سب گریڈیئنٹ طریقہ سے ملتا جلتا ہے، لیکن ابتدائی متغیرات کا اوسط وقت لیتا ہے۔ سافٹ ویئر کنویکس آپٹیمائزیشن کے لیے ایک بڑا سافٹ ویئر ماحولیاتی نظام ہے۔ اس ماحولیاتی نظام کی دو اہم قسمیں ہیں: ایک طرف حل کرنے والے اور دوسری طرف ماڈلنگ ٹولز (یا انٹرفیس)۔ حل کرنے والے الگورتھم کو خود نافذ کرتے ہیں اور عام طور پر سی میں لکھے جاتے ہیں۔ ان کے لیے صارفین کو بہت ہی مخصوص فارمیٹس میں اصلاح کے مسائل کی وضاحت کرنے کی ضرورت ہوتی ہے جو ماڈلنگ کے نقطہ نظر سے فطری نہیں ہو سکتے۔ ماڈلنگ ٹولز سافٹ ویئر کے الگ الگ ٹکڑے ہوتے ہیں جو صارف کو اعلی سطح کے نحو میں اصلاح کی وضاحت کرنے دیتے ہیں۔ وہ صارف کے اعلی سطحی ماڈل اور حل کنندہ کے ان پٹ/آؤٹ پٹ فارمیٹ میں تمام تبدیلیوں کا انتظام کرتے ہیں۔ نیچے دیا گیا جدول ماڈلنگ ٹولز (جیسے CVXPY اور Convex.jl) اور حل کرنے والوں (جیسے CVXOPT اور MOSEK) کا مرکب دکھاتا ہے۔ یہ میز کسی بھی طرح سے مکمل نہیں ہے۔ کنویکس آپٹیمائزیشن کی توسیعات میں بائیکونویکس، سیوڈو-کنویکس، اور کواسیکونویکس افعال کی اصلاح شامل ہے۔ کنویکس تجزیہ کے نظریہ کی توسیع اور غیر کنویکس کم سے کم مسائل کو تقریبا حل کرنے کے لیے تکراری طریقے عمومی کنویکسٹی کے میدان میں پائے جاتے ہیں، جسے تجریدی کنویکس تجزیہ بھی کہا جاتا ہے۔ ڈوئلٹی کروش-کوہن-ٹکر کنڈیشنز آپٹیمائزیشن کا مسئلہ پراکسیمل گریڈینٹ طریقہ نوٹ حوالہ جات ہیریارٹ-اروٹی، جین بپٹسٹ، اور لیماریچل، کلاڈ بھی دیکھیں۔ (2004)۔ کنویکس تجزیہ کی بنیادی باتیں۔ برلن: سپرنگر۔ نیسٹروف، یوری۔ (2004)۔ کنویکس آپٹیمائزیشن پر تعارفی لیکچرز، کلوور اکیڈمک پبلشرز شمٹ، ایل اے۔ فلوری، سی۔ 1980: تخمینہ تصورات اور دوہری طریقوں کو ملا کر ساختی ترکیب۔ جے آمیر۔ انسٹا۔ ایروناٹ۔ خلاباز 18، 1252-1260 بیرونی روابط EE364a: کنویکس آپٹیمائزیشن I اور EE364b: کنویکس آپٹیمائزیشن II، اسٹینفورڈ کورس کے ہوم پیجز 6.253: کنویکس تجزیہ اور آپٹیمائزیشن، ایک ایم آئی ٹی او سی ڈبلیو کورس کا ہوم پیج برائن بورچرز، کنویکس آپٹیمائزیشن کے لیے سافٹ ویئر کا ایک جائزہ۔