Linear Program to find line that best fits a set of points

Question

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 $z\ge|ax_i+by_i-c|$
or $-z\le ax_i+by_i-c\le 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?

Answer 1

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 $z\geq 0$ without changing the formulation), and constraint $b=1$ as a normalization.

Answer 2

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$.