مقاله الگوریتم بهینه سازی بر اساس برنامه ریزی خطی برای حل مسائل برنامه ریزی غیر خطی

توضیحات

  مقاله الگوریتم بهینه سازی بر اساس برنامه ریزی خطی برای حل مسائل برنامه ریزی غیر خطی دارای 47 صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد مقاله الگوریتم بهینه سازی بر اساس برنامه ریزی خطی برای حل مسائل برنامه ریزی غیر خطی  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی مقاله الگوریتم بهینه سازی بر اساس برنامه ریزی خطی برای حل مسائل برنامه ریزی غیر خطی،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از متن مقاله الگوریتم بهینه سازی بر اساس برنامه ریزی خطی برای حل مسائل برنامه ریزی غیر خطی :

خلاصه :

در این مقاله الگوریتم بهینه سازی براساس برنامه ریزی خطی که روش توالی 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 ، آن تکرار جدید باید تابع شایستگی (مزیت) را به انداز کافی کاهش دهد به منظور اینکه همگرایی را تضمین کند . و گرنه یک تکرار جدید باید به وجود آید به طوری که تابع شایستگی را به اندازه کافی کاهش دهد .

21 : زیر تکرارهای LP :

در هر زیر تکرار LP یک مسئل LP حل می شود . مسئل LP براساس (شکل گیری) صفحه های برش در تکرار جاری  است . در زیر تکرار (i) از تکرارهای NLP مسئل LP حل شده هست :

a1                                                    

b1                                                 

c1                                                                 

d1                                                                                                                

e1                                                                

f1                                                                       

g1                                                                      

که در نقط  به وجود آمده اند . مسئله 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 ایجاد می شود .

211 : تخمین افزایند لاگرانتری :

مقادیر بهین متغیرهای دوگان از 1 به عنوان تخمین های افزایند لاگرانتری برای توالی جستجوهای خطی و برای تخمین Hessian لاگرانتری به کار می رود . اگر مسئل LP در نقط مانای  برای NLP ایجاد شود سپس متغیرهای دوگان  از شرایط a1 و b1 برای حل  ، افزایند لاگرانتری برای  در NLP شناخته می شوند .

212 : مسائل LP غیر ممکن

اولین مسئل LP در طی تکرار NLP نمی تواند غیر عملی باشد . زیرا که متغیرهای  مسئله را به انداز کافی آرام می کنند به طوری که یک حل d=0 را برای هر مسئله می پذیرد . ( وقتی که متغیرهای آرام سازی برابر با ماکزیمم مقدار مجاز شرایط است ) . بنابراین نیازی به بررسی مساله های LP عملی به عنوان موردی در حالت محدب در الگوریتم ارائه شده در [19] نیست . توجه کنید که ثابت C برای تضمین در تکرارهای غیر ممکن به انداز کافی بزرگ انتخاب می شوند و یک حل بهینه وقتی که  است به دست می آید و غیر عملی بودن شرایط کاهش می یابد وقتی که برای حل بهین  داریم :  به طوری که  و یا وجود دارد  به طوری که    اگر مسئل در زیر تکرار LP اول بدست نیاید سپس مسئل NLP اصلی غیر عملی فرض می شود . به طور کلی چنانچه الگوریتم به نقط غیر ممکن (غیر قابل قبول) محلی همگرا شود ، این درست نیست . اگر چه این فرض شده که EMFCQ برقرار است و شرایط تضمین می کند که چنین جوابهایی را می تواند پیدا کند .

213 : جستجوی خطی :

حل بهین  برای  یک جهت جستجو را فراهم می کند و برای مینیمم کردن تابع در یک جستجوی خطی عمل می کند :

در اینجا  تخمین های افزایند لاگرانتری به دست آمده از متغییرهای دوگانه مسئل LP حل شد قبلی هستند و  . پارامتر P یک پارامتر جبرانی هست که در طی فرآیند بهینه سازی ثابت نگه داشته می شود . جستجوی خطی برای مینیمم کردن  استفاده می شود که  تخمین های افزایند لاگرانتری هستند که در زیر تکرار i(LP) به دست آمده اند . جستجوی خطی در جهت  باشد و شروع از  اجرا می شود که هست :  .

تکرار بعدی بر اساس  است و به عنوان نقط شروع در زیر تکرار LP بعدی به کار برده می شود . دقت کنید که جستجوی خطی دقیق ضرورتاً مورد نیاز نیست و همچنین معیار برای جستجوی خطی به انداز کافی کاهش یابد .

