The following seemingly simple question is confusing the heck out of me:
Take the least squares regression problem (for $X \in \mathbb{R}^{n×p}$ and $y \in \mathbb{R}^n$):
$$\min_{\beta \in \mathbb{R}^p} \| y-X\beta \|_2^2$$
Prove that the equivalent dual of this problem is:
$$\min_{v \in \mathbb{R}^n} \| y-v \|_2^2 \text{ subject to } X^T v = 0$$
Hint: In deriving the dual, you may start by introducing the auxiliary variable $z=X\beta$.
(Source: Q2.b in http://www.stat.cmu.edu/~ryantibs/convexopt/homework/homework3.pdf)
What I tried
Following the hint, of course, I get the Lagrangian:
$$L(\beta,z,v) = \lVert y – z \rVert_2^2 + v^T(z-X\beta)$$
Since this function is convex, we can take the gradient to find the point where it minimizes $L$ as a function of $z$ and $\beta$. Doing that gives us the following two conditions:
$$ -2(y-z) + v = 0 $$
$$ -X^T v = 0 $$
Plugging that back into the Lagrangian, I get:
$$ g(v) = \frac14 \lVert v \rVert^2 + v^T (y – \frac12 v) = v^T (y – \frac14 v) $$
And we have the constraint $X^Tv = 0$ as desired. However, while maximizing this $g(v)$ is equivalent to minimizing $\lVert y – v \rVert_2^2$, in that the same $v^\ast$ should optimize both, the two functions are not equal and should not have the same optimal value $g(v^\ast)$.
The second part of the question asks about the relationship between the primal and dual solutions, so I'm not sure how to proceed, given that I didn't find the two problems to be primal and dual. Did I make a mistake in the math, or is there something I'm missing about this question?
Best Answer
Think of this geometrically. Say $n>p$. The primal $\beta$ are the coefficients of the linear combination of columns of $X$ that is closest to $y$. The dual $\nu$ is the error vector. We want the error vector to be orthogonal to the columns of $X$, which is expressed by the constraint $X^T \nu = 0$.