# 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?

• This is the Fermat-Torricelli-Steiner Problem whose dual formulation can be found in "Foundations of Optimization" by O. Guler (Springer) Jan 4 at 12:09
• Thank you but I don't think this is how I'm suppose to solve this :( Jan 4 at 14:41
• The unweighted case m=3 of minimizing is dual to the construction of the largest equilateral triangle circumscribed to the triangle p1p2p3. [encyclopediaofmath.org/wiki/Fermat-Torricelli_problem] Jan 4 at 20:54
• @CMichael ok,but how do I solve my problem?(in the way that I've tried)? Jan 5 at 5:56

$$\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^T(z_i-x+a_i)=\sum_{i=1}^{3}\lambda_i^Tz_i+||z_i||-x\sum\lambda_i+\sum\lambda_i^Ta_i$$\
From $$-x\sum\lambda_i$$ we can deduce that $$\sum \lambda_i=0$$ else we get $$-\infty$$. Now when we try to solve for each $$z$$ we can see it is sperable for each $$i$$ and minimizing $$z_i$$ we get the following minimizing problem $$\min_{z_i}\lambda_i^Tz_i+||z_i||$$ which have finite solution iff $$||\lambda_i||\leq1$$(seen in class for 1-D case).\ So the dual problem is:\ $$\underset{\lambda_i\in B}{q(\lambda_1,\lambda_2,\lambda_3)}=\sum\lambda_i^Ta_i$$ $$B=\{\lambda_i\in\mathbb{R}^n:\sum_{i=1}^{3}\lambda_i=0,||\lambda_i||\leq1\}$$