0
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.