An arc search interior-point algorithm for monotone linear complementarity problems over symmetric cones

Mathematical Modelling and Analysis

Hossein Mansouri¹  Maryam Zangiabadi¹  Mohammad Pirhaji¹  Saman H. Amin² 

[1] Department of Applied Mathematics, Shahrekord University Shahrekord, Iran;Department of Mechanical and Industrial Engineering, Ryerson University Toronto, Canada;

关键词: linear complementarity problem;    symmetric cone;    ellipsoidal approximation;    interior-point methods;    polynomial complexity;   

DOI  :  10.3846/mma.2018.001

来源: DOAJ

【 摘 要 】

An arc search interior-point algorithm for monotone symmetric cone linear complementarity problem is presented. The algorithm estimates the central path by an ellipse and follows an ellipsoidal approximation of the central path to reach an ε-approximate solution of the problem in a wide neighborhood of the central path. The convergence analysis of the algorithm is derived. Furthermore, we prove that the algorithm has the complexity bound O (√rL) using Nesterov-Todd search direction and O (√rL) by the xs and sx search directions. The obtained iteration complexities coincide with the best-known ones obtained by any proposed interior-point algorithm for this class of mathematical problems.

【 授权许可】

Unknown