پرش به محتوا

برنامه‌سازی مخروط دوگانی

از ویکی‌پدیا، دانشنامهٔ آزاد

برنامه مخروط دوگان (SOCP) یکی از مسائل بهینه‌سازی محدب می‌باشد؛ و به این صورت است:

را کمینه کنید
اگر داشته باشیم

با پارامترهای ، و . در اینجا متغیر بهینه‌سازی ما است.[۱] اگر برای ، برنامه SOCP ما به یک مسئلهٔ برنامه‌سازی خطی کاهش می‌یابد. اگر برای ، برنامه SOCP ما معادل یک مسئله برنامه‌سازی خطی کوژ-درجه‌دوم محدود شده می‌شود. برنامه‌سازی درجه‌دوم درجه‌دوم محدود شده را نیز می‌توان به صورت حالت خاصی از SOCP نوشت. بهی

مثال: محدودیت درجه‌دوم

[ویرایش]

یک درجه‌دو محدود شده به صورت زیر را در نظر بگیرید

این معادل است با SOC محدود شده

مثال: برنامه‌سازی خطی تصادفی

[ویرایش]

یک برنامه خطی تصادفی به صورت زیر را در نظر بگیرید

را کمینه کنید
اگر داشته باشیم

که در آن پارامترهای بردارهای مستقل تصادفی گوسی هستند با میانگین و کوواریانس و . این معادل است با SOC به صورت زیر

را کمینه کنید
اگر داشته باشیم

که در آن معکوس تابع توزیع تجمعی طبیعی.[۱]

مثال: برنامه‌سازی مخروط دوگان تصادفی

[ویرایش]

ما با نام بردن از برنامه‌های مخروط دوگان به برنامه‌های مخروط دوگان قطعی می‌گفتیم چون داده‌های تعریف کننده آنها همگی قطعی هستند. برنامه‌های مخروط دوگان تصادفی[۲] یک کلاس از مسائل بهینه‌سازی است که مسئولیت رسیدگی به عدم قطعیت در داده‌هایی که قطعی تعریف شده‌اند را دارد.

حل کننده و زبان‌های برنامه‌نویسی

[ویرایش]
نام مجوز اطلاعات مختصر
ورک تجاری جبری زبان
CPLEX تجاری
Gurobi تجاری
MOSEK تجاری


برنامه ریزی مخروط مرتبه دوم بسط برنامه‌ریزی مربعی و برنامه‌ریزی خطی است که در آن ترکیب افاین متغیرها به صورت قید داخل یک مخروط مرتبه دوم تعریف می‌شوند. این نوع برنامه‌ریزی در حل مسائل هندسی کاربرد دارد و همچنین در برنامه ریزیهای خطی که داده‌ها با خطا همراه هستند و به‌طور دقیق مشخص نیستند کاربرد دارد.[۳]

مخروط مرتبه دوم

[ویرایش]

به مجموعه زیر، مخروط نرم مرتبط با نرم گفته می‌شود،[۴]

مخروط نرم مرتبه دوم، به ازای نرم اقلیدسی تعریف می‌شود که به‌طور مثال در به صورت زیر خواهد بود،

این مخروط به علت شکلی که دارد (به‌طور مثال در مانند قیف بستنی است) با عنوان مخروط بستنی هم شناخته می‌شود.

نمایش فرمولی برنامه ریزی مخروط مرتبه دوم[۴]

[ویرایش]

برنامه ریزی مخروط مرتبه دوم با در نظر گرفتن تابع هدف خطی و قیود نامساوی که به فرم مخروط مرتبه دوم هستند و قیود تساوی افاین به شکل زیر نوشته می‌شود:

که متغیر بهینه‌سازی است، ، و می‌باشند.

در حالتی که باشد، مسئله برنامه‌ریزی مخروط مرتبه دوم به برنامه‌ریزی مربعی با قیود مربعی (QCQP) تبدیل می‌شود. همچنین در حالت دیگر اگر باشد این مسئله به یک مسئله برنامه‌ریزی خطی تبدیل می‌شود.

مثال: برنامه ریزی خطی آماری[۵]

[ویرایش]

برنامه ریزی خطی آماری با قیود نامساوی را به شکل زیر در نظر بگیرید:

که متغیر گوسی مستقل با متوسط و کوواریانس هستند و ، این مسئله را می‌توان به فرم یک مسئله مخروط مرتبه دوم به شکل زیر نوشت:

که در اینجا معکوس تابع توزیع تجمعی گوسی می‌باشد.

مثال: قید مربعی

[ویرایش]

در این مثال دیده می‌شود که قید مربعی زیر:

را می‌توان به شکل قید SOCP همانند زیر بازنویسی کرد:

مثال: مربعات خطا مقاوم[۶]

[ویرایش]

