رهاسازی محدب

فرض کنید ${\displaystyle f:S\rightarrow R}$ که در آن ${\displaystyle S\subset R^{n}}$ یک مجموعه محدب غیر تهی باشد، آنگاه گوییم تابع ${\displaystyle u:S\rightarrow R}$ رهاسازی محدب ${\displaystyle f}$ است، اگر${\displaystyle u(x)\leq f(x)\forall x\in S}$.

در رهاسازی محدب، هر قید نامحدب با یک قید محدب بصورتی تقریب زده می‌شود تا بتوان مسئله بهینه سازی را به مسئله بهینه‌سازی محدب تبدیل کرد.

ایده اصلی رهاسازی محدب

در اغلب مسائل بهینه سازی، بعلت پیچیدگی محاسباتی که دارند، عملاً بهینه سراسری به دست نمی‌دهند. بنابراین نیاز است تا با یک تقریب مناسب آن‌ها را به مسائل محدب تقریب زد و یک پاسخ قابل قبول با سادگی محاسبات به دست آورد. یکی از روش‌های متداول انجام این کار، رهاسازی محدب است.

رهاسازی معمولاً با چشم پوشی از برخی قیود مسئله اصلی، یعنی بسط تابع هدف به یک فضای شدنی بزرگتر انجام می‌شود. بنابراین پاسخ به دست آمده، کران بالا یا پایین تری از مسئله اصلی خواهد بود.

مثلاً در مسئله حداقل سازی

$${\displaystyle minf(x)}$$

$${\displaystyle s.t.g(x)\geq 0}$$

ممکن است ${\displaystyle f(x)}$ و فضای شدنی Ω غیر محدب باشند. در رهاسازی محدب، یک مسئله جدید بفرم زیر تشکیل می دهیم:

$${\displaystyle min{\tilde {f}}(x)}$$

$${\displaystyle s.t.{\tilde {g}}(x)\geq 0}$$

که در آن  ${\displaystyle {\tilde {f}}(x)}$ و فضای شدنی ${\displaystyle {\tilde {\Omega }}}$ محدب هستند[1].

تبدیل مسئله نامحدب به مسئله محدب با رهاسازی

مسئله زیر را در نظر بگیرید:

$${\displaystyle minf_{0}(x)}$$

$${\displaystyle s.t.f_{i}(x)\leq 0,i=1,...,m}$$

$${\displaystyle h_{i}(x)=0}$$

تابع  ${\displaystyle h(x)}$ محدب است، به همین علت مسئله نامحدب است. برای حل آن به روش رهاسازی محدب، قید تساوی را به قید نامساوی تبدیل می کنیم، در نتیجه مسئله به محدب تبدیل می‌شود[2]:

$${\displaystyle minf_{0}(x)}$$

$${\displaystyle s.t.f_{i}(x)\leq 0,i=1,...,m}$$

$${\displaystyle h_{i}(x)\leq 0}$$

رهاسازی در برنامه‌ریزی خطی

رهاسازی برنامه‌ریزی خطی یک روس استاندارد برای طراحی الگوریتم‌های تقریب در مسائل بهینه‌سازی پیچیده است. در این کاربرد مفهومی به نام فاصله درستی تعریف می‌شود، که حداکثر نسبت بین حل کیفی برنامه و حل رهاسازی آن است[3].

مثال: رهاسازی در برنامه‌ریزی خطی بولین

در مسئله برنامه‌ریزی خطی بولین بفرم زیر نوشته می‌شود:

$${\displaystyle minc^{T}x}$$

$${\displaystyle s.t.Ax\preceq b}$$

$${\displaystyle x\in \{0,1\}}$$

که در آن قید

$${\displaystyle x\in \{0,1\}}$$

حل مسئله را مشکل می‌کند. برای حل آن می‌توان به جای قید فوق متغیر را در بازه ${\displaystyle 0\leq x\leq 1}$ تعریف کرد و مسئله را به صورت زیر بازنویسی کرد:

$${\displaystyle minc^{T}x}$$

$${\displaystyle s.t.Ax\preceq b}$$

$${\displaystyle 0\leq x\leq 1}$$

حل این مسئله کران پایین تری از حل مسئله اصلی ارائه می دهد زیرا ناحیه شدنی آن شامل ناحیه شدنی مسئله اصلی می‌باشد.

رهاسازی لاگرانژی

در زمینه بهینه سازی، رهاسازی لاگرانژی، یک روش رهاسازی است که یک مسئله پیچیده بهینه‌سازی مقید را به یک مسئله ساده‌تر تبدیل می‌کند. حل مسئله رهاسازی شده، تقریبی از مسئله اصلی خواهد بود.

در این روش از ضرایب لاگرانژی برای وزن دهی به قیود استفاده می‌کنند و این قیود وزن دار شده را به عنوان هزینه، به تابع هدف می افزایند و از این تابع هدف جدید در بهینه‌سازی استفاده می‌کنند. در عمل این مسئله رها شده حل ساده‌تری از مسئله اصلی دارد. به تابع هدف رهاسازی شده را تابع لاگرانژی و به حداکثرسازی آن، مسئله دوگانی گفته می‌شود[4].

منابع

1. Li، Li (۲۰۱۵). Selected Applications of Convex Optimization. Springer.
2. Boyd، Stephan (۲۰۰۴). convex optimization. newyork: cambridge.
3. «Linear programming relaxation».
4. «Lagrangian relaxation».

en:Convex optimization en:Mathematical optimization