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

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

${\displaystyle {\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}}}$

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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 می‌توان پاسخ آن را در ${\displaystyle O(n^{3})}$ بدست آورد (با تجزیه چولسکی ماتریس X).

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

${\displaystyle {\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) را می‌توان به صورت زیر نوشت:

${\displaystyle {\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}}}$

که در آن ${\displaystyle P\succeq Q}$ یا ${\displaystyle 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

نرم‌افزارها

• 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