Convert Primal LP to Dual and solve

319 Views Asked by At

I'm dealing with an LP of minimizing the maximum distance from a set of points $(1,1), (2,2), (2,4), (3,2)$ to at line $L:y=ax+b$

I've managed to formulate the LP as

\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} How would one formulate this as a dual?