214 : تخمین Hessian :

فرمول تجدید شد (BFGS)   Broyden – Fletcher – Goldfard – Shanno  استاندارد برای ایجاد تخمین ها برای Hessian به کار برده می شود اگرچه روش های دیگر هم به کار برده می شود . تخمین Hessian براساس تابع لاگرانتری زیر است :

215 : معیار خاتمه دادن زیر تکرار :

مراحل توصیف شد بالا تکرار می شود تا اینکه یک معیار خاتمه را مشاهده کند . تعدادی معیار برای پایان دادن به زیر تکرار LP به کار برده می شود . برخلاف الگوریتم توصیف شده در [19] اولین زیر مسئل LP در هر تکرار NLP نمی تواند عملی باشد ، همچنین متغیرهای  وجود دارد که زیر مسئل LP را آرام سازی می کند . در اولین زیر تکرار ، حل بهینه زیر مسئل LP که غیر عملی بودن را کاهش نمی دهد که ممکن است مسئل اصلی غیر عملی باشد و یا نقطه به نقط غیر عملی محلی نزدیک است .

در توالی زیر تکرارها اگر هر یک از متغیرهای آرام سازی از صفر بزرگتر باشند شرایط مساوی (1C) ممکن است بسیار محدود شود و زیر تکرارها خاتمه می یابد . الگوریتم بیشتر زیر تکرارهای LP را متوقف می کند اگر یکی از معیارهای زیر دیده شود :

