تحقیق مقاله بهینه سازی محدب

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

بهینه سازی محدب یک خرده زمینه از بهینه سازی ریاضیات می باشد. یک فضای برداری حقیقی X

با بر آمدگی با هم ،تابع واقعی ارزش گذاری شده F  : X→R 

تعیین شده تحت زیرمجموعه محدب X  از  X ،مسئله یافتن x* در X برای وضعیتی که مقدار f(x) کمترین باشد.تحدب  X و F ابزار قدرتمند آنالیز تحدبی را قابل کاربرد می کند.قضیه Hahn-Banach و تئوری

خرده گرادیان ها منجر به حالات کافی ومورد نیاز تئوری در حالت کامل واختصاصا قانع کننده برای بهینه سازی  می شود ،یک تئوری دوگانه و قابل مقایسه در تمتمیت با آن برای برنامه ریزی خطی ، وروش های موثر محاسبه ای .بهینه سازی محدب دارای کاربردهایی در حوزه وسیعی از رشته های علمی است ،که شامل

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

تئوری

اظهارات ذیل راجع به مسائل بهینه سازی تحدبی درست می باشند:

اگر یک کمینه عمومی وجود داشته باشد ،پس یک کمینه جهانی می باشد.

سری همه کمینه های جهانی محدب هستند.

اگر تابع صرفا محدب است ،پس حداکثر یک کمینه وجود خواهد داشت.

