Mathematical Theory of Optimization

بهینه سازی در همه علوم از اهمیت اساسی برخوردار است. طبیعت ذاتاً به دنبال راه حل های بهینه است. به عنوان مثال، نور از طریق \"کوتاه ترین\" مسیر حرکت می کند و حالت چین خوردگی یک پروتئین با ساختار با \"حداقل\" انرژی پتانسیل مطابقت دارد. در بهینه‌سازی ترکیبی، مشکلات محاسباتی متعددی وجود دارد که در کاربردهای دنیای واقعی، مانند برنامه‌ریزی کف در طرح‌های VLSI و درخت‌های اشتاینر در شبکه‌های ارتباطی ایجاد می‌شوند. برای این مشکلات، راه حل بهینه دقیق در حال حاضر قابل محاسبه بلادرنگ نیست. معمولاً یک راه حل تقریبی با انواع مختلف اکتشافی محاسبه می شود. اخیراً رویکردهای زیادی توسعه یافته اند که فضای گسسته بهینه سازی ترکیبی را به فضای پیوسته بهینه سازی غیرخطی از طریق تکنیک های هندسی، تحلیلی و جبری مرتبط می کند. بسیاری از محققان دریافته اند که چنین رویکردهایی منجر به اکتشافی بسیار سریع و کارآمد برای حل مسائل بزرگ می شود. اگرچه تقریباً تمام این اکتشافات در عمل به خوبی کار می کنند، هیچ تحلیل نظری محکمی وجود ندارد، به جز الگوریتم Karmakar برای برنامه ریزی خطی. با در نظر گرفتن این وضعیت، تصمیم گرفتیم سمیناری را با موضوع بهینه سازی غیرخطی با تاکید بر مبانی ریاضی آن آموزش دهیم. این کتاب حاصل آن سمینار است. در طول دهه‌های گذشته، کتاب‌های درسی و تک نگاری‌های زیادی در زمینه بهینه‌سازی غیرخطی منتشر شده است. چرا باید این جدید را بنویسیم؟ تفاوت این کتاب با بقیه چیست؟ انگیزه نگارش این کتاب از تلاش ما برای انتخاب کتاب درسی برای سمینار فارغ التحصیل با تمرکز بر مبانی ریاضی بهینه سازی نشات گرفته است.

Optimization is of central importance in all sciences. Nature inherently seeks optimal solutions. For example, light travels through the "shortest" path and the folded state of a protein corresponds to the structure with the "minimum" potential energy. In combinatorial optimization, there are numerous computationally hard problems arising in real world applications, such as floorplanning in VLSI designs and Steiner trees in communication networks. For these problems, the exact optimal solution is not currently real-time computable. One usually computes an approximate solution with various kinds of heuristics. Recently, many approaches have been developed that link the discrete space of combinatorial optimization to the continuous space of nonlinear optimization through geometric, analytic, and algebraic techniques. Many researchers have found that such approaches lead to very fast and efficient heuristics for solving large problems. Although almost all such heuristics work well in practice there is no solid theoretical analysis, except Karmakar's algorithm for linear programming. With this situation in mind, we decided to teach a seminar on nonlinear optimization with emphasis on its mathematical foundations. This book is the result of that seminar. During the last decades many textbooks and monographs in nonlinear optimization have been published. Why should we write this new one? What is the difference of this book from the others? The motivation for writing this book originated from our efforts to select a textbook for a graduate seminar with focus on the mathematical foundations of optimization.