Homec4science
Diffusion EMPoWER (master) Browse

R1252/simulation-code/cvx/examples/sparse_heuristics/html/sparse_infeas_dual.html
de096106547amaster

Last Change
Raw File

sparse_infeas_dual.html
View Options

<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Detecting a small subset of infeasible linear inequalities</title>
<link rel="canonical" href="http://cvxr.com/cvx/examples/sparse_heuristics/html/sparse_infeas_dual.html">
<link rel="stylesheet" href="../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Detecting a small subset of infeasible linear inequalities</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Section 5.8, Boyd &amp; Vandenberghe "Convex Optimization"</span>
<span class="comment">% Written for CVX by Almir Mutapcic - 02/18/06</span>
<span class="comment">%</span>
<span class="comment">% We consider a set of linear inequalities A*x &lt;= b which are</span>
<span class="comment">% infeasible. Here A is a matrix in R^(m-by-n) and b belongs</span>
<span class="comment">% to R^m. We apply a l1-norm heuristic to find a small subset</span>
<span class="comment">% of mutually infeasible inequalities from a larger set of</span>
<span class="comment">% infeasible inequalities. The heuristic finds a sparse solution</span>
<span class="comment">% to the alternative inequality system.</span>
<span class="comment">%</span>
<span class="comment">% Original system is A*x &lt;= b and it alternative ineq. system is:</span>
<span class="comment">%</span>
<span class="comment">% lambda &gt;= 0, A'*lambda == 0. b'*lambda &lt; 0</span>
<span class="comment">%</span>
<span class="comment">% where lambda in R^m. We apply the l1-norm heuristic:</span>
<span class="comment">%</span>
<span class="comment">% minimize sum( lambda )</span>
<span class="comment">% s.t. A'*lambda == 0</span>
<span class="comment">% b'*lambda == -1</span>
<span class="comment">% lambda &gt;= 0</span>
<span class="comment">%</span>
<span class="comment">% Positive lambdas gives us a small subset of inequalities from</span>
<span class="comment">% the original set which are mutually inconsistent.</span>
<span class="comment">% problem dimensions (m inequalities in n-dimensional space)</span>
m = 150;
n = 10;
<span class="comment">% fix random number generator so we can repeat the experiment</span>
seed = 0;
randn(<span class="string">'state'</span>,seed);
<span class="comment">% construct infeasible inequalities</span>
A = randn(m,n);
b = randn(m,1);
fprintf(1, [<span class="string">'Starting with an infeasible set of %d inequalities '</span> <span class="keyword">...</span>
<span class="string">'in %d variables.\n'</span>],m,n);
<span class="comment">% you can verify that the set is infeasible</span>
<span class="comment">% cvx_begin</span>
<span class="comment">% variable x(n)</span>
<span class="comment">% A*x &lt;= b;</span>
<span class="comment">% cvx_end</span>
<span class="comment">% solve the l1-norm heuristic problem applied to the alternative system</span>
cvx_begin
variables <span class="string">lambda(m)</span>
minimize( sum( lambda ) )
subject <span class="string">to</span>
A'*lambda == 0;
b'*lambda == -1;
lambda &gt;= 0;
cvx_end
<span class="comment">% report the smaller set of mutually inconsistent inequalities</span>
infeas_set = find( abs(b.*lambda) &gt; sqrt(eps)/n );
disp(<span class="string">' '</span>);
fprintf(1,<span class="string">'Found a smaller set of %d mutually inconsistent inequalities.\n'</span>,<span class="keyword">...</span>
length(infeas_set));
disp(<span class="string">' '</span>);
disp(<span class="string">'A smaller set of mutually inconsistent inequalities are the ones'</span>);
disp(<span class="string">'with row indices:'</span>), infeas_set'
<span class="comment">% check that this set is infeasible</span>
<span class="comment">% cvx_begin</span>
<span class="comment">% variable x_infeas(n)</span>
<span class="comment">% A(infeas_set,:)*x_infeas &lt;= b(infeas_set);</span>
<span class="comment">% cvx_end</span>
</pre>
<a id="output"></a>
<pre class="codeoutput">
Starting with an infeasible set of 150 inequalities in 10 variables.
Calling SDPT3: 150 variables, 11 equality constraints
------------------------------------------------------------
num. of constraints = 11
dim. of linear var = 150
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime
-------------------------------------------------------------------
0|0.000|0.000|3.3e+02|1.3e+01|2.7e+04| 1.837117e+03 0.000000e+00| 0:0:00| chol 1 1
1|1.000|0.722|8.0e-05|3.6e+00|9.3e+03| 1.890871e+03 1.394017e+00| 0:0:00| chol 1 1
2|1.000|1.000|6.1e-05|9.2e-03|1.2e+03| 1.202558e+03 2.851177e-01| 0:0:00| chol 1 1
3|0.988|1.000|8.5e-07|9.4e-04|1.4e+01| 1.428534e+01 2.837170e-01| 0:0:00| chol 1 1
4|0.894|1.000|8.5e-08|9.3e-05|1.6e+00| 1.926414e+00 3.698598e-01| 0:0:00| chol 1 1
5|1.000|0.620|4.6e-10|4.1e-05|7.8e-01| 1.310752e+00 5.276449e-01| 0:0:00| chol 1 1
6|0.710|0.829|2.3e-10|7.8e-06|3.7e-01| 9.383630e-01 5.653064e-01| 0:0:00| chol 1 1
7|1.000|1.000|2.4e-11|9.2e-08|1.8e-01| 7.659147e-01 5.879403e-01| 0:0:00| chol 1 1
8|0.828|0.911|1.6e-11|1.7e-08|7.5e-02| 6.698772e-01 5.952178e-01| 0:0:00| chol 1 1
9|0.785|1.000|8.2e-12|9.3e-10|3.4e-02| 6.327347e-01 5.982705e-01| 0:0:00| chol 1 1
10|0.995|0.807|4.4e-14|2.6e-10|4.2e-03| 6.047974e-01 6.005863e-01| 0:0:00| chol 1 1
11|0.990|0.960|3.3e-15|2.0e-11|2.9e-04| 6.015589e-01 6.012647e-01| 0:0:00| chol 1 1
12|0.987|0.987|3.2e-15|2.2e-12|3.8e-06| 6.013152e-01 6.013114e-01| 0:0:00| chol 1 1
13|0.998|0.991|7.8e-15|1.0e-12|5.5e-08| 6.013120e-01 6.013120e-01| 0:0:00| chol 1 1
14|1.000|0.992|4.9e-15|1.0e-12|6.6e-10| 6.013120e-01 6.013120e-01| 0:0:00|
stop: max(relative gap, infeasibilities) &lt; 1.49e-08
-------------------------------------------------------------------
number of iterations = 14
primal objective value = 6.01311981e-01
dual objective value = 6.01311980e-01
gap := trace(XZ) = 6.64e-10
relative gap = 3.01e-10
actual relative gap = 3.01e-10
rel. primal infeas = 4.87e-15
rel. dual infeas = 1.01e-12
norm(X), norm(y), norm(Z) = 2.8e-01, 8.1e-01, 1.7e+01
norm(A), norm(b), norm(C) = 4.1e+01, 2.0e+00, 1.3e+01
Total CPU time (secs) = 0.11
CPU time per iteration = 0.01
termination code = 0
DIMACS: 4.9e-15 0.0e+00 6.7e-12 0.0e+00 3.0e-10 3.0e-10
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.601312
Found a smaller set of 11 mutually inconsistent inequalities.
A smaller set of mutually inconsistent inequalities are the ones
with row indices:
ans =
1 22 33 54 59 73 79 94 115 136 149
</pre>
</div>
</body>
</html>
c4science · Help