برنامه ریزی با قیود درجه دوم (Quadratically Constrained Quadratic Programming - QCQP)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
برنامه ریزی با قیود درجه دوم (Quadratically Constrained Quadratic Programming - QCQP) :
📌 تعریف و ساختار کلی
برنامه ریزی با قیود درجه دوم (QCQP) یکی از شاخه های مهم بهینه سازی محدب است که در آن تابع هدف یک تابع درجه دوم و تمام قیود نیز توابع درجه دوم هستند. شکل کلی یک مسئله QCQP به صورت زیر است [citation:9]:
\[ \text{Minimize} \quad \frac{1}{2} x^T P_0 x + q_0^T x + r_0 \] \[ \text{Subject to:} \quad \frac{1}{2} x^T P_i x + q_i^T x + r_i \leq 0, \quad i = 1, \ldots, m \] \[ \quad A x = b \]در اینجا
\[ x \in \mathbb{R}^n \]بردار متغیرهای تصمیم است. ماتریس های
\[ P_i \](برای
\[ i=0,1,\ldots,m \]) معمولا ماتریس های متقارن هستند. برای محدب بودن مسئله، این ماتریس ها باید نیمه معین مثبت (Positive Semidefinite) باشند (
\[ P_i \succeq 0 \]).
🔬 ارتباط با سایر روش ها
QCQP یک حالت تعمیم یافته از برنامه ریزی درجه دوم (QP) است. در QP، قیود خطی هستند، اما در QCQP قیود نیز درجه دوم هستند. همچنین می توان نشان داد که QCDP های محدب را می توان به صورت برنامه ریزی مخروطی درجه دوم (SOCP) نیز فرموله کرد [citation:9]. این ارتباط باعث می شود که بتوان از حل کننده های قدرتمند SOCP برای حل QCQP نیز استفاده کرد.
💼 کاربردها
پردازش سیگنال: طراحی فیلترهای بهینه با قیود توان سیگنال.
مخابرات: بهینه سازی توان فرستنده ها در شبکه های بی سیم با در نظر گرفتن تداخل.
کنترل: مسائل کنترل بهینه با قیود مربعی روی حالت ها و ورودی ها.
مالی: بهینه سازی پرتفوی با قیود ریسک که به صورت واریانس بیان می شوند.
یادگیری ماشین: برخی از فرمولاسیون های ماشین بردار پشتیبان (SVM) با قیود درجه دوم.
🧮 مثال عددی ساده
می خواهیم تابع درجه دوم زیر را کمینه کنیم با یک قید درجه دوم:
\[ \text{Minimize} \quad x_1^2 + x_2^2 \] \[ \text{Subject to:} \quad (x_1 - 1)^2 + (x_2 - 1)^2 \leq 1 \] \[ \quad x_1, x_2 \geq 0 \]این مسئله به دنبال نزدیک ترین نقطه به مبدأ مختصات است که درون دایره ای به مرکز
\[ (1,1) \]و شعاع ۱ قرار دارد. جواب بهینه در مرز دایره و در امتداد خط واصل مبدأ به مرکز دایره قرار می گیرد.
⚙️ روش های حل
روش های اصلی حل QCDP عبارتند از:
روش های نقطه درونی (Interior-Point Methods): کارآمدترین روش برای QCDP های محدب.
تبدیل به SOCP: بسیاری از QCDP ها قابل تبدیل به SOCP هستند و با حل کننده های SOCP حل می شوند [citation:9].
روش SQP (Sequential Quadratic Programming): برای مسائل غیرمحدب.
روش های تجزیه (Decomposition Methods): برای مسائل بزرگ مقیاس.
📝 نکته مهم: اگر هر یک از ماتریس های
\[ P_i \]معین مثبت نباشند، مسئله غیرمحدب می شود و یافتن جواب سراسری بسیار دشوارتر خواهد بود. در چنین مواردی از روش های شاخه و کران (Branch and Bound) یا الگوریتم های فراابتکاری استفاده می شود.
