5
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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)?

$\endgroup$
6
  • $\begingroup$ \begin{aligned} & \underset{\{a,b,d\}}{\text{minimize}} & & d \\ & \text{ st.} & & \begin{pmatrix}1&1&-1\\ -1&-1&-1\\2&1&-1\\-2&-1&-1\\2&1&-1\\-2&1&-1\\3&1&-1\\-3&1&-1 \end{pmatrix}\begin{pmatrix} a\\b\\d \end{pmatrix}\leq\begin{pmatrix} 1\\-1\\2\\-2\\4\\-4\\2\\-2 \end{pmatrix} \end{aligned} $\endgroup$
    – Warsick
    Commented Oct 7, 2017 at 17:33
  • $\begingroup$ Applying the expression of the distance from points $x_i,y_i$ to line this the LP i get $\endgroup$
    – Warsick
    Commented Oct 7, 2017 at 17:35
  • $\begingroup$ And converting to the dual problem I get $\endgroup$
    – Warsick
    Commented Oct 7, 2017 at 17:42
  • $\begingroup$ \begin{aligned} & {\text{max}} & & u_1-u_2+2u_3-2u_4+4u_5-4u_6+2u_7-2u_8 \\ & \text{ st.} & & \begin{pmatrix}1&-1&2&-2&2&-2&3&-3\\ 1&-1&1&-1&1&-1&1&-1\\ -1&-1&-1&-1&-1&-1&-1&-1\end{pmatrix} \begin{pmatrix} u_1\\u_2\\u_3\\u_4\\u_5\\u_6\\u_7\\u_8 \end{pmatrix} \leq\begin{pmatrix} 0\\0\\1 \end{pmatrix} \end{aligned} $\endgroup$
    – Warsick
    Commented Oct 7, 2017 at 17:42
  • $\begingroup$ Is the correct dual? If so how would I go about solving the dual problem? Put it into standard form, start with a basis consisting of the three added slack variables and solve like I would would the primal using the tableau? $\endgroup$
    – Warsick
    Commented Oct 7, 2017 at 17:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .