Kernel-based interior-point methods for monotone linear complementarity problems over symmetric cones

Kernel-based interior-point methods for monotone linear complementarity problems over symmetric cones

Lesaja, G.
Roos, C.

Electrical Engineering, Mathematics and Computer Science

Software Computer Technology

2011-04-20

We present an interior-point method for monotone linear complementarity problems over symmetric cones (SCLCP) that is based on barrier functions which are defined by a large class of univariate functions, called eligible kernel functions. This class is fairly general and includes the classical logarithmic function, the self-regular functions, as well as many non-self-regular functions as special cases. We provide a unified analysis of the method and give a general scheme on how to calculate the iteration bounds for the entire class. We also calculate the iteration bounds of both large-step and short-step versions of the method for ten frequently used eligible kernel functions. For some of them we match the best known iteration bound for large-step methods, while for short-step methods the best iteration bound is matched for all cases. The paper generalizes results of Lesaja and Roos (SIAM J. Optim. 20(6):3014–3039, 2010) from P ?(?)-LCP over the non-negative orthant to monotone LCPs over symmetric cones.

linear complementarity problem
Euclidean Jordan algebras and symmetric cones
interior-point method
Kernel functions
polynomial complexity

http://resolver.tudelft.nl/uuid:1dbbd326-ef95-4435-9cf1-d15f87defdae

https://doi.org/10.1007/s10957-011-9848-9

Springer

0022-3239

http://www.springerlink.com/content/x462370006473264/

Journal of Optimization Theory and Applications, 150 (3), 2011

Institutional Repository

journal article

(c) 2011 Springer Science+Business Media, LLC