لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه18
فهرست مطالب
1 مقدمه........................................................................................................................ 4
2 مروری کوتاه بر برنامه ریزی خطی......................................................... 4
3 نکاتی پیرامون ماتریس ها و مخروط های نیمه معین.................... 6
4 برنامه ریزی نیمه معین................................................................................ 8
5 دوگان مسئله SDP............................................................................................ 11
6 خواص کلیدی مسائل برنامه ریزی خطی که به برنامه ریزی نیمه معین گسترش نمی یابند .................................................................................................................. 16
7 SDP در بهینه سازی تر کیبیاتی.............................................................. 16
1 . 7 بیان SDP Relaxation از مسئله برش یالی ماکسیمم..... 16
منابع و مراجع....................................................................................................... 19
1-مقدمه:
برنامه ریزی نیمه معین (SDP) جذاب ترین تحول برنامه ریزی ریاضی در دهه90میلادی محسوب می شود . SDP در موضوعات گوناگون از جمله بهینه سازی مقید محدب سنتی ، نظریه کنترل و بهینه سازی ترکیبیاتی کاربرد دارد. به دلیل آنکه SDP قابل حل به وسیله روش نقطه درونی می باشد ، بیشتر این موارد کاربرد ، در عمل نیز همانند تئوری کارا هستند.
2-مروری کوتاه بر برنامه ریزی خطی:
مسئله LPرا در حالت استاندارد در نظر بگیرید:
LP : minimize c.x
- t. ai.x = bi , i=1,…,m
- xR.
که در اینجا x یک بردار nمتغیره است و نماد« c.x »حاکی از ضرب داخلی "" می باشد . همچنین │ RnRn+ و Rn+ فضای اقلیدسی نا منفی نامیده می شود.در حقیقت Rn+ یک مخروط بسته محدب است ، زمانی به یک مجموعه مانند K یک مخروط بسته محدب می گوییم که شرایط زیر را داشته باشد :
- اگر x و y بهK تعلق داشته باشد آنگاه نیز به K تعلق داشته باشد که در آن و اسکالر های نا منفی هستند.
R+ :
- K یک مجموعه بسته باشد.
این تعریف را می توانیم اینگونه بیان کنیم :
" منیمم کردن تابع خطی« c.x » بطوری که x درm معادله ai.x = bi (i=1,…,m) صدق کند و x متعلق به مخروط بسته محدب Rn+ باشد "
دوگان یک مسئله LP را به صورت زیر نشان می دهیم :
LD : maximize
- t.
- sR.
اگر x یک جواب شدنی برای مسئله LP و(y,s) یک جواب شدنی برای مسئله LD باشد آنگاه فاصله دوگانی به صورت زیر است:
و نا مساوی بالا به خاطر و حاصل می شود . از قضیه قوی دوآلیتی می دانیم که اگر مسئله اولیه LP دارای جواب شدنی متناهی باشد آنگاه مسئله LD نیز شدنی متناهی است و c.x=y.b و این نتیجه می دهد که فاصله دوگانی (دوآلیتی) وجود ندارد.(برابر صفر است)یعنی اگرX فضای شدنی مسئله LP و F فضای شدنی مسئلهLD باشد آنگاه:
X F :
3- نکاتی پیرامون ماتریس ها و مخروط های نیمه معین:
اگر X یک ماتریس باشد زمانی گوئیم X یک ماتریس مثبت نیمه معین(PSD ) است که رابطه زیر برقرار باشد:
v Rn : vT X v
اگر X یک ماتریس باشد گوئیم X یک ماتریس مثبت معین(PD ) است هر گاه :
v Rn , v0 : vT X v
فرض کنید نشان دهنده مجموعه ماتریس های متقارن باشد و نشان دهنده مجموعه ماتریس های متقارن نیمه معین و مجموعه ماتریس های مثبت معین باشد.
فرض کنیم X و Y ماتریس های متقارن دلخواهی باشند. می نویسیم "" به این منظور که نشان دهیم X یک ماتریس مثبت نیمه معین است و نماد "" بیانگر آن است که "" یعنی ماتریس مثبت نیمه معین است. به طریق مشابه هر گاه X یک ماتریس متقارن و مثبت معین باشد آن را با "" نشان می دهیم .
تذکر 1: یک مخروط بسته محدب در R است که بعد آن برابر است.
برای اثبات تذکر 1 فرض می کنیم XوW و فرض می کنیم ثابت دلخواه باشند در این صورت هر گاه Rnv و دلخواه باشد داریم :
تحقیق در مورد برنامه ریزی نیمه معین (SDP)
