Для расстояний

Так, ну погнали

Есть \(N\) объектов, каждый из которых описывается \(2\) координатами на двумерной плоскости, в работе координата объекта \(i\) обозначена за \(x_{i}=(x_{i1},x_{i2})\).

Теперь наш функционал

\begin{equation} F(x)=\sum_{ij\in D_{\alpha}}\frac{1}{\rho_{ij}^{\gamma}}(\rho_{ij}-||x_{i}-x_{j}||_{2})^{2}\nonumber \\ \end{equation}

Способ 1

Решаем задачу, как типичную задачу нелинейного программирования без ограничений. Для решения потребуется вычисление градиентов.

В качестве возможных предложений по готовым солверам. Из поддерживаемых на данный момент нашёл только dlib: де есть BFGS и LBFGS алгоритмы (это квази-ньютоновские методы, должны работать очень быстро даже без гессиана).

Оптимизация запускается функцией find_min, описание на сайте есть. По-моему, там не требуется подключение сторонних библиотек.

Способ 2

Здесь мы будем решать уже с учётом структуры нашей задачи. А именно

\begin{equation} F(x)=\sum_{ij\in D_{\alpha}}\rho_{ij}^{\gamma}(\rho_{ij}^{2}-2\rho_{ij}||x_{i}-x_{j}||+||x_{i}-x_{j}||^{2})=\\ \displaystyle=\rho_{ij}^{2+\gamma}|D_{\alpha}|+\sum_{ij\in D_{\alpha}}\rho_{ij}^{\gamma}||x_{i}-x_{j}||^{2}-\sum_{ij\in D_{\alpha}}2\rho_{ij}^{1+\gamma}||x_{i}-x_{j}||=\\ \displaystyle=|D_{\alpha}|+f(x)-g(x)\\ \end{equation}

не буду объяснять очевидное, но понятно, что \(\arg\min_{x}F(x)=\arg\min_{x}(F(x)-const)\), поэтому \(|D_{\alpha}|\) мы опускаем.

Получившаяся задача относится к классу DC программирования, или difference of two convex functions. Для неё есть двух-шаговый проективный метод, который можно легко запрогать.