I am considering the following problem:
$$ \min_u \frac{1}{2}\|Au\|_2^2 + \lambda\|u\|_1, \quad \text{s.t.} \quad Cu = b, \|u\|_{\infty} \leq 1, $$ where $u\in\mathbb{R}^m, \lambda \in \mathbb{R}^+, b\in\mathbb{R}^n$. The main goal is to convert this into a quadratic program. In the case of no equality constraints, I have the following solution. Rewrite the problem as
$$ \min_{u,v} \frac{1}{2}\|Au\|_2^2 + \lambda\|v\|_1, \quad \text{s.t.} \quad u = v $$
The Lagrangian is then $L(u,v,\mu) = \frac{1}{2}\|Au\|_2^2 + \lambda\|v\|_1 + \mu^\intercal(u-v)$, where $\mu\in\mathbb{R}^m$. The lagrange dual function is then
$$ g(\mu) = \inf_{u,v} L(u,v,\mu) $$
First, compute the infimum over $u$, by taking the gradient and setting it to zero, i.e.
$$ \nabla_u L(u,v,\mu) = A^\intercal A u + \mu = 0 \Rightarrow \boxed{u^* = -(A^\intercal A)^{-1}\mu} $$
Next, compute the infimum over $v$, i.e.
$$ \inf_v \lambda\|v\| - \mu^\intercal v = \begin{cases} 0 & \text{if} \quad \|\mu\|_{\infty} \leq \lambda\\ -\infty & \text{otherwise} \end{cases} $$
Therefore, the dual problem becomes
$$ \max_{\|\mu\|_{\infty}\leq\lambda} \frac{1}{2}\|A(A^\intercal A)^{-1}\mu\|_2^2 - \mu^\intercal (A^\intercal A)^{-1}\mu $$
Simplifying this, we get
$$ \max_{\|\mu\|_{\infty}\leq\lambda} -\frac{1}{2}\mu^\intercal(A^\intercal A)^{-\intercal} \mu = \min_{\|\mu\|_{\infty}\leq\lambda} \mu^\intercal B \mu, $$ where $B = \frac{1}{2}(A^\intercal A)^{-\intercal}$. This is clearly a quadratic program. I want to follow a similar procedure to my problem at hand, but I don't see a clear way to do it.
In my current problem, we can write the lagrange dual function as
$$ g(\mu_1,\mu_2) = \inf_{u,v} \frac{1}{2}\|Au\|_2^2 + \lambda\|v\|_1 + \mu_1^\intercal(u-v) + \mu_2^\intercal(Cv-b) \quad \text{s.t.} \quad \|u\|_{\infty} \leq 1 $$
The infimum over $u$ is now
$$ \begin{align} &\inf_u \{\frac{1}{2}u^\intercal A^\intercal A u + \mu_1^\intercal u : \|u\|_{\infty} \leq 1\}\\ &= \inf_u \{u^\intercal \bar{A} u : \|u\|_{\infty} \leq 1 \} - \sup_u \{(-\mu_1^\intercal u) : \|u\|_{\infty} \leq 1\}\\ &= \inf_u \{u^\intercal \bar{A} u : \|u\|_{\infty} \leq 1 \} - \|\mu_1\|_1 \end{align}, $$ where $\bar{A} = \frac{1}{2}A^\intercal A$, and the definition of the dual norm is used to simplify the second term. My problem is that I am stuck with that infimum in the first term, and don't see how to simplify this further. The infimum over $v$ becomes
$$ \inf_v \lambda\|v\|_1 - (\mu_1^\intercal - \mu_2^\intercal C) v = \begin{cases} 0 & \text{if} \quad \|\mu_1^\intercal - \mu_2^\intercal C\|_{\infty} \leq \lambda\\ -\infty & \text{otherwise} \end{cases} $$
Any help would be greatly appreciated!