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

بخشی از مقاله

خلاصه :

در این مقاله الگوریتم بهینه سازی براساس برنامه ریزی خطی که روش توالی 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 حل شده هست :

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 ایجاد می شود .

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

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

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

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

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

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

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

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

2.1.4 : تخمین Hessian :

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

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

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

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

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

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

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

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

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

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

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

2.2 : تکرار NLP :

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

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

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

2                                                                                 

3                                                                                                  

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

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

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

تکرار جدید در پایان تکرار 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] توضیح داده شده است .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3: همگرایی :

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

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