پرش به محتوا

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

از ویکی‌پدیا، دانشنامهٔ آزاد

بهینه‌سازی نیمه معین یا 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, ISBN 1-4020-0547-4.
  • Robert M. Freund, "Introduction to Semidefinite Programming (SDP), SDP-Introduction

پیوند به بیرون

[ویرایش]
نرم‌افزارها