Dattorro Convex Optimization of Eternity II

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Line 4: Line 4:
*<math>\tau\!\in\!\mathbb{R}^{11077}</math> and <math>\,E\!\in\!\mathbb{R}^{11077\times262144}</math> is the million column Eternity II matrix having redundant rows and columns removed analytically,
*<math>\tau\!\in\!\mathbb{R}^{11077}</math> and <math>\,E\!\in\!\mathbb{R}^{11077\times262144}</math> is the million column Eternity II matrix having redundant rows and columns removed analytically,
*<math>\tilde{\tau}\!\in\!\mathbb{R}^{10054}</math> and <math>\,\tilde{E}\!\in\!\mathbb{R}^{10054\times204304}</math> has columns removed corresponding to some known zero variables (removal produced dependent rows),
*<math>\tilde{\tau}\!\in\!\mathbb{R}^{10054}</math> and <math>\,\tilde{E}\!\in\!\mathbb{R}^{10054\times204304}</math> has columns removed corresponding to some known zero variables (removal produced dependent rows),
-
*<math>b\!\in\!\mathbb{R}^{7362}</math>&nbsp;&nbsp; and <math>A\!\in\!\mathbb{R}^{7362\times150638}</math>&nbsp; has columns removed not in smallest face (containing <math>\tilde{\tau}</math>) of polyhedral cone <math>\mathcal{K}\triangleq\{\tilde{E}^{}x~|~x\!\succeq\!0\}</math>.
+
*<math>b\!\in\!\mathbb{R}^{7362}</math>&nbsp;&nbsp; and <math>A\!\in\!\mathbb{R}^{7362\times150638}</math>&nbsp; has columns removed not in smallest face (containing <math>\tilde{\tau}</math>) of polyhedral cone <math>\mathcal{K}=\{\tilde{E}^{}x~|~x\!\succeq\!0\}</math>.
The following linear program is a very difficult problem that remains unsolved:
The following linear program is a very difficult problem that remains unsolved:
Line 19: Line 19:
Direction vector <math>z\,</math> is determined by [[Convex Iteration]]:
Direction vector <math>z\,</math> is determined by [[Convex Iteration]]:
<center>
<center>
-
<math>\begin{array}{rl}\mbox{maximize}_z&z^{\rm T\!}x^\star\\
+
<math>\begin{array}{rl}\mbox{maximize}_z&z^{\rm T\!}x^*\\
\mbox{subject to}&0\preceq z\preceq\mathbf{1}\\
\mbox{subject to}&0\preceq z\preceq\mathbf{1}\\
&z^{\rm T}\mathbf{1}=256
&z^{\rm T}\mathbf{1}=256
Line 28: Line 28:
The Eternity II puzzle is solved when
The Eternity II puzzle is solved when
<center><math>
<center><math>
-
z^{\star\rm T\!}x^\star\triangleq_{}256
+
z^{*\rm T\!}x^*=_{}256
</math></center>
</math></center>
Minimal cardinality of this Eternity II problem is equal to number of puzzle pieces, 256.
Minimal cardinality of this Eternity II problem is equal to number of puzzle pieces, 256.
-
Comment: The technique, convex iteration, requires no modification (and works very well) when applied instead to mixed integer programming (MIP, not discussed in book). There is no modification to the linear program statement here except 256 variables, corresponding to the largest entries of iterate <math>x^\star</math>, are declared binary.
+
Comment: The technique, convex iteration, requires no modification (and works very well) when applied instead to mixed integer programming (MIP, not discussed in book). There is no modification to the linear program statement here except 256 variables, corresponding to the largest entries of iterate <math>x^*</math>, are declared binary.

Revision as of 11:56, 24 November 2011

An Eternity II puzzle problem formulation LaTeX: A_{}x\!=\!b\, is discussed thoroughly in section 4.6.0.0.15 of the book Convex Optimization & Euclidean Distance Geometry which is freely available. That LaTeX: A\, matrix is obtained by presolving a sparse 864,593 LaTeX: \!\times\! 1,048,576 system. This Matlab binary contains three successive reductions, each equivalent to that larger system:

  • LaTeX: \tau\!\in\!\mathbb{R}^{11077} and LaTeX: \,E\!\in\!\mathbb{R}^{11077\times262144} is the million column Eternity II matrix having redundant rows and columns removed analytically,
  • LaTeX: \tilde{\tau}\!\in\!\mathbb{R}^{10054} and LaTeX: \,\tilde{E}\!\in\!\mathbb{R}^{10054\times204304} has columns removed corresponding to some known zero variables (removal produced dependent rows),
  • LaTeX: b\!\in\!\mathbb{R}^{7362}   and LaTeX: A\!\in\!\mathbb{R}^{7362\times150638}  has columns removed not in smallest face (containing LaTeX: \tilde{\tau}) of polyhedral cone LaTeX: \mathcal{K}=\{\tilde{E}^{}x~|~x\!\succeq\!0\}.

The following linear program is a very difficult problem that remains unsolved:

LaTeX: \begin{array}{cl}\mbox{maximize}_x&z^{\rm T}x\\
\mbox{subject to}&A\,x=b\\
&x\succeq_{}\mathbf{0}\end{array}

Matrix LaTeX: A\!\in\!\mathbb{R}^{7362\times150638} is sparse having only 782,087 nonzeros. All entries of LaTeX: A\, are integers from the set LaTeX: \{{-1},0,1\}\,.

Vector LaTeX: b_{\!}\in\!\{0,1\}^{7362} has only 358 nonzeros.

Direction vector LaTeX: z\, is determined by Convex Iteration:

LaTeX: \begin{array}{rl}\mbox{maximize}_z&z^{\rm T\!}x^*\\
\mbox{subject to}&0\preceq z\preceq\mathbf{1}\\
&z^{\rm T}\mathbf{1}=256
\end{array}

These two problems are iterated to find a minimal cardinality solution LaTeX: x\,.  Constraint LaTeX: A_{}x\!=\!b\, bounds the variable from above by LaTeX: \mathbf{1}. Any minimal cardinality solution is binary and solves the Eternity II puzzle. The Eternity II puzzle is solved when

LaTeX: 
<p>z^{*\rm T\!}x^*=_{}256
</p>

Minimal cardinality of this Eternity II problem is equal to number of puzzle pieces, 256.


Comment: The technique, convex iteration, requires no modification (and works very well) when applied instead to mixed integer programming (MIP, not discussed in book). There is no modification to the linear program statement here except 256 variables, corresponding to the largest entries of iterate LaTeX: x^*, are declared binary.

Personal tools