semi definite programming

strict quadratic program:

شبیه linear programming است فقط به جای اینکه توابع خطی باشند درجه ۲ یا ثابت اند.

حاصل relax کردن چنین برنامه‌ای یک vector program است و ضرب متغیرها را بر حسب ضرب داخلی بردارها می‌نویسیم پس هر بردار باید به تعداد متغیرها درایه داشته باشد.

لازم نیست همیشه vector program را با این روش به دست بیاوریم.

معمولاً از این روش برای حل مسائل np-hard استفاده می‌شود.

اگر ضرایب ماتریسی تشکیل بدهند که به ازای هر بردار حقیقی x عبارت x^t A x >=0 باشد به آن positive semidefinite می‌گویند.

یک semidefinite program شبیه linear programming است اما به جای اینکه با بردارها کار کنیم با ماتریس‌ها کار می‌کنیم و باید ماتریس مقادیر متغیرها positive semidefinite و متقارن باشد. ضرب دو ماتریس به جای یک رابطه خطی یک ماتریس می‌دهد که برای به دست آوردن رابطه خطی جمع عناصر قطر اصلی آن (trace) را حساب می‌کنند.

separating oracle: به ازای هر نقطه غیرمجاز جواب اگر بتوان ابرصفحه‌ای پیدا کرد که آن را از جوابهای مجاز جدا کند به این ابر صفحه separating oracle می‌گویند. چنین چیزی را در زمان چندجمله‌ای می‌توان به دست آورد.

نتیجه: هر semidefinite program می‌تواند در زمان چندجمله‌ای بر حسب n و log(1/epsilon) با خطای جمعی اپسیلون با استفاده از روش ellipsoid حل شود.

نحوه محاسبه:

ابتدا باید امکان پذیر بودن ماتریس جواب A را چک کنیم. اگر در قیود صدق کرد و semidefinite بود و متقارن بود جواب است. این کار در زمان چندجمله‌ای ممکن است. در غیر این صورت برای آن می‌توان separating oracle پیدا کرد:

اگر A متقارن نیست به ازای یک درایه آن مقدار قرینه‌ی آن نسبت به قطر اصلی از خودش بیشتر است پس متغیر متناظر آنها با جهت نامساوی برعکس جواب است.

اگر A یک ماتریس positive semidefinite نباشد حتما مقدار ویژه‌ی منفی دارد. بردار متناظر آن را پیدا می‌کنیم. vYv^t>=0 جواب است. (Y ماتریس متغیرهاست.)

اگر هر قیدی نقض شود، خودش یک ابرصفحه جداکننده می‌دهد.

(می‌توان برای حل vector programming از رند کردن تصادفی بردارها استفاده کرد.)