3
$\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$
4
  • $\begingroup$ This is the Fermat-Torricelli-Steiner Problem whose dual formulation can be found in "Foundations of Optimization" by O. Guler (Springer) $\endgroup$ Jan 4 at 12:09
  • $\begingroup$ Thank you but I don't think this is how I'm suppose to solve this :( $\endgroup$
    – convxy
    Jan 4 at 14:41
  • $\begingroup$ 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] $\endgroup$
    – CMichael
    Jan 4 at 20:54
  • $\begingroup$ @CMichael ok,but how do I solve my problem?(in the way that I've tried)? $\endgroup$
    – convxy
    Jan 5 at 5:56
1
$\begingroup$

$$\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\}$$

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

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