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$

2 Answers 2

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
  • $\begingroup$ Thank you very much I appreciate this $\endgroup$
    – convxy
    Commented Jan 5, 2021 at 14:14
  • $\begingroup$ you're welcome! $\endgroup$ Commented Jan 5, 2021 at 14:20
  • $\begingroup$ maybe you could take a look here? math.stackexchange.com/questions/3972913/… $\endgroup$
    – convxy
    Commented Jan 5, 2021 at 14:30
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
    Commented Jan 5, 2021 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$ Commented Jan 5, 2021 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
    Commented Jan 5, 2021 at 11:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .