IE417 Lecture 24
Convergence of Lemke’s Algorithm
De nition 1. A matrix M is copositive if z>Mz ≥ 0 for every z ≥ 0. M is copositive plus if z ≥ 0 and z>Mz = 0 implies M + M>)z = 0.
Recall that a solution is called nondegenerate if all the basic variables have positive value.
Theorem 1. If each CBFS is nondegenerate and M is copositive-plus, then Lemke’s algorithm terminates in a nite number of steps.
If M has nonnegative entries with positive diagonal elements, then M is copositive-plus.