0
$\begingroup$

I have a problem of the form

$$\begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & \lVert \mathbf{x-a} \rVert_2 \\ & \text{subject to} & & \lVert \mathbf{x-v} \rVert_2 \leq \lVert \mathbf{s-v} \rVert_2 \end{aligned} \end{equation*}$$

where $\mathbf{a}$, $\mathbf{s}$, $\mathbf{v}$ are constant. I am not sure how I could reformulate this into the standard form with $Ax \leq b$ inequality constraints and would appreciate any help. I have seen some examples for L1 norm (e.g. here) but not sure how to apply it in this case.

$\endgroup$
1
  • 2
    $\begingroup$ You can formulate it either as a quadratic problem (QP) or a second order conic problem (SOCP). $\endgroup$ Aug 25, 2018 at 16:09

1 Answer 1

2
$\begingroup$

The feasible set is not a polyhedral, hence it can't be directly be described in terms of $Ax \le b$. Unless perhaps you change the feasible set of which the optimal solution is still preserved.

Your problem however can be solved.

First, we can see if $a$ is in the feasible set. If it is, then $x=a$ is the solution.

Suppose $a$ is not in the feasible set. Draw a straight line between the center, $v$ and $a$. The closest point on the sphere that is the closest to $a$ must be on the surface and on the straight line. $$x^*=v+\frac{(a-v)}{\|a-v\|}\|s-v\|$$

$\endgroup$
2
  • $\begingroup$ Thanks a lot for your answer! Though I should have added the _i subscript for the $\mathbf{v}$. Since there can be multiple $\mathbf{v}$, it complicates this solution a bit because the line intersection is not always the solution! E.g. in this picture, where green = s, red = $v_i$, blue = a, yellow is the solution, which led me to the convex optimization in the first place! $\endgroup$
    – eok
    Aug 25, 2018 at 20:20
  • $\begingroup$ I see, in that case, the feasible set is still not a polyhedral. I think your problem is a semidefinite programming problem. $\endgroup$ Aug 26, 2018 at 2:41

You must log in to answer this question.

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