Euclidean distance between polyhedra
randn('state',0);
rand('state',0);
n = 5;
m1 = 2*n;
m2 = 3*n;
A1 = randn(m1,n);
A2 = randn(m2,n);
b1 = rand(m1,1);
b2 = rand(m2,1) + A2*randn(n,1);
cvx_begin
variables x(n) y(n)
minimize (norm(x - y))
A1*x <= b1;
A2*y <= b2;
cvx_end
disp('------------------------------------------------------------------');
disp('The distance between the 2 polyhedra C and D is: ' );
disp(['dist(C,D) = ' num2str(cvx_optval)]);
Calling SDPT3: 31 variables, 11 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------
num. of constraints = 11
dim. of socp var = 6, num. of socp blk = 1
dim. of linear var = 25
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap mean(obj) cputime
-------------------------------------------------------------------
0|0.000|0.000|4.9e+01|4.7e+00|1.7e+03| 7.007010e+01| 0:0:00| chol 1 1
1|0.275|0.688|3.5e+01|1.5e+00|1.0e+03| 5.887076e+01| 0:0:00| chol 1 1
2|0.912|0.746|3.1e+00|3.9e-01|3.5e+02| 7.069801e+01| 0:0:00| chol 1 1
3|1.000|0.944|1.2e-05|2.3e-02|4.7e+01| 1.827628e+01| 0:0:00| chol 1 1
4|0.875|1.000|2.7e-06|7.8e-05|8.1e+00| 1.532117e+00| 0:0:00| chol 1 1
5|1.000|1.000|3.0e-09|8.1e-06|3.4e+00| 3.281659e-01| 0:0:00| chol 1 1
6|1.000|0.974|1.7e-10|9.5e-07|1.3e+00|-1.642444e-01| 0:0:00| chol 1 1
7|0.878|0.835|1.5e-10|2.2e-07|3.1e-01|-4.106208e-01| 0:0:00| chol 1 1
8|1.000|0.855|4.7e-11|3.8e-08|1.4e-01|-4.754591e-01| 0:0:00| chol 1 1
9|0.859|1.000|2.3e-11|7.6e-10|2.0e-02|-5.009468e-01| 0:0:00| chol 1 1
10|1.000|0.972|1.3e-14|9.9e-11|5.7e-03|-5.071087e-01| 0:0:00| chol 1 1
11|0.948|0.984|4.9e-15|1.0e-11|2.5e-04|-5.084744e-01| 0:0:00| chol 1 1
12|1.000|1.000|2.6e-13|1.8e-12|2.2e-05|-5.085616e-01| 0:0:00| chol 1 1
13|1.000|1.000|9.8e-15|1.0e-12|3.7e-07|-5.085670e-01| 0:0:00| chol 1 1
14|1.000|1.000|2.2e-12|1.0e-12|7.9e-09|-5.085671e-01| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations = 14
primal objective value = -5.08567054e-01
dual objective value = -5.08567062e-01
gap := trace(XZ) = 7.88e-09
relative gap = 3.91e-09
actual relative gap = 3.90e-09
rel. primal infeas = 2.17e-12
rel. dual infeas = 1.00e-12
norm(X), norm(y), norm(Z) = 1.8e+00, 1.7e+00, 4.2e+00
norm(A), norm(b), norm(C) = 1.1e+01, 2.0e+00, 6.8e+00
Total CPU time (secs) = 0.3
CPU time per iteration = 0.0
termination code = 0
DIMACS: 2.2e-12 0.0e+00 1.8e-12 0.0e+00 3.9e-09 3.9e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.508567
------------------------------------------------------------------
The distance between the 2 polyhedra C and D is:
dist(C,D) = 0.50857