0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I'm not familiar with conjugate function $\endgroup$ – convxy Jan 5 at 7:13
  • $\begingroup$ 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! $\endgroup$ – Leon Jan 5 at 10:34
  • $\begingroup$ 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?? $\endgroup$ – convxy Jan 5 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.