# Convex Optimization Problem - Least Squares with Euclidean Norm Inequality

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.

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

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.
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\|$$
• 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!