Consider a problem of the form:

\begin{equation*} \begin{aligned} & \underset{p_i}{\text{maximize}} & & \sum_i \sum_j \Vert p_i - p_j \Vert_2^2 \\ & \text{subject to} & & Gx \leq h \\ & && Ax=b \end{aligned} \end{equation*}

Where $p_i, p_j \in \mathbb{R}^n$, and $x$ is the vector containing all of these points side by side. So given some fixed $k$ number of points, $x \in \mathbb{R}^{kn}$.

For example, if we have 4 points $p_1, p_2, p_3, p_4 \in \mathbb{R}^2$, $x=[p_{1x}, p_{1y}, p_{2x}, p_{2y},p_{3x}, p_{3y},p_{4x}, p_{4y}]$. This allows for constraints to use all the elements of each point.

What is a good way to approach this? The techniques for least squares don't seem to work because it's being maximized, and quadratic programming doesn't work either because, as far as I can tell, there isn't a way to phrase it that keeps the $Q$ matrix in the objective function ($x^t Q x$) semi-positive definite. Is there something trivial I am missing?

  • $\begingroup$ Could you clarify what you mean when you say "x is the vector containing all of these points side by side?" Not sure I follow. $\endgroup$ – user23658 Dec 4 '15 at 4:47
  • $\begingroup$ Sorry, I edited the question to try and clarify it. Did that help? $\endgroup$ – Phylliida Dec 4 '15 at 5:00
  • $\begingroup$ This is typically handled with Spatial Simulated Annealing. $\endgroup$ – whuber Dec 4 '15 at 15:15
  • $\begingroup$ @whuber Thanks for the suggestion, that looks like it will often work. However, that method seems to only converge to local optima. Is there any methods that are guaranteed to converge to global optima? $\endgroup$ – Phylliida Dec 4 '15 at 15:44
  • $\begingroup$ I'm not sure. The special nature of your objective function and the convexity of the constraints certainly help. Another area to search in is that of interval arithmetic, because I believe what you are computing is tantamount to finding one endpoint of a weighted variance of interval-valued data. Note that SSA will of course converge to a global optimum when there are no other local optima. $\endgroup$ – whuber Dec 4 '15 at 15:50

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.