موضوع مقاله: برنامه‌سازی مخروط دوگانی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # برنامه‌سازی مخروط دوگانی | مقدمه: برنامه مخروط دوگان (SOCP) یکی از مسائل بهینه‌سازی محدب می‌باشد؛ و به این صورت است: را کمینه کنید اگر داشته باشیم با پارامترهای ، و . | ## بخش 1: برنامه‌سازی مخروط دوگانی | اگر برای ، برنامه SOCP ما معادل یک مسئله برنامه‌سازی خطی کوژ-درجه‌دوم محدود شده می‌شود. برنامه‌سازی درجه‌دوم درجه‌دوم محدود شده را نیز می‌توان به صورت حالت خاصی از SOCP نوشت. بهی مثال: محدودیت درجه‌دوم یک درجه‌دو محدود شده به صورت زیر را در نظر بگیرید این معادل است با SOC محدود شده مثال: برنامه‌سازی خطی تصادفی یک برنامه خطی تصادفی به صورت زیر را در نظر بگیرید را کمینه کنید اگر داشته باشیم که در آن پارامترهای بردارهای مستقل تصادفی گوسی هستند با میانگین و کوواریانس و . این معادل است با SOC به صورت زیر را کمینه کنید اگر داشته باشیم که در آن معکوس تابع توزیع تجمعی طبیعی. مثال: برنامه‌سازی مخروط دوگان تصادفی ما با نام بردن از برنامه‌های مخروط دوگان به برنامه‌های مخروط دوگان قطعی می‌گفتیم چون داده‌های تعریف کننده آنها همگی قطعی هستند. برنامه‌های مخروط دوگان تصادفی یک کلاس از مسائل بهینه‌سازی است که مسئولیت رسیدگی به عدم قطعیت در داده‌هایی که قطعی تعریف شده‌اند را دارد. حل کننده و زبان‌های برنامه‌نویسی ناممجوزاطلاعات مختصرورکتجاری جبری زبانCPLEXتجاریGurobiتجاریMOSEKتجاری برنامه ریزی مخروط مرتبه دوم بسط برنامه‌ریزی مربعی و برنامه‌ریزی خطی است که در آن ترکیب افاین متغیرها به صورت قید داخل یک مخروط مرتبه دوم تعریف می‌شوند. | ## بخش 2: برنامه‌سازی مخروط دوگانی | این نوع برنامه‌ریزی در حل مسائل هندسی کاربرد دارد و همچنین در برنامه ریزیهای خطی که داده‌ها با خطا همراه هستند و به‌طور دقیق مشخص نیستند کاربرد دارد. مخروط نرم مرتبه دوم، به ازای نرم اقلیدسی تعریف می‌شود که به‌طور مثال در به صورت زیر خواهد بود، این مخروط به علت شکلی که دارد (به‌طور مثال در مانند قیف بستنی است) با عنوان مخروط بستنی هم شناخته می‌شود. نمایش فرمولی برنامه ریزی مخروط مرتبه دوم برنامه ریزی مخروط مرتبه دوم با در نظر گرفتن تابع هدف خطی و قیود نامساوی که به فرم مخروط مرتبه دوم هستند و قیود تساوی افاین به شکل زیر نوشته می‌شود: که متغیر بهینه‌سازی است، ، و می‌باشند. در حالتی که باشد، مسئله برنامه‌ریزی مخروط مرتبه دوم به برنامه‌ریزی مربعی با قیود مربعی (QCQP) تبدیل می‌شود. همچنین در حالت دیگر اگر باشد این مسئله به یک مسئله برنامه‌ریزی خطی تبدیل می‌شود. مثال: برنامه ریزی خطی آماری برنامه ریزی خطی آماری با قیود نامساوی را به شکل زیر در نظر بگیرید: که متغیر گوسی مستقل با متوسط و کوواریانس هستند و ، این مسئله را می‌توان به فرم یک مسئله مخروط مرتبه دوم به شکل زیر نوشت: که در اینجا معکوس تابع توزیع تجمعی گوسی می‌باشد. مثال: قید مربعی در این مثال دیده می‌شود که قید مربعی زیر: را می‌توان به شکل قید SOCP همانند زیر بازنویسی کرد: مثال: مربعات خطا مقاوم فرض کنید که مجموعه فرامعینی از معادلات به فرم که و مجهول هستند اما به صورت و محدود شده‌اند (نرم ماتریسی در اینجا همان نرم طیفی یا حداکثر مقدار تکین است). | ## بخش 3: برنامه‌سازی مخروط دوگانی | در مسئله بالا تابع هدف با پیگیری روند زیر می‌تواند به فرم بسته نوشته شود: بنابراین مسئله اصلی به صورت زیر تبدیل می‌شود: که مجموع نرمهای اقلیدسی است. با اینحال، در صورت استفاده از تجزیه مقدار تکین A می‌توان به حل ساده‌تری دست پیدا کرد. به این صورت که فرض کنید، سطرهای ماتریس مرتبط با خطاهای مستقل هستند و البته درون یک بیضی‌گون هستند؛ به عبارتی ، که: حال می‌توان تخمین مربعات خطا مقاوم را با حداقل سازی بدترین باقی‌مانده به فرم زیر بدست آورد: با انجام برخی اعمال ریاضی می‌توان رابطه بالا را به صورت زیر بازنویسی کرد: که به صورت مسئله SOCP زیر قابل بازنویسی خواهد بود: کاربردها طراحی وزن آرایه‌های آنتن در بحث آرایه آنتنی، خروجی المانهای آنتن به صورت خطی با یکدیگر ترکیب شده و خروجی نهایی را تشکیل می‌دهند. خروجی آرایه دارای جهتی است که وابسته به وزنهای نسبی المانها ربط دارد و هدف از داشتن آرایه‌ای از آنتنها این است که در جهت دلخواهی که مد نظر است بتوانیم جهت خروجی را تنظیم کنیم. مسئله را می‌توان به شکل زیر تعریف کرد: که است، پهنای بیم است و بازه که در حداقل سازی مورد نظر است ملزم می‌دارد که امواج رسیده از سایر جهات غیر از جهت هدف حداقل شوند. این مسئله، با گسسته سازی زاویه (به صورت به ازای ) می‌تواند به فرم یک مسئله SOCP تقریب زده شود. پاسخ آرایه را به صورت زیر در نظر بگیرید: که و آنگاه مسئله بهینه‌سازی می‌تواند به فرم SOCP زیر تقریب زده شود: که زمانیکه به صورت ترمهای از بخش‌های حقیقی و موهومی نوشته شود، فرم SOCP خواهد داشت. | ## جمع‌بندی | سایر کاربردها طراحی فیلتر با پاسخ ضربه متناهی هم نمونه دیگری از کاربرد برنامه‌ریزی SOCP است؛ که در آن هم سعی می‌شود خطای بین پاسخ ضربه دلخواه و پاسخ ضربه تولیدی توسط برخی ضرایب است را حداقل کنند.