وبلاگ

 روش نقطه درونی طی 30 سال گذشته دیدگاه ما را در مورد مسایل بهینه سازی محدب تغییر داده است . در این پایان نامه ، ما روی مسایل محدب به ویژه مسایلی که الگورریتم های روش نقطه درونی را بهبود می دهند، می پردازیم . تئوری و نکات این روش ها را بیان می کنیم .

 

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

 

بر این اساس ، الگوریتم میرا شده نیوتن برای بهینه سازی توابع خود هماهنگ پیشنهاد می شود؛ که تضمین می کند جواب در هر همسایگی کوچکی از جواب بهینه قرار می گیرد  و وجود و منحصر به فردی آن ثابت می شود .در نهایت کران پیچیدگی محاسباتی روش های ارائه شده ، بیان می گردد.

 

Abstract

 

Interior-point methods have changed the way we look at optimization problems over the last thirty years. In this paper we have concentrated on convex problems, and in particular on the classes of structured convex problems for which interior-point methods provide provably efficient algorithms. We have highlighted the theory and motivation for these methods and their domains of applicability, and also pointed out new topics of research.

 

This paper discusses self-concordant functions . In Euclidean space, this class of functions are utilized extensively in interior-point methods for optimization because of the associated low computational complexity.

 

Here, the self-concordant function is carefully defined on a differential manifold. First, generalizations of the properties of self-concordant functions in Euclidean space are derived. Then, Newton decrement is defined and analyzed on the manifold that we consider. Based on this, a damped Newton algorithm is proposed for optimization of self-concordant functions, which guarantees that the solution falls in any given small neighborhood of the optimal

 solution, with its existence and uniqueness also proved in this paper.

 

The computational complexity bound of the proposed approach is also given explicitly.

 

تاریخچه

 

طی 30 سال گذشته انقلابی در حل مسایل بهینه سازی ایجاد شده است .در اوایل سال 1980 برنامه ریزی درجه دوم و روش لاگرانژ برای حل مسایل غیر خطی محبوب بودند ؛ در حالی که روش سیمپلکس برای حل مسایل خطی اساسا بی رقیب بود . از آن زمان به بعد ، روش های نقطه درونی به وجود آمدند.

 

روش های نقطه درونی در ابتدا برای حل مسایل برنامه ریزی خطی (LP) معرفی شدند . این روش ها ابتدا توسط خاچیان[1] در سال 1979 با الگوریتم برای مسایل LP به وجود آمدند ؛ سپس در سال 1984 کارمارکار[2] طرح پیشنهادی خود را با کران پیچیدگی بهبود یافته در این زمینه وارد عرصه بهینه سازی شد .

 

رنگار[3]  درسال 1988 و گونزاگا[4] در سال 1989 روش های مسیر تعقیب  را با یک بهبود پیچیدگی معرفی کردند . در همان زمان نستروف[5] ونمیروسکی[6] روی گسترش الگوریتم نقطه درونی از برنامه ریزی خطی به برنامه ریزی نیمه معین کار کردند. ]3[

 

و به طور مستقل توسط علیزاده در سال 1991 انجام گرفت . [1]

 

همچنین نستروف و نمیروسکی نشان دادند که هر مسئله بهینه سازی محدب را می توان با یک مانع [1]خود هماهنگ  ارائه کرد . آن ها تعداد قابل توجهی از مسایل مهم را که در آن موانع خود هماهنگ محاسبه پذیر در دسترس بودند ، ذکر کردند .

 

تئوری موانع خود هماهنگ به بهینه سازی محدب محدود شده است ، اما بیشتر مسایل علمی و مهندسی را می توان به بهینه سازی محدب تبدیل کرد . محققان در کنترل تئوری بسیار تحت تاثیر توانایی حل مسایل برنامه ریزی نیمه معین قرار گرفته اند . ]14[

 

همچنین تعدادی از مسایل غیر محدب ناشی از طراحی مهندسی را می توان به مسایل بهینه سازی محدب تبدیل کرد . ]15و16[

 

تعاریف مقدماتی

 

تعریف 1-1-1: ترکیب  برای بردارهای  و  یک ترکیب خطی است.

 

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

 

تعریف 1-1-2: هر گاه به ازای هر دو عضو  و  متعلق به مجموعه C و هر  که  داشته باشیم:

 

آنگاه مجموعه C را محدب می گوییم.

 

تابع  روی مجموعه محدب C، تابع محدب نامیده می شود هر گاه به ازای هر  و  داشته باشیم: