Revised simplex method: Difference between revisions

Revision as of 09:31, 11 March 2014

Revision as of 09:31, 11 March 2014

Line 80:

If <math>\boldsymbol{s_N} \ge \boldsymbol{0}</math> at this point, the KKT conditions are satisfied, and thus <math>\boldsymbol{x}</math> is optimal.

=== 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&nbsp;13.4}}

Line 93:

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

== Practical issues ==

=== Degeneracy ===

{{seealso|Simplex method#Degeneracy: Stalling and cycling}}

Because the revised simplex method is mathematically equivalent to the simplex method, it also suffers from degeneracy, where a pivot operation does not results in a decrease in <math>\boldsymbol{c}^{\mathrm{T}} \boldsymbol{x}</math>, and a chain of pivot operations causes the basis to cycle. A perturbation or lexicographic strategy can be used to prevent cycling and guarantee termination.{{sfn|Nocedal|Wright|2006|p=381|loc=§13.5}}

=== Basis representation ===

Two [[System of linear equations|linear systems]] involving <math>\boldsymbol{B}</math> are present in the revised simplex method:

Line 110:

Instead of refactorizing <math>\boldsymbol{B}</math> after each pivot operation, usually an [[LU factorization]] is directly updated, for which purpose there exist several strategies such as the Bartels−Golub method. However, the amount of data representing the updates as well as numerical errors builds up over time and makes periodic refactorization necessary.{{sfn|Morgan|1997|loc=§2}}{{sfn|Nocedal|Wright|2006|p=372|loc=§13.4}}

== Notes and references ==

=== Notes ===

{{notelist}}

=== References ===

{{reflist|2}}

=== Bibliography ===

{{refbegin}}

* {{cite thesis