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?

  • $\begingroup$ Thank you for your question. I've clarified it now. It's the Euclidean norm $\endgroup$ Nov 13, 2020 at 13:37
  • $\begingroup$ Have you tried to rewrite in terms of the incidence matrix of the underlying graph? $\endgroup$ Nov 13, 2020 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, 2020 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$ Nov 13, 2020 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$ Nov 15, 2020 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.