بهینه‌سازی نیمه‌معین

بهینه‌سازی نیمه معین یا SDP یک مسئله بهینه‌سازی برای تابع هدف خطی است.

بهینه‌سازی نیمه معین تقریباً زمینه‌ای جدید است و در حال رشد است. بسیاری از مسائل در زمینه‌های تحقیق در عملیات و بهینه‌سازی ترکیبیاتی را می‌توان به صورت تقریبی به صورت بهینه‌سازی نیمه معین در آورد. تقریباً همهٔ مسائل برنامه‌ریزی خطی را می‌توان به صورت بهینه‌سازی نیمه معین تعریف کرد.

مقدمات

در مسئلهٔ برنامه‌ریزی خطی قصد بهینه‌سازی تابعی خطی روی یک چندوجهی را داریم، اما تابع و شروط بهینه‌سازی باید توابعی خطی از متغیرها باشند. در یک مسئلهٔ بهینه‌سازی نیمه معین می‌توان از ضرب داخلی متغیرها نیز استفاده کرد. به عبارت دیگر:

$\begin{array}{cc}\underset{x^1,\dots ,x^n\in {ℝ}^n}{\min }& \sum _{i,j\in [n]}{c}_{i,j}(x^i\cdot x^j)\\ \text{subject to}& \sum _{i,j\in [n]}{a}_{i,j,k}(x^i\cdot x^j)\le b_k\mathrm{\forall }k.\end{array}$

روابط معادل

ماتریس $M$ با سایز $n\times n$ را مثبت نیمه معین می‌نامیم در صورتی که ماترس گرادیان مجموعه‌ای از بردارها باشد (یعنی بردارهای $x^1,\dots ,x^n$ وجود داشته باشند که که $m_{i,j}=x^i\cdot x^j$ به ازای همهٔ مقادیر $i,j$). در این صورت داریم $M⪰0$. (توجه کنید که مثبت نیمه معین بودن تعاریف مختلف دارد.)

فرض کنید ${𝕊}^n$ فضای تمام ماتریس‌های حقیقی متقارن $n\times n$ باشد. در اینصورت تعریف می‌کنیم

$⟨A,B{⟩}_{{𝕊}^n}=\mathrm{t}\mathrm{r}(A^{T}B)=\sum _{i=1,j=1}^n{A}_{ij}{B}_{ij}.$

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

$\begin{array}{cc}\underset{X\in {𝕊}^n}{\min }& ⟨C,X{⟩}_{{𝕊}^n}\\ \text{subject to}& ⟨A_k,X{⟩}_{{𝕊}^n}\le b_k,k=1,\dots ,m\\ & X⪰0\end{array}$

با اضافه کردن متغیرهای اضافی می‌توان مسئله را به اینصورت عوض کرد:

$\begin{array}{cc}\underset{X\in {𝕊}^n}{\min }& ⟨C,X{⟩}_{{𝕊}^n}\\ \text{subject to}& ⟨A_i,X{⟩}_{{𝕊}^n}=b_i,i=1,\dots ,m\\ & X⪰0.\end{array}$

با داشتن تعریف استاندارد SDP می‌توان پاسخ آن را در $O(n^3)$ بدست آورد (با تجزیه چولسکی ماتریس X).

فرم دیگر (dual)

با داشتن فرم اولیه

$\begin{array}{cc}\underset{X\in {𝕊}^n}{\min }& ⟨C,X{⟩}_{{𝕊}^n}\\ \text{subject to}& ⟨A_i,X{⟩}_{{𝕊}^n}=b_i,i=1,\dots ,m\\ & X⪰0\end{array}$

می‌توان فرم دیگر مسئلهٔ فوق (P-SDP) را می‌توان به صورت زیر نوشت:

$\begin{array}{cc}\underset{y\in {ℝ}^m}{\max }& ⟨b,y{⟩}_{{ℝ}^m}\\ \text{subject to}& \sum _{i=1}^m{y}_i{A}_i⪯C\end{array}$

که در آن $P⪰Q$ یا $P-Q⪰0$.

کاربردها

روشهای بهینه‌سازی نیمه معین کاربردهای بسیاری در مسائل بهینه‌سازی ترکیبیاتی مثلاً مسئلهٔ برش بیشینه دارند. همچنین کاربردهای بسیار در کنترل دارند.

منابع

• Lieven Vandenberghe, Stephen Boyd, "Semidefinite Programming", SIAM Review 38, March 1996, pp.  49–95. pdf
• Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming", Report PNA-R0210, CWI, Amsterdam, April 2002. optimization-online
• E. de Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications", Kluwer Academic Publishers, March 2002, الگو:ISBN.
• Robert M. Freund, "Introduction to Semidefinite Programming (SDP), SDP-Introduction

پیوند به بیرون

• Links to introductions and events in the field
• Lecture notes from Laszlo Lovasz on Semidefinite Programming

نرم‌افزارها

• JOptimizer: open source java library for convex optimization
• Overview of existing software
• NEOS Solvers: A server that runs multiple algorithms for solving SDPs and other optimization problems
• SeDuMi: (Self-Dual-Minimization) solves optimization problems over symmetric cones (this includes semidefinite optimization).
• YALMIP: MATLAB optimization toolbox and frontend for many sdp solver
• PICOS: a simple python interface for sdp solvers
• cvx: a MATLAB frontend that uses either SeDuMi or SDPT3
• cvxopt: a python solver