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

Autor:	Mohammad Pirhaji, Maryam Zangiabadi, Hossein Mansouri, Saman H. Amin
Jazyk:	angličtina
Rok vydání:	2018
Předmět:	linear complementarity problem symmetric cone ellipsoidal approximation interior-point methods polynomial complexity Mathematics QA1-939
Zdroj:	Mathematical Modelling and Analysis, Vol 23, Iss 1 (2018)
Druh dokumentu:	article
ISSN:	1392-6292 1648-3510
DOI:	10.3846/mma.2018.001
Popis:	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.
Databáze:	Directory of Open Access Journals
Externí odkaz:	https://doaj.org/article/cbf3ff3a84b84586a1ccca912e54caa8 Zobrazit plný text záznamu View record in DOAJ Plný text ve formátu PDF