رهاسازی محدب

فرض کنید f : S → R {\displaystyle f:S\rightarrow R} که در آن S ⊂ R n {\displaystyle S\subset R^{n}} یک مجموعه محدب غیر تهی باشد، آنگاه گوییم تابع u : S → R {\displaystyle u:S\rightarrow R} رهاسازی محدب f {\displaystyle f} است، اگر u ( x ) ≤ f ( x ) ∀ x ∈ S {\displaystyle u(x)\leq f(x)\forall x\in S} .
در رهاسازی محدب، هر قید نامحدب با یک قید محدب بصورتی تقریب زده می شود تا بتوان مسئله بهینه سازی را به مسئله بهینه سازی محدب تبدیل کرد.
در اغلب مسائل بهینه سازی، بعلت پیچیدگی محاسباتی که دارند، عملاً بهینه سراسری به دست نمی دهند. بنابراین نیاز است تا با یک تقریب مناسب آن ها را به مسائل محدب تقریب زد و یک پاسخ قابل قبول با سادگی محاسبات به دست آورد. یکی از روش های متداول انجام این کار، رهاسازی محدب است.
رهاسازی معمولاً با چشم پوشی از برخی قیود مسئله اصلی، یعنی بسط تابع هدف به یک فضای شدنی بزرگتر انجام می شود. بنابراین پاسخ به دست آمده، کران بالا یا پایین تری از مسئله اصلی خواهد بود.