## Thursday, June 19, 2008

### Median DNLP

The median (http://en.wikipedia.org/wiki/Median) can be found by minimizing sum(i, abs(x-a(i))). This is not a well-defined optimization model, and many solvers have problems with it.

An AMPL representation can be found here: http://orfe.princeton.edu/~rvdb/ampl/nlmodels/median/median.mod. A GAMS translation is:

``\$set m 19 set i /i1*i%m%/; parameter a(i);a(i) = uniform(0,1); variable   x 'median'   z 'objective'; equation sumdist; sumdist.. z =e= sum(i, abs(x-a(i))); x.l = 0.5; model median /sumdist/;solve median minimizing z using dnlp;``

Some results:
solverxzNote
Minos0.50024.9424The current point cannot be improved.
Snopt0.50024.9424The current point cannot be improved.
Conopt0.50024.9424Convergence too slow
Mosek1.864341E+123.542248E+13TERMINATED BY SOLVER
Ipopt0.50024.9424Restoration Failed!
Knitro0.5002-0.0002TERMINATED BY SOLVER
Baron,optcr=0,reslim=250.50024.9424Listing file has contradictory info
OQNLP0.50024.9424NORMAL COMPLETION

Baron mentions on the log that bounds are converging to 0.494241D+01, but in the listing file it says Best possible = -1E50.

Note: This model can be reformulated as an LP:

``\$set m 19 set i /i1*i%m%/; parameter a(i);a(i) = uniform(0,1); variable   x    'median'   e(i) 'abs deviation'   z    'objective'; equation  sumdist  e1(i)  e2(i); sumdist.. z =e= sum(i, e(i));e1(i)..   -e(i) =l= x-a(i);e2(i)..             x-a(i) =l= e(i);  model median /all/;solve median minimizing z using lp;``