مساله بهینه سازی

بهینه سازی به  فرایندی گفته می شود که در آن بهترین جواب (با توجه به مجموعه‌ای از قیود) از میان مجموعه‌ای از جواب‌های ممکن، برای یک مسأله خاص انتخاب می‌شود

1. اجزای مساله بهینه سازی
2. بهینه سازی محلی و سراسری
   1_2. بهینه سازی محلی
   2_2. بهینه سازی سراسری
3. بهینه سازی محدب و غیر محدب
   1_3. بهینه محدب
   2_3. بهینه غیر محدب
   3_3. بهينه سازي يکنوا
4. انواع مساله بهینه سازی (به زودي اضافه مي شود)
   1_3. بهینه سازی گسسته
   2_3. بهینه سازی پیوسته
5. انواع تابع هدف در بهینه سازی
6. قیود در بهینه سازی

اجزای مساله بهینه سازی

هر مساله بهینه سازی شامل قسمت های زیر می باشد:

• هدف (Objective): مساله بهینه سازی شامل کمینه یا بیشینه کردن یک یا چند تابع هدف (multi objective) می باشد در برازش تابع ، هدف کم کردن خطا داده‌های پیش‌بینی شده (Predicted Data) از مقدار داده‌های مشاهده شده (Observed Data) می باشد.
• متغیرها (Variables):مؤلفه‌هایی بهینه سازی هستند که قرار است مقادیر مناسبی برای آن‌ها یافت شود. برای مثال بالا مقادیر پیش بینی شده متغییر های مساله می باشند.
• قیود (Constraints): توابعی هستند که روابط میان متغیرها را نشان می‌دهد. بنابراین مطابق قیود مساه تنها جواب هایی لحاظ می شود ک قیود مساله را براورده سازند. قیود به دو دسته قیود برابری‌ (Equalities) و قیود نابرابری‌ (Inequalities) دسته بندی می شوند.

بهینه سازی محلی و سراسری

درحالت کلی مساله بهینه سازی به دو نوع بهینه سازی محلی (Local Optimization) و بهینه سازی سراسری (Global Optimization) دسته بندی می شود.

بهینه سازی محلی

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

بهینه سازی سراسری

بهینه سازی Global پیدا کردن بهینه ترین حالت مجموعه ورودی هاست. (در مسائلی که تعداد بهینه های محلی بیشتر از یکی می باشد). بهینه سازی سراسری، شاخه ای از ریاضیات کاربردی و تجزیه و تحلیل عددی است که سعی می کند مینیمم ها یا ماکزیمم های یک تابع را در یک مجموعه معین پیدا کند. همچنین به دلیل تمرکز بر یافتن مقدار مینیمم یا ماکزیمم سراسری در مجموعه داده شده، از بهینه سازی محلی متمایز است.
یافتن مینیمم محلی دلخواه با استفاده از روش های کلاسیک بهینه سازی محلی نسبتاً ساده است. لیکن یافتن مینیمم سراسری یک تابع بسیار دشوارتر است. روش های تحلیلی غالباً کاربردی نیستند و استفاده از استراتژی های حل عددی اغلب منجر به چالش های بسیار سخت می شود.

بهینه سازی محدب وغیر محدب

از تعاریف گفته شده می توان چنین استنباط کرد که گاهی جواب مساله بهینه سازی بهینه محلی (Local Optimum) بوده یا بهینه سراسری (Global Optimum) می باشد. با توجه به پیش تعاریف گفته شده به دو دسته بهینه سازی محدب و غیرمحدب می پردازیم.

بهینه سازی محدب

در مسائل «بهینه سازی محدب» (Convex Optimization)، در صورتی که یک جواب بیشینه محلی یا کمینه محلی برای مسأله وجود داشته باشد، این جواب، بهینه سراسری مسأله مورد نظر نیز خواهد بود.

 ویژگی اصلی مسایل بهینه سازی محدب، سرعت روشهای عددی در حل آنهاست و ضمنا جواب به دست آمده توسط این روشها جواب بهینه عمومی است.
