Simplex Algorithm: Difference between revisions

Revision as of 07:02, 8 May 2024

Context:
- It can require 1 trillion edges traversals to find the optimal corner in problems with 41 dimensions. (Klee & Minty, 1972)
- It can avoid a degenerative solution by Pivot Rules.
- It must maintain a Canonical Tableau.
- It can (typically) take [math]\displaystyle{ 2m }[/math] to [math]\displaystyle{ 3m }[/math] iterations (where [math]\displaystyle{ m }[/math] is the number of equality constraints).
- …
Counter-Example(s):
- an Interior Point Algorithm.
See: Linear Equation, Linear System.

(Wikipedia, 2012) ⇒ http://en.wikipedia.org/wiki/Simplex_algorithm
- In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.
  The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial cones, and these become proper simplices with an additional constraint.^[1]^[2]^[3] The simplicial cones in question are the corners (i.e., the neighborhoods of the vertices) of a geometric object called a polytope. The shape of this polytope is defined by the constraints applied to the objective function.

↑ Stone, Richard E.; Tovey, Craig A. (1991). "The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review 33 (2): 220–237. doi:10.1137/1033049. JSTOR 2031142. MR 1124362.
↑ Stone, Richard E.; Tovey, Craig A. (1991). "Erratum: The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review 33 (3): 461. doi:10.1137/1033100. JSTOR 2031443. MR 1124362.
↑ Strang, Gilbert (1 June 1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer (New York: Springer) 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 883185 '''883185'''.

http://en.wikipedia.org/wiki/Simplex_algorithm#Algorithm
- Let a linear program be given by a canonical tableau. The simplex algorithm proceeds by performing successive pivot operations which each give an improved basic feasible solution; the choice of pivot element at each step is largely determined by the requirement that this pivot does improve the solution.

Carreira-Perpiñán, Miguel Á. “Simplex Method." From MathWorld -- A Wolfram Web Resource, created by Eric W. Weisstein. http://mathworld.wolfram.com/SimplexMethod.html
- QUOTE: The simplex method is a method for solving problems in linear programming. This method, invented by George Dantzig in 1947, tests adjacent vertices of the feasible set (which is a polytope) in sequence so that at each new vertex the objective function improves or is unchanged. The simplex method is very efficient in practice, generally taking [math]\displaystyle{ 2m }[/math] to [math]\displaystyle{ 3m }[/math] iterations at most (where m is the number of equality constraints), and converging in expected polynomial time for certain distributions of random inputs (Nocedal and Wright 1999, Forsgren 2002). However, its worst-case complexity is exponential, as can be demonstrated with carefully constructed examples (Klee and Minty 1972).

(Kelner & Spielman, 2006) ⇒ Jonathan A. Kelner, and Daniel A. Spielman. (2006). “A Randomized Polynomial-time Simplex Algorithm for Linear Programming.” In: Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing. doi:10.1145/1132516.1132524

(Spielman & Teng, 2004a) ⇒ Daniel A. Spielman, and Shang-Hua Teng. (2004). “Smoothed Analysis of Algorithms: Why the simplex algorithm usually takes polynomial time.” In: Journal of the ACM (JACM) 51, no. 3.
(Spielman & Teng, 2004b) ⇒ Daniel A. Spielman, and Shang-Hua Teng. (2004). “Nearly-linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems.” In: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing. doi:10.1145/1007352.1007372

(Forsgreen et al., 2002) ⇒ A. Forsgren, P. E. Gill, and M. H. Wright. (2002). “Interior Methods for Nonlinear Optimization.” In: SIAM Rev. 44.

Nocedal, J. and Wright, S. J. (1999). “Numerical Optimization." New York: Springer-Verlag.

(Klee & Minty, 1972) ⇒ Victor Klee and George Minty. (1972). “How Good is the Simplex Algorithm?". In Shisha, Oved. Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin). New York-London: Academic Press..

(Nelder & Mead, 1965) ⇒ J. A. Nelder, and R. Mead. (1965). “A Simplex Method for Function Minimization.” In: Comp. J. 7.

(Dantzig, 1963) ⇒ G. B. Dantzig. (1963). “Linear Programming and Extensions.” Princeton University Press.

@@ Line 26: / Line 26: @@
 === 2011 ===
-* Carreira-Perpiñán, Miguel Á. "Simplex Method." From MathWorld -- A Wolfram Web Resource, created by Eric W. Weisstein. http://mathworld.wolfram.com/SimplexMethod.html
+* Carreira-Perpiñán, Miguel Á. “Simplex Method." From MathWorld -- A Wolfram Web Resource, created by Eric W. Weisstein. http://mathworld.wolfram.com/SimplexMethod.html
 ** QUOTE: The [[Simplex Algorithm|simplex method]] is a method for [[linear programming task|solving problems in linear programming]]. [[Simplex Algorithm|This method]], invented by George Dantzig in 1947, tests adjacent vertices of the feasible set (which is a polytope) in sequence so that at each new vertex the [[objective function]] improves or is unchanged. The [[Simplex Algorithm|simplex method]] is very efficient in practice, generally taking <math>2m</math> to <math>3m</math> iterations at most (where m is the number of [[equality constraint]]s), and [[converging]] in expected [[polynomial time]] for certain distributions of random inputs (Nocedal and Wright 1999, Forsgren 2002). However, its worst-case complexity is exponential, as can be demonstrated with carefully constructed examples (Klee and Minty 1972).