KKT و روش‌های interior-point؛ وقتی قیود وارد بازی می‌شوند

از لاگرانژین و شرایط KKT تا ایده barrier method؛ ریاضیات اصلی پشت Convex QP Solver را مرحله‌به‌مرحله می‌خوانیم.

بهینه‌سازی و متاهیوریستیک‌هاپیشرفته

مشاهده آموزش‌های دیگر

هدف یادگیری

شرایط KKT را برای یک مسئله مقید بنویسید، نقش multiplierها را بفهمید و ایده interior-point را توضیح دهید.

پیش‌نیازها

مشتق چندمتغیره
جبر خطی مقدماتی
مبانی بهینه‌سازی

مسئله مقید

بهینه‌سازی مقید

min_{x} f (x) s.t. g_{i} (x) \leq 0, h_{j} (x) = 0

در مسئله بدون قید، نقطه داخلی معمولاً با ∇f=0 بررسی می‌شود. با وجود قید، هندسه ناحیه مجاز وارد شرط بهینگی می‌شود.

لاگرانژین

Lagrangian

L (x, λ, ν) = f (x) + \sum_{i}^{} λ_{i} g_{i} (x) + \sum_{j}^{} ν_{j} h_{j} (x)

ضرایب λ برای قیود نابرابری و ν برای قیود تساوی وارد مدل می‌شوند و در شرایط مناسب، اطلاعات لازم برای نقطه بهینه را حمل می‌کنند.

شرایط KKT

Primal feasibility: قیود اصلی برقرارند.
Dual feasibility: λ_i برای قید نابرابری نامنفی است.
Stationarity: گرادیان Lagrangian نسبت به x صفر است.
Complementary slackness: λ_i g_i(x)=0.

خلاصه KKT

\nabla_{x} L = 0, g_{i} (x) \leq 0, λ_{i} \geq 0, λ_{i} g_{i} (x) = 0

مثال یک‌بعدی

یک مسئله ساده

\min_x x^2\quad\text{s.t.}\quad x\ge1

جواب بدون قید x=0 است، اما قید اجازه آن را نمی‌دهد. جواب مقید x*=1 است و قید فعال است.

ایده barrier

یک روش interior-point می‌تواند با افزودن جمله barrier، تکرارها را داخل ناحیه مجاز نگه دارد. با کاهش μ، مسئله barrier به مسئله اصلی نزدیک‌تر می‌شود.

Barrier formulation

min_{x} f (x) - μ \sum_{i}^{} \log (- g_{i} (x))

ارتباط با Convex QP Solver

هسته این پروژه از primal-dual interior-point و Mehrotra predictor-corrector استفاده می‌کند. بنابراین KKT از یک شرط کتاب درسی به یک سیستم عددی واقعی تبدیل می‌شود.

تمرین

برای minimize x² با قید x≥2 شرایط KKT را بنویسید.
مشخص کنید کدام قید در جواب فعال است.
تفاوت stationarity و feasibility را با یک مثال توضیح دهید.

پروژه مرتبط

Convex Quadratic Programming Solver

KKT، residualها و interior-point در هسته solver استفاده شده‌اند.

باز کردن منبع

راهکارهای مرتبط

مدل‌سازی، الگوریتم و بهینه‌سازی

با یک مسئله بهینه‌سازی مقید روبه‌رو هستید؟

می‌توان از مدل و قیود شروع کرد و تا روش عددی و پیاده‌سازی ادامه داد.

گفت‌وگو درباره مسئله