# Formulation of the dual linear program for the simple linear regression

Objective: Write the dual linear program for the $$\ell_\infty$$ form of the primal linear program corresponding to simple linear regression.

Let the data set $$\{x_i, y_i \}_{i=1}^n$$ be stacked in a vector form $$\{x,y\}$$, where $$x,y \in \mathbb{R}^n$$. We perform a simple linear regression utilizing the given data set. One could describe such a problem in (primal) linear program form as

\begin{align} \text{minimize}_{\alpha \in \mathbb{R},\ \beta \in \mathbb{R}, \ r \in \mathbb{R}} \quad & r\\ \text{subject to }\quad & 1r - \left(y - \alpha x - 1\beta \right) \geq 0 \Longleftrightarrow -1r + \left(y - \alpha x - 1\beta \right) \leq 0\\ & 1r + \left(y - \alpha x - 1\beta \right) \geq 0 \Longleftrightarrow -1r - \left(y - \alpha x - 1\beta \right) \leq 0 \ , \end{align} where $$r$$ is the maximum residual, $$1$$ is all ones column vector, and the inequality is element wise.

Attempt:

In order to obtain the dual of the above primal linear program, adding the constraints with the non-negative dual variables, say $$u, v \geq 0$$, to the cost function as

\begin{align} \text{max}_{u, v} \ \text{min}_{\alpha,\beta,r} \quad & r \\ & + u^T \left( -1r + \left(y - \alpha x - 1\beta \right) \right) \\ & + v^T \left( -1r - \left(y - \alpha x - 1\beta \right) \right) \ . \end{align}

Rewriting the above problem as \begin{align} \text{max}_{u, v} \ \text{min}_{\alpha,\beta,r} \quad & \left(u - v\right)^T y \\ & + \left( 1 - \left(u + v\right)^T 1\right) r \\ & + \left[ \left(v- u \right)^T x \right] \alpha \\ & + \left[ v^T1 - u^T1 \right] \beta \ . \end{align}

Thus, the dual can be shown as \begin{align} \text{maximize}_{u \in \mathbb{R}^n,\ v \in \mathbb{R}^n} \quad & \left(u - v\right)^T y \\ \text{subject to }\quad & \left(u + v\right)^T 1 = 1\\ & \left(v- u \right)^T x = 0 \\ & (v - u)^T1 = 0 \\ & v \geq 0 \\ & u \geq 0 \ . \end{align}

Is this correct?

• A quick check looks good to me, yes – David M. Apr 4 at 0:14