Presolver

From Wikimization

(Difference between revisions)
Jump to: navigation, search
(assumptions)
(Geometry of Constraints)
Line 38: Line 38:
===Geometry of Constraints===
===Geometry of Constraints===
[[Image:pyramid.jpg|thumb|right|234px|Euclidean pyramid]]
[[Image:pyramid.jpg|thumb|right|234px|Euclidean pyramid]]
-
The central idea in our presolving method is best understood geometrically.
+
The idea central to our presolve method is best understood geometrically.
Constraints
Constraints
<center><math>
<center><math>

Revision as of 00:59, 23 August 2011

Introduction

Presolving conventionally means quick elimination of some variables and constraints prior to numerical solution of an optimization problem. Presented with constraints LaTeX: a^{\rm T}x_{\!}=_{\!}0\,,~x\succeq0 for example, a presolver is likely to check whether constant vector LaTeX: a\, is positive; for if so, variable LaTeX: \,x 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:

LaTeX: 
<pre>   \begin{array}{rl}
      \mbox{minimize}_{x\in_{}\mathbb{R}^{^n}} & f(x)
   \\ \mbox{subject to}                        & A_{}x=b
   \\                                          & g(x)_{\!}\in\mathcal{S}
   \\                                          & x\succeq0
   \\                                          & x_{j\!}\in\mathbb{Z}~,\qquad j\in\mathcal{J}
   \end{array}
</pre>

where LaTeX: A\, is a real LaTeX: m\!\times_{\!}n matrix, LaTeX: \mathbb{Z} represents the integers, LaTeX: \reals the real numbers, LaTeX: \mathcal{S} is some predetermined set, and LaTeX: \mathcal{J} 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 LaTeX: n\, independent parallel subproblems is its saving grace; speedup becomes proportional to number of parallel processors.

Geometry of Constraints

Euclidean pyramid
Euclidean pyramid

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

LaTeX: 
<pre>   \begin{array}{l}
   \\                 A_{}x=b
   \\                 x\succeq0
   \end{array}
</pre>

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 LaTeX: \,\mathcal{K} in LaTeX: \,\reals^m as a set

LaTeX: \mathcal{K}\triangleq\{A_{}x~|~x\succeq0\}

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

A pointed polyhedral cone (truncated)
A pointed polyhedral cone (truncated)

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 LaTeX: A\,. Those four columns completely describe the semiinfinite Pyramid per definition of LaTeX: \mathcal{K}\,. But LaTeX: A\, can have more than four columns and still describe the same Pyramid. For such a fat LaTeX: A\,, each additional column resides anywhere in LaTeX: \mathcal{K}\,: either interior to the cone LaTeX: (\{A_{}x~|~x\succ0\}) or on one of its faces (the vertex, an edge, or 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

Our presolve method applies only to pointed polyhedral cones. So it is prudent to ask whether a given set of generators for LaTeX: \mathcal{K}\,, the columns of LaTeX: A\,, describe a pointed cone. We utilize a definition saying that a pointed cone contains no line. This is equivalent to the statement that a pointed cone LaTeX: \mathcal{K} and its polar LaTeX: -\mathcal{K} intersect only at the origin;

LaTeX: \mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}

which is necessary and sufficient to establish pointedness. A practical test for pointedness therefore attempts to establish existence of a line; a proof by counterexample: given matrix LaTeX: A\, having no zero columns,

LaTeX: \begin{array}{rl}\mbox{find}&x\\
<p>\mbox{subject to}&A_{}x=\mathbf{0}\\
&\mathbf{1}^{\rm T}x=1\\
&x\succeq0\end{array}
</p>

This test says that if LaTeX: \mathcal{K} contains a line, then at least two of its generators point in opposite directions LaTeX: (A_{}x\!=\!\mathbf{0}). Constraint LaTeX: \mathbf{1}^{\rm T}x\!=\!1 precludes the trivial solution. If there is an LaTeX: x\, solving this convex feasibility problem, then the cone described by LaTeX: A\, cannot be pointed.







2) point LaTeX: b\, belongs to cone boundary...

Personal tools