![Unitcube](https://upload.wikimedia.org/wikipedia/commons/8/89/Unitcube.svg)
In
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
, the criss-cross algorithm is any of a family of
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s for
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
. Variants of the criss-cross algorithm also solve more general problems with
linear inequality constraints and
nonlinear
In mathematics and science, a nonlinear system is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathematicians, and many other ...
objective functions; there are criss-cross algorithms for
linear-fractional programming In mathematical optimization, linear-fractional programming (LFP) is a generalization of linear programming (LP). Whereas the objective function in a linear program is a linear function, the objective function in a linear-fractional program is a r ...
problems,
quadratic-programming problems, and
linear complementarity problem In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968.
...
s.
Like the
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 n ...
of
George B. Dantzig
George Bernard Dantzig (; November 8, 1914 – May 13, 2005) was an American mathematical scientist who made contributions to industrial engineering, operations research, computer science, economics, and statistics.
Dantzig is known for his ...
, the criss-cross algorithm is not a
polynomial-time algorithm
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
for linear programming. Both algorithms visit all 2
''D'' corners of a (perturbed)
cube
In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross.
The cube is the only r ...
in dimension ''D'', the
Klee–Minty cube
The Klee–Minty cube or Klee–Minty polytope (named after Victor Klee and George J. Minty) is a unit cube, unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorith ...
(after
Victor Klee
Victor LaRue Klee, Jr. (September 18, 1925 – August 17, 2007) was a mathematician specialising in convex sets, functional analysis, analysis of algorithms, optimization, and combinatorics. He spent almost his entire career at the University of ...
and
George J. Minty), in the
worst case
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
.
However, when it is started at a random corner, the criss-cross algorithm
on average visits only ''D'' additional corners.
[The simplex algorithm takes on average ''D'' steps for a cube. : ] Thus, for the three-dimensional cube, the algorithm visits all 8 corners in the worst case and exactly 3 additional corners on average.
History
The criss-cross algorithm was published independently by
Tamas Terlaky Tamas may refer to:
* ''Tamas'' (philosophy), a concept of darkness and death in Hindu philosophy
* Tamás (name), a given name in Hungarian (Thomas)
* ''Tamas'' (film), a 1987 TV series/movie directed by Govind Nihalani
* ''Tamas'' (novel), a ...
and by Zhe-Min Wang;
related algorithms appeared in unpublished reports by other authors.
Comparison with the simplex algorithm for linear optimization
![Simplex description](https://upload.wikimedia.org/wikipedia/commons/7/78/Simplex_description.png)
In linear programming, the criss-cross algorithm pivots between a sequence of bases but differs from the
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 n ...
. The simplex algorithm first finds a (primal-) feasible basis by solving a "''phase-one'' problem"; in "phase two", the simplex algorithm pivots between a sequence of basic ''feasible ''solutions so that the objective function is non-decreasing with each pivot, terminating with an optimal solution (also finally finding a "dual feasible" solution).
The criss-cross algorithm is simpler than the simplex algorithm, because the criss-cross algorithm only has one phase. Its pivoting rules are similar to the
least-index pivoting rule of Bland.
[
] Bland's rule uses only
sign
A sign is an object, quality, event, or entity whose presence or occurrence indicates the probable presence or occurrence of something else. A natural sign bears a causal relation to its object—for instance, thunder is a sign of storm, or me ...
s of coefficients rather than their
(real-number) order when deciding eligible pivots. Bland's rule selects an entering variables by comparing values of reduced costs, using the real-number ordering of the eligible pivots.
Unlike Bland's rule, the criss-cross algorithm is "purely combinatorial", selecting an entering variable and a leaving variable by considering only the signs of coefficients rather than their real-number ordering.
The criss-cross algorithm has been applied to furnish constructive proofs of basic results in
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices.
...
, such as the
lemma of Farkas.
While most simplex variants are monotonic in the objective (strictly in the non-degenerate case), most variants of the criss-cross algorithm lack a monotone merit function which can be a disadvantage in practice.
Description
The criss-cross algorithm works on a standard pivot tableau (or on-the-fly calculated parts of a tableau, if implemented like the revised simplex method). In a general step, if the tableau is primal or dual infeasible, it selects one of the infeasible rows / columns as the pivot row / column using an index selection rule. An important property is that the selection is made on the union of the infeasible indices and the standard version of the algorithm does not distinguish column and row indices (that is, the column indices basic in the rows). If a row is selected then the algorithm uses the index selection rule to identify a position to a dual type pivot, while if a column is selected then it uses the index selection rule to find a row position and carries out a primal type pivot.
Computational complexity: Worst and average cases
The
time complexity
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
of an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
counts the number of
arithmetic operation
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers—addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th cen ...
s sufficient for the algorithm to solve the problem. For example,
Gaussian elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
requires on the
order of'' D''
3 operations, and so it is said to have polynomial time-complexity, because its complexity is bounded by a
cubic polynomial
In mathematics, a cubic function is a function of the form f(x)=ax^3+bx^2+cx+d
where the coefficients , , , and are complex numbers, and the variable takes real values, and a\neq 0. In other words, it is both a polynomial function of degree ...
. There are examples of algorithms that do not have polynomial-time complexity. For example, a generalization of Gaussian elimination called
Buchberger's algorithm
In the theory of multivariate polynomials, Buchberger's algorithm is a method for transforming a given set of polynomials into a Gröbner basis, which is another set of polynomials that have the same common zeros and are more convenient for extract ...
has for its complexity an exponential function of the problem data (the
degree of the polynomials and the number of variables of the
multivariate polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
s). Because exponential functions eventually grow much faster than polynomial functions, an exponential complexity implies that an algorithm has slow performance on large problems.
Several algorithms for linear programming—
Khachiyan
Leonid Genrikhovich Khachiyan (; russian: Леони́д Ге́нрихович Хачия́н; May 3, 1952April 29, 2005) was a Soviet and American mathematician and computer scientist.
He was most famous for his ellipsoid algorithm (1979) fo ...
's
ellipsoidal algorithm,
Karmarkar
Narendra Krishna Karmarkar (born Circa 1956) is an Indian Mathematician. Karmarkar developed Karmarkar's algorithm. He is listed as an ISI highly cited researcher.
He invented one of the first provably polynomial time algorithms for linear pro ...
's
projective algorithm, and
central-path algorithms—have polynomial time-complexity (in the
worst case
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
and thus
on average). The ellipsoidal and projective algorithms were published before the criss-cross algorithm.
However, like the simplex algorithm of Dantzig, the criss-cross algorithm is ''not'' a polynomial-time algorithm for linear programming. Terlaky's criss-cross algorithm visits all the 2
''D'' corners of a (perturbed) cube in dimension ''D'', according to a paper of Roos; Roos's paper modifies the
Klee
Paul Klee (; 18 December 1879 – 29 June 1940) was a Swiss-born German artist. His highly individual style was influenced by movements in art that included expressionism, cubism, and surrealism. Klee was a natural draftsman who experimented wi ...
–Minty construction of a
cube
In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross.
The cube is the only r ...
on which the simplex algorithm takes 2
''D'' steps.
Like the simplex algorithm, the criss-cross algorithm visits all 8 corners of the three-dimensional cube in the worst case.
When it is initialized at a random corner of the cube, the criss-cross algorithm visits only ''D'' additional corners, however, according to a 1994 paper by
Fukuda and Namiki.
Trivially, the simplex algorithm takes on average ''D'' steps for a cube.
Like the simplex algorithm, the criss-cross algorithm visits exactly 3 additional corners of the three-dimensional cube on average.
Variants
The criss-cross algorithm has been extended to solve more general problems than linear programming problems.
Other optimization problems with linear constraints
There are variants of the criss-cross algorithm for linear programming, for
quadratic programming
Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize (minimize or maximize) a multivariate quadratic function subject to linear constra ...
, and for the
linear-complementarity problem with "sufficient matrices";
conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.
A
sufficient matrix is a generalization both of a
positive-definite matrix
In mathematics, a symmetric matrix M with real entries is positive-definite if the real number z^\textsfMz is positive for every nonzero real column vector z, where z^\textsf is the transpose of More generally, a Hermitian matrix (that is, a co ...
and of a
P-matrix In mathematics, a -matrix is a complex square matrix with every principal minor is positive. A closely related class is that of P_0-matrices, which are the closure of the class of -matrices, with every principal minor \geq 0.
Spectra of -matri ...
, whose
principal minors are each positive.
The criss-cross algorithm has been adapted also for
linear-fractional programming In mathematical optimization, linear-fractional programming (LFP) is a generalization of linear programming (LP). Whereas the objective function in a linear program is a linear function, the objective function in a linear-fractional program is a r ...
.
Vertex enumeration
The criss-cross algorithm was used in an algorithm for
enumerating all the vertices of a polytope, which was published by
David Avis and
Komei Fukuda
Komei Fukuda ( ja, 福田 公明, born 1951) is a Japanese mathematician known for his contributions to optimization,
polyhedral computation and oriented matroid theory. Fukuda is a professor in optimization and computational geometry
in the De ...
in 1992. Avis and Fukuda presented an algorithm which finds the ''v'' vertices of a
polyhedron
In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.
A convex polyhedron is the convex hull of finitely many points, not all on th ...
defined by a nondegenerate system of ''n''
linear inequalities
Linearity is the property of a mathematical relationship (''function (mathematics), function'') that can be graph of a function, graphically represented as a straight Line (geometry), line. Linearity is closely related to ''Proportionality (mat ...
in ''D''
dimension
In physics and mathematics, the dimension of a Space (mathematics), mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any Point (geometry), point within it. Thus, a Line (geometry), lin ...
s (or, dually, the ''v''
facet
Facets () are flat faces on geometric shapes. The organization of naturally occurring facets was key to early developments in crystallography, since they reflect the underlying symmetry of the crystal structure. Gemstones commonly have facets cut ...
s of the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
of ''n'' points in ''D'' dimensions, where each facet contains exactly ''D'' given points) in time
O(''nDv'') and O(''nD'')
space
Space is the boundless three-dimensional extent in which objects and events have relative position and direction. In classical physics, physical space is often conceived in three linear dimensions, although modern physicists usually consider ...
.
Oriented matroids
![max-flow min-cut example](https://upload.wikimedia.org/wikipedia/commons/0/0e/Max-flow_min-cut_example.svg)
The criss-cross algorithm is often studied using the theory of
oriented matroid
An oriented matroid is a mathematics, mathematical mathematical structure, structure that abstracts the properties of directed graphs, Vector space, vector arrangements over ordered fields, and Arrangement of hyperplanes, hyperplane arrangements o ...
s (OMs), which is a
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
abstraction of linear-optimization theory.
[The theory of ]oriented matroid
An oriented matroid is a mathematics, mathematical mathematical structure, structure that abstracts the properties of directed graphs, Vector space, vector arrangements over ordered fields, and Arrangement of hyperplanes, hyperplane arrangements o ...
s was initiated by R. Tyrrell Rockafellar. :Rockafellar was influenced by the earlier studies of
Albert W. Tucker
Albert William Tucker (28 November 1905 – 25 January 1995) was a Canadian mathematician who made important contributions in topology, game theory, and non-linear programming.
Biography
Albert Tucker was born in Oshawa, Ontario, Canada, and ea ...
and George J. Minty. Tucker and Minty had studied the sign patterns of the matrices arising through the pivoting operations of Dantzig's simplex algorithm.
Indeed, Bland's pivoting rule was based on his previous papers on oriented-matroid theory. However, Bland's rule exhibits cycling on some oriented-matroid linear-programming problems.
The first purely combinatorial algorithm for linear programming was devised by
Michael J. Todd.
Todd's algorithm was developed not only for linear-programming in the setting of oriented matroids, but also for
quadratic-programming problems and
linear-complementarity problems.
Todd's algorithm is complicated even to state, unfortunately, and its finite-convergence proofs are somewhat complicated.
The criss-cross algorithm and its proof of finite termination can be simply stated and readily extend the setting of oriented matroids. The algorithm can be further simplified for ''linear feasibility problems'', that is for
linear system
In systems theory, a linear system is a mathematical model of a system based on the use of a linear operator.
Linear systems typically exhibit features and properties that are much simpler than the nonlinear case.
As a mathematical abstraction o ...
s with
nonnegative variables; these problems can be formulated for oriented matroids.
The criss-cross algorithm has been adapted for problems that are more complicated than linear programming: There are oriented-matroid variants also for the quadratic-programming problem and for the linear-complementarity problem.
Summary
The criss-cross algorithm is a simply stated algorithm for linear programming. It was the second fully combinatorial algorithm for linear programming. The partially combinatorial simplex algorithm of Bland cycles on some (nonrealizable) oriented matroids. The first fully combinatorial algorithm was published by Todd, and it is also like the simplex algorithm in that it preserves feasibility after the first feasible basis is generated; however, Todd's rule is complicated. The criss-cross algorithm is not a simplex-like algorithm, because it need not maintain feasibility. The criss-cross algorithm does not have polynomial time-complexity, however.
Researchers have extended the criss-cross algorithm for many optimization-problems, including linear-fractional programming. The criss-cross algorithm can solve quadratic programming problems and linear complementarity problems, even in the setting of oriented matroids. Even when generalized, the criss-cross algorithm remains simply stated.
See also
*
Jack Edmonds
Jack R. Edmonds (born April 5, 1934) is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, pol ...
(pioneer of combinatorial optimization and oriented-matroid theorist; doctoral advisor of Komei Fukuda)
Notes
References
*
*
*
*
*
*
*
*
*
*
*
*
External links
Komei Fukuda (ETH Zentrum, Zurich)wit
Tamás Terlaky (Lehigh University)wit
publications
{{Optimization algorithms, convex, state=collapsed
Linear programming
Oriented matroids
Combinatorial optimization
Optimization algorithms and methods
Combinatorial algorithms
Geometric algorithms
Exchange algorithms