Geometric Presolver example - Revision history

Ranjelin at 00:51, 6 May 2016

2016-05-06T00:51:46Z

←Older revision		Revision as of 00:51, 6 May 2016
Line 1:		Line 1:
	Assume that the following optimization problem is massive:		Assume that the following optimization problem is massive:
	<center>		<center>
-	<math>\begin{array}{rl}\mbox{find}&x\in\mathbb{R}^n\\	+	<math>\begin{array}{rl}\mbox{ find}&x\in\mathbb{R}^n\\
	\mbox{subject to}&E\,x=t\\		\mbox{subject to}&E\,x=t\\
	&x\succeq_{}\mathbf{0}\end{array}</math>		&x\succeq_{}\mathbf{0}\end{array}</math>

Dattorro at 00:14, 14 April 2013

2013-04-14T00:14:59Z

←Older revision		Revision as of 00:14, 14 April 2013
Line 10:		Line 10:

	[http://www.convexoptimization.com/TOOLS/EAndy.mat This Matlab workspace file]		[http://www.convexoptimization.com/TOOLS/EAndy.mat This Matlab workspace file]
-	contains a real <math>E</math> matrix having dimension <math>533\times 2704</math> and compatible <math>t</math> vector. There exists a cardinality <math>36</math> ~~binary~~ solution <math>x</math>. Before attempting to find it, we presume to have no choice but to reduce dimension of the <math>E</math> matrix prior to computing a solution.	+	contains a real <math>E</math> matrix having dimension <math>533\times 2704</math> and compatible <math>t</math> vector. There exists a cardinality <math>36</math> solution <math>x</math>. Before attempting to find it, we presume to have no choice but to reduce dimension of the <math>E</math> matrix prior to computing a solution.

	A lower bound on number of rows of <math>\,E\in\mathbb{R}^{533\times 2704}\,</math> retained is <math>217</math>.<br>		A lower bound on number of rows of <math>\,E\in\mathbb{R}^{533\times 2704}\,</math> retained is <math>217</math>.<br>

Dattorro at 21:06, 12 April 2013

2013-04-12T21:06:51Z

←Older revision		Revision as of 21:06, 12 April 2013
Line 13:		Line 13:

	A lower bound on number of rows of <math>\,E\in\mathbb{R}^{533\times 2704}\,</math> retained is <math>217</math>.<br>		A lower bound on number of rows of <math>\,E\in\mathbb{R}^{533\times 2704}\,</math> retained is <math>217</math>.<br>
-	A lower bound on number of columns retained is <math>1104</math>.	+	A lower bound on number of columns retained is <math>1104</math>.<br>
		+	An eliminated column means it is evident that the corresponding entry in solution <math>x</math> must be <math>0</math>.

	The present exercise is to determine whether any contemporary presolver can meet this lower bound.		The present exercise is to determine whether any contemporary presolver can meet this lower bound.

Dattorro at 00:15, 12 April 2013

2013-04-12T00:15:19Z

←Older revision		Revision as of 00:15, 12 April 2013
Line 1:		Line 1:
-	Assume that the following problem is massive:	+	Assume that the following optimization problem is massive:
	<center>		<center>
-	<math>\begin{array}{rl}\mbox{find}&x\\	+	<math>\begin{array}{rl}\mbox{find}&x\in\mathbb{R}^n\\
	\mbox{subject to}&E\,x=t\\		\mbox{subject to}&E\,x=t\\
	&x\succeq_{}\mathbf{0}\end{array}</math>		&x\succeq_{}\mathbf{0}\end{array}</math>
	</center>		</center>
-	The problem is presumed solvable but not computable by any contemporary means.	+	The problem is presumed solvable but not computable by any contemporary means.<br>
-	The most logical strategy is to make the problem smaller.	+	The most logical strategy is to somehow make the problem smaller.<br>
		+	Finding a smaller but equivalent problem is called ''presolving.''

	[http://www.convexoptimization.com/TOOLS/EAndy.mat This Matlab workspace file]		[http://www.convexoptimization.com/TOOLS/EAndy.mat This Matlab workspace file]
	contains a real <math>E</math> matrix having dimension <math>533\times 2704</math> and compatible <math>t</math> vector. There exists a cardinality <math>36</math> binary solution <math>x</math>. Before attempting to find it, we presume to have no choice but to reduce dimension of the <math>E</math> matrix prior to computing a solution.		contains a real <math>E</math> matrix having dimension <math>533\times 2704</math> and compatible <math>t</math> vector. There exists a cardinality <math>36</math> binary solution <math>x</math>. Before attempting to find it, we presume to have no choice but to reduce dimension of the <math>E</math> matrix prior to computing a solution.

-	A lower bound on ~~the~~ number of rows of <math>\,E\in\mathbb{R}^{533\times 2704}\,</math> retained is <math>217</math>.<br>	+	A lower bound on number of rows of <math>\,E\in\mathbb{R}^{533\times 2704}\,</math> retained is <math>217</math>.<br>
-	A lower bound on ~~the~~ number of columns retained is <math>1104</math>.	+	A lower bound on number of columns retained is <math>1104</math>.

-	The present exercise is to determine ~~those rows and columns using~~ any contemporary presolver.	+	The present exercise is to determine whether any contemporary presolver can meet this lower bound.

Dattorro at 23:54, 11 April 2013

2013-04-11T23:54:57Z

←Older revision		Revision as of 23:54, 11 April 2013
Line 8:		Line 8:
	The most logical strategy is to make the problem smaller.		The most logical strategy is to make the problem smaller.

-	This file contains a real E matrix having dimension <math>533\times 2704</math> and compatible <math>t</math> vector. There exists a cardinality <math>36</math> binary solution <math>x</math>. Before attempting to find it, we presume to have no choice but to reduce dimension of the <math>E</math> matrix prior to computing a solution.	+	[http://www.convexoptimization.com/TOOLS/EAndy.mat This Matlab workspace file]
		+	contains a real <math>E</math> matrix having dimension <math>533\times 2704</math> and compatible <math>t</math> vector. There exists a cardinality <math>36</math> binary solution <math>x</math>. Before attempting to find it, we presume to have no choice but to reduce dimension of the <math>E</math> matrix prior to computing a solution.

	A lower bound on the number of rows of <math>\,E\in\mathbb{R}^{533\times 2704}\,</math> retained is <math>217</math>.<br>		A lower bound on the number of rows of <math>\,E\in\mathbb{R}^{533\times 2704}\,</math> retained is <math>217</math>.<br>

Dattorro at 23:48, 11 April 2013

2013-04-11T23:48:09Z

←Older revision		Revision as of 23:48, 11 April 2013
Line 8:		Line 8:
	The most logical strategy is to make the problem smaller.		The most logical strategy is to make the problem smaller.

-	This file contains a real E matrix having dimension <math>533\times 2704</math> and compatible t vector. There exists a cardinality <math>36</math> binary solution <math>x</math>. Before attempting to find it, we have no choice but to reduce	+	This file contains a real E matrix having dimension <math>533\times 2704</math> and compatible <math>t</math> vector. There exists a cardinality <math>36</math> binary solution <math>x</math>. Before attempting to find it, we presume to have no choice but to reduce dimension of the <math>E</math> matrix prior to computing a solution.
		+
		+	A lower bound on the number of rows of <math>\,E\in\mathbb{R}^{533\times 2704}\,</math> retained is <math>217</math>.<br>
		+	A lower bound on the number of columns retained is <math>1104</math>.
		+
		+	The present exercise is to determine those rows and columns using any contemporary presolver.

Dattorro: New page: Assume that the following problem is massive: $\begin{array}{rl}\mbox{find}&x\\ \mbox{subject to}&E\,x=t\\ &x\succeq_{}\mathbf{0}\end{array}$ The problem is p...

2013-04-11T23:13:00Z

New page: Assume that the following problem is massive: <center> <math>\begin{array}{rl}\mbox{find}&x\\ \mbox{subject to}&E\,x=t\\ &x\succeq_{}\mathbf{0}\end{array}</math> </center> The problem is p...

New page

Assume that the following problem is massive:
<center>
<math>\begin{array}{rl}\mbox{find}&x\\
\mbox{subject to}&E\,x=t\\
&x\succeq_{}\mathbf{0}\end{array}</math>
</center>
The problem is presumed solvable but not computable by any contemporary means.
The most logical strategy is to make the problem smaller.

This file contains a real E matrix having dimension <math>533\times 2704</math> and compatible t vector. There exists a cardinality <math>36</math> binary solution <math>x</math>. Before attempting to find it, we have no choice but to reduce