.. 52

.. 53

.. 54

.. 55

.. 56

.. 57

.. 65

69

.. 71

.. 72

.. 76

. 84

. 85

. 86

. 87

. 88

. 94

. 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.