اگر i>n خاتمه می یابد                                     (1

اگر  به صفر نزدیک شود خاتمه می یابد           (2

اگر                کاهش نیابد خاتمه می یابد           (3

 به طوری که  وجود ندارد و  به طوری که

    برای حل بهین  وجود دارد .

اگر i>1 باشد و هر متغیر  از صفر بزرگتر باشند خاتمه می یابد .                                         (4

اگر  به یک نزدیک باشد خاتمه می یابد .                                                                                (5

22 : تکرار NLP :

هر تکرار NLP یک مجموعه از زیر تکرارهای LP را شامل می شود . بنابراین چندین مسئل LP حل می شود و چندین جستجوی خطی در هر تکرار NLP اجرا می شود تا اینکه اولین معیار خاتم زیر تکرارها چنانچه در 215 توضیح داده شده مشاهده می شود . در پایان هر تکرار NLP ، تکرار جدید باید یک تابع شایستگی را به انداز کافی کاهش دهد تا همگرایی به نقط مانای KKT را تضمین کند . در غیر این صورت تکرار جدید باید با یک تکراری که تابع شایستگی را به انداز کافی کاهش دهد جایگزین شود . بنابراین یک تکرار با شروع از تکرار پذیرفته شد قبلی به دست می آید و تابع شایستگی را نسبت به تابع  در جهت تر ولی برای تابع شایستگی مینیمم می کند . تابع شایستگی به کار برده شده در اینجا هست :

که  ترم جبرانی هست که به صورت زیر تعریف شده است :

پارامترهای  باید به صورتی انتخاب شوند که از قدر مطلق مقدار هر تخمین افزایند لاگرانتری بزرگتر باشد . بنابراین :

2                                                                                 

3                                                                                                  

باید برای هر تخمین افزایند لاگرانتری  به دست آمده در طی پروس بهینه سازی برقرار باشد .

در عمل آزمایشات عددی نشان می دهد که بهتر است پروسه (فرآیندی) را به کار ببریم که  را به صورت پویا در طی فرآیند بهینه سازی وقتی که تخمین های افزایند لاگرانتری بزرگتر از  در حال استفاده هستند تجدید می کند ( یا بعضی از روش های مشابه برای تخمین این پارامترها به کار رود ) . فرض های 2و3 برای اثبات همگرایی مورد نیاز است .

221 : آزمایش کاهش کافی :

تکرار جدید در پایان تکرار NLP باید آزمایش کاهش کافی را ارضا کند . ابتدا دقت کنید که مشتق های جهتی  در جهت d هستند :

,    

در نتیجه : مشتق جهتی M در جهت d هست :

تکرار جدید  در پایان تکرار k,NLP باید روابط زیر را ارضا کند :

4                                                                                           

 باید ارضا کند رابط :

5                                                

6                                                             

در اینجا  تکرار در حال اجرا در اولین زیر تکرار LP برای تکرار NLP K است و  جهت جستجوی به دست آمده به عنوان حل برای  است و  نتایج برای جستجوی خطی متناظر است . از آنجایی که جستجوی خطی به   محدود می شود تکرار می تواند به ازای  قابل قبول باشد حتی اگر رابط 6 برقرار نشود . شرایط ذکر شده در 4-6 شرایط تئوری مورد نیاز هستند که همگرایی الگوریتم را بهبود می بخشد .

شرط 5 اطمینان می دهد که تابع شایستگی به انداز کافی کاهش می دهد و 6 اطمینان می دهد که مراحل (پله ها) به انداز کافی در هر تکرار اجرا شده اند . این  اختیاری کوچک پذیرفته نمی شود . به علاوه  متناوباً پذیرفته می شود . در آخر ، 4 اطمینان می دهد که آن تکرار در انتهای تکرار NLP مقدار تابع شایستگی را بیشتر از مقدار تابع شایستگی به دست آمده بعد از اولین زیر تکرار LP در تکرار NLP افزایش نمی دهد . توجه کنید که بعداً در قضی 6 ثابت می شود که  است مگر اینکه  نقط مانای KKT باشد . دقت کنید که اگر  یک جهت نزولی برای M باشد و یک جستجوی خطی دقیق با شروع از  که M را مینیمم می کند اجرا شود ، سپس  معیار کاهش کافی (6) و (4) را ارضا می کند اما ضرورتاً (5) را ارضا نمی کند.

اگر چه در عمل از انتخاب 6 که به انداز کافی به صفر نزدیک باشد اجتناب می شود . به طور متناوب الگوریتم جستجوی خطی غیر دقیق مرحله ای را پیدا می کند که 5 و 6 و همچنین 4 را ارضا کند به شرطی که  که در [13] توضیح داده شده است .

222 : ایجاد تکرارهای مورد قبول :

اگر تکرار  آزمایش کاهش کافی را که در 4 – 6 بیان شده ارضا نکند یک تکرار جدید که آزمایش را ارضا کند ایجاد می شود . در قضی 6 نشان داده شده که حل  برای اولین زیر مسئل LP در یک تکرار NLP یک جهت نزولی برای تابع شایستگی M است . بنابراین یک نقط جدید که ازمایش کاهش کافی را ارضا کند می تواند با شروع زیرتکرار LP از  و تکرار کردن جستجوهای خطی در جهت های  به دست آمده در زیر تکرارهای LP به دست آید (ایجاد شود ) . اما البته M را به جای  در هر جستجوی خطی min می کنیم . از آنجایی که  یک جهت نزولی برای تابع شایستگی است یک تکرار قابل قبول با به کار بردن این فرآیند ایجاد می شود .

23 : تجدید کردن باندها (حدهای) ناحیه ی اطمینان :

حدها (باندهای)  یک ناحیه ی اطمینان را برای حل d برای زیر مسئل LP شکل می دهند . این ناحی اطمینان ممکن است افزایش یابد اگر ناحی اطمینان در حال اجرا خیلی کوچک باشد و یا کاهش یابد اگر ناحی اطمینان در حال اجرا خیلی بزرگ باشد . یک فرآیند نمونه برای تجدید کردن ناحی اطمینان براساس طول مراحل استفاده شده در هر تکرار NLP به کار برده شده است . در نظر بگیریم :

و    . در اینجا  مرحل بین 2 تکرار NLP وابسته به باندهای بالا و پایین را اندازه گیری می کند .

توجه کنید که  ممکن است از 1 بزرگتر باشد زیرا زیر تکرارهای افزایند LP در هر تکرار NLP اجرا می شود. به علاوه  را به عنوان میزان دقتی در نظر بکیرید که چگونه بزرگی یا کوچکی یک پله (مرحله) بدون کاهش یا افزایش باندهای ناحی اطمینان صورت می گیرد .

بنابراین اگر  ، باندهای ناحیه ی اطمینان کاهش می یابد :

اگر  ، باندهای ناحیه ی اطمینان افزایش می یابد :

24 : معیار خاتمه ی تکرار NLP :

تکرارهای NLP ادامه می یابد تا اینکه در حال اجرا یک نقط مانا شود . در اینجا فرض شده است که مسئله ها همیشه نقاط مانا دارند . به طور کلی الگوریتم ممکن است در نقاطی که غیر عملی بودن شرایط نمی تواند کاهش یابد متوقف شود . متغیرهای آرام سازی  به حدهای بالای این متغیرها برای اولین زیر مسئل LP یک تکرار NLP نزدیک می شود . در این مورد این باید فرض شود که مسئل NLP اصلی غیر عملی است اگر چه ممکن است به این صورت باشد که الگوریتم به نقط غیر ممکن محلی همگرا شود . تکرار در حال اجرای  یک نقط مانا است اگر اولین دستور از شرط  Karush – Kuhn – Tucker را ارضا کند .

محاسبه ی این معیارها با به کار بردن تقریب های  آسان است که  از مسئل دوگان زیر مسئل LP به دست امده اند . دقت کنید که 4 همیشه به عنوان تقریب  براساس مسئل دوگان زیر مسئله LP به شرط  ارضا می شود . دقت کنید همچنین ممکن است الگوریتم در مواردی برنامه هایی را حل کند که نقط مانا یک نقط مانای Karush – Kuhn – Tucker نیست همچنین معیارهای بالا در چنین نقطه ای برقرار نیستند . در این موارد اگر چه آزمایشات عددی اولیه نشان می دهد که الگوریتم ممکن است هنوز یک نقط مانای Karush – Kuhn – Tucke را در طی حل پذیرفته شده ای در همسایگی جواب درست به دست آورد .

25 : الگوریتم SCP :

الگوریتم SCP به صورت خلاصه در زیر امده است .

• تنظیم کردن نقط شروع اولیه .
• انجام زیر تکرارهای LP

21) تنظیم کردن :             

22) ایجاد  و حل آن برای به دست آوردن جهت جستجوی  و تخمین افزایند لاگرانتری  (حل بهین دوگان)

23) بررسی اینکه آیا تکرار در حال اجرا یک نقط مانا هست یا نه ؟ (بخش 24) .

24) اجرای جستجوی خطی برای مینیمم کردن  (بخش 213 ) در نظر بگیریم :

25) تجدید کردن تخمین Hessian لاگرانتری با به کار بردن فرمول تجدید کنند BFGS و نامیده آن به صورت  (بخش 214 )

