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

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

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

مقدمات

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

{\begin{array}{rl}{\displaystyle \min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n}}}&{\displaystyle \sum _{i,j\in [n]}c_{i,j}(x^{i}\cdot x^{j})}\\{\text{subject to}}&{\displaystyle \sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}\qquad \forall k}.\\\end{array}}

روابط معادل

ماتریس $M$

با سایز

n\times n

را مثبت نیمه معین می‌نامیم در صورتی که ماترس گرادیان مجموعه‌ای از بردارها باشد (یعنی بردارهای

x^{1},\ldots ,x^{n}

وجود داشته باشند که که

m_{i,j}=x^{i}\cdot x^{j}

به ازای همهٔ مقادیر

i, j

). در این صورت داریم

M\succeq 0

. (توجه کنید که مثبت نیمه معین بودن تعاریف مختلف دارد.)

فرض کنید $\mathbb {S} ^{n}$

فضای تمام ماتریس‌های حقیقی متقارن

n\times n

باشد. در اینصورت تعریف می‌کنیم

$\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}.$

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

{\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0\end{array}}

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

{\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{i},X\rangle _{\mathbb {S} ^{n}}=b_{i},\quad i=1,\ldots ,m\\&X\succeq 0.\end{array}}

با داشتن تعریف استاندارد SDP می‌توان پاسخ آن را در $O(n^{3})$

بدست آورد (با تجزیه چولسکی ماتریس X).

فرم دیگر (dual)

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

{\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{i},X\rangle _{\mathbb {S} ^{n}}=b_{i},\quad i=1,\ldots ,m\\&X\succeq 0\end{array}}

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

{\begin{array}{rl}{\displaystyle \max _{y\in \mathbb {R} ^{m}}}&\langle b,y\rangle _{\mathbb {R} ^{m}}\\{\text{subject to}}&{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}

که در آن $P\succeq Q$

یا

P-Q\succeq 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 1-4020-0547-4.
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

نرم‌افزارها