بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بهينه سازي غير محدب با کرانهاي دو گان و کاربرد در سيستم هاي مخابراتي
چکيده
بهينه سازي محدب ، يک ابزار مفيد و يک نگرش جالب را براي تجزيه و تحليل و طراحي سيستم هـاي مخـابراتي در چند سال اخير فراهم کرده است . مهمترين چالش امروزه مربوط به مسائل غير محدب است . اين مقاله ، نتـايج بررسـي کرانهاي دوگان براي برنامه ريزي درجه دوم غير محدب با يک محدوديت غير خطي و نماي کلي مسئله بهينه سـازي غير محدب را در سيستم هاي مخابراتي شبکه اي ارائه مي دهد .
واژه هاي کليدي
کران دوگان ، برنامه ريزي درجه دوم ، روش کران دوگاني ، بهينه سازي غير محدب ، ماکسيمم سازي مطلوبيت شبکه
١- مقدمه
دو دورة مهم در تاريخچه تئوري بهينه سازي وجود دارد:
اولين دوره در مورد روش سيمپلکس و برنامه ريزي خطـي در دهه ١٩٤٠ ، و دومين آن مربوط به نقطه دروني و بهينـه سازي محدب در دهه ١٩٨٠ است .
هر کدام از آنها چرخه هـاي کـاربردي ارزيـابي و انتقـالي را دنبال مي کنند:
چون اکثر مردم کاربرد اين نوع بهينه سازي محدب (LP) را درک نموده اند، بيشتر به دنبال فرمول هاي آن در کاربردهـاي مختلـف هـستيم . بنـابراين توجـه بيـشتر بـه ايـن تئـوري ، الگوريتم ها و نرم افزارهاي مناسب تري را ارائه مي دهـد و ابزارها مفيدتر و مطلوب تـر از قبـل مـي شـوند ، در نتجـه تعداد بيشتري ، کاربردآن را درک مي کنند.
سيــستم هــاي مخــابراتي ١ اساســاً از هــر دو دورة مــذکور، راه حل هاي جريان چنـد گانـه اي (ماننـد الگـوريتم بلمـن 2 فورد) از LP و ماکسيمم سازي مطلوبيـت شـبکه اصـلي و طراحي فرستنده - گيرنده ٣ مقـاوم از بهينـه سـازي محـدب ، سود مي برند.
اکثر تحقيقات فعلي در زمينه دورة سوم يا همان بهينه سازي غير محدب است .
اغلب اقتصاد دانان دريافته اند که در مـسائل برنامـه ريـزي اقتصادي ، غير خطي بودن توابع نه استثناهاي مـوردي بلکـه يک قاعده کلي است . از اين رو گستردگي دامنه کاربردهاي برنامه ريزي غير خطي ايجاب مي کند که اين مقوله مهم نيز مورد توجه قرار گيرد .
تنوعي از دستاوردها، از تبديل غير خطي يـک مـسئله غيـر محدب موجود به مسئله محدب ، از تقريب محدب متـوالي به دوگاني ، از تاثير ساختارهاي خاص مسائل ( مثلاً، تفـاوت توابع محدب ، مي نيمم سـازي مقعـر ، غيـر تحـدب مرتبـه پائين ) به توسعه موثرتـر روش شـاخه و کـران ، ارائـه شـده است .
محققان در سيـستم مخـابرات و شـبکه ، بهينـه سـازي غيـر محدب را به کمک ساختارهاي اصلي و خـاص در مـسائل مهم حوزه هاي شبکۀ بي سيم ٤، مهندسي اينترنت ٥ و تئوري مخابرات ، مورد بررسي قرار داده اند .
احتمالاً چهار موضوع اصلي ، تنوع مسائل چالشي را از بهينه سازي غير محدب در سيستم هاي مخابراتي به بهترين شکل بيان مي کند:
مي نيمم کردن هدف غير محدب . به عنوان مثـال ، کنترل ازدحام ٦ براي کاربردهاي غير کشسان .
مجموعه محدوديت غير محدب . بـه عنـوان مثـال کنترل توان ٧ در سيستم هاي low SIR .
محدوديت هاي صحيح . دو مثال مهـم آن ، مـسير بندي منفرد٨ و تشخيص چند کاربري ٩ است .
مجموعه محدوديت هاي تحـدبي کـه بـه تعـدادي نمايه نامساوي در توصيف دقيـق خـود نيازمنـد اسـت . بـه عنوان مثال طرح بندي بهينه .
آخرين نتايج تحقيقات اخير در مـورد دو موضـوع اول ، در [٤]مورد مطالعه قرار گرفته است .
در مقاله حاضر، کران دوگاني براي برنامه ريزي درجـه دوم کلي در بخش ٢ و مباحث مربوط به کنترل ازدحام اينترنـت در بخش ٣ مورد بررسي قرار گرفته است . بخـش ٤ شـامل نتيجه گيري مطالب بيان شده مي باشد.
٢- کران دوگاني براي برنامه ريزي درجۀ دوم کلي
يک مـسئله برنامـه ريـزي درجـه دوم کلـي ، تنهـا بـا يـک محدوديت غير خطي ١٠ به صورت زير است :
که Qو Cماتريس هاي حقيقي nn هستند،
مجموعه نقاط شدني مسئله مي باشد.
٢-١- کران پائين
براي هر مستطيل
مي خواهيم کران پائين از تابع f را روي محاسبه کنيم . به عبارت ديگر کران پائين مسئله
را مورد محاسبه قرار مي دهيم .
هدف اصلي اين روش براي محاسبه کردن کران پائين اين است که مسئله معادل مسئله ((QR) را توسط جايگزيني جمله هاي درجه دوم با فرم هاي دو خطي متناظر ايجاد کرده و سپس دوگان لاگرانژي مسئله حاصل شده را طبق ([١]، گزارة ٢.٦.١ ) حل کنيم .
به همين منظور، فرض کنيم بردارهاي به صورت مقابل تعريف شده باشند:
که براي هر به ترتيب سطرهاي iام ماتريس Qو C هستند. با استفاده از بردارهاي کمکي از متغيرهاي مسئله ((Q)R)را به مسئله تبديل مي کنيم :
([٧] ،گزارة ٢.١ )تعادل بين مسئله ((QR)و ((PR)را نشان مي دهد .
برخي نتايج مطالعه شدة [٧] به صورت زير مورد بررسي قرار گرفته است :
(الف )( [٧]، گزارة مقدار بهينه برنامه خطي است :
(ب )([٧]، گزارة ٢.٣ ) کران حداقل به خوبي هر کران به دست آمده از مدل سازي محدب است .
ادعاي (الف ) در [٧] با انجام محاسبات طولاني ثابت مي کند. که دوگان لاگـرانژي بـه برنامه خطـي تبديل مي شود اما، در مدت کوتاهي نشان داده شده که اين محاسبات غير ضروري هستند، زيرا فقط مقدار بهينه مدل سازي خطي معمولي از مي باشد، که فوراً بدون استفاده از مدل سازي لاگرانژي به دست آمده .
به عبارت ديگر(ب ) با مثال نقض زير رد شده است . مثال نقض . برنامه درجه دوم با يک متغير را در نظر بگيريد:
که مقدار بهينه آن برابر o است .
در مقايسه اين مسئله با برنامه مشاهده مي کنيم که و مسئله متناظر آن به صورت
و هم چنين برنامه خطي آن به قرار زير است :
بـا حـل کـردن ايـن برنامـه خطـي بـه دسـت مي آيد، که يک کران بسيار پائيني بـراي مقـدار بهينـه o از مسئله (٣) را نتيجه مي دهد .
علاوه بر اين ، از کراني که بـا مـدل سـازي محـدب به دست آمده کمتر است .
در مدل سازي محدب از مسئله با پوشش محدبشان روي R يعني به ترتيب
جايگزين شده و برنامه خطي
را نتیجه مي دهد ، که مقدار بهينه اش برابـر ٦- اسـت و در مقايسه با از مسئله يک کران بـسيار بهتري مي باشد.
بنابراين ادعاي (ب ) صحيح نيست .
هم چنين جالب است توجـه کنـيم کـه دو گـان لاگرانـژي مسئله (٣) به صورت
است .
از آنجايي که براي ١ = u :
است و با توجه به اينکه مقدار بهينه مسئله (٣) برابر o است ،
طبق قضيه دوگاني ضعيف [٢] داريم :
