پایان نامه ارشد:روش های نقطه درونی برای بهینه سازی

متن کامل پایان نامه مقطع کارشناسی ارشد رشته :ریاضی

گرایش :ریاضی کاربردی

عنوان : روش های نقطه درونی برای بهینه سازی

دانشگاه الزهرا)س)

دانشکده علوم پایه

پایان نامه

برای دریافت درجه کارشناسی ارشد

رشته ریاضی کاربردی

عنوان

روش های نقطه درونی برای بهینه سازی

استاد راهنما

خانم دکتر ترانه تجویدی

 استاد مشاور

آقای دکتر یداله اردوخانی

اسفند 1392

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود

(در فایل دانلودی نام نویسنده موجود است)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)

 

 

 

 

 

فهرست مطالب

 

تاریخچه. 1

فصل اول.. 3

کلیات.. 3

1-1- تعاریف مقدماتی.. 3

1-2  دوگان فنچل.. 8

فصل ۲. 11

توابع خود هماهنگ… 11

2-1 تابع خودهماهنگ… 12

2-2  ترکیب قواعد اولیه. 14

2-3 .خواص توابع خود هماهنگ : 17

فصل ۳.. 38

مانع خود هماهنگ… 38

3-1 تعریف و ترکیب قواعد. 38

3-2. خواص موانع خود هماهنگ… 41

فصل ۴.. 51

روش های نقطه درونی.. 51

4-1 روش های نقطه درونی.. 52

4-1-1  تابع مانع لگاریتمی و مسیر مرکزی.. 53

4-2 روش مسیر تعقیب.. 54

4-2-1  روشF– تولید مسیر تعقیب.. 55

4-2-2  طرح اولیه مسیر تعقیب.. 56

4-2-3  همگرایی و پیچیدگی.. 57

4-2-4  مقداردهی اولیه و روش دوفازی مسیر تعقیب.. 65

4-2-5 نتیجه گیری : 69

4-3 مسائل مخروطی و دوگان آن.. 71

4-3-1  مسائل مخروطی.. 72

4-3-2  موانع لگاریتمی همگن.. 76

4-4 روش کارمارکار. 84

4-4-1 قرارداد و فرض های مسئله. 85

4-4-2  شکل همگن مسئله. 86

4-4-3  تابع پتانسیل کارمارکار. 87

4-4-4  طرح به روز رسانی کارمارکار. 88

4-4-5  پیچیدگی روش کارمارکار. 94

4-4-6  چگونگی پیاده سازی روش کارمارکار. 96

نتیجه گیری و کارهای آینده. 100

کتاب نامه : 102

واژه نامه ی فارسی به انگلیسی.. 104

واژه نامه ی انگلیسی به فارسی.. 109

 

چکیده

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

تعداد صفحه : 124

قیمت : 14000تومان

بلافاصله پس از پرداخت ، لینک دانلود پایان نامه به شما نشان داده می شود

و در ضمن فایل خریداری شده به ایمیل شما ارسال می شود.

پشتیبانی سایت :        09361998026        info@arshadha.ir

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

شماره کارت :  6037997263131360 بانک ملی به نام محمد علی رودسرابی

11

مطالب مشابه را هم ببینید

فایل مورد نظر خودتان را پیدا نکردید ؟ نگران نباشید . این صفحه را نبندید ! سایت ما حاوی حجم عظیمی از پایان نامه های دانشگاهی است. مطالب مشابه را هم ببینید. برای یافتن فایل مورد نظر کافیست از قسمت جستجو استفاده کنید. یا از منوی بالای سایت رشته مورد نظر خود را انتخاب کنید و همه فایل های رشته خودتان را ببینید