A critical index algorithm for nearest point problems on simplicial cones

Abstract

We consider the linear complementarity problem ( q, M ) in which M is a positive definite symmetric matrix of order n. This problem is equivalent to a nearest point problem [ Γ; b ] in which Γ = { A . 1 , ⋯, A. n } is a basis for R n , b is a given point in R n ; and it is required to find the nearest point in the simplicial cone Pos( Γ ) to b. We develop an algorithm for solving the linear complementarity problem ( q, M ) or the equivalent nearest point problem [ Γ; b ]. Computational experience in comparison with an existing algorithm is presented.