Reduction of monotone linear complementarity problems over cones to linear programs over cones

Masakazu Kojima, Masayuki Shida and Susumu Shindoh

This short note presents a constructive way of reducing monotone LCPs (linear complementarity problems) over cones to LPs (linear programs) over cones. In particular, the monotone LCP in symmetric matrices, which was recently proposed by Kojima, Shindoh and Hara, is reducible to an SDP (semidefinite program). This gives a negative answer to their question whether the monotone LCP in symmetric matrices is an essential generalization of the SDP.

Research Reports on Information Sciences B-296, Feb. 1995