# IE417 Lecture 24

10

# 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.