# Formulate a Linear Program of minimizing maximum distance from a set of points to a line and formulate its dual

Say we define the distance from a point to a line in the plane as the length of the vertical distance "you would have to walk" from the point till you hit the line.

Then find a line $L:y=ax+b$ , where $a,b\in \mathbb{R}$ in the plane that minimize the maximum distance from the points $(1,1),(2,2),(2,4),(3,2)$ to $L$.

How would you formulate this problem as a linear problem and write down its dual LP?

First, ask yourself what your variables are: $a$ and $b$.
Next, what are you minimizing? The maximum distance to the line, that is $$\max_i\{|y_i-(ax_i+b)|\},$$ where $(x_i,y_i)$ are your set of points. You are going to need to linearize this expression. Here is a start: you are going to want to minimize $$z$$ subject to $$|y_i-(ax_i+b)| \le z \quad \forall i$$ Can you do the last bit (get rid of the absolute values)?
• Applying the expression of the distance from points $x_i,y_i$ to line this the LP i get Commented Oct 7, 2017 at 17:35