Про проверку сходимости численно — сначала очень затупил, пока пишу промежуточный отчёт

Первая кувалдоидея - рассмотреть функцию от M переменных - сумму квадратов уравнений. Она вычисляется за O(M), как и её градиент, и попробовать численно бежать в локальный минимум от случайного старта.

Метод, который прилично работает вдалеке от локального минимума, а потом начинает тупить, я нарисовал почти сразу (потом распишу отдельно)

Вблизи от локального минимума качественно работает Broyden–Fletcher–Goldfarb–Shanno, но у него итерация стоит O(M^2) (то есть O(n^4))
И только сейчас дошло, что можно делать два шага в параллель:
1. Зафиксировали разделяющие прямые, можем независимо минимизировать по переменным, привязанным к каждому квадрату (их 24 + 4*(n-1) - 8 координат, для каждой координаты по две фиктивные переменные для неравенств, для каждой связанной с квадратом разделяющей прямой по 4 фиктивных переменных) - тут BFGS легко потянет
2. Зафиксировали многоугольники, для каждой разделяющей прямой задача сужается на 11 независимых переменных (3 -координаты прямой, 4 - неравенства для первого квадрата, 4 - неравенства для второго квадрата). Систем (n^2-n)/2, он они сверхмалые, при этом для не пересекающихся многоугольников легко ищется точное решение.

Осталось это написать