Presolver

From Wikimization

(Difference between revisions)
Jump to: navigation, search
(Geometry of Constraints)
Current revision (21:23, 3 October 2016) (edit) (undo)
(Assumptions)
 
(35 intermediate revisions not shown.)
Line 1: Line 1:
==Introduction==
==Introduction==
''Presolving'' conventionally means quick elimination of some variables and constraints prior to numerical solution of an optimization problem.
''Presolving'' conventionally means quick elimination of some variables and constraints prior to numerical solution of an optimization problem.
-
Presented with constraints <math>a^{\rm T}x=0\,,~x\succeq0</math> for example,
+
Presented with constraints <math>a^{\rm T}x_{\!}=_{\!}0\,,\,\,x\succeq0</math> for example,
a presolver is likely to check whether constant vector <math>a\,</math> is positive; for if so,
a presolver is likely to check whether constant vector <math>a\,</math> is positive; for if so,
variable <math>\,x</math> can have only the trivial solution.
variable <math>\,x</math> can have only the trivial solution.
Line 7: Line 7:
Most commercial optimization problem solvers incorporate presolving.
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.
+
Particular reductions can be proprietary or invisible,
-
But all presolvers have the same motivation: to make an optimization problem smaller
+
while some control or selection may be given to a user.
-
and (ideally) easier to solve.
+
But all presolvers have the same motivation:
 +
to make an optimization problem smaller and (ideally) easier to solve.
There is profit potential because
There is profit potential because
a solver can then compete more effectively in the marketplace for large-scale problems.
a solver can then compete more effectively in the marketplace for large-scale problems.
Line 16: Line 17:
<center><math>
<center><math>
\begin{array}{rl}
\begin{array}{rl}
-
\mbox{minimize}_{x\in_{}\mathbb{R}^{^n}} & f(x)
+
\mbox{minimize}_{x\in_{}\mathbb{R}^n} & f(x)
\\ \mbox{subject to} & A_{}x=b
\\ \mbox{subject to} & A_{}x=b
 +
\\ & g(x)_{\!}\in\mathcal{S}
\\ & x\succeq0
\\ & x\succeq0
-
\\ & x_{j\!}\in\mathbb{Z}~,\qquad j\in\mathcal{J}
+
\\ & x_{j\!}\in\mathbb{Z}\,,\qquad j\in\mathcal{J}
\end{array}
\end{array}
</math></center>
</math></center>
-
where <math>A\,</math> is a matrix of predetermined dimension, <math>\mathbb{Z}</math> represents the integers, <math>\reals</math> the real numbers,
+
where <math>A\,</math> is a real <math>m\!\times_{\!}n</math> matrix,
 +
<math>\mathbb{Z}</math> represents the integers,
 +
<math>\mathbb{R}</math> the real numbers,
 +
<math>\mathcal{S}</math> is some predetermined set,
and <math>\mathcal{J}</math> is some possibly empty index set.
and <math>\mathcal{J}</math> is some possibly empty index set.
-
The ''caveat'' to use of our proposed method for presolving is that it is not fast.
+
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;
+
'''('''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 is, when solver software chronically exits with error or hangs.''')'''
 +
That it can be decomposed into <math>n\,</math> independent parallel subproblems is its saving grace;
 +
