خلاصه :
در این مقاله الگوریتم بهینه سازی براساس برنامه ریزی خطی که روش توالی cutting plane (صفحۀ برش ) نامیده می شود ارائه شده است . ویژگی اصلی این الگوریتم توصیف شده ( توضیح داده شده ) است ، همگرایی به نقطۀ مانای Karush - Kuhn - Tucker ثابت شده و نتایج عددی روی مجموعه ای از نمونه های شناخته شده نشان داده شده است . این روش بر اساس حالت خطی برای مسائل با (محدودیت نامساوی) محدب است اما در اینجا این روش به مسائل برنامه ریزی غیر خطی دیفرانسیلی متناوب شامل هر دو محدودیت مساوی و نامساوی غیر خطی گسترش داده شده است . در مقایسه با حل کننده های موجود فهمیده می شود که این روش قابل رقابت با این حل کننده ها است . بنابراین این روش که براساس حل زیر برنامه ، برنامه ریزی خطی است یک روش خوب برای حل مسائل برنامه ریزی غیر خطی است . این الگوریتم به عنوان زیر حل کننده در الگوریتم برنامه ریزی غیر خطی اعداد مختلط در جایی که مسائل خطی باندهای پایین برای حل بهینه در زیر مسئله های برنامه ریزی غیر خطی در درخت شاخه و باند برای مسائل با محدودیت غیر خطی محدب به کار برده می شود .
مقدمه :
روش cutting plane (صفحۀ برش) Kelly [11] در سال 1960 برای حل مسائل برنامه ریزی غیر خطی (NP) با حل یک توالی از مسائل برنامه ریزی خطی (LP) ارائه شد . اگر چه بعضی روش های دیگر که براساس برنامه ریزی خطی هستند وجود دارد مثل روش برنامه ریزی تقریبی [6] ، تکنیک های LP کاملاً در طرفداری از روش برنامه ریزی درجۀ 2 متوالی (SQP) کنار گذاشته شده اند . بعد از اینکه Han همگرایی اصلی و محلی را در روش (SQP) [8و7] ثابت کرد تعداد زیادی از مقالات تحقیقاتی براساس تکنیک های SQP تولید شدند . در واقع امروزه تعدادی از حل کننده های NLP فرم هایی از تکنیک های SQP را به کار برده اند . اخیراً مقالات جالبی در تایید موفقیت تکنیک های برنامه ریزی خطی (SLP) ارائه شده است . در [2] مقاله ای ارائه شده که برنامه ریزی خطی و زیر مسائل برنامه ریزی خطی درجۀ 2 با موفقیت حل شده و حل بهینه را به دست آورده است . مسائل برنامه ریزی خطی یک برآوردی از شرایط (محدودیت های) فعال در ناحیۀ معتبر فراهم کرده است و یک مسئلۀ برنامه ریزی درجه 2 با استفاده از شرایط (محدودیت های) فعال در حل بهینۀ مسئلۀ خطی ساختاربندی شده و حل شده است . اگرچه روش ارائه شده در [2] اساساً برای برآورد (تخمین) شرایط (محدودیت های) فعال در هر تکرار، مسائل برنامه ریزی خطی را به کار می برد و به علاوه در هر تکرار یک مسئله با محدودیت مساوی درجه 2 را حل می کند . در این مقاله این نشان داده می شود که تکنیک های LP در حل مسائل NLP به صورت مؤثری با موفقیت به کار می رود حتی بدون اینکه مجبور باشد زیر مسئله های درجه 2 را حل کند . در واقع آزمایشات عددی روی 2 مجموعۀ مورد آزمایش از مسائل استاندارد نشان می دهد که روش توصیف شده قالب رقابت با سایر حل کننده های NLP است . روش توصیف شده در اینجا می تواند برای حل مسائل NLP با هر دو شرط مساوی و نامساوی غیرخطی به کار برده شود و همگرایی اصلی به نقطۀ مانا Karush - Kuhn – Tucker (KKT) برای مسائل دیفرانسیلی متناوب غیر محدب نشان داده شده است . الگوریتم پیشنهاد شده یک بسطی از الگوریتم (SCP) صفحۀ برش متوالی که در [19] معرفی شده است . روش اصلی فقط مسائل محدب با شرایط نامساوی غیر خطی را حل می کند . دقت کنید که سر نام SCP با Sequential Conven Programming ارائه شده در [24] نباید اشتباه گرفته شود . در برنامه ریزی محدب متوالی مسئلۀ NLP اصلی با حل کردن یک توالی از زیربرنامه های غیر خطی مجزای محدب حل می شود . در اینجا ، این روش زیر مسئله های خطی را برای حل مسئلۀ NLP اصلی استفاده می کند . هدف اصلی الگوریتم توصیف شده در این مقاله به ویژه در حالت محدب الگوریتم بهینه کردن اجرا روی مسئله هاست به طوری که هدف و شرایط به آسانی ارزیابی شوند . هدف اصلی مینیمم کردن ارزیاب های تابع نیست .
اگر شرایط و تابع برای محاسبه کردن زمان بر باشد تعدادی الگوریتم دیگر برای چنین مسائلی وجود دارد که کاربردی تر و مفیدتر است . یکی از کاربردهای الگوریتم این است که به عنوان یک ترکیب کننده در یک الگوریتم برنامه ریزی غیر خطی عدد مختلط (MINLP) به کار رود . برای مسائل MINLP با محدودیت نامساوی محدب زیر مسئله ها LP به راحتی یک باند پایین برای حل بهینۀ مسئلۀ NLP محدب فراهم می کند . باندهای پایین (حدهای پایین) در روش شاخه و باند برای اثبات درست مورد نیاز هستند . جزئیات بیشتر در [21] دیده می شود . نتایج بسیار امیدوار کننده ای برای یک مجموعۀ خاص از مسائل بهینه سازی پیچیده در [20] گزارش شده است . مدل MINLP از الگوریتم می تواند حل های بهتری را در یک دقیقه بدست می آورد در حالی که حل کننده های اقتصادی که جواب ها را در مدت 12 ساعت به دست می آورند . حل مسائل MINLP محدب در بهینه سازی MINLP اصلی مهم است زیرا بیشتر الگوریتم های مشخص براساس حل یک توالی از مسائل MINLP محدب هستند [23و16و1] این الگوریتم می تواند همچنین برای حل کلی مسائل MINLP غیر محدب به عنوان حل کنندۀ فرعی در روش شاخه و باند NLP به کار برده شود [4] . آزمایشات عددی نشان می دهد که الگوریتم SCP می تواند برای این نوع از مسائل به کار برده شود و نیز همگرایی به نقطۀ مانا سریعتر آشکار می شود نسبت به زمانی که تکرارها از نقطۀ مانا دور هستند .
مرور : الگوریتم پیشنهادی ما مسائلی از این فرم را حل می کند .
که تابع های
دیفرانسیل های متناوب روی هستند . برخلاف [19] تابع و شرایط به صورت محدب در نظر گرفته نشده است . در نظر گرفته شده که شرایط شامل می شود شرایط خطی که یک ناحیۀ محدود X تعریف می کند . همچنین فرض شده است که ویژگی های شرایط (محدودیت) Mangasarion – Fromovitz توسعه یافته (EMFCQ) برای هر بر قرار است . شرایط در هر برای وقتی که مستقل خطی هستند برقرار است و یک وجود دارد به طوری که :
که یک مجموعه شاخص هایی هستند که بر شرایط مرزی دلالت می کند .
و یک مجموعه از شاخص هایی است که بر شرایط فعال دلالت می کند .
EMFCQ و رابطه ی آن توابع پنالتی (جبرانی) ملاحظه شده در [15] را نیاز دارد . در این الگوریتم ویژگی شرایط (محدودیت ها) به صورتی است که ضمانت می کند که برای هر نقطۀ غیر عملی می تواند یک جهت جستجویی را پیدا می کند به طوری که غیر عملی بودن شرایط کاهش یابد .
2. الگوریتم :
این الگوریتم شبیه به الگوریتم ارائه شده در [16] است از این جهت که یک توالی از تکرارهای NLP را اجرا می کند تا اینکه حل بهینۀ محلی را به دست آورد . هر تکرار NLP یک توالی از زیر تکرارهای LP را شامل می شود .
در هر زیر تکرار LP یک مسئلۀ LP حل می شود و یک جستجوی خطی در جهت جستجوی به دست آمده به عنوان حل برای مسئلۀ LP اجرا می شود . در پایان تکرار NLP ، آن تکرار جدید باید تابع شایستگی (مزیت) را به اندازۀ کافی کاهش دهد به منظور اینکه همگرایی را تضمین کند . و گرنه یک تکرار جدید باید به وجود آید به طوری که تابع شایستگی را به اندازه کافی کاهش دهد .
2.1 : زیر تکرارهای LP :
در هر زیر تکرار LP یک مسئلۀ LP حل می شود . مسئلۀ LP براساس (شکل گیری) صفحه های برش در تکرار جاری است . در زیر تکرار (i) از تکرارهای NLP مسئلۀ LP حل شده هست :
که در نقطۀ به وجود آمده اند . مسئله LP( ) و حل بهینه مسئلۀ در جایی که است بیان شده است . در اینجا شرایط a1 و b1 خطی شدۀ تابع شرایط غیر خطی h,g در هستند و مجموعه ای برای آرام سازی شرایط هستند به طوری که یک حل d در حل محدودۀ شرایط (1d) ایجاد می شود این شرایط اطمینان می دهد که جواب با توجه به جهت جستجوی به دست آمدۀ قبلی در طی تکرار NLP به صورت یک جهت ترکیبی می شود . جهت های جستجو برای زیر تکرارهای LP قبلی در طی تکرار NLP با مشخص شده است و برآورد (تخمین) است در زیر تکرار LP(i) در Hessian لاگرانتری در (NLP) .
توجه کنید که برای اثبات همگرایی فقط یک زیر تکرار در LP در تکرار NLP مورد نیاز است . توالی زیر تکرارهای LP فقط برای بهبود شرعت همگرایی اجرا می شوند . توالی زیر تکرارهای LP جهت های جستجوی ترکیبی را ایجاد می کند و بنابراین این الگوریتم روش جستجوی (شیب) گرادیانی ترکیبی را برای مسائل بدون محدودیت اجرا می کند . باندهای پایین (حدهای پایین) به صورت منفی و حدهای بالا (باندهای بالا) به صورت مثبت در نظر گرفته شده است . است . دقت کنید که هر دو خطی سازی شرایط به خوبی شرایط ترکیب را با توجه به تخمین Hessian لاگرانتری محدود می کند می توانند به عنوان صفحه های برش دیده شوند شرایط a1 حالت نیم فضایی ناحیۀ قابل قبول برای g را تقریب می زنند و b1 ها صفحه های رویین برش هستند که ناحیۀ قابل قبول را برای h تخمین می زنند و c1 صفحه های رویین برش هستند که جهت جستجوی d را با این شرایط که برروی صفحه های رویین وجود داشته باشند محدود می کند و بنابراین یک صفحه ترکیبی برای جهت های جستجوی به دست آمدۀ قبلی در طی تکرار NLP ایجاد می شود .
2.1.1 : تخمین افزایندۀ لاگرانتری :
مقادیر بهینۀ متغیرهای دوگان از 1 به عنوان تخمین های افزایندۀ لاگرانتری برای توالی جستجوهای خطی و برای تخمین Hessian لاگرانتری به کار می رود . اگر مسئلۀ LP در نقطۀ مانای برای NLP ایجاد شود سپس متغیرهای دوگان از شرایط a1 و b1 برای حل ، افزایندۀ لاگرانتری برای در NLP شناخته می شوند .