В современную эру машинного обучения, сжатия данных и обработки сигналов (Compressed Sensing) регулярно возникают задачи оптимизации огромной размерности, в которых целевая функция является суммой гладкой и негладкой составляющих. Классическим примером является задача регуляризованной регрессии LASSO, где гладкая квадратичная ошибка штрафуется негладкой L1-нормой для обеспечения разреженности решения. Для эффективного решения таких задач традиционные градиентные методы неприменимы, а субградиентные методы сходятся недопустимо медленно. Решением стал математический аппарат проксимальных операторов и методы проксимального градиента.

Теория двойственности Фенхеля (Fenchel Duality) является одним из самых глубоких и абстрактных обобщений классической двойственности в нелинейном программировании. Опираясь на аппарат выпуклого анализа, эта теория позволяет рассматривать задачи оптимизации не через призму точек и градиентов, а через пространства сопряженных функций и опорных гиперплоскостей. Двойственность Фенхеля дает мощнейшие инструменты для решения задач негладкой оптимизации, математической физики и машинного обучения, где классический метод множителей Лагранжа сталкивается с аналитическими трудностями.

Когда вычисление значения целевой функции является крайне долгим, дорогостоящим или требует проведения реального физического эксперимента (например, обучение сверхглубокой нейронной сети, бурение разведочной скважины или синтез нового белка), классические методы градиентного спуска и эволюционные алгоритмы становятся неприменимыми. Они требуют тысяч итераций, что экономически нецелесообразно. Байесовская оптимизация (Bayesian Optimization) представляет собой математическую стратегию глобального поиска, которая минимизирует количество обращений к целевой функции за счет построения ее вероятностной суррогатной модели.

Среди бесчисленного множества эвристических алгоритмов, разработанных для NP-трудной задачи коммивояжера (Traveling Salesperson Problem, TSP), эвристика Лина-Кернигана (Lin-Kernighan, LK) занимает место безоговорочного лидера. Предложенный в 1973 году Шенем Лином и Брайаном Керниганом, этот алгоритм локального поиска продемонстрировал невероятную способность находить решения, отличающиеся от абсолютного математического оптимума на десятые доли процента, для графов с миллионами узлов. Его успех базируется на элегантной концепции обмена ребрами с динамически изменяемой глубиной перебора.