Максиминное расположение точек на сфере

[мат-ламер]

B@R5uk в сообщении #1682004 писал(а):

Возможно, это и делается в статье китайцев
, что я приводил ранее. Надо уже в конце-концов прочитать её и вникнуть в суть дела там.

Вкратце глянул на статью. Вначале приводится метод, который я тут предлагал ранее:

мат-ламер в сообщении #1681275 писал(а):

Думаю попробовать такой подход.

У меня руки до такого подхода пока не дошли. Китайцы считают, что этот метод неудовлетворительный

[B@R5uk]

Интересно, есть ли какая-нибудь обзорная инфа по тому, какие методы и на сколько удачно применяются для нахождения локальных минимумов задачи Таммеса? Пока без относительно поиска глобального. Чтобы если и пытаться придумать что-нибудь новое, то хотя бы знать, что уже опробовано и на сколько высока планка для перепрыгивания. Китайцы, судя по параграфу:

Цитата:

The subproblem dened by Eqs. (5) and (6) is still a constrained optimization problem which is not easy to handle by popular local optimization methods like the LBFGS method. To perform the local optimization, we convert the problem further to an unconstrained optimization problem by using the spherical coordinate transformation of points on S²

тоже используют что-то стороннее и не заморачиваются особо. И дальше, на странице 13 они упоминают алгоритм LBFGS и дают ссылку на статью On the limited memory BFGS method for large scale optimization авторов Dong C. Liu и Jorge Nocedal. Непонятно, правда, они самостоятельно его пишут или пользуются чей-то сторонней библиотекой, как, например, Laszlo Hars пользовался LD_SLSQP из библиотеки NLopt в своей работе.

[zgemm]

B@R5uk в сообщении #1682176 писал(а):

И дальше, на странице 13 они упоминают алгоритм LBFGS и дают ссылку на статью On the limited memory BFGS method for large scale optimization авторов Dong C. Liu и Jorge Nocedal. Непонятно, правда, они самостоятельно его пишут или пользуются чей-то сторонней библиотекой, как, например, Laszlo Hars пользовался LD_SLSQP из библиотеки NLopt в своей работе.

если писать по Носедалю или по Википедии, то LBFGS без одномерного поиска и с внешней функцией градиента умещается в 20 строк кода. Проще самому, чем разбираться в чужих библиотеках.

У меня правда на несколько тысяч строк раздулся мой вариант, но он сразу подцепляет многое полезное, как отжиг и Баур-Штрассена, без которых для многих такого типа задач LBFGS не приведет к хорошим результатам.

[B@R5uk]

Вот есть теорема (лемма?) Фейеш-Тота, которая даёт верхнюю границу для оптимальной длины (угла) задачи Таммеса:

$$\cos\beta\ge\frac{1}{2}\left(\ctg^2\left(\frac{n}{n-2}\frac{\pi}{6}\right)-1\right)$$

А есть ли какая-нибудь такая же оценка для нижней границы? Всё, что я смог найти (нагуглить) из более-менее вразумительного — это вот это обсуждение, но там идёт речь о асимптотическом поведении при больших n.

Самому в голову приходит только идея о расположении на сфере на равных угловых расстояниях порядка $\sqrt{n}$ окружностей в параллельных плоскостях и упаковка точек на эти окружности с расстоянием между точками не более расстояния между окружностями. Но это больше получается примитивный оптимизационный алгоритм с обращением сложной суммы с округлениями, чем удобосчитаемая формула для быстрой оценки. Что-то как-то даже не верится, что этот вопрос никем раньше не рассматривался.

-- 19.04.2025, 13:38 --

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

[Sender]

Можно взять какое-нибудь более-менее регулярное разбиение сферы. Например, в одной из похожих тем предлагалось взять (сферический или вписанный) икосаэдр и разбить каждую грань на $k^2$ почти одинаковых треугольников. Затем можно взять к получившемуся многограннику двойственный, в каждую его грань вписать окружность и взять минимальный радиус, он и даст нижнюю оценку.

[мат-ламер]

B@R5uk
Из асимптотического поведения конкретно для этой задачи вряд ли возможно получить достаточно точные и близкие друг к другу оценки. Дело в том, что если вы построите график зависимости оцениваемой величины (косинус угла) от размерности задачи, то на нём будут периодические всплески для некоторых значений $n$ , для которых будет наблюдаться повышенная симметрия. Поэтому между оценкой сверху и оценкой снизу будет зазор. Однако, может вам удастся тут самому что-то оценить? Но тема эта трудная.