روش مانع (Barrier Function Methods / Interior Point Methods)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش مانع (Barrier Function Methods / Interior Point Methods) :
روش های نقاط داخلی با استفاده از توابع مانع
توضیح ساده: روش های مانع (یا روش های نقاط داخلی) یک خانواده قدرتمند از الگوریتم ها برای حل مسائل بهینه سازی مقید (خطی و غیرخطی) هستند. برخلاف روش های جریمه خارجی که از خارج ناحیه شدنی شروع می کنند، روش های مانع با یک نقطه داخلی (داخل ناحیه شدنی) شروع کرده و با استفاده از یک تابع مانع (که در مرز ناحیه به بی نهایت می رود)، از خروج از ناحیه جلوگیری می کنند. با کاهش تدریجی پارامتر مانع، جواب به سمت جواب بهینه (که روی مرز قرار دارد) حرکت می کند. روش های نقاط داخلی برای برنامه ریزی خطی و درجه دوم بسیار کارآمد هستند و برای مسائل غیرخطی نیز تعمیم داده شده اند.
شرح گام به گام: برای مسئله minimize f(x) subject to gᵢ(x) ≥ 0:
۱. یک تابع مانع انتخاب کنید، مثلا تابع مانع لگاریتمی:
\[ B(x; \mu) = f(x) - \mu \sum_i \ln(g_i(x)) \]۲. با یک نقطه شروع شدنی x₀ (که gᵢ(x₀) > 0) و μ₀ > 0 شروع کنید.
۳. برای k = ۰,۱,۲,...:
- مسئله نامقید minimize B(x; μₐ) را با روش نیوتن (با توجه به اینکه در داخل ناحیه هستیم) حل کنید و xₐ* را بیابید.
- μₐ₊₁ = c μₐ با c<1 (مثلا ۰.۲) کاهش دهید.
- xₐ* را به عنوان نقطه شروع برای تکرار بعدی استفاده کنید.
۴. با کاهش μ به سمت صفر، دنباله xₐ* به جواب مسئله مقید همگرا می شود.
در عمل، از روش های پیشرفته تری مانند روش پیش بینی-تصحیح (Predictor-Corrector) برای کارایی بیشتر استفاده می شود.
مثال عددی: برنامه ریزی خطی. روش نقاط داخلی (مثل روش کرمارکر) با حرکت در داخل ناحیه شدنی (جایی که قیود نامساوی به صورت اکید برقرارند) و با استفاده از جهت های نیوتن، به جواب بهینه همگرا می شود. این روش ها برای مسائل بزرگ بسیار سریع تر از روش سیمپلکس هستند.
مزایا: کارآمد برای مسائل بزرگ، همگرایی سریع (معمولا چند ده تکرار)، قابل تعمیم به مسائل غیرخطی.
معایب: پیاده سازی پیچیده، نیاز به یک نقطه شروع داخلی، برای مسائل با قیود برابری نیز باید اصلاح شود.
کاربردها: در برنامه ریزی خطی و غیرخطی، در کنترل بهینه، در یادگیری ماشین.
نکته: روش نقاط داخلی انقلابی در حل مسائل LP ایجاد کرد.
