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$

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.