Content deleted Content added
Line 82:
=== 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, 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
:<math>\frac{\partial (\boldsymbol{c}^{\mathrm{T}} \boldsymbol{x})}{\partial x_q} = s_q\text{,}</math>
i.e., every unit increase in <math>x_q</math> will results in a decrease by <math>-s_q</math> in <math>\boldsymbol{c}^{\mathrm{T}} \boldsymbol{x}</math>.{{sfn|Nocedal|Wright|2006|p=369|loc=Eq. 13.24}} Since
:<math>\boldsymbol{B x_B} + \boldsymbol{A}_q x_q = \boldsymbol{b}\text{,}</math>
<math>\boldsymbol{x_B}</math> must be correspondingly decreased by <math>\Delta \boldsymbol{x_B} = \boldsymbol{B}^{-1} \boldsymbol{A}_q x_q</math> subject to <math>\boldsymbol{x_B} - \Delta \boldsymbol{x_B} \ge \boldsymbol{0}</math>. Let <math>\boldsymbol{d} = \boldsymbol{B}^{-1} \boldsymbol{A}_q</math>. If <math>\boldsymbol{d} \le \boldsymbol{0}</math>, no matter how much <math>x_q</math> is increased, <math>\boldsymbol{x_B} - \Delta \boldsymbol{x_B}</math> will stay nonnegative. Hence, <math>\boldsymbol{c}^{\mathrm{T}} \boldsymbol{x}</math> can be arbitrarily decreased, and thus the problem is unbounded. Otherwise, select an index <math>p = \operatorname{argmin}_{1 \le i \le m} \{x_i / d_i \mathop{|} d_i > 0\}</math> as the ''leaving index''. This choice effectively increases <math>x_q</math> from zero until <math>x_p</math> is reduced to zero while maintaining feasibility. The pivot operation concludes with replacing <math>\boldsymbol{A}_p</math> with <math>\boldsymbol{A}_q</math> in the basis.
== Notes and references ==
| |||