بسیار مسایل مهندسی در شاخه های مختلف قابلیت تبدیل شدن به مساله بهینه سازی ریاضی دارند. اعم از مهندسی برق مخابرات الکترونیک قدرت برق پردازش تصویر و سیگنال و مهندسی صنایع و مکانیک و حتی اقتصاد . لیکن اگر این مسایل بتوانند به گونه ای به مساله محدب تبدیل شوند زمان حل آنها بسیار نسبت به حالت غیر محدب کاهش می یابد. ابزارهای ریاضی زیادی برای حل مسایل محدب وجود دارند.
از بین مسایل محدب، دسته ای خاص از مسایل محدب وجود دارند که در حالت کلی روش های سریع تر و موثرتری برای حل آنها وجود دارد. اين روش ها نسبت به روشهای برنامه ریزی برای حل مسایل محدب برتری از نظر سرعت دارند. سه گونه بسیار مهم این مسایل عبارت اند از
۱- مسایل بهینه سازی مخروط درجه دوم
۲- مسایل بهینه سازی مخروط نیمه معین مثبت
۳- مسایل بهینه سازی برنامه ریزی هندسی

این سه دسته مساله در علم بهینه سازی به علت سرعت همگرایی solver هایشان آنقدر مهم و کلیدی هستند که به مسایل محدب منظم معروف هستند و همه تلاش می کنند که مسایل خود را علاوه بر تبدیل به فرم محدب، به فرم منظم نیز تبدیل کنند که از سرعت حل بالای آنها بهره ببرند.حتی بسیاری نیز تلاش می کنند مستقیم مسایل غیر محدب را با فرم منظم تقریب بزنند.
حل کننده های مسایل منظم به صورت محصولات تجاری و مجانی موجودند و تعدادی از مهمترینان آنها sedumi و sdpt3 و gurobi و glpk است. هدف آن پیدا کردن نقطه بهینه سراسری مسایل بهینه سازی است

بهینه سازی غیر محدب

در یک مسأله بهینه سازی «غیر محدب» (Non-Convex) برخلاف تابع هدف مسأله بهینه سازی محدب، ممکن است بیش از یک «کمینه محلی» (Local Minimum) یا «بیشینه محلی» (Local maximum) در مسأله وجود داشته باشد.

بهینه سازی یکنوا (مونوتونیک):

همانطور که گفته شد مسائل به دو دسته محدب و نامحدب تقسیم می شوند. در صورت محدب بودن، روش هایی همچون تقريب دروني برای دستیابی به راه حل سراسری این مسائل مطرح می شود. لیکن دسته عمده ای از مسائلِ نامحدب، دارای ویژگی یکنوایی هستند و با بهره گیری از روش ها و الگوریتم های موجود از جمله الگوریتم پلی بلاک، می توان به راه حل بهینه سراسری در اینگونه از مسائل دست یافت.
تکنیک های اخیر بهینه سازی به طور عمده بر محدب بودن فرمول بندی مسئله متکی است. در حالی که بسیاری از توابع در مدل سازی ریاضی سیستم های دنیای واقعی در طیف وسیعی از فعالیتها، از جمله اقتصاد و مهندسی، با اینکه ماهیت غیر محدب دارند ولی نسبت به متغیرهای مسئله دارای ویژگی یکنوایی می باشند.
برای درک مزیت ساختار یکنوا، باید در نظر داشت که از آنجا که اطلاعات محلی به طور کلی برای تأیید بهینه سراسری یک راه حل کافی نیست، باید جستجوی بهینه سراسری روی کل مجموعه جواب انجام شود.
استفاده اصولی از خواص یکنوایی، می تواند چالش دستیابی به راه حل بهینه سراسری مسائل را تا حد قابل توجهی کاهش دهد و این در واقع ایده اصلی نظریه بهینه سازی مونوتونیک است..