Content deleted Content added
Line 81:
=== Pivot operation ===
If the KKT conditions are violated, a ''pivot operation'' consisting of introducing a column of <math>\boldsymbol{N}</math> into the basis at the expense of an existing column in <math>\boldsymbol{B}</math> is performed. In the absence of [[Degeneracy (mathematics)|degeneracy]], a pivot operation always results in a strict decrease in <math>\boldsymbol{c}^{\mathrm{T}} \boldsymbol{x}</math>. Therefore, if the problem is bounded, the revised simplex method must terminate at an optimal vertex after repeated pivot operations because there are only a finite number of vertices.{{sfn|Nocedal|Wright|2006|p=370|loc=Theorem 13.4}}
Select an index <math>m < q \le n</math> such that <math>s_q < 0</math> as the ''entering index''. The corresponding column of <math>\boldsymbol{A}</math>, <math>\boldsymbol{A}_q</math>, will be moved into the basis, and <math>x_q</math> will be allowed to increase from zero. It can be shown that
| |||