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

و برای هر <math>x</math>، <math>\phi_t(x)</math> یک تابع غیر صعودی از <math>t</math> است. فرض کنید <math>p^*</math> جواب بهینه مسئله بهینه‌سازی شبه محدب باشد.

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