آرامش نیمه‌معین برای مسائل بهینه‌سازی مربعی

در سالهای اخیر، تکینک آرامش نیمه معین (SDR) در مرکز برخی از تحولات در حوزه مخابرات و پردازش سیگنال بوده است. این روش دارای اهمیت و ارتباط زیادی با کاربردهای متنوع می‌باشد. بطور کلی، SDR یک روش تقریب قدرتمند برای انبوهی از مسائل بهیه سازی بسیار دشوار است. بطور خاص، از این روش برای تعداد زیادی از مسائل غیر محدب درجه دو با قید درجه دو (QCQP) با تقریب مورد استفاده قرار گیرد. از جمله مسئله زیر:
مسئله QPQC
بصورت حقیقی، متقارن و احتملا نا معین هستند. مسئله غیر محدب QCQPs (1) مسائل زیادی در حوزه مخابرات و پردازش سیگنال در بر می‌گیرد. به عنوان مثال، مسئله درجه دوم بولی (BQP) بصورت زیر در نظر گرفته می‌شود:
مسئله BQP
BQP برای مدت زیادی به عنوان یک مسئله سخت محاسباتی شناخته می‌شد. بطور خاص، در کلاس مسائل NP-hard قرار می‌گیرد. با این وجود، حل مسئله BQP تاثیر زیادی در آشکارسازی برای سیستم‌های چند ورودی و چند خروجی (MIMO)1 و چندکاربره2 دارد. یکی دیگر از مسائل NP-hard در QCQP غیر محدب (۱) بصورت زیر است:
474x474پیکسل
که همگی مثبت نیمه معین هستند. مسئله (۳) مسئله شکل دهی پرتو در ارتباط فروسو چند بخشی را در بر می‌گیرد، برای جزئیات بیشتر را مشاهده کنید. یک تصویر نمونه از مسئله (۳) در شکل۱ به نمایش گذاشته شده است. همان‌طور که در شکل مشاهده می‌کنید ناحیه شدنی اشتراک ناحیه خارجی بیضی‌ها می‌باشد، که مسئله را دشوار می‌سازد.
در واقع، SDR مدت‌ها قبل از اینکه تاثیرش بر مسائل مخابرات و پردازش سیگنال بررسی شود، در بهینه سازی مورد مطالعه و بررسی قرار گرفته بود. ایده SDR را می‌توان در مقاله Lovasz در سال 1979 پیدا کرد، اما مسلما کار بدوی Goemans و Williamson در سال 1995 بود که گسترش قابل توجهی را در روش SDR بوجود آورد. آنها نشان دادن که می‌توان از SDR برای حل مسئله برش-بیشینه1 با دقت تقریبی که در بدترین حالت برابر ۰٫۸۷۵۶ است، استفاده کرد. به بیان دیگر، اگر چه مسئله برش-بیشنه یک مسئله NP-Hard است، اما یک حل کارآمد وجود داردکه مقدار بهینه مسئله حداقل ۰٫۸۷۵۶ برابر مقدار بهینه است که توسط SDR یدست می‌آید. امروزه، ما می‌توانم شرایطی که تحت آن SDR همان جواب مسئله اصلی را فراهم می‌کند، را روی مسئله بهینه سازی اعمال کنیم.
معرفی
معرفی SDR در اویل قرن ۲۱ روش بررسی بسیاری از موضوعات که امروز در زمینه ارتباطات و پردازش سیگنال می‌بینیم را تغییر شکل داد. در بسیاری از تجارب عملی حال حاضر نشان داده شده است که SDR قادر به ارائه تقریب دقیق (و گاهی اوقات نزدیک به نقطه بهینه) است. برای مثال، در آشکار سازی MIMO، SDR یک روش کارآمد و شناخته شده است. عملکرد امیدوار کننده تقریب SDR باعث ایجاد انگیزه برای تلاش‌های بیشتر در برخی از زمینه‌های تحقیقاتی جدید را ایجاد کرده است. برای مثال زمینه شکل دهی پرتو، که اخیرا مورد توجه قرار گرفته است؛ شکل دهی پرتو موثر وابستگی زیادی به چگونگی پیاده سازی مسائل QCQP(که اغلب غیر محدب هستند) دارد. می‌توان گفت که اگر SDR وارد مسائل مخابرات و پردازش سیگنال نمی‌شد، این زمینه‌ها دارای پیشرفت کندی می‌بودند. مثال دیگر مسئله محلی سازی شبکه‌های حسگر است. یک مسئله عملا مهم ولی چالش‌برانگیز است که SDR یک روش موثر برای حل این مسئله ارائه می‌دهد، این موضوع هم از نظر عملی و هم از نظر تئوری اثبات شده است. علاوه بر کاربردهای فوق، SDR در بسیاری از کاربردهای دیگر مانند: طراحی شکل موج در رادار، تشخیص گفتار و … استفاده می‌شود.
معرفی SDR
یک یادآوری مختصر، مسئله (۴) در نظر گرفته شده، یعنی، QCQP همگن با مقادیر حقیقی، که که نماینده " "،" " یا " = " برای همه iها است. مجموع تمام ماتریس‌های متقارن حقیقی در نظر گرفته شده است؛ و می‌باشند. اولین گام برای استخراج SDR از مسئله (۴) رعایت رابطه زیر است.
تبدیل فرم مربعی با تریس
فرم کلی QPQC (4)
بطور خاص، هم تابع هدف و هم قیدها در (۴) نسبت به ماتریس خطی هستند. بدین ترتیب، با معرفی متغیر جدید X = x x^{T
و توجه به اینکه معادل یک ماتریس متقارن مثبت نیمه معین (PSD)1 است. رابطه زیر از فرمول (۴) بدست می‌آید:
معادل مثبت نیمه معین برای مسائل مقید مربعی
که ، بیان می‌کند که ،PSD است. با توجه به رابطه فوق در می‌یابیم که در رابطه با پیچیدگی حل مسئله بهبودی حاصل نمی‌گردد، و حل رابطه (۵) به دشواری حل رابطه (۴) است. تنها قید دشوار در (۵) قید rank،( ) است، که غیر محدب است (تابع هدف و مابقی قیود نسبت به X محدب هستند). ما می‌توانم مسئله اصلی را رها کرده و بجای آن از نسخه ساده شده (۴) که بصورت زیر است استفاده کنیم:
مسئله آسوده شده مسائل مربعی با قید مربعی
رابطه (۶) بعنوان SDR مسئله (۴) در نظر گرفته می‌شود، که نمونه از مسئله PSD است. رابطه (۶) یک مسئله قابل حل و کارآمد از لحاظ عددی است. در واقع، SDR هم اکنون در بسیاری از بسته‌های نرم‌افزاری (و رایگان) به طور موثر مورد استفاده قرار می‌گیرد. به عنوان مثال فرض کنید که برای ، معادل و برای ، معادل = است. با استفاده از جعبه ابزار CVX متلب، می‌توان مسئله (۶) را در متلب با کد داده شده ریز حل کرد:
کد بهینه سازی در متلب
شکل ۱:یک مسئله غیر محدب QCQP در فضای دو بعدی، خطوط رنگی نشان دهنده کانتورها تابع هدف است.
1 semidefinite programming
1 positive semidefinite
1 maximum cut problem
1 multiple-input, multiple-output
2 multiuser