When I am doing my convex optimization homework, I encountered a problem regarding deriving the dual problem.
Define $\|x\| = \max_{1\leq i_1\leq…\leq i_r}|x_{i_1}| +…+|x_{i_r}|$, then it's plain to see that $\|x\|$ is the optimal value of the optimization problem:$$\max\quad x^Ty$$$$\text{subject to}\quad\|y\|_\infty\leq1, \|y\|_1\leq r$$
Then my teacher says this is equivalent to:
$$\min\quad -x^Ty$$$$\text{subject to}\quad \|y\|_1\leq r$$
with $\textbf{dom} f = \{y | \|y\|_\infty\leq1\}$
My teacher wants me to derive the dual problem $\textbf{exactly}$ in the second form (i.e. let $\textbf{dom} f = \{y | \|y\|_\infty\leq1\}$, instead of an inequality constraint), and use this result to formulate the following problem:
$$\min\quad\|Ax-b\|_2^2+\|x\|$$
as quadratic programming.
So I follow the definition and try to write down the dual function: $L(\lambda) = \inf_{\|y\|_\infty\leq1}(-x^Ty+\lambda(\|y\|_1-r)) = \inf_{\|y\|_\infty\leq1}(-x^Ty+\lambda\|y\|_1)-\lambda r$
Thanks to @nowhere, I think the right way to proceed with this dual function:
$\inf_{\|y\|_\infty\leq1}(-x^Ty+\lambda\|y\|_1) = \inf_{\|y\|_\infty\leq1}(\sum_i -x_iy_i + \lambda|y_i|)$
We can then take the infimum componentwise:
$\inf_{|y|\leq1}(-x_iy_i + \lambda|y_i|) = (\lambda – |x_i|)|y_i|$
$$ =\left\{
\begin{aligned}
0 &\quad |x_i|\leq \lambda \\
\lambda-|x_i| &\quad |x_i|>\lambda
\end{aligned}
\right.
$$
but I can't proceed further with the formulation of the Quadratic Programming, so I'm wondering how can I move forward to derive the dual problem and formulate the quadratic programming.Any hints on how can I get this?
Best Answer
I think I have an idea, but I'm not 100% sure. (I wished to post it as a comment first, but it's too long.) So please take what I say with a grain of salt.
Summarizing what we have so far: The notation $\|x\|$ means $\max_{i_1, \dots, i_r} |x_{i_1}| + \dotsb + |x_{i_r}|$, i.e., sum of the $r$ largest absolute values of $x$. We have shown that \begin{align*} -\|x\| & = \min_{\|y\|_\infty \leq 1} -x^T y \quad \text{s.t.} \ \|y\|_1 \leq r \end{align*} By strong duality, we get \begin{align*} -\|x\| & = \max_{\lambda \geq 0} L(\lambda)\\ & = \max_{\lambda \geq 0} \Big( -\lambda r + \sum_{i = 1}^n \min(0, \lambda - |x_i|) \Big) \end{align*} If we flip the sign, we get \begin{align*} \|x\| & = \min_{\lambda \geq 0} \Big( \lambda r + \sum_{i = 1}^n \max(0, |x_i| - \lambda) \Big) \end{align*} Now let's return to the problem \begin{align*} \min_{x \in \mathbb{R}^n} & \quad \|Ax - b\|_2^2 + \|x\| \end{align*} It can be written as \begin{align*} \min_{x \in \mathbb{R}^n} & \quad \Big\{\|Ax - b\|_2^2 + \min_{\lambda \geq 0} \Big( \lambda r + \sum_{i = 1}^n \max(0, |x_i| - \lambda) \Big)\Big\} \end{align*} That's the same as \begin{align*} \min_{x \in \mathbb{R}^n, \lambda \geq 0} & \quad \|Ax - b\|_2^2 + \lambda r + \sum_{i = 1}^n \max(0, |x_i| - \lambda) \end{align*} This problem can be reformulated as \begin{align*} \min_{x \in \mathbb{R}^n, \lambda \geq 0, s_1, \dots, s_n} & \quad \|Ax - b\|_2^2 + \lambda r + \sum_{i = 1}^n s_i\\ \text{subject to} & \quad \max(0, |x_i| - \lambda) \leq s_i, \quad i = 1, \dots, n \end{align*} which is equivalent to \begin{align*} \min_{x \in \mathbb{R}^n, \lambda \geq 0, s_1, \dots, s_n} & \quad \|Ax - b\|_2^2 + \lambda r + \sum_{i = 1}^n s_i\\ \text{subject to} & \quad 0 \leq s_i,\\ & \quad |x_i| \leq \lambda + s_i, \quad i = 1, \dots, n \end{align*} To get rid of the absolute value sign, introduce slack variables $y_1, \dots, y_n$ and write the problem as \begin{align*} \min_{x \in \mathbb{R}^n, \lambda \geq 0, s_1, \dots, s_n, y_1, \dots, y_n} & \quad \|Ax - b\|_2^2 + \lambda r + \sum_{i = 1}^n s_i\\ \text{subject to} & \quad 0 \leq s_i,\\ & \quad -y_i \leq x_i \leq y_i,\\ & \quad y_i \leq \lambda + s_i, \quad i = 1, \dots, n \end{align*} Now the objective is quadratic, and all constraints are linear.