تحقیق در مورد برنامه ریزی نیمه معین (SDP)

اختصاصی از فی دوو تحقیق در مورد برنامه ریزی نیمه معین (SDP) دانلود با لینک مستقیم و پر سرعت .

لینک پرداخت و دانلود *پایین مطلب*

فرمت فایل: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

1. t.   ai.x = bi ,  i=1,…,m

1. 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  

1. t.  

1. 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 و دلخواه باشد داریم :