26) اگر بعضی معیارهای خاتم زیر تکرارها ارضا شود ( بخش 215 ) . سپس از زیر تکرارهای LP خارج می شود . ( برو به 3 ) .

پس در نظر می گیریم : i:=i+1 و به 22 می رویم .

• ذخیر تکرار در حال اجرا و تخمین Hessian از زیر تکرارهای LP
• اگر کاهش کافی برای تابع شایستگی وجود نداشت (بخش 221 ) سپس یک تکرار جدید با کاهش کافی پیدا می کنیم . (بخش 222)
• اگر ناحیه ی اطمینان خیلی کوچک یا خیلی بزرگ باشد ناحیه ی اطمینان را تجربه می کنیم (بخش 23)
• اگر تکرار یک نقط مانا نباشد (بخش 24) سپس k:=k+1 را در نظر می گیریم و تکرار NLP جدید را شروع می کنیم . (به 2 برو )

3: همگرایی :

در این بخش نشان داده می شود که الگوریتم ویژگی همگرایی کلی را دارد . این بخش به صورت ادامه تقسیم بندی شده است : در قضیه ی 2 نشان داده می شود که ثابت C ممکن است به دست بیاید به صورتی که غیر عملی بودن شرایط در زیر تکرار LP کاهش یابد .

در قضیه ی 6 نشان داده می شود که این الگوریتم در اولین زیر تکرار LP ، جهت هایی که جهت های نزولی برای تابع شایستگی هستند در زمانی که مسال LP ، را حل می کند به وجود می آورد . در آخر در قضیه ی 8 نشان داده می شود که هر نقط محدود در مراحل نامحدود تکرارها یک نقط محدود مانای KKT است . دقت کنید که قضی 6 بیان می کند که اگر جواب مسئل LP حل شده در اولین زیر تکرار از تکرار NLP برای تابع شایستگی یک جهت نزولی بنا شده پس تکرار در حال اجرا یک نقط مانای KKT برای NLP است . ابتدا این نشان داده می شود که ممکن است در اولین زیر تکرار LP ثابت های C برای هر  به گونه ای به دست آید که غیر عملی بودن شرایط برای خطی سازی مسئل  کاهش یابد . اثبات این موضوع به قضایایی که در ادامه آمده است نیازمند است .

برای دریافت اینجا کلیک کنید