Dattorro Convex Optimization of Eternity II

(Difference between revisions)

Revision as of 00:02, 14 February 2011

Eternity II puzzle formulation is discussed in section 4.6.0.0.15 of Convex Optimization & Euclidean Distance Geometry.

$LaTeX: \,\tau\in\!\mathbb{R}^{11077}$ and $LaTeX: \,E\!\in\!\mathbb{R}^{11077\times262144}$ is the million column Eternity II matrix with redundant columns removed,
$LaTeX: \,\tilde{\tau}\in\!\mathbb{R}^{10054}$ and $LaTeX: \,\tilde{E}\!\in\!\mathbb{R}^{10054\times204304}$ has columns removed corresponding to zero variables,
$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: \{\tilde{E}^{}x~|~x\!\succeq\!0\}$

I regard the following as a very difficult problem, having spent considerable time with it.

$LaTeX: \begin{array}{cl}\mbox{minimize}_x&c^{\rm T}x\\ \mbox{subject to}&\tilde{E}\,x=\tilde{\tau}\\ &x\succeq_{}\mathbf{0}\end{array}$

Matrix $LaTeX: \tilde{E}\!\in\!\mathbb{R}^{10054\times204304}$ is sparse having only 1,170,516 nonzeros.

All entries of $LaTeX: \tilde{E}\,$ are integers from the set $LaTeX: \{{-1},0,1\}\,$ . $LaTeX: \tilde{\tau}\in\{0,1\}^{10054}$ .

Vector $LaTeX: c\,$ is left unspecified because it is varied later as part of a Convex Iteration.

Vector $LaTeX: c\,$ may arbitrarily be set to $LaTeX: \mathbf{0}$ or $LaTeX: \mathbf{1}$ .

@@ Line 1: / Line 1: @@
+Eternity II puzzle formulation is discussed in section 4.6.0.0.15 of [http://meboo.convexoptimization.com/Meboo.html Convex Optimization &amp; Euclidean Distance Geometry].
 This [http://www.convexoptimization.com/TOOLS/EternityII.mat Matlab binary] contains:
 *<math>\,\tau\in\!\mathbb{R}^{11077}</math> and <math>\,E\!\in\!\mathbb{R}^{11077\times262144}</math> is the million column Eternity II matrix with redundant columns removed,