##
A Strongly Polynomial Rounding Procedure Yielding
A Maximally Complementary Solution for
$P_*(\kappa)$ Linear Complementarity Problems

###
T. Illés, J. Peng, C. Roos and T. Terlaky

We deal with Linear Complementarity Problems (LCPs) with $P_*(\kappa)$
matrices. First we establish the convergence rate of the complementary
variables along the central path. The central path is parameterized by
the barrier parameter $\mu$, as usual. Our elementary proof reproduces
the known result that the variables on, or close to the central path
fall apart in three classes in which these variables are O(1), O(\mu)
and O(sqrt(\mu)), respectively. The constants hidden in these bounds
are expressed in, or bounded by, the input data. All this is
preparation for our main result: a strongly polynomial rounding
procedure. Given a point with sufficiently small complementarity gap
and close enough to the central path, the rounding procedure produces
a maximally complementary solution in at most O(n^3) arithmetic
operations.
The result implies that Interior Point Methods (IPMs) not only converge
to a complementary solution of $P_*(\kappa)$ LCPs but, when furnished
with our rounding procedure, they can produce a maximally complementary
(exact) solution in polynomial time.
Report 98-15,

Faculty of Information Technology and Systems

Subfaculty of Technical Mathematics and Informatics,

Department of Statistics, Stochastic and Operations Research

Delft University of Technology,

P.O. Box 5031, 2600 GA Delft, The Netherlands.

Contact: terlaky@ssor.twi.tudelft.nl