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

Subject Areas : Statistics

M. Zangiabadi ¹ , H. Mansouri ² , M. Pirhaji ³

1 - Department of Applied Mathematics, Faculty of Mathematical Sciences, Shahrekord University, Shahrekord, Iran
2 - Department of Applied Mathematics, Faculty of Mathematical Sciences, Shahrekord University, Shahrekord, Iran
3 - Department of Applied Mathematics, Faculty of Mathematical Sciences, Shahrekord University, Shahrekord, Iran

Received: 2015-10-11 Accepted : 2016-11-11 Published : 2016-02-01

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

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.

References:

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)