Dattorro Convex Optimization of Eternity II

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Line 1: Line 1:
-
[http://www.convexoptimization.com/TOOLS/E/mas.mat mas.mat]
+
The [http://www.convexoptimization.com/TOOLS/Wotao.Yin/EternityII.mat Matlab binary] contains matrices <math>\,E</math> and <math>\,t</math>.
-
<pre>
+
I regard the following as a very difficult problem, having spent considerable time with it.
-
%%% Theorem of the Alternative.
+
 
-
clear all
+
<center>
-
clc
+
<math>\begin{array}{cl}\mbox{minimize}_{x\in\{0,1\}}&c^{\rm T}x\\
-
load E_small
+
\mbox{subject to}&E\,x=t\\
-
%load E_full
+
&x\geq_{}\mathbf{0}\end{array}</math>
-
[m n] = size(E);
+
</center>
-
found=[];
+
 
-
cvx_quiet('true')
+
Matrix <math>E\!\in\!\mathbb{R}^{10054\times204304}</math> is sparse having only 1,170,516 nonzeros.
-
cvx_precision('low')
+
 
-
for i=1:n
+
All its entries are integers from the set <math>\{{-1},0,1\}</math>.&nbsp;
-
inconclusive = true;
+
 
-
cvx_begin
+
Vector <math>c\,</math> is left unspecified because it is varied later as part of a
-
variable a(n+1,1);
+
[[Convex Iteration]]. &nbsp;
-
a(1:n) >= 0;
+
 
-
-E(:,i) == [E t]*a;
+
Vector <math>c\,</math> may arbitrarily be set to <math>\mathbf{0}</math> or <math>\mathbf{1}</math>.
-
cvx_end
+
-
if strcmp(cvx_status,'Solved') || strcmp(cvx_status,'Solved/Inaccurate')
+
-
problem_solved = 1;
+
-
inconclusive = false;
+
-
else
+
-
cvx_begin
+
-
variable z(m,1);
+
-
t'*z == 0;
+
-
E(:,i)'*z == 1;
+
-
E'*z >= 0;
+
-
cvx_end
+
-
if strcmp(cvx_status,'Solved') || strcmp(cvx_status,'Solved/Inaccurate')
+
-
problem_solved = 2;
+
-
inconclusive = false;
+
-
end
+
-
end
+
-
fprintf('%6d/%6d',i,n);
+
-
if inconclusive, fprintf(' numeric failure\n'), else fprintf(' problem %d solved\n',problem_solved), end
+
-
end
+
-
</pre>
+

Revision as of 00:03, 31 January 2011

The Matlab binary contains matrices LaTeX: \,E and LaTeX: \,t.

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

LaTeX: \begin{array}{cl}\mbox{minimize}_{x\in\{0,1\}}&c^{\rm T}x\\ \mbox{subject to}&E\,x=t\\ &x\geq_{}\mathbf{0}\end{array}

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

All its entries are integers from the set LaTeX: \{{-1},0,1\}. 

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}.

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Dattorro_Convex_Optimization_of_Eternity_II"
Personal tools