Presolver

From Wikimization

(Difference between revisions)
Jump to: navigation, search
(→Geometry of Constraints)
Line 39: Line 39:
</math></center>
</math></center>
suggest that a ''polyhedral cone'' comes into play.
suggest that a ''polyhedral cone'' comes into play.
-
There are geometers who regard cones as convex Euclidean bodies that are semi-infinite in extent.
+
There are geometers who regard cones as convex Euclidean bodies semi-infinite in extent.
Examples of finite polyhedral cones are the great Pyramids of Egypt,
Examples of finite polyhedral cones are the great Pyramids of Egypt,
while finite circular cones hold ice cream and block traffic in daily life.
while finite circular cones hold ice cream and block traffic in daily life.
The geometer defines a polyhedral (semi-infinite) cone <math>\,\mathcal{K}</math> in <math>\,\reals^m</math> thus:
The geometer defines a polyhedral (semi-infinite) cone <math>\,\mathcal{K}</math> in <math>\,\reals^m</math> thus:
<center><math>\mathcal{K}=\{A_{}x~|~x\succeq0\}</math></center>
<center><math>\mathcal{K}=\{A_{}x~|~x\succeq0\}</math></center>
 +
which is closed and convex.
To visualize a polyhedral cone in three dimensions, think of one Egyptian Pyramid continuing into the ground
To visualize a polyhedral cone in three dimensions, think of one Egyptian Pyramid continuing into the ground
and then out into space from the opposite side of Earth.
and then out into space from the opposite side of Earth.
-
Four edges correspond to four columns from matrix <math>\,A</math>.
+
Its four edges correspond to four columns from matrix <math>\,A</math>.
 +
Those four columns completely describe the Pyramid by our definition of <math>\mathcal{K}\,</math>.
But <math>\,A</math> can have more than four columns and still describe that same Pyramid.
But <math>\,A</math> can have more than four columns and still describe that same Pyramid.
-
When <math>\,A</math> does so, then four columns define that Pyramid's edges while each remaining column resides interior to the cone or on one of its ''faces'' (the vertex, an edge, or a flat).
+
When <math>\,A</math> does so, then each remaining column resides interior to the cone or on one of its ''faces'' (the vertex, an edge, or facet).

Revision as of 23:13, 8 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 \\ & x\succeq0 \\ & x_{j\!}\in\mathbb{Z}~,\qquad j\in\mathcal{J} \end{array} </pre>

where LaTeX: \,A is a matrix of predetermined dimension, LaTeX: \mathbb{Z} represents the integers, LaTeX: \reals the real numbers, and LaTeX: \mathcal{J} is some possibly empty index set.

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

Geometry of Constraints

The idea, central to our method for presolving, is more easily understood geometrically. Constraints

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

suggest that a polyhedral cone comes into play. There are geometers who regard cones as convex Euclidean bodies semi-infinite in extent. Examples of finite polyhedral cones are the great Pyramids of Egypt, while finite circular cones hold ice cream and block traffic in daily life. The geometer defines a polyhedral (semi-infinite) cone LaTeX: \,\mathcal{K} in LaTeX: \,\reals^m thus:

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

which is closed and convex. To visualize a polyhedral cone in three dimensions, think of one Egyptian Pyramid continuing into the ground and then 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 Pyramid by our definition of LaTeX: \mathcal{K}\,. But LaTeX: \,A can have more than four columns and still describe that same Pyramid. When LaTeX: \,A does so, then each remaining column resides interior to the cone or on one of its faces (the vertex, an edge, or facet).

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Presolver"
Personal tools