Методы штрафных и барьерных функций: алгоритмы внутренней точки в нелинейной оптимизации
Задачи нелинейного программирования (НЛП), содержащие сложные ограничения-неравенства, исторически представляли колоссальную трудность для вычислительной математики. Если безусловная оптимизация легко решается методами градиентного спуска или Ньютона-Рафсона, то наличие нелинейных «стен», за которые решению нельзя выходить, постоянно срывает сходимость алгоритмов. В 1960-х годах Ричард Фиакко и Гарт Маккормик разработали гениальный математический трюк, позволивший свести сложную условную оптимизацию к серии простых безусловных задач. Этот подход, известный как метод штрафных и барьерных функций, впоследствии переродился в алгоритмы внутренней точки, которые навсегда изменили ландшафт промышленного исследования операций.