در ادامه پست قبلی با عنوان مقدمه ای بر محاسبه پیچیدگی محاسباتی، در این قسمت به طور خاص بر روی محاسبه پیچیدگی محاسباتی برای الگوریتمهای حاوی مسئله بهینه سازی محدب تمرکز می کنیم. با ما همراه باشید.
اولین مرحله اینه که شما باید بدونید یا بتونید تخمین بزنید که الگوریتم شما در هر کدام از حلقه ها چند بار تکرار میشود تا همگرایی حاصل شود. اگه با CVX مسئله تون را حل میکنید این برنامه یک تخمینی از تعداد تکرار مورد نیاز ارائه میدهد.
مرتبه تعداد تکرارهای مورد نیاز در CVX می تواند بسته به نمونه مسئله و داده های ورودی متفاوت باشد. CVX برای حل مسائل بهینه سازی محدب از یک روش نقطه داخلی (مخصوصاً از یک روش primal-dual) استفاده می کند و تعداد تکرارهای مورد نیاز این روش می تواند به عوامل مختلفی مانند اندازه مسئله، دقت مورد نیاز، تعداد شرط مسئله و نقطه امکان پذیر اولیه بستگی داشته باشد.
با این حال، به طور کلی، تعداد تکرارهای مورد نیاز توسط CVX را می توان با مرتبه O(sqrt(n*log(1/epsilon))) تخمین زد، که در آن n بعد مسئله است (یعنی تعداد متغیرهای تصمیم گیری) و اپسیلون تلورانس برای optimality gap است. تعداد واقعی تکرارها بسته به نمونه مشکل خاص و داده های ورودی ممکن است بیشتر یا کمتر باشد.
در قدم دوم لازم هستش که پیچیدگی محاسباتی را برای سالور مورد نیازتون در نظر بگیرید.
در اینجا بدترین پیچیدگی های O بزرگ برای روش های تکراری Gradient Descent، Sedumi، SDPT3، روش نیوتن و همچنین زبان های مدل سازی CVX و YALMIP آمده است:
- Gradient Descent: O((n + m) * (1 / epsilon))
- Sedumi: O(n^3 * (log(n) + log(1/epsilon)))
- SDPT3: O(n^3 * (log(n) + log(1/epsilon)))
- Newton's Method: O((n + m)^3)
- CVX (using interior point method): O(n^3 + n^2*m + n^2*(log(1/epsilon)))
- YALMIP (using interior point method): O(n^3 + n^2*m + n^2*(log(1/epsilon)))
باز هم، اینها در بدترین حالت پیچیدگی های O بزرگ هستند و عملکرد واقعی یک الگوریتم ممکن است به عوامل مختلفی مانند نمونه مسئله خاص، داده های ورودی و اجرای الگوریتم بستگی داشته باشد.
