آشنایی با برنامه ریزی مخروطی درجه دوم

رده خاصی از مسائل غیرخطی، جز دسته مسائل برنامه ریزی مخروطی درجه دوم (second order conic programs) قرار می‌گیرند که در زمینه‌های متعدد علوم کنترل، سرمایه‌گذاری، علوم مهندسی و پزشکی و عیره کاربرد دارند. امروزه با پیشرفت علوم رایانشی، این دسته مسایل با استفاده از الگوریتم‌های تخصصی نقطه درونی (interior point) که در اکثر نرم‌افزارهای تجاری توسعه داده شده‌اند قابل حل هستند.

 

فرم ریاضی این نوع مخروط در ذیل آمده است:

$$\textbf{minimize} \quad f^Tx \\ s.t. \quad \|A_ix+b_i\|^2 \leq (c_i^Tx+d_i)^2 \quad \forall i \\ c_i^Tx+d_i \geq 0 \quad \forall i$$

به عبارت دیگر شرایط زیر بایستی برقرار باشند:

x'Qx <= y^2 where y >= 0 and Q is PSD
x'Qx <= yz where y >= 0 , z >= 0, and Q is PSD

بنابراین خواص مدل های دسته SOCP را در چهار مورد می توان معرفی کرد:

۱- قابل تبدیل به فرم استاندارد برنامه ریزی درجه دوم

۲- عدم نیمه معین مثبت بودن

۳- دارای فضای محدب

۴- کارایی حل با استفاده از الگوریتم های نقطه داخلی

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

$$\textbf{minimize} \quad \sum_j \sqrt {(x-a_j)^2+(y-b_j)^2}$$

که در این رابطه \( (x,y) \) مختصات تسهیل جدید و \( (a_j,b_j) \) مختصات تسهیلات قدیمی می باشند.

واضح است که این مدل به این صورت را در نرم‌افزارهای بهینه‌سازی شامل Gurobi و CPLEX نمی‌توان پیاده کرد، تابع شامل عبارت رادیکال می باشد. بایستی توجه کرد که عبارات داخل جذر مثبت و توان دوم بوده و بنابراین شامل مجموعه ای محدب است. متعاقبا یک رابطه آفینی تعریف کرده و ارتباط آن را با مجموعه محدب توسط مفهوم اپی‌گراف (epigraph) مشخص می‌کنیم. در این صورت مدل به مخروط درجه دوم (SOCP) تبدیل می شود.

$$\textbf{minimize} \quad \textstyle{\sum_j} z_j \\ (x-a_j)^2 + (y-b_j)^2 \leq z_j ^2 \quad \forall j \in C \\ z_j \geq 0$$

 

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

دیدگاه بگذارید