Skoči na glavni sadržaj

Izvorni znanstveni članak

https://doi.org/10.17535/crorr.2018.0004

A full Nesterov-Todd step primal-dual path-following interior-point algorithm for semidefinite linear complementarity problems

Mohamed Achache ; Laboratoire de Mathématiques Fondamentales et Numériques, Université de Sétif1, Sétif, Algérie
Nersine Tabchouche ; Laboratoire de Mathématiques Fondamentales et Numériques, Université de Sétif1, Sétif, Algérie


Puni tekst: engleski pdf 346 Kb

str. 37-50

preuzimanja: 370

citiraj


Sažetak

In this paper, a feasible primal-dual path-following interior-point algorithm for monotone semidefinite linear complementarity problems is proposed. At each iteration, the algorithm uses only full Nesterov-Todd feasible steps for tracing approximately the central-path and getting an approximated solution of this problem. Under a new appropriate choices of the threshold \(\tau\) which defines the size of the neighborhood of the central-path and of the update barrier parameter \(\theta\), we show that the algorithm is well-defined and enjoys the locally quadratically convergence. Moreover, we prove that the short-step algorithm deserves the best known iteration bound, namely, \(\O(\sqrt{n} log \frac{n}{\epsilon}))\). Finally, some numerical results are reported to show the practical performance of the algorithm.

Ključne riječi

Semidefinite linear complementarity, Interior-point algorithm, Short-step method, Polynomial complexity

Hrčak ID:

203892

URI

https://hrcak.srce.hr/203892

Posjeta: 748 *