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

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

Полуопределенное программирование (Semidefinite Programming, SDP) — это высшая ступень иерархии выпуклого конического программирования, поглощающая в себя линейное, квадратичное и коническое программирование второго порядка. В SDP переменной оптимизации выступает не вектор, а симметричная матрица, и задача состоит в минимизации линейной функции от ее элементов при условии, что сама матрица (или аффинная комбинация заданных матриц) является положительно полуопределенной. Этот математический аппарат совершил настоящую революцию в теории управления, комбинаторной оптимизации и квантовой теории информации.