I am looking for the dual of the following optimization problem
\begin{alignat}{2} \tag{P1} &\underset{x \in \mathbb{R}^{n \times 1}}{\text{minimize}}&\quad \frac{1}{2}\left\|x - a \right\|_2^2\\ &\text{subject to }&\quad \|x\|_{\infty} \leq b, \end{alignat} where $a \in \mathbb{R}^{n \times 1}$ and $b \in \mathbb{R}_{\geq0}$.
Question:
How to find the dual of this problem ${\text{P}}1$ (in particular, unconstrained problem by using the dual of the infinity norm ball)?
Partial understanding (perhaps I should say everything is mixed up in my head):
As I understand so far, the dual norm of the inifinity norm ball is $\ell_1$ norm, that is, $\|x\|_1 = \underset{\|z \|_{\infty} \leq 1}{\max} z^Tx$. My "problem" is how to remove the constraint in the primal problem ${\text{P}}1$ and convert the problem as unconstrained by using the fact there is an equivalent notion of dual norm. Can anybody help me please?
Let the Lagrangian be: $$L(\mathbf{x};\lambda,\mathbf{\mu})=\frac{1}{2}\|\mathbf{x}-\mathbf{a}\|_2^2+\mathbf{\lambda}^T(\mathbf{x}-\mathbf{b})-\mathbf{\mu}^T(\mathbf{x}+\mathbf{b}),$$ where $\lambda,\mu\in \mathbb{R}^n_+$ and $\mathbf{b}=(b,b,\dots,b)$ is an $n$-long vector with all components equal to $b$. What we did is to convert the constraint $\|\mathbf{x}\|_{\infty}\leq b$ to separable linear constraints $-b\leq x_i\leq b$. The gradient of $L$ will be $$\nabla_x L = \mathbf{x}-\mathbf{a} +\lambda -\mu \overset{\nabla_x L=\mathbf{0}}{\longrightarrow}\mathbf{x}^*=\mathbf{a}-\lambda+\mu.$$ Overall we have $$L(\mathbf{x}^*;\lambda,\mathbf{\mu})=q(\lambda,\mu)=\frac{1}{2}\|\mu-\lambda\|^2+\lambda^T(\mathbf{a}+\mu-\lambda-\mathbf{b})-\mu^T(\mathbf{a}+\mu-\lambda+\mathbf{b})=\\ -\frac{1}{2}\|\mu-\lambda\|^2-\mathbf{a}^T(\mu-\lambda)-\mathbf{b}^T(\mu+\lambda)$$ and your dual problem is $$\max_{\lambda,\mu\in\mathbb{R}^n_+}q(\lambda,\mu).$$
Not the most appealing dual problem I have to admit. We moved from a one variable problem to two variables, and for iterative methods - projecting onto the $l_{\infty}$ ball is a easy as projecting onto $\mathbb{R}^n_+$. Duality comes in handy if we were able to get a problem of lower dimension or a "better" constraint set, which is not the case in hand.