بخشی از مقاله
چکیده
در این مقاله الگوریتمی مبتنی بر مفهوم زیرگرادیان برای حل مسایل بهینه سازی ناهموار مورد بررسی قرار گرفته است. این الگوریتم برای کمینه سازی موضعی توابع لیپ شیتز ارایه شده است. در این الگوریتم جهت کاهشی با حل دستگاه نامعادلات خطی محاسبه شده و همگرایی الگوریتم برای توابع شبه مشتق پذیر نیمه هموار نیز بررسی شده است. نتایج عددی با هر دو تابع هدف منظم و نامنظم ارایه گردیده و برای سرعت همگرایی بهتر زیرگرادیان تصویری در الگوریتم جهت کاهشی با روش مستقیم با استفاده از قضایای مربوطه جایگزین شده است. الگوریتم پیشنهاد شده با دو نمونه متفاوت آزمون شده و با به کارگیری نتایج عددی مقایسه شده است، نتایج حاصل برتری الگوریتم پیشنهاد شده را نسبت به روش زیرگرادیان تقریبی نشان می دهد.
١ مقدمه
برای حل مسایل بهینه سازی ناهموار از تعمیم تعریف های جدید مشتق استفاده شده است. مفهوم زیرگرادیان که با تعریف مجموعه ای از بردارها معرفی می شود، برای توابع محدب اولین بار به عنوان تعمیمی برای مشتق اول طرح و بررسی شد. ضعف عمده در زیرمشتق، بزرگ بودن مجموعه تعریف شده در آن است و آن هم ناشی از نوع تعریف مشتق سویی است. برای رفع این مشکل تعریف های جدیدی از مشتق سویی ارایه و بر اساس آنها تعمیم های جدیدی از مشتق مطرح شده است که از شبه مشتق دمیانوف-رابینوف ١ و زیرمشتق میشل-پنو ٢ می توان به عنوان مهم ترین این تعمیم ها نام برد. اما زیرمشتق، تعمیمی از مشتق است که به راحتی قابل پیاده سازی عددی می شود، تعریف های معرفی شده برای تعمیم های مشتق تنها برای توابع لیپ شیتز موضعی ارایه شده اند.
در دهه های اخیر تلاش برای تعمیم تعریف مشتق به توابع نیم پیوسته پایینی ٣ با استفاده از تعریف گراف تابع ادامه یافته است. اکثر الگوریتم هایی که برای مسایل بهینه سازی ناهموار کارایی دارند از الگوریتم های مرتبه اول استفاده می کنند که این الگوریتم ها نیز مشتق اول توابع را به کار می گیرند و بدین منظور ابتدا توابع به صورت تقریبی هموارسازی می شود. برای نمونه می توان از الگوریتم شور ۴ که برای حل مسایل بهینه سازی محدب به کار می رود و الگوریتم های گرادیان گسسته ۵ و زیرگرادیان تقریبی ۶ که برای حل مسایل بهینه سازی نیمه هموار ٧ به کار می روند، نام برد.
٢ نتایج اصلی
گرادیان گسسته نمونه ای از تفاضلات متناهی برای تخمین زیرگرادیان ها است. از طرفی گرادیان گسسته نسبت به یک جهت تعریف می شود و این موجب می گردد که یک الگوریتم کارا برای محاسبه جهت شدنی برای یک تابع به دست آورد. البته می توان با استفاده از زیرگرادیان ها تخمینی برای ابر مشتقات یافت که فقط از دیدگاه نظری قابل اهمیت اند. برای محاسبه جهت شدنی برای یک نقطه داده شده فقط به محاسبه تعدادی از زیرگرادیان ها در آن نقطه نیاز است و نشان داده می شود که این محاسبات متناهی اند.
برای مطالعه بهینه سازی توابع لیپ شیتز نیاز به پیوستگی نگاشت زیرمشتقات و شبه مشتقات است. با استفاده از روش گرادیان گسسته یک تقریب پیوسته برای ابرمشتقات و شبه مشتقات ارایه شده است. سپس با استفاده از تقریب های پیوسته برای زیرمشتقات و ابرمشتقات، روش های عددی برای حل مسایل مختلف کمینه سازی ناهموار به کار برده شده است، این روش ها به دسته ای از روش های بهینه سازی مرتبط هستند که بدون استفاده از مشتق به محاسبه نقطه بهینه تابع می پردازند.
