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

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

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