Sum-of-squares optimization
ایک سم آف اسکوائرز آپٹیمائزیشن پروگرام لکیری لاگت فنکشن اور فیصلہ متغیرات پر ایک خاص قسم کی رکاوٹ کے ساتھ ایک اصلاح کا مسئلہ ہے۔ یہ رکاوٹیں اس شکل کی ہوتی ہیں کہ جب فیصلہ متغیرات کو بعض کثیر الجہتی میں گتانک کے طور پر استعمال کیا جاتا ہے، تو ان کثیر الجہتی میں کثیر الجہتی ایس او ایس پراپرٹی ہونی چاہیے۔ اس میں شامل کثیر الجہتی کی زیادہ سے زیادہ ڈگری کو طے کرتے وقت، جم-آف-اسکوائرز آپٹیمائزیشن کو سیمیڈفائنٹ پروگرامنگ میں نرمی کے لاسر ہیرارکی کے نام سے بھی جانا جاتا ہے۔ سم آف اسکوائرز آپٹیمائزیشن تکنیک کا اطلاق مختلف شعبوں میں کیا گیا ہے، بشمول کنٹرول تھیوری (خاص طور پر، کثیر الجہتی ویکٹر فیلڈز کے ذریعہ بیان کردہ متحرک نظاموں کے لیے کثیر الجہتی لیاپونوف افعال کی تلاش کے لیے)، شماریات، مالیات اور مشین لرننگ۔ "مربع پروگرامنگ کے مجموعے کا استعمال کرتے ہوئے کنٹرول لیاپونوف افعال کی تلاش"۔ میں: ایلرٹن کانف۔ کمیونیکیشن، کنٹرول اور کمپیوٹنگ پر۔ پی پی۔ 210-219۔ چکرورتی، پی سیلر، اور جی بالاس، "فالنگ لیف موڈ میں ایف/اے-18 فلائٹ کنٹرولرز کی حساسیت: غیر لکیری تجزیہ"، اے آئی اے اے جرنل آف گائیڈنس، کنٹرول، اور ڈائنامکس، جلد۔ 34 نمبر۔ 1 (2011)، پی پی۔ 73-85۔ اصلاح کا مسئلہ، کے لیے ایک ویکٹر اور کثیر الجہتی کو دیکھتے ہوئے، ایک مجموعہ مربع اصلاح کا مسئلہ اس طرح لکھا جاتا ہے کہ یہاں "ایس او ایس" مجموعہ مربع (ایس او ایس) کثیر الجہتی کی کلاس کی نمائندگی کرتا ہے۔ مقداریں فیصلہ متغیر ہیں۔ ایس او ایس پروگراموں کو ایس او ایس کثیر الجہتی پروگرام کی دوہری حیثیت کا استعمال کرتے ہوئے سیمیڈفائنٹ پروگراموں (ایس ڈی پیز) میں تبدیل کیا جاسکتا ہے اور مثبت-سیمیڈفائنٹ میٹرکس کا استعمال کرتے ہوئے محدود کثیر الجہتی اصلاح کے لیے نرمی، درج ذیل سیکشن دیکھیں۔ دوہری مسئلہ: محدود کثیر الجہتی اصلاح فرض کریں کہ ہمارے پاس ایک-متغیر کثیر الجہتی ہے، اور فرض کریں کہ ہم اس کثیر الجہتی کو ذیلی سیٹ پر کم کرنا چاہیں گے۔ مزید فرض کریں کہ سب سیٹ پر موجود رکاوٹوں کو زیادہ سے زیادہ ڈگری کی کثیر مساوات کا استعمال کرتے ہوئے انکوڈ کیا جا سکتا ہے، ہر ایک شکل جہاں زیادہ سے زیادہ ڈگری کا کثیر الجہتی ہے۔ اس اصلاح کے مسئلے کے لیے ایک قدرتی، اگرچہ عام طور پر غیر کنویکس پروگرام درج ذیل ہے: اس کے تابع: جہاں-جہتی ویکٹر زیادہ سے زیادہ ڈگری کے ہر مونومیل کے لیے ایک اندراج کے ساتھ ہے، تاکہ ہر ملٹی سیٹ کے لیے، کثیر الجہتی کے کوفشنٹس کا ایک میٹرکس ہو جسے ہم کم کرنا چاہتے ہیں، اور ذیلی سیٹ پر-th رکاوٹ کو انکوڈنگ کرنے والے کثیر الجہتی کے کوفشنٹس کا ایک میٹرکس ہے۔ ہمارے سرچ اسپیس میں اضافی، فکسڈ مستقل انڈیکس، کثیر الجہتی لکھنے کی سہولت اور میٹرکس کی نمائندگی میں شامل کیا جاتا ہے۔ یہ پروگرام عام طور پر غیر کنویکس ہے، کیونکہ رکاوٹیں () کنویکس نہیں ہیں۔ اس کم سے کم کرنے کے مسئلے کے لیے ایک ممکنہ کنویکس نرمی متغیرات کے رینک ون میٹرکس کو مثبت-سیمیڈفائنٹ میٹرکس سے تبدیل کرنے کے لیے سیمیڈفائنٹ پروگرامنگ کا استعمال کرتی ہے: ہم زیادہ سے زیادہ انڈیکس کے ملٹی سیٹ کے ذریعے سائز کے ہر مونومیل کو انڈیکس کرتے ہیں۔ اس طرح کے ہر مونومیل کے لیے، ہم پروگرام میں ایک متغیر بناتے ہیں، اور ہم متغیرات کو میٹرکس بنانے کے لیے ترتیب دیتے ہیں، جہاں حقیقی میٹرکس کا مجموعہ ہوتا ہے جس کی قطاریں اور کالم زیادہ سے زیادہ سائز کے عناصر کے ملٹی سیٹوں سے پہچانے جاتے ہیں۔ اس کے بعد ہم متغیرات میں درج ذیل سیمیڈفائنٹ پروگرام لکھتے ہیں: اس کے تابع: جہاں دوبارہ کثیر الجہتی کے کوفشنٹس کا میٹرکس ہے جسے ہم کم کرنا چاہتے ہیں، اور ذیلی سیٹ پر-th رکاوٹ کو کوڈ کرنے والے کثیر الجہتی کے کوفشنٹس کا میٹرکس ہے۔ تیسری رکاوٹ اس بات کو یقینی بناتی ہے کہ ایک مونومیل کی قیمت جو میٹرکس کے اندر کئی بار ظاہر ہوتی ہے وہ پورے میٹرکس میں برابر ہوتی ہے، اور کواڈریٹک شکل میں موجود ہم آہنگی کا احترام کرنے کے لیے شامل کی جاتی ہے۔ ڈوئلٹی کوئی بھی مندرجہ بالا سیمیڈفائنٹ پروگرام کا ڈوئل لے سکتا ہے اور مندرجہ ذیل پروگرام حاصل کر سکتا ہے: اس کے تابع: ہمارے پاس رکاوٹ کے مطابق ایک متغیر ہے (جہاں میٹرکس تمام اندراجات کے ساتھ صفر کے ساتھ انڈیکس شدہ اندراج کے لیے محفوظ ہے)، ہر کثیر الجہتی رکاوٹ کے لیے ایک حقیقی متغیر اور ملٹی سیٹوں کے ہر گروپ کے لیے، ہمارے پاس ہم آہنگی کی رکاوٹ کے لیے ڈوئل متغیر ہے۔ مثبت-مساوی حد بندی کی رکاوٹ اس بات کو یقینی بناتی ہے کہ یہ کثیر الجہتی کا مجموعہ ہے: مثبت-سمائڈفائنٹ میٹرکس کی خصوصیت سے، کسی بھی مثبت-سمائڈفائنٹ میٹرکس کے لیے، ہم ویکٹرز کے لیے لکھ سکتے ہیں۔ اس طرح کسی بھی کے لیے، جہاں ہم نے ویکٹروں کی شناخت زیادہ سے زیادہ ڈگری کے کثیر الجہتی کے گتانک کے ساتھ کی ہے۔ یہ مربعوں کا مجموعہ اس بات کا ثبوت دیتا ہے کہ قیمت ختم ہو گئی ہے۔ مذکورہ بالا کو کثیر الجہتی عدم مساوات سے متعین علاقوں تک بھی بڑھایا جا سکتا ہے۔ مربع درجہ بندی کا مجموعہ مربع درجہ بندی (ایس او ایس درجہ بندی)، جسے لاسر درجہ بندی بھی کہا جاتا ہے، بڑھتی ہوئی طاقت اور بڑھتی ہوئی کمپیوٹیشنل لاگت کی کنویکس نرمی کا درجہ بندی ہے۔ ہر قدرتی عدد کے لیے متعلقہ کنویکس نرمی کو ایس او ایس درجہ بندی کی ویں سطح یا-ویں راؤنڈ کے نام سے جانا جاتا ہے۔ ایس ٹی راؤنڈ، جب، ایک بنیادی سیمیڈفائنٹ پروگرام سے مطابقت رکھتا ہے، یا زیادہ سے زیادہ ڈگری کے کثیر الجہتی پر مجموعہ کے مربع کی اصلاح سے مطابقت رکھتا ہے۔ درجہ بندی کی پہلی سطح پر بنیادی کنویکس پروگرام کو-th سطح تک بڑھانے کے لیے، پروگرام میں اضافی متغیرات اور رکاوٹیں شامل کی جاتی ہیں تاکہ پروگرام زیادہ سے زیادہ ڈگری کے کثیر الجہتی پر غور کرے۔ ایس او ایس درجہ بندی کا نام اس حقیقت سے اخذ کیا گیا ہے کہ-th سطح پر آبجیکٹیو فنکشن کی قدر ڈوئل کے ذریعے زیادہ سے زیادہ ڈگری کے کثیر الجہتی کا استعمال کرتے ہوئے مربع ثبوت کے مجموعے سے منسلک ہوتی ہے (اوپر "دوہری" دیکھیں)۔ نتیجتا، کسی بھی مربع کے مجموعے کا ثبوت جو زیادہ سے زیادہ ڈگری کے کثیر الجہتی کا استعمال کرتا ہے اسے معروضی قدر کو پابند کرنے کے لیے استعمال کیا جا سکتا ہے، جس سے کسی کو نرمی کی جکڑن پر ضمانت ثابت کرنے کی اجازت ملتی ہے۔ برگ کے نظریہ کے ساتھ مل کر، اس کا مزید مطلب یہ ہے کہ کافی زیادہ راؤنڈز دیے جانے پر، کسی بھی مقررہ وقفے پر نرمی من مانی طور پر سخت ہو جاتی ہے۔ برگ کے نتیجے میں کہا گیا ہے کہ ایک پابند وقفے کے اندر ہر غیر منفی حقیقی کثیر الجہتی کو اس وقفے پر درستگی کے اندر کافی زیادہ ڈگری کے حقیقی کثیر الجہتی کے مجموعے کے ساتھ تخمینہ لگایا جا سکتا ہے، اور اس طرح اگر کثیر الجہتی معروضی قدر نقطہ کی تقریب کے طور پر ہے، اگر عدم مساوات دلچسپی کے علاقے میں سب کے لیے ہے، تو اس حقیقت کا مجموعہ مربع ثبوت ہونا ضروری ہے۔ قابل عمل خطے پر کم از کم معروضی فنکشن کا انتخاب کرتے ہوئے، ہمارے پاس نتیجہ ہے۔ کمپیوٹیشنل لاگت متغیرات میں کسی فنکشن کو بہتر بناتے وقت، درجہ بندی کی-th سطح کو متغیرات پر سیمیڈفائنٹ پروگرام کے طور پر لکھا جا سکتا ہے، اور ایلیپسائڈ طریقہ استعمال کرتے ہوئے وقت پر حل کیا جا سکتا ہے۔ ایک کثیر الجہتی مربعوں کا مجموعہ (ایس او ایس) ہے اگر اس طرح کے کثیر الجہتی موجود ہیں۔ مثال کے طور پر، مربعوں کا مجموعہ ہے جہاں سے نوٹ کریں کہ اگر مربعوں کا مجموعہ ہے تو سب کے لیے۔ کثیر الجہتی ایس او ایس کی تفصیلی وضاحتیں ہیں available.Parrilo، پی۔ (2003) "سیمی الجبری مسائل کے لیے سیمیڈفائنٹ پروگرامنگ میں نرمی"۔ ریاضیاتی پروگرامنگ سر۔ B 96 (2)، 293-320۔ کواڈریٹک شکلوں کا اظہار اس طرح کیا جا سکتا ہے جہاں ایک سمیٹرک میٹرکس ہے۔ اسی طرح، ڈگری ≤ 2d "کے کثیر الجہتی کو اس طرح ظاہر کیا جا سکتا ہے جہاں ویکٹر ڈگری کے تمام یک الجہتی پر مشتمل ہوتا ہے۔ اسے گرام میٹرکس فارم کہا جاتا ہے۔ ایک اہم حقیقت یہ ہے کہ ایس او ایس صرف اس صورت میں ہے جب اس طرح کا ہم آہنگی اور مثبت-سیمیڈفائنٹ میٹرکس موجود ہو۔ یہ ایس او ایس کثیر الجہتی اور مثبت-سیمیڈفائنٹ میٹرکس کے درمیان تعلق فراہم کرتا ہے۔ سافٹ ویئر ٹولز ایس او ایس ٹولز، جو جی این یو جی پی ایل کے تحت لائسنس یافتہ ہیں۔ حوالہ گائیڈ arXiv: 1310.4716 [math.OC] پر دستیاب ہے، اور اس کے اندرونی حصوں کے بارے میں ایک پریزنٹیشن یہاں دستیاب ہے۔ سی ڈی سی ایس-ایس او ایس، سی ڈی سی ایس کا ایک پیکیج، جو بڑے پیمانے پر ایس او ایس پروگراموں سے نمٹنے کے لیے ایک بڑھا ہوا لگرینجین طریقہ حل کرنے والا ہے۔ جولیا کے لیے جے یو ایم پی کی سم آف اسکوائرز توسیع۔ جولیا کے لیے ٹی ایس ایس او ایس، ایک کثیر الجہتی اصلاح کا ٹول ہے جو سپیرسٹی پر مبنی مومنٹ-ایس او ایس کی درجہ بندی پر مبنی ہے۔ محدود کثیر الجہتی اصلاح کے دوہرے مسئلے کے لیے، GloptiPoly کے لیے MATLAB/आक्ٹو، این سی پول 2 ایس ڈی پی اے کے لیے ازگر اور مومنٹ آپٹ کے لیے جولیا۔ حوالہ جات ریاضیاتی اصلاح حقیقی الجبرائی جیومیٹری