Математики представили контрпример, опровергающий гипотезу Лакоста-Жюльена и Джагги, сформулированную в 2015 году. Утверждалось, что пирамидальная ширина многогранника не может увеличиваться при добавлении новой вершины, если все исходные точки сохраняют статус вершин. Исследователи доказали обратное, используя конструкцию из шести целочисленных точек в трехмерном пространстве.
Гипотеза была тесно связана с анализом сложности алгоритмов оптимизации, в частности, методов Франка-Вулфа, которые широко применяются в машинном обучении для решения задач выпуклой оптимизации. Пирамидальная ширина является важным параметром, определяющим скорость сходимости этих алгоритмов. Опровержение этой гипотезы меняет теоретическое понимание границ эффективности итерационных методов при работе с многогранными множествами.
Авторы работы продемонстрировали, что при переходе от многогранника $P$, образованного пятью точками, к многограннику $Q$ с добавлением шестой вершины, пирамидальная ширина системы возрастает. Этот результат ставит под сомнение некоторые теоретические предположения о поведении алгоритмов оптимизации в пространствах высокой размерности и требует пересмотра оценок сложности для ряда вычислительных задач.
Ключевые факты
- Гипотеза Лакоста-Жюльена и Джагги 2015 года утверждала неизменность пирамидальной ширины при добавлении вершин.
- Контрпример построен на основе шести целочисленных точек в пространстве $\mathbb{R}^3$.
- Результат напрямую влияет на теоретические оценки скорости сходимости алгоритмов типа Франка-Вулфа.
- Работа опубликована на платформе arXiv под номером 2607.29555v1.