2
$\begingroup$

I want to solve the following optimization problem in variables $\theta_1, \theta_2, \dots, \theta_K$

\begin{equation} \begin{aligned} & \underset{\theta}{\text{minimize}} & & \sum_{k=1}^{K} \|g_k - \theta_k\|_2^2 \\ & \text{subject to} & & \| \theta_m - \theta_l \|_2^2 \leq \| x_m - x_l \|_2^2 , \quad 1 \leq m < l \leq K, \end{aligned} \end{equation}

where $x_i$ and $g_i$ are constants and $\| \cdot \|_2$ denotes the Euclidean norm.

Is there any closed-form for arbitrary $K$? Or an appropriate first-order iterative method which yields an approximate solution?

$\endgroup$
8
  • $\begingroup$ Thank you for your question. I've clarified it now. It's the Euclidean norm $\endgroup$ – Manuel Madeira Nov 13 '20 at 13:37
  • $\begingroup$ Have you tried to rewrite in terms of the incidence matrix of the underlying graph? $\endgroup$ – Rodrigo de Azevedo Nov 13 '20 at 18:04
  • 1
    $\begingroup$ I doubt there can be a closed-form solution for $K \geq 3$. I would rewrite the problem in a saddle point form and then apply some first order method. But you need to give more details: what is the dimension of $\theta_k$, how big is $K$? $\endgroup$ – cheyp Nov 13 '20 at 19:45
  • $\begingroup$ @RodrigodeAzevedo I haven't, but I'm more interested on the type of approach suggested by the next answer. Thank you for your idea anyway $\endgroup$ – Manuel Madeira Nov 13 '20 at 23:46
  • 1
    $\begingroup$ The default for CVX is SeDuMi or SDPT3, neither of which are as good as Mosek or Gurobi, which both can be used under CVX. You re probably best off not squaring any of the norms, so as not to square condition numbers. $\endgroup$ – Mark L. Stone Nov 15 '20 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.