This note is about a well-known fact in linear programming: variable splitting and minimizing absolute values lead to complementarity pairs \[r_i^{\bf +} \cdot r_i^{\bf -} = 0\] in the solution. A simple example is implementing LAD (Least Absolute Deviation) regression through Linear Programming.
Let's have a look.
Problem: LAD regression
I created an artificial dataset with a few possible outliers:
---- 25 PARAMETER data x y observation1 0.442 6.448 observation2 3.823 10.020 observation3 6.231 7.789 observation4 5.727 9.704 observation5 4.607 12.430 observation6 8.779 11.618 observation7 9.277 14.677 observation8 5.934 28.955 observation9 2.727 6.060 observation10 8.390 15.843 observation11 7.665 11.440 observation12 5.798 8.444 observation13 9.096 7.256 observation14 7.773 11.288 observation15 4.459 7.596 observation16 1.593 6.750 observation17 3.951 7.491 observation18 2.772 11.990 observation19 1.752 11.374 observation20 4.911 11.558 observation21 5.613 12.916 observation22 6.168 11.604 observation23 7.551 11.726 observation24 5.057 6.750 observation25 2.547 6.266 observation26 8.157 11.052 observation27 2.398 8.139 observation28 5.162 10.734 observation29 8.787 12.720 observation30 2.949 11.679
The outliers will heavily impact standard least-squares regression, but using absolute deviations reduces its impact.
