0

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?

user137481
  • 2,605

2 Answers2

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.

LinAlg
  • 19,822
  • Apologies, I made a typo. I meant $z, a, b, c \ge 0$. But, $a, b \ge 0$ means that we are restricting our solution to lines with -ve slope. That does not sound right. – user137481 Nov 17 '18 at 03:10
  • As well, given that $z=0$ is already optimal, the LP will simply terminate. In that case, what are the values of $a$ and $b$ that result in $z = 0$? – user137481 Nov 17 '18 at 03:25
  • @user137481 $z=0$ is probably infeasible, unless you can find a matching pair $(a,b)$. – LinAlg Nov 17 '18 at 17:52
  • If I understand you correctly, there should be no non-negativity constraints on $a$ and $c$. However, since the line we are looking for is $ax+by=c$, $b$ must be strictly greater than zero. Could you tell me how we express such a constraint? Thanks. – user137481 Nov 17 '18 at 20:01
  • @user137481 you cannot have strict inequalities in linear optimization, but you can set $b=1$, since $a$ and $c$ can simply rescale. That also avoids all coefficients from becoming close to $0$ (which in turn reduces $z$). – LinAlg Nov 17 '18 at 20:11
1

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

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • You're right. There should be no sign constraints (i.e. non-negativity constraints) on $a$, $b$ or $c$. However, given that the equation of the line is $ax+by=c$ this means we cannot have $b=0$. Could you tell me how you express such a constraint? – user137481 Nov 17 '18 at 20:06