# Presolver

### From Wikimization

(→assumptions) |
(→Geometry of Constraints) |
||

Line 63: | Line 63: | ||

But <math>A\,</math> can have more than four columns and still describe the same Pyramid. | But <math>A\,</math> can have more than four columns and still describe the same Pyramid. | ||

For such a fat <math>A\,</math>, each additional column resides anywhere in <math>\mathcal{K}\,</math>: | For such a fat <math>A\,</math>, each additional column resides anywhere in <math>\mathcal{K}\,</math>: | ||

- | either interior to the cone <math>(\{A_{}x~|~x\succ0\})</math> or on one of its ''faces'' (the vertex, an edge, or facet). | + | either interior to the cone <math>(\{A_{}x~|~x\succ0\})</math> or on one of its ''faces'' (the vertex, an edge, or a facet). |

Polyhedral cones have infinite variety. Most are not so regularly shaped as a Pyramid, | Polyhedral cones have infinite variety. Most are not so regularly shaped as a Pyramid, | ||

and they can have any number of edges and facets. | and they can have any number of edges and facets. | ||

- | We assume a pointed polyhedral cone throughout, so there can be only one vertex | + | We assume a ''pointed'' polyhedral cone throughout, so there can be only one vertex |

(which resides at the origin in Euclidean space by definition). | (which resides at the origin in Euclidean space by definition). | ||

- | ==== | + | ====Assumptions==== |

'''1) <math>\mathcal{K}</math> Pointedness.''' | '''1) <math>\mathcal{K}</math> Pointedness.''' | ||

Our presolve method applies only to pointed polyhedral cones. | Our presolve method applies only to pointed polyhedral cones. | ||

- | + | We invoke a definition saying that a pointed cone contains no ''line''. | |

- | + | (Recall that a line is a 1-dimensional Euclidean body that extends infinitely in two opposite direction.) | |

- | + | This is equivalent to the statement that a pointed cone <math>\mathcal{K}</math> and its ''polar cone'' <math>-\mathcal{K}</math> intersect only at the origin: | |

- | We | + | |

- | This is equivalent to the statement that a pointed cone <math>\mathcal{K}</math> and its ''polar'' <math>-\mathcal{K}</math> intersect only at the origin | + | |

<center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}</math></center> | <center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}</math></center> | ||

which is necessary and sufficient to establish pointedness. | which is necessary and sufficient to establish pointedness. | ||

+ | |||

+ | So it is prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math> | ||

+ | (the columns of <math>A\,</math>) | ||

+ | describe a pointed cone. | ||

A practical test for pointedness therefore attempts to establish existence of a line; a proof by counterexample: | A practical test for pointedness therefore attempts to establish existence of a line; a proof by counterexample: | ||

given matrix <math>A\,</math> having no zero columns, | given matrix <math>A\,</math> having no zero columns, | ||

Line 85: | Line 87: | ||

\mbox{subject to}&A_{}x=\mathbf{0}\\ | \mbox{subject to}&A_{}x=\mathbf{0}\\ | ||

&\mathbf{1}^{\rm T}x=1\\ | &\mathbf{1}^{\rm T}x=1\\ | ||

- | &x\succeq0\end{array} | + | &x\succeq0.\end{array} |

</math></center> | </math></center> | ||

This test says that if <math>\mathcal{K}</math> contains a line, then at least two of its generators point in opposite directions <math>(A_{}x\!=\!\mathbf{0})</math>. Constraint <math>\mathbf{1}^{\rm T}x\!=\!1</math> precludes the trivial solution. | This test says that if <math>\mathcal{K}</math> contains a line, then at least two of its generators point in opposite directions <math>(A_{}x\!=\!\mathbf{0})</math>. Constraint <math>\mathbf{1}^{\rm T}x\!=\!1</math> precludes the trivial solution. |

## Revision as of 22:36, 6 September 2011

## Introduction

*Presolving* conventionally means quick elimination of some variables and constraints prior to numerical solution of an optimization problem.
Presented with constraints for example,
a presolver is likely to check whether constant vector is positive; for if so,
variable can have only the trivial solution.
The effect of such tests is to reduce the problem dimensions.

