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

**بهینه‌سازی نیمه معین** یا 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. &nbsp;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, .
* 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

رده:برنامه‌ریزی خطی
رده:بهینه‌سازی ریاضی
رده:بهینه‌سازی محدب
رده:تحقیق در عملیات
رده:مسئله‌های پی-کامل
رده:هندسه جبری حقیقی