Vrftsjtryk

Given a set of points $(x1,y1),(x2,y2),...,(xn,yn)$ the following is supposed to be a linear program that finds a line$ $ax+by=c that minimizes $max|ax_i+by_i-c|$.

Let $z=max|ax_i+by_i-c|$

This implies $zge|ax_i+by_i-c|$

or $-zle ax_i+by_i-cle z$

The LP is:

Maximize : -z

subject to:

1) $-z-ax_i-by_i+c le 0$

2) $-z+ax_i+by_i-c le 0$

3) $z,a,b,c ge 0$

I don't understand why this is correct since:

1) the coefficient of z in the objective function is negative which would mean the max value is achieved at $z=0$

2) $a,b,c ge 0$. Rewriting the line as $y=-frac{a}{b}x+c$
we see that this means that we are restricting ourselves to lines of -ve slope.
So, this can't be right either.

I'm looking on clarification on what I'm missing?

1) $z=0$ is a perfect match, so indeed that is optimal.

2) the part $z,a,b,c=0$ is obviously wrong. You should not constrain these variables (although you could add $zgeq 0$ without changing the formulation), and constraint $b=1$ as a normalization.

Consider the problem of $$max -z$$

where $$-z+1 le 0$$
$$-z-1 le 0$$
$$z ge 0$$

Having the coefficient of $z$ being negative in your constraint doesn't mean that $z=0$. In fact $z=0$ is not feasible for the first costraint. My constraints sets is actually equivalent to $z ge 1$.

Also, there is no sign constraint on $a,b,c$.