A path-following feasible interior-point algorithm for mixed symmetric cone linear complementarity problems

Authors

Department of Applied Mathematics, Faculty of Mathematical Sciences, Shahrekord University, Shahrekord, Iran

Abstract

In this paper, we propose a feasible interior-point algorithm for mixed symmetric cone linear complementarity problems which are a general class of complementarity problems. The symmetrization of the search directions used in this paper is based on Nesterov and Todd scaling scheme. By using Euclidean Jordan algebra, we prove the convergence analysis of the proposed algorithm and show that the complexity bound of the algorithm matches the currently best known iteration bound for feasible interior-point methods.

Keywords


Article Title [Persian]

یک الگوریتم نقطه درونی شدنی برای مسائل مکمل خطی ترکیبی بر روی مخروط‌های متقارن

Authors [Persian]

  • مریم زنگی‌آبادی
  • حسین منصوری
  • محمد پیرحاجی
گروه ریاضی کاربردی، دانشکده علوم ریاضی، دانشگاه شهرکرد، شهرکرد، ایران
Abstract [Persian]

در این مقاله، یک روش نقطه درونی شدنی برای حل مسائل مکمل خطی ترکیبی متقارن که یک کلاس کلی و جامع از مسائل مکمل خطی می‌یاشند ارائه خواهیم می­شود. جهت­های جستجوگر نیوتن با استفاده از روش نسترو تاد متقارن­سازی خواهند شد و با بکارگیری جبر جردن اقلیدسی  همگرایی الگوریتم ارائه شده در این مقاله اثبات می­شود. نشان داده می­شود که پیچیدگی الگوریتم پیشنهادی منطبق بر بهترین کران پیچیدگی بدست آمده بوسیله روش‌های نقطه درونی شدنی برای حل مسائل بهینه­سازی است.




 

Keywords [Persian]

  • مساله‌ی مکمل خطی ترکیبی
  • روش نقطه درونی شدنی
  • آنالیز همگرایی
  • پیچیدگی چند جمله‌ای

1. Roos, C. A full-Newton step O (n) infeasible interior-point algorithm for linear optimiza- tion. SIAM J. Optim., 16 (4), 1110-1136 (2006)

2. Faraut, J., and Koranyi, A.: Analysis on Symmetric Cones. Oxford University Press, New York (1994)

3. Potra, F.A.: An O (n) infeasible-interiorpoint algorithm for LCP with quadratic conver-gence. Ann. Oper. Res., 62, 81-102 (1996)

4. Potra, F.A.: An infeasible interior-point method for linear complementarity problems over symmetric cones. in Proceedings of the 7th International Conference of Numerical Analysis and Applied Mathematics, Rethymno, Crete, Greece, 18-22 September (2009)

 5. Wang, G.Q., Yue, Y., and Ci, X.Z.: Weighted-path-following interior-point algorithm to monotone mixed linear complementarity problem. Fuzzy Inf. Eng., 4, 435-445 (2009)

6. Gu, G., Zangiabadi, M., and Roos, C.: Full Nesterov-Todd step interior-point methods for symmetric optimization. Eur. J. Oper. Res., 214(3), 473-484 (2011)