X hits on this document

36 views

0 shares

0 downloads

0 comments

11 / 15

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.

Document info
Document views36
Page views36
Page last viewedMon Dec 05 23:23:05 UTC 2016
Pages15
Paragraphs182
Words1167

Comments