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

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

بهینه سازی محدب یک خرده زمینه از بهینه سازی ریاضیات می باشد. یک فضای برداری حقیقی 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  برای اثبات قابلیت حلی چند جمله ای زمان برنامه های خطی استفاده میشود.

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

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

عملکرد

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