Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems

اخیراً پیشرفت‌های زیادی در الگوریتم‌های تقریب برای مسائل غیر محدب پیوسته و گسسته از منظر نظری و عملی صورت گرفته است. در بهینه‌سازی گسسته (یا ترکیبی) اخیراً رویکردهای زیادی ایجاد شده است که جهان گسسته را از طریق تکنیک‌های هندسی، تحلیلی و جبری به جهان پیوسته مرتبط می‌کند. چنین تکنیک هایی شامل فرمول های بهینه سازی جهانی، برنامه نویسی نیمه معین و نظریه طیفی است. در نتیجه الگوریتم های تقریبی جدید کشف شده اند و بسیاری از رویکردهای محاسباتی جدید توسعه یافته اند. به طور مشابه، برای بسیاری از مسائل بهینه‌سازی غیرمحدب پیوسته، الگوریتم‌های تقریبی جدیدی بر اساس برنامه‌نویسی نیمه معین و تکنیک‌های تصادفی‌سازی جدید توسعه داده شده‌اند. از سوی دیگر، پیچیدگی محاسباتی که از تعاملات بین علوم کامپیوتر و بهینه‌سازی عددی نشات می‌گیرد، یکی از نظریه‌های عمده‌ای است که رویکرد حل مسائل بهینه‌سازی و تحلیل دشواری ذاتی آنها را متحول کرده است. تمرکز اصلی پیچیدگی مطالعه این است که آیا الگوریتم‌های موجود برای حل مسائل کارآمد هستند و کدام مسائل احتمالاً قابل حل هستند. تلاش برای توسعه الگوریتم‌های کارآمد همچنین به رویکردهای کلی ظریف برای حل مسائل بهینه‌سازی منجر می‌شود و ارتباطات شگفت‌انگیزی را بین مسائل و راه‌حل‌های آنها آشکار می‌کند. کنفرانسی در مورد تقریب و پیچیدگی در بهینه سازی عددی: مسائل پیوسته و گسسته در طول 28 فوریه تا 2 مارس 1999 در مرکز بهینه سازی کاربردی دانشگاه فلوریدا برگزار شد.

There has been much recent progress in approximation algorithms for nonconvex continuous and discrete problems from both a theoretical and a practical perspective. In discrete (or combinatorial) optimization many approaches have been developed recently that link the discrete universe to the continuous universe through geomet­ ric, analytic, and algebraic techniques. Such techniques include global optimization formulations, semidefinite programming, and spectral theory. As a result new ap­ proximate algorithms have been discovered and many new computational approaches have been developed. Similarly, for many continuous nonconvex optimization prob­ lems, new approximate algorithms have been developed based on semidefinite pro­ gramming and new randomization techniques. On the other hand, computational complexity, originating from the interactions between computer science and numeri­ cal optimization, is one of the major theories that have revolutionized the approach to solving optimization problems and to analyzing their intrinsic difficulty. The main focus of complexity is the study of whether existing algorithms are efficient for the solution of problems, and which problems are likely to be tractable. The quest for developing efficient algorithms leads also to elegant general approaches for solving optimization problems, and reveals surprising connections among problems and their solutions. A conference on Approximation and Complexity in Numerical Optimization: Con­ tinuous and Discrete Problems was held during February 28 to March 2, 1999 at the Center for Applied Optimization of the University of Florida.