speedup becomes proportional to number of parallel processors.
-
==Geometry of Constraints==
+
===Geometry of Constraints===
[[Image:pyramid.jpg|thumb|right|234px|Euclidean pyramid]]
[[Image:pyramid.jpg|thumb|right|234px|Euclidean pyramid]]
-
The idea, central to our method for presolving, is more easily understood geometrically.
+
The idea central to our presolve method is best understood geometrically.
Constraints
Constraints
<center><math>
<center><math>
Line 40: Line 47:
</math></center>
</math></center>
suggest that a ''polyhedral cone'' comes into play.
suggest that a ''polyhedral cone'' comes into play.
-
Geometers in ''convex analysis'' regard cones as convex Euclidean bodies semi-infinite in extent.
+
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.
Finite circular cones hold ice cream and block road traffic in daily life.
-
The great Pyramids of Egypt are each an example of finite polyhedral cone.
+
Each of the great Pyramids of Egypt is a finite polyhedral cone.
-
The geometer defines a polyhedral (semi-infinite) cone <math>\,\mathcal{K}</math> in <math>\,\reals^m</math> as the set:
+
The geometer defines a polyhedral (semiinfinite) cone <math>\,\mathcal{K}</math> in <math>\,\mathbb{R}^m</math> as a set
-
<center><math>\mathcal{K}\triangleq\{A_{}x~|~x\succeq0\}</math></center>
+
<center><math>\mathcal{K}=\{A_{}x~|~x\succeq0\}</math></center>
-
which is closed and convex but not necessarily pointed (does not necessarily have a vertex).
+
that is closed and convex but not necessarily pointed (might not have a vertex).
[[Image:Polycone2.jpg|thumb|right|200px|A pointed polyhedral cone (truncated)]]
[[Image:Polycone2.jpg|thumb|right|200px|A pointed polyhedral cone (truncated)]]
-
To visualize a pointed polyhedral cone in three dimensions, think of one Egyptian Pyramid continuing into the ground
+
To visualize a pointed polyhedral cone in three dimensions,
-
and then indefinitely out into space from the opposite side of Earth.
+
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 <math>A\,</math>.
Its four edges correspond to four columns from matrix <math>A\,</math>.
-
In fact, those four columns completely describe this semi-infinite Pyramid per definition of <math>\mathcal{K}\,</math>.
+
Those four columns completely describe the semiinfinite Pyramid
-
But <math>A\,</math> can have more than four columns and still describe that same Pyramid.
+
per definition of <math>\mathcal{K}\,</math>.
-
For such a fat <math>A\,</math>, each remaining column resides anywhere in <math>\mathcal{K}\,</math>:
+
But <math>A\,</math> can have more than four columns and still describe the same Pyramid.
-
interior to the cone <math>(\{A_{}x~|~x\succ0\})</math> or on one of its ''faces'' (the vertex, an edge, or facet).
+
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 a facet).
-
There is infinite variety of polyhedral cones; most are not so regularly shaped as a Pyramid.
+
Polyhedral cones have infinite variety. Most are not so regularly shaped as a Pyramid,
-
In fact, a polyhedral cone 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) Pointedness of cones.'''&nbsp;
 +
Our presolve method applies only to pointed polyhedral cones,
 +
namely cones that contain no ''line''.
 +
(Recall that a line is a 1-dimensional Euclidean body that extends infinitely in two opposite directions.)
 +
A cone <math>\mathcal{K}</math> contains no line if and only if the cone
 +
and its ''polar cone'' <math>-\mathcal{K}</math> intersect only at the origin:
 +
<center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}.</math></center>
 +
This condition is necessary and sufficient to establish pointedness.
 +
'''Halfspace figure as example of cone that contains line...'''
 +
 
 +
It is now 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.
 +
The test we choose is proof by counterexample:
 +
given matrix <math>A\,</math> having no zero columns,
 +
<center><math>\begin{array}{rl}{\text find}&x\\
 +
\mbox{subject to}&A_{}x=\mathbf{0}\\
 +
&\mathbf{1}^{\rm T}x=1\\
 +
&x\succeq0.\end{array}
 +
</math></center>
 +
This test says that if <math>\mathcal{K}</math> contains a line, then some conic combination of its generators can be made to point opposite in direction to another <math>(A_{}x\!=\mathbf{0})</math>. Constraint <math>\mathbf{1}^{\rm T}x\!=\!1</math> precludes the trivial solution.
 +
If there is an <math>x\,</math> solving this convex feasibility problem, then the cone described by <math>A\,</math> cannot be pointed.
 +
 
 +
'''2) <math>\,b</math> on Boundary.'''&nbsp;
 +
Success of our method relies on point <math>b\,</math> belonging
 +
to the boundary of cone <math>\mathcal{K}\,</math>.
 +
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 <math>A\,</math>.
 +
Consequently, nonnegative coordinates <math>x\,</math> of <math>\,b</math> are not unique;
 +
there are, generally, an infinite number of coordinates <math>x\,</math>.
 +
We can discern a smaller set of coordinate axes among the columns of <math>A\,</math> by finding
 +
the smallest face of cone <math>\mathcal{K}\,</math> to which <math>b\,</math> belongs.
 +
Then the generators of that smallest face constitute a subset of conic coordinate axes
 +
that can describe <math>b\,</math>. Once found, remaining coordinates may be assumed zero.
 +
 
 +
This assumption, that <math>b\,</math> resides on the boundary <math>\partial\,</math> of cone
 +
<math>\mathcal{K}\,</math>, is realistic. This phenomenon occurs whenever
 +
<math>b\,</math> has sparse representation in its coordinates.
 +
It is therefore prudent to check, before presolving, whether <math>b\,</math> resides on the boundary:
 +
For full-dimensional pointed closed convex cone <math>\mathcal{K}\,</math>
 +
described by given matrix <math>A\,</math>
 +
<center><math>\begin{array}{rl}{\text find}_{x,y}&y\not=\mathbf{0}\\
 +
\mbox{subject to}&b^{\rm T}y=0\\
 +
&A^{\rm T}y\succeq0\\
 +
&A^{}x=b\\
 +
&x\succeq0\end{array}
 +
</math></center>
 +
this linear feasibility problem has a solution iff <math>b\!\in\partial\mathcal{K}\,</math>.
 +
The requirement that <math>\mathcal{K}</math> be full-dimensional is equivalent to the condition that fat matrix <math>A\,</math> be full rank.
 +
This feasibility problem is a statement of boundary membership relation from convex analysis []...

Current revision

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: \mathbb{R} 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: \,\mathbb{R}^m as a set

LaTeX: \mathcal{K}=\{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 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 of cones.  Our presolve method applies only to pointed polyhedral cones, namely cones that contain no line. (Recall that a line is a 1-dimensional Euclidean body that extends infinitely in two opposite directions.) A cone LaTeX: \mathcal{K} contains no line if and only if the cone and its polar cone LaTeX: -\mathcal{K} intersect only at the origin:

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

This condition is necessary and sufficient to establish pointedness. Halfspace figure as example of cone that contains line...

It is now prudent to ask whether a given set of generators for LaTeX: \mathcal{K}\, (the columns of LaTeX: A) describe a pointed cone. A practical test for pointedness therefore attempts to establish existence of a line. The test we choose is proof by counterexample: given matrix LaTeX: A\, having no zero columns,

LaTeX: \begin{array}{rl}{\text 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 some conic combination of its generators can be made to point opposite in direction to another 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) LaTeX: \,b on Boundary.  Success of our method relies on point LaTeX: b\, belonging to the boundary of cone LaTeX: \mathcal{K}\,. 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 LaTeX: A\,. Consequently, nonnegative coordinates LaTeX: x\, of LaTeX: \,b are not unique; there are, generally, an infinite number of coordinates LaTeX: x\,. We can discern a smaller set of coordinate axes among the columns of LaTeX: A\, by finding the smallest face of cone LaTeX: \mathcal{K}\, to which LaTeX: b\, belongs. Then the generators of that smallest face constitute a subset of conic coordinate axes that can describe LaTeX: b\,. Once found, remaining coordinates may be assumed zero.

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

LaTeX: \begin{array}{rl}{\text find}_{x,y}&y\not=\mathbf{0}\\
<p>\mbox{subject to}&b^{\rm T}y=0\\
&A^{\rm T}y\succeq0\\
&A^{}x=b\\
&x\succeq0\end{array}
</p>

this linear feasibility problem has a solution iff LaTeX: b\!\in\partial\mathcal{K}\,. The requirement that LaTeX: \mathcal{K} be full-dimensional is equivalent to the condition that fat matrix LaTeX: A\, be full rank. This feasibility problem is a statement of boundary membership relation from convex analysis []...

Personal tools