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:

solver	x	z	Note
Minos	0.5002	4.9424	The current point cannot be improved.
Snopt	0.5002	4.9424	The current point cannot be improved.
Conopt	0.5002	4.9424	Convergence too slow
Mosek	1.864341E+12	3.542248E+13	TERMINATED BY SOLVER
Ipopt	0.5002	4.9424	Restoration Failed!
Knitro	0.5002	-0.0002	TERMINATED BY SOLVER
Baron,optcr=0,reslim=25	0.5002	4.9424	Listing file has contradictory info
OQNLP	0.5002	4.9424	NORMAL 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;