مسئلهٔ بهینه سازی محدب یا بهینه سازی کوژ ( به انگلیسی: Convex Optimization ) به یافتن مقدار حداقل یک تابع محدب ( یا حداکثر یک تابع مقعر ) از بین مجموعه ای محدب گفته می شود. مهمترین مزیت این نوع مسائل بهینه سازی در این است که هر نقطهٔ بهینهٔ محلی یک نقطه بهینهٔ سراسری نیز است و هر الگوریتم بهینه سازی که یک نقطه بهینهٔ محلی را یافت در حقیقت یک نقطه بهینهٔ سراسری را یافته است. [ ۱]
مسئله بهینه سازی شبه محدب، فرم استاندارد زیر را دارد:[ ۲]
min f o ( x ) s . t . f i ( x ) ≤ 0 i = 1 , . . . , m , A x = b
که قیود نامساوی محدب هستند و تابع هدف نیز شبه محدب می باشد ( زمانیکه مسئله محدب باشد تابع هدف نیز محدب است ) . قیود شبه محدب می توانند با معادل محدب شان جایگزین شوند. در این نوشتار بعضی از اختلافات پایه ای بین مسائل بهینه سازی محدب و شبه محدب نشان داده خواهد شد، همچنین نشان داده می شود حل یک مسئله بهینه سازی شبه محدب چگونه می تواند به حل چند دنباله از مسائل بهینه سازی محدب کاهش یابد.
مهمترین اختلاف بین بهینه سازی محدب و شبه محدب این است که مسائل بهینه سازی شبه محدب می توانند جواب های بهینه محلی داشته باشد. این پدیده می تواند حتی در ساده ترین مورد، کمینه سازی بدون قید یک تابع شبه محدب روی R دیده شود.
برای یک مسئله بهینه سازی محدب، x بهینه است اگر:
▽ f 0 ( x ) T ( y − x ) ≥ 0 f o r a l l y ∈ X
انواع شرایط بهینگی برای مسائل بهینه سازی شبه محدب با توابع هدف مشتق پذیر برقرار است. X را فضای شدنی برای مسئله بهینه سازی شبه محدب در نظر بگیرید، در این صورت x بهینه است اگر:
x ∈ X , ▽ f 0 ( x ) T ( y − x ) > 0 f o r a l l y ∈ X
دو تفاوت مهم بین معیار فوق و معیار بهینگی برای مسائل محدب وجود دارد:
۱ - معیار مسائل شبه محدب برای بهینگی پاسخ شرط کافی است و برقراری آن برای نقطه بهینه ضروری نیست اما برقراری رابطه فوق برای مسائل محدب شرط لازم و کافی برای بهینگی x می باشد.
۲ - معیار فوق نیازمند این است که گرادیان تابع هدف غیر صفر باشد در حالی که در رابطه بهینگی مسائل محدب اینگونه نیست، در واقع زمانی که ▽ f 0 ( x ) = 0 ، معیار بهینگی مسائل محدب صادق است و x نقطه بهینه است.
یک روش کلی برای مسائل بهینه سازی شبه محدب وابسته به نمایش مجموعه های زیرسطحی از یک تابع شبه محدب است. ϕ t : R n → t ∈ R را به عنوان مجموعه ای از توابع محدب که در رابطه زیر صدق می کنند در نظر بگیرید. [ ۳]
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفمسئله بهینه سازی شبه محدب، فرم استاندارد زیر را دارد:[ ۲]
min f o ( x ) s . t . f i ( x ) ≤ 0 i = 1 , . . . , m , A x = b
که قیود نامساوی محدب هستند و تابع هدف نیز شبه محدب می باشد ( زمانیکه مسئله محدب باشد تابع هدف نیز محدب است ) . قیود شبه محدب می توانند با معادل محدب شان جایگزین شوند. در این نوشتار بعضی از اختلافات پایه ای بین مسائل بهینه سازی محدب و شبه محدب نشان داده خواهد شد، همچنین نشان داده می شود حل یک مسئله بهینه سازی شبه محدب چگونه می تواند به حل چند دنباله از مسائل بهینه سازی محدب کاهش یابد.
مهمترین اختلاف بین بهینه سازی محدب و شبه محدب این است که مسائل بهینه سازی شبه محدب می توانند جواب های بهینه محلی داشته باشد. این پدیده می تواند حتی در ساده ترین مورد، کمینه سازی بدون قید یک تابع شبه محدب روی R دیده شود.
برای یک مسئله بهینه سازی محدب، x بهینه است اگر:
▽ f 0 ( x ) T ( y − x ) ≥ 0 f o r a l l y ∈ X
انواع شرایط بهینگی برای مسائل بهینه سازی شبه محدب با توابع هدف مشتق پذیر برقرار است. X را فضای شدنی برای مسئله بهینه سازی شبه محدب در نظر بگیرید، در این صورت x بهینه است اگر:
x ∈ X , ▽ f 0 ( x ) T ( y − x ) > 0 f o r a l l y ∈ X
دو تفاوت مهم بین معیار فوق و معیار بهینگی برای مسائل محدب وجود دارد:
۱ - معیار مسائل شبه محدب برای بهینگی پاسخ شرط کافی است و برقراری آن برای نقطه بهینه ضروری نیست اما برقراری رابطه فوق برای مسائل محدب شرط لازم و کافی برای بهینگی x می باشد.
۲ - معیار فوق نیازمند این است که گرادیان تابع هدف غیر صفر باشد در حالی که در رابطه بهینگی مسائل محدب اینگونه نیست، در واقع زمانی که ▽ f 0 ( x ) = 0 ، معیار بهینگی مسائل محدب صادق است و x نقطه بهینه است.
یک روش کلی برای مسائل بهینه سازی شبه محدب وابسته به نمایش مجموعه های زیرسطحی از یک تابع شبه محدب است. ϕ t : R n → t ∈ R را به عنوان مجموعه ای از توابع محدب که در رابطه زیر صدق می کنند در نظر بگیرید. [ ۳]
wiki: بهینه سازی محدب