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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

بهینه‌سازی نیمه معین یا 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

لنک‌های خارجی[ویرایش]

نرم‌افزارها