Presolver - Revision history

Ranjelin at 23:27, 6 May 2026

Ranjelin — Wed, 06 May 2026 23:27:39 GMT

←Older revision		Revision as of 23:27, 6 May 2026
Line 51:		Line 51:
	Each of the great Pyramids of Egypt is a finite polyhedral cone.		Each of the great Pyramids of Egypt is a finite polyhedral cone.
	The geometer defines a polyhedral (semiinfinite) cone <math>\,\mathcal{K}</math> in <math>\,\mathbb{R}^m</math> as a 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}=\{A_{}x~\|~x\succeq0\}</math></center>	+	<center><math>\mathcal{K}=\{A_{}x\;\|\;x\succeq0\}</math></center>
	that is closed and convex but not necessarily pointed (might not have a vertex).		that is closed and convex but not necessarily pointed (might not have a vertex).

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 a 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,

Ranjelin: /* Assumptions */

Ranjelin — Tue, 04 Oct 2016 04:23:12 GMT

Assumptions

←Older revision		Revision as of 04:23, 4 October 2016
Line 87:		Line 87:
	The test we choose is proof by counterexample:		The test we choose is proof by counterexample:
	given matrix <math>A\,</math> having no zero columns,		given matrix <math>A\,</math> having no zero columns,
-	<center><math>\begin{array}{rl}~~\mbox~~{find}&x\\	+	<center><math>\begin{array}{rl}{\text find}&x\\
	\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\\
Line 119:		Line 119:
	For full-dimensional pointed closed convex cone <math>\mathcal{K}\,</math>		For full-dimensional pointed closed convex cone <math>\mathcal{K}\,</math>
	described by given matrix <math>A\,</math>		described by given matrix <math>A\,</math>
-	<center><math>\begin{array}{rl}\~~mbox{~~find}_{x\,~~,\;~~y}&y^{\~~!}\neq_{\!}~~\mathbf{0}\\	+	<center><math>\begin{array}{rl}{\text find}_{x,y}&y\not=\mathbf{0}\\
	\mbox{subject to}&b^{\rm T}y=0\\		\mbox{subject to}&b^{\rm T}y=0\\
	&A^{\rm T}y\succeq0\\		&A^{\rm T}y\succeq0\\

Ranjelin: /* Introduction */

Ranjelin — Mon, 05 Dec 2011 06:51:29 GMT

Introduction

←Older revision		Revision as of 06:51, 5 December 2011
Line 21:		Line 21:
	\\ & g(x)_{\!}\in\mathcal{S}		\\ & 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>

Ranjelin: /* Introduction */

Ranjelin — Mon, 05 Dec 2011 06:50:37 GMT

Introduction

←Older revision		Revision as of 06:50, 5 December 2011
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.

Ranjelin: /* Introduction */

Ranjelin — Mon, 05 Dec 2011 06:44:52 GMT

Introduction

←Older revision		Revision as of 06:44, 5 December 2011
Line 82:		Line 82:

	It is now prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math>		It is now prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math>
-	(the columns of <math>A\,</math>)	+	(the columns of <math>A</math>)
	describe a pointed cone.		describe a pointed cone.
	A practical test for pointedness therefore attempts to establish existence of a line.		A practical test for pointedness therefore attempts to establish existence of a line.
Line 92:		Line 92:
	&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 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.	+	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.		If there is an <math>x\,</math> solving this convex feasibility problem, then the cone described by <math>A\,</math> cannot be pointed.

Line 125:		Line 125:
	&x\succeq0\end{array}		&x\succeq0\end{array}
	</math></center>		</math></center>
-	this linear feasibility problem has a solution iff <math>b\!\in\!\partial\mathcal{K}\,</math>.	+	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.		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 []...		This feasibility problem is a statement of boundary membership relation from convex analysis []...

Ranjelin at 20:49, 24 November 2011

Ranjelin — Thu, 24 Nov 2011 20:49:30 GMT

←Older revision		Revision as of 20:49, 24 November 2011
Line 26:		Line 26:
	where <math>A\,</math> is a real <math>m\!\times_{\!}n</math> matrix,		where <math>A\,</math> is a real <math>m\!\times_{\!}n</math> matrix,
	<math>\mathbb{Z}</math> represents the integers,		<math>\mathbb{Z}</math> represents the integers,
-	<math>\~~reals~~</math> the real numbers,	+	<math>\mathbb{R}</math> the real numbers,
	<math>\mathcal{S}</math> is some predetermined set,		<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.
Line 50:		Line 50:
	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.
	Each of the great Pyramids of Egypt is a finite polyhedral cone.		Each of the great Pyramids of Egypt is a finite polyhedral cone.
-	The geometer defines a polyhedral (semiinfinite) cone <math>\,\mathcal{K}</math> in <math>\,\~~reals~~^m</math> as a 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>
	that is closed and convex but not necessarily pointed (might not have a vertex).		that is closed and convex but not necessarily pointed (might not have a vertex).

Ranjelin: /* Introduction */

Ranjelin — Thu, 24 Nov 2011 20:48:15 GMT

Introduction

←Older revision		Revision as of 20:48, 24 November 2011
Line 17:		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}		\\ & g(x)_{\!}\in\mathcal{S}

Ranjelin: /* Assumptions */

Ranjelin — Tue, 15 Nov 2011 20:16:29 GMT

Assumptions

←Older revision		Revision as of 20:16, 15 November 2011
Line 92:		Line 92:
	&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 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.		If there is an <math>x\,</math> solving this convex feasibility problem, then the cone described by <math>A\,</math> cannot be pointed.

Mikesaunders at 07:20, 7 September 2011

Mikesaunders — Wed, 07 Sep 2011 07:20:15 GMT

←Older revision		Revision as of 07:20, 7 September 2011
Line 79:		Line 79:
	<center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}.</math></center>		<center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}.</math></center>
	This condition is necessary and sufficient to establish pointedness.		This condition is necessary and sufficient to establish pointedness.
		+	'''Halfspace figure as example of cone that contains line...'''

-	~~So it~~ is prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math>	+	It is now prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math>
	(the columns of <math>A\,</math>)		(the columns of <math>A\,</math>)
	describe a pointed cone.		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.
		+	The test we choose is proof by counterexample:
	given matrix <math>A\,</math> having no zero columns,		given matrix <math>A\,</math> having no zero columns,
	<center><math>\begin{array}{rl}\mbox{find}&x\\		<center><math>\begin{array}{rl}\mbox{find}&x\\

Mikesaunders: /* Geometry of Constraints */

Mikesaunders — Wed, 07 Sep 2011 07:07:46 GMT

Geometry of Constraints

←Older revision		Revision as of 07:07, 7 September 2011
Line 71:		Line 71:

	====Assumptions====		====Assumptions====
-	'''1) ~~<math>\mathcal{K}</math>~~ Pointedness.'''	+	'''1) Pointedness of cones.'''
-	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''.	+	namely cones that contain no ''line''.
-	(Recall that a line is a 1-dimensional Euclidean body that extends infinitely in two opposite ~~direction~~.)	+	(Recall that a line is a 1-dimensional Euclidean body that extends infinitely in two opposite directions.)
-	~~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:	+	A cone <math>\mathcal{K}</math> contains no line if and only if the cone
-	<center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}</math></center>	+	and its ''polar cone'' <math>-\mathcal{K}</math> intersect only at the origin:
-	~~which~~ is necessary and sufficient to establish pointedness.	+	<center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}.</math></center>
		+	This condition is necessary and sufficient to establish pointedness.

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