A Descent Algorithm for the Complementary Programming Problem.

In this memorandum, we propose a descent type algorithm for a class of Complementary Programming Problems. In general, these are linear programs with the further restriction that certain specified pairs of variables be orthogonal to each other. Here we study a particular class that arises in the solution of certain variational inequality problems and network design and show that our algorithm converges to a solution if the underlying matrix is a P matrix, that is, a matrix all of whose principle minors are positive.