Linear programming not working in earth Mover's distance

2 views (last 30 days)
I am using the Earth Mover's Distance code from file exchange http://www.mathworks.de/matlabcentral/fileexchange/22962-the-earth-movers-distance
The linear programming returns this for every iteration
Residuals: Primal Dual Duality Total
Infeas Infeas Gap Rel
A*x-b A'*y+z-f x'*z Error
---------------------------------------------------
Iter 0: 4.02e+06 2.01e+05 5.15e+09 1.11e+09
Iter 1: 2.02e+02 4.36e-11 2.60e+05 2.00e+02
Iter 2: 1.28e+00 4.48e-11 2.87e+03 1.67e+00
Iter 3: 3.63e-01 6.51e-11 1.10e+03 1.84e+00
Iter 4: 1.08e-01 6.68e-11 5.04e+02 1.30e+00
Iter 5: 6.04e-02 1.21e-10 3.11e+02 8.94e-01
Iter 6: 3.80e-02 1.41e-10 2.08e+02 6.53e-01
Iter 7: 3.08e-02 1.25e-10 1.66e+02 5.25e-01
Iter 8: 2.26e-02 1.62e-10 1.26e+02 4.19e-01
Iter 9: 1.91e-02 1.51e-10 1.08e+02 3.55e-01
Iter 10: 1.58e-02 2.21e-10 9.19e+01 2.96e-01
Iter 11: 7.25e-03 2.72e-10 4.72e+01 1.74e-01
Iter 12: 5.02e-03 2.18e-10 3.39e+01 1.27e-01
Iter 13: 2.17e-03 2.53e-10 1.53e+01 5.92e-02
Iter 14: 6.71e-04 2.84e-10 5.99e+00 2.53e-02
Iter 15: 8.55e-05 3.31e-10 1.42e+00 7.33e-03
Iter 16: 2.08e-05 3.13e-10 3.51e-01 1.82e-03
Iter 17: 8.37e-06 3.08e-10 1.45e-01 7.45e-04
Iter 18: 1.56e-06 3.52e-10 2.78e-02 1.43e-04
Iter 19: 1.35e-07 3.32e-10 2.38e-03 1.22e-05
Iter 20: 2.55e-09 3.38e-10 1.03e-05 1.24e-07
Iter 21: 2.03e-09 2.77e-10 2.96e-06 8.86e-08
Iter 22: 2.50e-08 2.65e-10 1.84e-06 8.77e-08
Iter 23: 5.22e-09 2.65e-10 1.83e-12 6.91e-08
Iter 24: 2.89e-09 3.30e-10 6.19e-13 7.44e-08
Iter 25: 2.70e-09 2.54e-10 1.48e-13 7.45e-08
Iter 26: 2.70e-09 2.58e-10 1.48e-13 7.45e-08
Iter 27: 2.70e-09 2.56e-10 1.48e-13 7.45e-08
Iter 28: 2.70e-09 2.53e-10 1.48e-13 7.45e-08
Iter 29: 2.70e-09 2.44e-10 1.48e-13 7.45e-08
Iter 30: 2.55e-09 1.63e-08 1.20e-05 3.64e-06
Iter 31: 1.77e-09 4.96e-07 6.04e-03 1.34e-04
Iter 32: 1.73e-09 6.16e-07 8.36e-03 1.78e-04
Iter 33: 1.72e-09 1.19e-06 1.80e-02 3.80e-04
Iter 34: 1.72e-09 1.86e-06 2.99e-02 6.27e-04
Iter 35: 1.71e-09 2.29e-06 4.45e-02 9.31e-04
Iter 36: 1.71e-09 2.42e-06 4.60e-02 9.61e-04
Iter 37: 1.71e-09 5.97e-06 9.33e-02 1.95e-03
Iter 38: 1.71e-09 1.39e-05 1.39e-01 2.89e-03
Iter 39: 1.71e-09 1.11e-05 2.06e-01 4.30e-03
Iter 40: 1.71e-09 1.24e-05 2.06e-01 4.30e-03
Iter 41: 1.71e-09 4.54e-05 5.71e-01 1.19e-02
Iter 42: 1.71e-09 7.54e-05 1.27e+00 2.66e-02
Iter 43: 1.71e-09 4.48e-04 6.43e+00 1.34e-01
Iter 44: 1.71e-09 4.29e-04 6.43e+00 1.34e-01
Iter 45: 1.71e-09 4.97e-04 6.43e+00 1.34e-01
Iter 46: 1.71e-09 3.88e-04 1.28e+00 2.68e-02
Iter 47: 1.71e-09 3.91e-04 1.28e+00 2.68e-02
Iter 48: 1.71e-09 2.26e-04 1.46e+00 3.05e-02
Iter 49: 1.71e-09 7.55e-04 1.04e+01 2.17e-01
Iter 50: 1.71e-09 3.68e-03 6.14e+01 1.28e+00
Iter 51: 1.71e-09 3.63e-03 6.14e+01 1.28e+00
Iter 52: 1.71e-09 4.23e-03 6.14e+01 1.28e+00
Iter 53: 1.71e-09 4.51e-03 6.14e+01 1.28e+00
Iter 54: 1.71e-09 6.32e-03 1.04e+02 1.85e+00
Iter 55: 1.71e-09 7.31e-03 1.04e+02 1.85e+00
Iter 56: 1.71e-09 7.81e-03 1.04e+02 1.85e+00
Iter 57: 1.71e-09 7.92e-03 1.04e+02 1.85e+00
Iter 58: 1.71e-09 9.08e-03 1.04e+02 1.85e+00
Exiting: One or more of the residuals, duality gap, or total relative error
has stalled:
the dual appears to be infeasible (and the primal unbounded).
(The primal residual < TolFun=1.00e-08.)
From iteration 42 onwards the duality gap starts increasing along with other options. Is it like the optimization already found its minimum solution at 41st iteration and somehow it got stuck?
How to interpret this repetitive values in primal infeasibility and the increasing values in other columns?
Thanks for any help.

Accepted Answer

Alan Weiss
Alan Weiss on 20 Mar 2013
I am not sure what is going on here, but I suspect that the tolerances have been set to unreasonably low values. At iteration 23 all gaps are below 1e-7, so I would normally expect linprog to exit. It seems to me (though I could be wrong) that this is a case of too-small tolerances leading to futile iterations well after the solver converged.
Alan Weiss
MATLAB mathematical toolbox documentation

More Answers (1)

bidisha
bidisha on 20 Mar 2013
Thanks a lot Alan.
I was using the default tolerance value of 10e-8. I increased the tolerance value to 10e-07 and it works fine but increases the total relative error. Since I am using this image similarity metric for a huge data of images, I am quite not sure whether changing the tolerance level would impact the distance metric computation for other images to what extent.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!