A full Nesterov-Todd step infeasible interior-point algorithm for symmetric cone linear complementarity problem

Document Type: Research Paper


1 Azarbaijan university of tarbiat moallem

2 Sharif University of Technology


‎A full Nesterov-Todd (NT) step infeasible interior-point algorithm‎ ‎is proposed for solving monotone linear complementarity problems‎ ‎over symmetric cones by using Euclidean Jordan algebra‎. ‎Two types of‎ ‎full NT-steps are used‎, ‎feasibility steps and centering steps‎. ‎The‎ ‎algorithm starts from strictly feasible iterates of a perturbed‎ ‎problem‎, ‎and, using the central path and feasibility steps, find‎s ‎strictly feasible iterates for the next perturbed problem‎. ‎By using‎ ‎centering steps for the new perturbed problem‎, ‎strictly feasible‎ ‎iterates are obtained to be close enough to the central path of the‎ ‎new perturbed problem‎. ‎The starting point depends on two positive‎ ‎numbers $rho_p$ and $rho_d$‎. ‎The algorithm terminates either by‎ ‎finding an $epsilon$-solution or detecting that the symmetric cone ‎linear complementarity problem has no optimal solution with‎ ‎vanishing duality gap satisfying a condition in terms of $rho_p$‎ ‎and $rho_d$‎. ‎The iteration bound coincides with the best known‎ ‎bound for infeasible interior-point methods‎.


Main Subjects