برنامه ریزی نیمه معین (Semidefinite Programming - SDP)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
برنامه ریزی نیمه معین (Semidefinite Programming - SDP) :
📌 تعریف و فرم استاندارد
برنامه ریزی نیمه معین (SDP) یکی از عمومی ترین و قدرتمندترین شاخه های بهینه سازی محدب است. در SDP، متغیرها ماتریس های متقارن هستند و قید اصلی این است که یک ترکیب خطی از این ماتریس ها باید نیمه معین مثبت (Positive Semidefinite) باشد. شکل استاندارد SDP به صورت زیر است [citation:5][citation:7]:
\[ \text{Minimize} \quad \sum_{i,j=1}^n C_{ij} X_{ij} \] \[ \text{Subject to:} \quad \sum_{i,j=1}^n A_{ijk} X_{ij} = b_k, \quad k = 1, \ldots, m \] \[ \quad X \succeq 0 \quad \text{(مثبت نیمه معین)} \]در فرم دیگر (مسئله اولیه)، SDP به صورت زیر نوشته می شود [citation:5]:
\[ \text{Maximize} \quad \sum_{k=1}^m b_k y_k \] \[ \text{Subject to:} \quad \sum_{k=1}^m y_k A_k \preceq C \]در اینجا
\[ X \]و
\[ A_k \]و
\[ C \]ماتریس های متقارن هستند و علامت
\[ \succeq \]به معنای نیمه معین مثبت بودن است [citation:5].
🎯 اهمیت SDP
SDP به دلیل کاربردهای گسترده و قدرت بیان بالا، یکی از مهم ترین زمینه های تحقیق در بهینه سازی است. کاربردهای آن شامل موارد زیر است [citation:2][citation:7][citation:10]:
ترکیبیات: تقریب مسائل NP-سخت مانند مسئله برش بیشینه (Max-Cut) با استفاده از relaxation SDP (روید مشهور Goemans-Williamson) [citation:10].
کنترل: طراحی کنترل کننده با نامساوی های ماتریسی خطی (LMI) [citation:10].
یادگیری ماشین: کاهش ابعاد، یادگیری کرنل، و PCA مقاوم [citation:10].
مدیریت انرژی: برنامه ریزی توقف نیروگاه های هسته ای و مسائل تعادل عرضه و تقاضا [citation:2][citation:7].
بهینه سازی کوانتومی: بهینه سازی حالت ها و عملگرهای کوانتومی [citation:10].
آمار و اقتصادسنجی: مدل سازی ماتریس های همبستگی [citation:10].
⚡ چالش های محاسباتی
روش های کلاسیک نقطه درونی برای SDP دارای پیچیدگی محاسباتی بالا (حدود
\[ O(n^3) \]تا
\[ O(n^4) \]) هستند و برای مسائل بزرگ (بیش از چند هزار متغیر) عملا غیرقابل حل می شوند [citation:10]. به همین دلیل، تحقیقات اخیر بر روی روش های مرتبه اول مانند PDHG (Primal-Dual Hybrid Gradient) متمرکز شده است که امکان حل مسائل بزرگ مقیاس را با استفاده از موازی سازی و GPU فراهم می کنند [citation:10].
