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

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

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

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

روابط معادل 
ماتریس  با سایز  را مثبت نیمه معین می‌نامیم در صورتی که ماترس گرادیان مجموعه‌ای از بردارها باشد (یعنی بردارهای  وجود داشته باشند که که  به ازای همهٔ مقادیر ). در این صورت داریم . (توجه کنید که مثبت نیمه معین بودن تعاریف مختلف دارد.)

فرض کنید  فضای تمام ماتریس‌های حقیقی متقارن  باشد. در اینصورت تعریف می‌کنیم

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

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

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

فرم دیگر (dual) 
با داشتن فرم اولیه

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

که در آن  یا .

مثال‌ها

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

منابع 

 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, .
 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

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