Most commercial optimization problem solvers incorporate presolving. Particular reductions can be proprietary or invisible, while some control or selection may be given to a user. But all presolvers have the same motivation: to make an optimization problem smaller and (ideally) easier to solve. There is profit potential because a solver can then compete more effectively in the marketplace for large-scale problems.

We present a method for reducing variable dimension based upon geometry of constraints in the problem statement:

where is a real matrix, represents the integers, the real numbers, is some predetermined set, and is some possibly empty index set.

A *caveat* to use of our proposed method for presolving is that it is not fast.
**(**One would incorporate this method only when a problem is too big to be solved;
that is, when solver software chronically exits with error or hangs.**)**
That it can be decomposed into independent parallel subproblems is its saving grace;
speedup becomes proportional to number of parallel processors.

### Geometry of Constraints

The idea central to our presolve method is best understood geometrically. Constraints

suggest that a *polyhedral cone* comes into play.
Geometers in *convex analysis* regard cones as convex Euclidean bodies semiinfinite in extent.
Finite circular cones hold ice cream and block road traffic in daily life.
Each of the great Pyramids of Egypt is a finite polyhedral cone.
The geometer defines a polyhedral (semiinfinite) cone in as a set

that is closed and convex but not necessarily pointed (might not have a vertex).

To visualize a pointed polyhedral cone in three dimensions,
imagine one Egyptian Pyramid continuing into the ground
and then indefinitely out into Space from the opposite side of Earth.
Its four edges correspond to four columns from matrix .
Those four columns completely describe the semiinfinite Pyramid
per definition of .
But can have more than four columns and still describe the same Pyramid.
For such a fat , each additional column resides anywhere in :
either interior to the cone or on one of its *faces* (the vertex, an edge, or a facet).

Polyhedral cones have infinite variety. Most are not so regularly shaped as a Pyramid,
and they can have any number of edges and facets.
We assume a *pointed* polyhedral cone throughout, so there can be only one vertex
(which resides at the origin in Euclidean space by definition).

#### Assumptions

**1) Pointedness.**
Our presolve method applies only to pointed polyhedral cones.
We invoke a definition saying that a pointed cone contains no *line*.
(Recall that a line is a 1-dimensional Euclidean body that extends infinitely in two opposite direction.)
This is equivalent to the statement that a pointed cone and its *polar cone* intersect only at the origin:

which is necessary and sufficient to establish pointedness.

So it is prudent to ask whether a given set of *generators* for
(the columns of )
describe a pointed cone.
A practical test for pointedness therefore attempts to establish existence of a line; a proof by counterexample:
given matrix having no zero columns,

This test says that if contains a line, then at least two of its generators point in opposite directions . Constraint precludes the trivial solution. If there is an solving this convex feasibility problem, then the cone described by cannot be pointed.

**2) on Boundary.**
Success of our method relies on point belonging
to the boundary of cone .
One way to think of a pointed closed convex cone is as a kind
of coordinate system whose basis is generally nonorthogonal and overcomplete;
a conic system, very much like the familiar Cartesian system
whose analogous cone is the first quadrant (the *nonnegative orthant*)
and whose generators are the Cartesian coordinate axes.

In the context of pointed polyhedral cones,
*overcomplete* means an abundance of linearly dependent generators in .
Consequently, nonnegative coordinates of are not unique;
there are, generally, an infinite number of coordinates .
We can discern a smaller set of coordinate axes among the columns of by finding
the smallest face of cone to which belongs.
Then the generators of that smallest face constitute a subset of conic coordinate axes
that can describe . Once found, remaining coordinates may be assumed zero.

This assumption, that resides on the boundary of cone , is realistic. This phenomenon occurs whenever has sparse representation in its coordinates. It is therefore prudent to check, before presolving, whether resides on the boundary: For full-dimensional pointed closed convex cone described by given matrix

this linear feasibility problem has a solution iff . The requirement that be full-dimensional is equivalent to the condition that fat matrix be full rank. This feasibility problem is a statement of boundary membership relation from convex analysis []...