Interior Point Methods of Mathematical Programming

باید همه چیز را تا حد امکان ساده کرد اما هرگز ساده تر از این نیست. اکتشاف آلبرت اینشتین شامل دیدن آنچه که هر بدن دیده است و فکر کردن به چیزی است که هیچ کس فکر نکرده است. Albert S. ent_Gyorgy; هدف اصلی این کتاب ارائه مقدمه ای بر نظریه روش های نقطه داخلی (IPMs) در برنامه ریزی ریاضی است. در عین حال، ما سعی می کنیم مروری سریع از تأثیر گسترش IPM ها بر بهینه سازی غیرخطی صاف ارائه کنیم و پتانسیل IPM ها را برای حل مسائل عملی دشوار نشان دهیم. روش سیمپلکس از سال 1947 که دانتسیگ آن را کشف کرد، بر نظریه و عمل برنامه نویسی ریاضی تسلط داشت. در دهه‌های پنجاه و شصت چندین تلاش برای توسعه روش‌های راه‌حل جایگزین انجام شد. در آن زمان پایه اصلی روشهای نقطه داخلی نیز توسعه یافت، به عنوان مثال در کار فریش (1955)، کارول (1961)، هاارد (1967)، فیاکو و مک کورمیک (1968) و دیکین (1967). در سال 1972، کلی و مینتی تصریح کردند که در بدترین حالت، برخی از انواع روش سیمپلکس ممکن است برای حل مسائل برنامه‌ریزی خطی (LP) به مقدار زیادی کار نیاز داشته باشند. این در زمانی بود که نظریه پیچیدگی به موضوعی بسیار مورد توجه تبدیل شد. مردم شروع به طبقه بندی مسائل برنامه ریزی ریاضی به عنوان مسائل کارآمد (در زمان چند جمله ای) و به عنوان مسائل دشوار (NP-hard) کردند. برای مدتی باز باقی ماند که آیا LP در زمان چند جمله ای قابل حل است یا نه. حل این مشکل توسط خاچیجان (1989) بدست آمد.

One has to make everything as simple as possible but, never more simple. Albert Einstein Discovery consists of seeing what every­ body has seen and thinking what nobody has thought. Albert S. ent_Gyorgy; The primary goal of this book is to provide an introduction to the theory of Interior Point Methods (IPMs) in Mathematical Programming. At the same time, we try to present a quick overview of the impact of extensions of IPMs on smooth nonlinear optimization and to demonstrate the potential of IPMs for solving difficult practical problems. The Simplex Method has dominated the theory and practice of mathematical pro­ gramming since 1947 when Dantzig discovered it. In the fifties and sixties several attempts were made to develop alternative solution methods. At that time the prin­ cipal base of interior point methods was also developed, for example in the work of Frisch (1955), Caroll (1961), Huard (1967), Fiacco and McCormick (1968) and Dikin (1967). In 1972 Klee and Minty made explicit that in the worst case some variants of the simplex method may require an exponential amount of work to solve Linear Programming (LP) problems. This was at the time when complexity theory became a topic of great interest. People started to classify mathematical programming prob­ lems as efficiently (in polynomial time) solvable and as difficult (NP-hard) problems. For a while it remained open whether LP was solvable in polynomial time or not. The break-through resolution ofthis problem was obtained by Khachijan (1989).