قالب کاری تئوریک برای بهینه سازی تحدبی واقیت های بالا را در تقابل با تفکرات ناشی از آنالیز تحدبی مانند Hilbert projection theorem,the separating hyperplane theorem,and Farkas`s lemma استفاده میشود.

قالب استاندارد

قالب استاندارد ابتدایی ترین ومعمول ترین فرم تشریح یک مسئله بهینه سازی تحدبی می باشد و از

3 بخش زیر تشکیل شده است :

یک تابع محدب f0(x) : Rn→R  تا اینکه تحت متغیر x کمینه شود.

محدودیت های غیر یکنواخت فرم fi(x) ≤0  ،جایی که توابع مذکور محدب باشند.

محدودیت های یکنواخت فرم hi(x) = 0  ،جایی که توابع مذکور متناهی باشند.در عمل ،لغات

خطی  ومتناهی در حالت کلی به برابری می کنند وبسیاری اوقات با فرم Ax = b بیان می شود،جایی که A یک ماتریکس  و b  یک گره می باشند.

یک مسئله بهینه سازی تحدبی این چنین نوشته می شود

کمینه کردن f0(x)  در ارتباط با

fi(x) ≤ 0,       i = 1,……,m                                    hi(x) = 0,       i = 1,…….,p     

مثال ها

   ارایه مرتبه ای مسائل معمول بهینه سازی تحدبی

مسائل ذیل همه مسائل بهینه سازی تحدبی می باشند، یا اینکه می تون آنها را از طریق تغییر در متغیرها به مسائل بهینه سازی تحدبی انتقال داد :

کوچکترین مربعات

برنامه ریزی خطی

بهینه سازی مخروطی

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

برنامه ریزی مخروطی سفارش دوم

برنامه ریزی نیمه معین

برنامه ریزی درجه دوم اجباری

حداکثر سازی افت

روش ها

روش های ذیل در حل مسائل بهینه سازی تحدبی استفاده می شود :

روش بیضوی

روش خرده گرادیان

روش صفحه برش

روش نکته داخلی

نرم افزار

اگرچه هدف عمومی اکثر حل کنندگان معادلات غیر خطی مانند LSSOL,LOQO,MINOS, and Lancelot work well ،بسته نرم افزاری بسیاری که با مسائل بهینه سازی تحدبی سر وکار دارند همچنین در دسترس می باشند :

زبان های برنامه ریزی تحدبی

YALMIP

CVX

CVXOPT

حل کنندگان بهینه سازی تحدبی

MOSEK

Solver.com

SeDuMi

روش صفحه برش

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

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

روش بیضوی

روش بیضوی الگوریتمی است برای حل کردن مسائل بهینه سازی تحدبی می باشد که توسط

Naum Z.Shor, Arkady Nemirovsky ,David B.Yudin in 1972  معرفی شده است .

و توسط Khachiyan  برای اثبات قابلیت حلی چند جمله ای زمان برنامه های خطی استفاده میشود.

در این زمان ،روش بیضوی تنها الگوریتم برای حل برنامه های خطی است که زمان اجرای آنها چند جمله ای است.در عمل ،اگرچه ،نوسانات الگوریتم تک جهتی بسیار سریعتر هستند ، وروش های منطقه داخلی از روش بیضوی هم در تئوری و هم در عمل سریعتر می باشد.الگوریتم با در میان گذاشتن کمینه کننده تابع محدب در یک توالی بیضوی وار که میزان آن در هر تکرار کاهش می یابد.

برنامه کاربردی در برنامه ریزی خطی

عملکرد

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

روش مرز داخلی

روش های مرز داخلی کلاس خاصی از الگوریتم ها هستند که در حل مسائل بهینه سازی تحدبی خطی وغیر خطی مورد استفاده قرار می گیرد.این الگوریتم ها توسط الگوریتم کارماکار ایجاد شده است ،و توسط Narendra Karmarkar in 1984 برای برنامه ریزی خطی توسعه یافت .المان های پایه این روش شامل

یک تابع مانع خود پرداز که برای رمز دار کردن سری تحدب استفاده میشود.همان گونه که با روش تک جهتی ضد شد ،و با گردش حوزه محتمل داخلی به اوج بهینگی می رسد.هر نوع مسئله بهینه سازی تحدبی

می تواند به کمینه سازی یا بیشینه سازی یک تابع خطی در یک سری تحدیب منتقل می شود.نظریه رمزدار کردن سری محتمل با استفاده از مانع و طراحی روش های محدودیتی در اوایل دهه 60 توسط Fiacco-McCormickودیگران مورد مطالعه قرار گرفته بود.این نظریه ها به طور عمده برای برنامه ریزی عمومی غیر خطی توسعه یافته است ،اما بعدها با توجه به حضور روش های رقابتی بیشتری برای این کلاس مسائل

محدود شده بود.Nesterov and Nemirovskii با یک کلاس خاص از موانع مواجه شدند که برای رمزگذاری هر نوع سری محدبی استفاده میشود.آنها ضمانت دادند که تعداد تکرارهای الگوریتم توسط چندجمله ای در بعدوصحت مسئله محدود شده است.بازسازی شکافتی کارماکار و مطاعه روش های حوزه داخلی .مسائل مانعی ،نشان میدهد که ایجاد وساخت یک الگوریتم برای برنامه ریزی خطی که توسط پیچیدگی

چندجمه ای مشخص شده است ،و بیشتر اینکه با روش تک جهتی قابل رقابت است. هم اکنون روش بیضوی خاچیان  یک الگوریتم زمان چند جمله ای است.اگرچه ،در عمل بسیار کند بود تا عملی شود.کلاس مسیر دوتایی اصلی که روش های حوزه داخلی را بنبال می کند موفق ترین فرض شده اند.الگوریتم اصلاح کر –پیش بینی کننده مهروترا پایه ای برای اکثر عملکردهای این سری از روش ها تامین می کند.

روش خرده گرادیان

روش های خرده گرادیان الگوریتم هایی برای حل مسائل بهینه سازی تحدبی هستند.اصلا توسط Shor ودیگران در دهه 60 و70 توسعه یافته اند.روش های خره گرادیان می تواند با یک تابع هدف غیر قابل تشخیص استفاده شود ،وقتی تابع هدف قابل تشخیص است ،روش های خرده گرادیان برای مسائل غیر اجباری

همان مسیر جستجوی مشابه با روش تندترین شیب کاهش را استفاده میکتد.اگرچه روش های خرده گرادیان می توانند بسیار کندتر از روش های حوزه داخلی وروش نیوتن در عمل باشند ،آنها می توانند برای وسعه پهن تری از مسائل به کار برده شوند وحافظه کمتری نیاز دارند.بیشتر اینکه ،با ترکیب روش خرده گرادیان با تکنیک های تجزیه دوتایی یا ابتدایی گاهی ممکن است الگوریتم ساده توزیعی برای مسئله ایجاد شود.توجه داشته باشید که سایز های مراحل ذکر شده بالا قبل اجرای الگوریتم تعیین شده اند وبه هیچ محاسبه اطلاعاتی در طی الگوریتم بستگی ندارند .این با قوانین سایزهای مراحل یافته شده در روش های استاندارد کاهشی متفاوت می باشد ،که به نکته اخیر ومسیر جستجو بستگی دارد.