بهینه‌سازی محدب: تفاوت میان نسخه‌ها

<math>\min f_o(x)\quad s.t. \quad f_i(x)\leq0 \quad i=1,...,m \quad, Ax=b</math>

 

 

مهمترین اختلاف بین بهینه سازی محدب و شبه محدب این است که مسائل بهینه سازی شبه محدب می توانند جواب های بهینه محلی داشته باشد که بهینه (سراسری) نیستند. این پدیده می تواند جتی در  ساده ترین مورد کمینه سازی بدون قید یک تابع شبه محدب روی R دیده شود.

 

 

شدنی باشد سپس خواهیم داشت <math>p* \leq t</math>. در طرف مقابل اگر مسئله فوق نشدنی باشد می توانیم نتیجه بگیریم <math>p*\geq t</math>. مسئله فوق یک مسئله امکان سنجی محدب است چون قیود نامساوی محدب هستند و قید تساوی نیز خطی است. بنابراین می توانیم بررسی کنیم مقدار آیا <math>p*</math> کمتر یا بیشتر از مقدار t ای است که با حل مسئله امکان سنجی فوق به دست می آید. اگر مسئله امکان سنجی شدنی باشد پس داریم <math>p* \leq t</math> و هر نقطه شدنی مثل x برای مسئله شبه محدب نیز شدنی است و رابطه <math>f_0(x)\leq t</math> را ارضا می کند. اگر مسئله امکان سنجی محدب نشدنی باشد سپس می دانیم <math>p*\geq t</math>.

<references />