بهینهسازی محدب
بهینهسازی محدب مطالعه کمینهسازی توابع محدب روی مجموعههای محدب است، که دستهای از مسائل را شامل میشود که برای آنها بهینههای محلی، سراسری هستند و الگوریتمهای کارآمدی برای حل آنها وجود دارد.
Definition
مسئله بهینهسازی محدب، یک تابع هدف محدب را تحت محدودیتهای نابرابری محدب و محدودیتهای برابری آفین کمینه میکند؛ مجموعه شدنی محدب است، که تضمین میکند هر کمینه محلی نیز یک کمینه سراسری است.
Scope
این موضوع شامل مجموعهها و توابع محدب، شناسایی و مدلسازی مسائل محدب، برنامهریزی خطی، درجه دوم، مخروطی مرتبه دوم و نیمهمعین، دوگانگی لاگرانژ و شرایط کاروش-کوهن-تاکر برای مسائل محدب، و الگوریتمهای نقطه داخلی و مرتبه اول با تضمینهای پیچیدگی آنها میشود.
Core questions
- چگونه میتوان یک مسئله را به عنوان محدب شناسایی یا بازفرمولبندی کرد؟
- چرا محدب بودن تضمین میکند که بهینههای محلی، سراسری هستند؟
- دوگانگی چه چیزی را در مورد یک مسئله محدب و راهحل آن آشکار میکند؟
- کدام الگوریتمها مسائل محدب را به طور کارآمد و با چه تضمینهایی حل میکنند؟
Key theories
- بهینگی سراسری مسائل محدب
- از آنجا که یک تابع محدب روی یک مجموعه محدب هیچ کمینه محلی کاذبی ندارد، هر نقطه بهینه محلی، بهینه سراسری است، که مسائل محدب را به طور قابل اعتماد قابل حل میکند.
- دوگانگی لاگرانژ و شرایط KKT
- هر مسئله محدب دارای یک مسئله دوگان مرتبط است که گواهیهای بهینگی را ارائه میدهد، و تحت شرایط محدودیت، شرایط کاروش-کوهن-تاکر برای بهینگی لازم و کافی هستند.
- روشهای نقطه داخلی
- روشهای نقطه داخلی مسیری مرکزی را از طریق فضای داخلی منطقه شدنی دنبال میکنند و مسائل محدب از جمله برنامههای نیمهمعین را در زمان چندجملهای اثباتپذیر حل میکنند.
Clinical relevance
بهینهسازی محدب در یادگیری ماشین، پردازش سیگنال و تصویر، کنترل، مالی و طراحی مهندسی بسیار رایج است، زیرا بسیاری از مسائل تخمین و تصمیمگیری را میتوان به عنوان برنامههای محدب مدلسازی کرد و به طور قابل اعتماد در مقیاس بزرگ حل نمود.
History
این حوزه بر تحلیل محدبی که توسط راکفلار در حدود سال ۱۹۷۰ نظاممند شد، استوار است. روش نقطه داخلی کارمارکار در سال ۱۹۸۴ و نظریه بعدی نستروف و نمیروفسکی نشان داد که دستههای وسیعی از مسائل محدب در زمان چندجملهای قابل حل هستند، که رویکرد مدرن و مدلمحور به بهینهسازی محدب را شعلهور ساخت.
Key figures
- R. Tyrrell Rockafellar
- Stephen Boyd
- Yurii Nesterov
- Narendra Karmarkar
Related topics
Seminal works
- boyd2004
- rockafellar1970
Frequently asked questions
- چرا در صورت امکان مدلهای محدب ترجیح داده میشوند؟
- مسائل محدب با تضمین اینکه هر راهحل یافت شده بهینه سراسری است و با الگوریتمهای بالغ و کارآمد همراه هستند. مدلهای غیرمحدب ممکن است حلکنندهها را در بهینههای محلی پایینتر به دام بیندازند، بنابراین بخش زیادی از کارهای کاربردی به بازفرمولبندی مسائل به صورت محدب اختصاص دارد.
- آیا برنامهریزی خطی نوعی بهینهسازی محدب است؟
- بله. یک برنامه خطی، یک تابع هدف خطی را روی یک چندوجهی کمینه میکند، و هم توابع خطی و هم چندوجهی محدب هستند، بنابراین برنامهریزی خطی یک حالت خاص و به ویژه شناخته شده از بهینهسازی محدب است.