Find the dual problem of $\min_x\{||x-a_1||+||x-a_2||+||x-a_3||,a_i\in\mathbb{R}^n\}$

Find the dual problem of
$$\min_x\{||x-a_1||+||x-a_2||+||x-a_3||,a_i\in\mathbb{R}^n\}$$

I've tried the following but got stuck $$\min_x\{||x-a_1||+||x-a_2||+||x-a_3||,a_i\in\mathbb{R}^n\}=\min_{x,z_i}\{||z_1||+||z_2||+||z_3||,a_i\in\mathbb{R}^n\,z_i=x-a_i\}$$
and the Lagrangian is:\ $$L(x,z,\lambda)= ||z_1||+||z_2||+||z_3||+\sum_{i=1}^3\lambda_i(z_i-x+a_i)=\sum_{i=1}^{3}z_i\lambda_i+||z_i||-x\sum\lambda_i+\sum\lambda_ia_i$$

from $$-x\sum\lambda_i$$ we can deduce that $$\sum \lambda_i=0$$ else we get $$-\infty$$. Now when I try to solve for each $$z_i$$ I get $$\frac{\partial L}{\partial z_i}=\lambda_i+\frac{z_i}{||z_i||}=0$$ and I'm not sure how to continue from here.
Any hint?

According to the request of the host, I propose here an answer without using the notion of conjugate function. However I have to admit that the idea behind the computations is of conjugate function.

Recall that the Lagrangian function is \begin{align} L(x,z,\lambda)=\sum_{i=1}^{3} \langle z_i,\lambda_i\rangle +||z_i||-\langle x, \sum_{i=1}^3\lambda_i\rangle +\sum_{i=1}^3 \langle \lambda_i, a_i\rangle, \end{align} where $$x, z_i, \lambda_i \in \mathbb R^n$$ for $$i=1,2,3$$.

We claim that the dual problem is

$$\sup_{\lambda} \inf_{x,z} L(x,z,\lambda) =\sup_{\lambda\in D} \sum_{i=1}^3 \langle \lambda_i, a_i\rangle. \label{eq1} \tag{1}$$

where \begin{align} D=\{\lambda=(\lambda_1, \lambda_2, \lambda_3): \sum_{i=1}^3\lambda_i=0 \text{ and } ||\lambda_i||_*\leq 1 \text{ for } i=1,2,3\}. \end{align} Here $$||\cdot||_*$$ is the dual norm of $$||\cdot||$$ in $$\mathbb R^n$$ and defined as \begin{align} ||u||_*:=\sup_{||v||\leq 1} \langle u,v\rangle. \end{align}

Proof of \eqref{eq1}.

We now focus on $$\inf_{x,z} L(x,z, \lambda)$$. We claim that $$\inf_x -\langle x, \sum_{i=1}^3\lambda_i\rangle = \begin{cases} 0, & \text{ if } \sum_{i=1}^3\lambda_i=0,\\ -\infty, & \text{ otherwise.} \end{cases} \label{eq2} \tag{2}$$ and $$\inf_{z_i} \langle z_i, \lambda_i \rangle +||z_i||= \begin{cases} 0, & \text{ if } ||\lambda_i||_* \leq 1,\\ -\infty, & \text{ if } ||\lambda_i||_* > 1. \end{cases} \label{eq3} \tag{3}$$

If \eqref{eq2} and \eqref{eq3} hold true, we obtain the dual problem \eqref{eq1}. Since the host already know how to prove \eqref{eq2}, we now only concentrate on \eqref{eq3}.

To simplify the notations, in \eqref{eq3} we shall remove the index $$i$$, i.e. we are going to prove $$\inf_{z} \langle z, \lambda\rangle +||z||= \begin{cases} 0, & \text{ if } ||\lambda||_* \leq 1,\\ -\infty, & \text{ if } ||\lambda||_* > 1. \end{cases} \textbf{ for z, \lambda are in \mathbb R^n from here on.} \label{eq4} \tag{4}$$

Let $$\lambda'=-\lambda$$, we have $$\inf_{z} \langle z, \lambda\rangle +||z||=-\sup_{z} \langle z, \lambda'\rangle -||z||.$$

Case 1. If $$||\lambda'||_*\leq 1$$, we have $$\sup_{z} \langle \frac{z}{||z||}, \lambda'\rangle \leq ||\lambda'||_*\leq 1.$$ Here the first inequality holds due to the definition of dual norm. Thus $$\sup_{z} \langle z, \lambda'\rangle -||z||\leq 0.$$ Furthermore, the equality holds if we take $$z=0$$.

Case 2. If $$||\lambda'||_*> 1$$, from the definition of dual norm, we deduce the existence of some $$z$$ such that $$||z||\leq 1$$ and $$\langle z,\lambda'\rangle >1$$. Now, we have $$\sup_{t\in \mathbb R} \langle tz, \lambda'\rangle-||tz|| =\sup_{t\in \mathbb R} t( \langle z, \lambda'\rangle-||z||) =+\infty.$$

Note that $$||\lambda'||_*=||\lambda||_*$$, all together tell us that \eqref{eq4} is true.

Hence, \eqref{eq1} is true.

Based on your arguments, the remainder is to pay attention to the following quantity, \begin{align} F(\lambda)=\inf_{z\in \mathbb R^n} (\langle z, \lambda \rangle +||z||). \end{align}

This quantity can be quantified using the notion of conjugate function. Recall that the conjugate function of $$f$$, denoted by $$f^*$$, is defined by \begin{align} f^*(y)=\sup_{x \in \mathbb R^n} (\langle x, y \rangle -f(x)). \end{align}

Now, $$F(\lambda)$$ can be rewritten in term of conjugate function of $$f(x)=||x||$$ as follows \begin{align} F(\lambda) & =\inf_{z\in \mathbb R^n} (-\langle z, -\lambda \rangle +f(z))\\ & = - \sup_{z\in \mathbb R^n} (\langle z, -\lambda \rangle - f(z))\\ & = - f^*(-\lambda). \end{align} Here, in the case $$f(x)=||x||$$, $$f^*$$ is \begin{align} f^*(\lambda)= \begin{cases} 0, & \text{ if } ||\lambda||_*\leq 1.\\ +\infty, & \text{ if } ||\lambda||_*> 1. \end{cases} \end{align} Where $$||\cdot||_*$$ is the dual norm of $$||\cdot||$$. To see how to obtain such formula for $$f^*$$, see the first answer here.

• I'm not familiar with conjugate function – convxy Jan 5 at 7:13
• In my answer, the conjugate function is defined explicitly in term of dual norm. I hope that know about it. Anyway, in most of duality results in optimization, conjugate function is the main tool! – Leon Jan 5 at 10:34
• We haven't learnt this yet and I guess in more advanced courses I will.Can you solve this only with norm duality and from where I stopped or give some hint?? – convxy Jan 5 at 11:00