برنامهریزی غیرخطی
برنامهریزی غیرخطی بهینهسازی یک تابع هدف غیرخطی هموار را با در نظر گرفتن محدودیتهای غیرخطی انجام میدهد و هم نظریه بهینگی و هم الگوریتمهایی را که راهحلها را محاسبه میکنند، پوشش میدهد.
Definition
یک برنامه غیرخطی، یک تابع هدف احتمالاً غیرخطی را در یک مجموعه امکانپذیر که توسط محدودیتهای تساوی و نابرابری غیرخطی تعریف شده است، کمینه میکند؛ برخلاف مسائل محدب، ممکن است دارای چندین بهینه محلی باشد، بنابراین بیشتر روشها به دنبال نقاطی هستند که شرایط بهینگی لازم را برآورده میکنند.
Scope
این موضوع شامل کمینهسازی نامقید، استراتژیهای جستجوی خطی و ناحیه اعتماد، روشهای گرادیان، نیوتن و شبهنیوتن، شرایط بهینگی مرتبه اول و دوم، شرایط کاروش-کوهن-تاکر و صلاحیتهای محدودیت، و روشهای مقید مانند جریمه، لاگرانژین افزوده، و برنامهریزی ترتیبی درجه دوم است.
Core questions
- چه شرایطی یک بهینه محلی از یک مسئله غیرخطی مقید را مشخص میکند؟
- روشهای نزولی چگونه یک نقطه ایستایی از یک مسئله نامقید را پیدا میکنند؟
- محدودیتها چگونه در الگوریتمهای تکراری گنجانده میشوند؟
- چه زمانی میتوان به یک بهینه محلی محاسبه شده به عنوان یک بهینه سراسری اعتماد کرد؟
Key theories
- شرایط بهینگی
- شرایط کاروش-کوهن-تاکر مرتبه اول و شرایط انحنای مرتبه دوم، بهینههای محلی مسائل مقید را تحت صلاحیتهای محدودیت مناسب مشخص میکنند.
- روشهای نزولی و از نوع نیوتن
- روشهای گرادیان، نیوتن و شبهنیوتن جهتهای نزولی را تولید میکنند و از جستجوهای خطی یا نواحی اعتماد برای همگرایی به نقاط ایستایی استفاده میکنند، با بهروزرسانیهای شبهنیوتن که انحنا را با هزینه کمتری تخمین میزنند.
- الگوریتمهای بهینهسازی مقید
- روشهای جریمه، لاگرانژین افزوده، و برنامهریزی ترتیبی درجه دوم مسائل مقید را به دنبالهای از مسائل سادهتر تبدیل میکنند و محدودیتهای تساوی و نابرابری را به طور سیستماتیک مدیریت میکنند.
Clinical relevance
برنامهریزی غیرخطی در هر جایی که اهداف یا محدودیتها غیرخطی باشند، از جمله برازش مدل و آموزش مدلهای آماری و یادگیری ماشین، طراحی مهندسی، کنترل بهینه، و تخمین پارامتر در علوم مختلف استفاده میشود.
History
شرایط کاروش-کوهن-تاکر، که در سال ۱۹۵۱ تدوین شد و کاروش در سال ۱۹۳۹ آن را پیشبینی کرده بود، ضربکنندههای لاگرانژ را به محدودیتهای نابرابری تعمیم داد و نظریه غیرخطی مقید را پایهگذاری کرد. روشهای شبهنیوتن، لاگرانژینهای افزوده، و برنامهریزی ترتیبی درجه دوم در طول اواخر قرن بیستم توسعه یافتند و به ابزار محاسباتی استاندارد تبدیل شدند.
Key figures
- Harold Kuhn
- Albert Tucker
- Isaac Newton
- Magnus Hestenes
Related topics
Seminal works
- nocedal2006
- bertsekas1999
Frequently asked questions
- چرا برنامهریزی غیرخطی دشوارتر از برنامهریزی خطی است؟
- مسائل غیرخطی میتوانند دارای نواحی امکانپذیر منحنی و چندین بهینه محلی باشند، بنابراین معمولاً تضمینی وجود ندارد که یک راهحل محاسبه شده بهترین راهحل سراسری باشد، و بهینهها لزوماً در رئوس قرار نمیگیرند. الگوریتمها باید به اطلاعات محلی مانند گرادیانها و انحنا تکیه کنند.
- روش شبهنیوتن چیست؟
- این یک روش تکراری است که گام نیوتن را بدون محاسبه کامل ماتریس مشتق دوم تخمین میزند و اطلاعات انحنا را از گرادیانهای متوالی جمعآوری میکند. روشهایی مانند BFGS همگرایی سریع را با هزینه بسیار کمتر از گامهای دقیق نیوتن به دست میآورند.