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?

Improve this question
$\endgroup$
8
  • $\begingroup$ Thank you for your question. I've clarified it now. It's the Euclidean norm $\endgroup$
    – Manuel Madeira
    Commented Nov 13, 2020 at 13:37
  • $\begingroup$ Have you tried to rewrite in terms of the incidence matrix of the underlying graph? $\endgroup$
    – Rodrigo de Azevedo
    Commented 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
    Commented 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$
    – Manuel Madeira
    Commented 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$
    – Mark L. Stone
    Commented Nov 15, 2020 at 8:55

0

Reset to default

You must log in to answer this question.