Здравствуйте klovetski, Вы писали:

GS>>Боюсь, что дело куда сложнее. Можно упростить задачу, рассматривая ее как нахождение минимальной описывающей
...
GS>>нетривиальна. В любом случае — существенно многомерные задачи оптимизации имеют экспоненциальную сложность по числу степеней свободы.

K>min R

K>по X, Y и всем Xi, Yi, таким, что
K>{диски должны не пересекаться}
K>1. sqr(Xi-Xj)+sqr(Yi-Yj) >= sqr(Ri+Rj) для всех i<>j, i, j = 1..N
K>{диски должны находиться внутри описанной окружности}
K>2. sqr(Xi-X) + sqr(Yi-Y)<= sqr(R) — sqr(Ri), i = 1..N.

K>Получена задача минимизации с ограничениями типа неравенств. Можно построить точную строго выпуклую штрафную функцию (с использованием функции Лагранжа)

Расскажи, как ты будешь использовать ф.Л. для чиленной оптимизации. Напиши функцию и расскажи, как ты численно будешь находить оптимум.
Как будешь обрабатывать ситуацию, когда решение находтся вблизи (части) ограничений.

K>Численная минимизация ее (лучше всего с помощью метода Ньютона – достаточно всего 7-10 итераций) и даст «наиболее близкое» к исходному приближению решение.

Расскажи мне про метод Ньютона в многомерных задачах. Оцени заодно собственные числа матрицы квадратичных коэффициентов (овражистость) и вычислительную сложность.