فرض کنید که مجموعه فرامعینی از معادلات به فرم که و مجهول هستند اما به صورت و محدود شده‌اند (نرم ماتریسی در اینجا همان نرم طیفی یا حداکثر مقدار تکین است). می‌توان جواب حداقل مربعات مقاوم را معادل با که جواب حداقل سازی بزرگترین باقی‌مانده ممکن است و به صورت زیر تعریف می‌شود، در نظر گرفت:

این مسئله، مسئله حداقل مربعات مقاوم است.[۷][۸][۹][۱۰]

در مسئله بالا تابع هدف با پیگیری روند زیر می‌تواند به فرم بسته نوشته شود:

بنابراین مسئله اصلی به صورت زیر تبدیل می‌شود:

که مجموع نرمهای اقلیدسی است.

این مجموع می‌تواند به عنوان یک فرم SOCP مد نظر قرار گیرد. با اینحال، در صورت استفاده از تجزیه مقدار تکین A می‌توان به حل ساده‌تری دست پیدا کرد. مسئله SOCP با قیود دیگر مفیدتر خواهد بود به‌طور مثال در نظر گرفتن قیود نامنفی. می‌توان صورت دیگری برای این مسئله متصور بود. به این صورت که فرض کنید، سطرهای ماتریس مرتبط با خطاهای مستقل هستند و البته درون یک بیضی‌گون هستند؛ به عبارتی ، که:

حال می‌توان تخمین مربعات خطا مقاوم را با حداقل سازی بدترین باقی‌مانده به فرم زیر بدست آورد:

با انجام برخی اعمال ریاضی می‌توان رابطه بالا را به صورت زیر بازنویسی کرد:

که به صورت مسئله SOCP زیر قابل بازنویسی خواهد بود:

کاربردها

[ویرایش]

طراحی وزن آرایه‌های آنتن

[ویرایش]

در بحث آرایه آنتنی، خروجی المانهای آنتن به صورت خطی با یکدیگر ترکیب شده و خروجی نهایی را تشکیل می‌دهند. خروجی آرایه دارای جهتی است که وابسته به وزنهای نسبی المانها ربط دارد و هدف از داشتن آرایه‌ای از آنتنها این است که در جهت دلخواهی که مد نظر است بتوانیم جهت خروجی را تنظیم کنیم. مسئله را می‌توان به شکل زیر تعریف کرد:

که است، پهنای بیم است و بازه که در حداقل سازی مورد نظر است ملزم می‌دارد که امواج رسیده از سایر جهات غیر از جهت هدف () حداقل شوند. همچنین سیگنال باند پایه متناظر با سیگنال باند میانی است. علاوه بر این شرط به معنای نرمالیزه بودن است.

این مسئله، با گسسته سازی زاویه (به صورت به ازای ) می‌تواند به فرم یک مسئله SOCP تقریب زده شود. پاسخ آرایه را به صورت زیر در نظر بگیرید:

که و

آنگاه مسئله بهینه‌سازی می‌تواند به فرم SOCP زیر تقریب زده شود:

که زمانیکه به صورت ترمهای از بخش‌های حقیقی و موهومی نوشته شود، فرم SOCP خواهد داشت.

سایر کاربردها

[ویرایش]

طراحی فیلتر با پاسخ ضربه متناهی هم نمونه دیگری از کاربرد برنامه‌ریزی SOCP است؛ که در آن هم سعی می‌شود خطای بین پاسخ ضربه دلخواه و پاسخ ضربه تولیدی توسط برخی ضرایب است را حداقل کنند. نشان داده شده‌است که این مسئله را هم به فرم SOCP درآورد.


منابع

[ویرایش]
  1. ۱٫۰ ۱٫۱ Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved October 3, 2011.
  2. Alzalg, Baha (2012). "Stochastic second-order cone programming: Application models". Applied Mathematical Modelling. 36 (10): 5122–5134. doi:10.1016/j.apm.2011.12.053.
  3. «نسخه آرشیو شده». بایگانی‌شده از اصلی در ۲ ژانویه ۲۰۱۷. دریافت‌شده در ۱۸ ژانویه ۲۰۱۷.
  4. ۴٫۰ ۴٫۱ Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
  5. https://en.wikipedia.org/wiki/Second-order_cone_programming
  6. http://www.seas.ucla.edu/~vandenbe/publications/socp.pdf
  7. El Ghaoui, Laurent, and Hervé Lebret. "Robust solutions to least-squares problems with uncertain data." SIAM Journal on Matrix Analysis and Applications 18.4 (1997): 1035-1064.
  8. Chandrasekaran, Shivkumar, et al. "Efficient algorithms for least squares type problems with bounded uncertainties." Recent Advances in Total Least Squares Techniques and Errors-in-Variables Modeling (1997): 171-180.
  9. Chandrasekaran, S. , et al. "Parameter estimation in the presence of bounded data uncertainties." SIAM Journal on Matrix Analysis and Applications 19.1 (1998): 235-252.
  10. Sayed, A. H. , et al. "Exponentiallyweighted iterative solutions for worst-case parameter estimation." Proceedings of the 5th IEEE Med. Conf. Control and Systems, Cyprus. 1997.