Алгоритмы минимизации с ограничениями: метод штрафных функций и барьерные методы

Реальный мир диктует жесткие условия

В теории оптимизации (при поиске максимума или минимума целевой функции) часто рассматривают безусловные задачи — когда переменные могут принимать абсолютно любые значения от минус до плюс бесконечности. Но в реальной инженерии и экономике так не бывает. Толщина балки не может быть отрицательной, расход топлива лимитирован объемом бака, а бюджет рекламной кампании жестко ограничен. Все эти физические рамки математически выражаются в виде систем уравнений и неравенств. Оптимизация при наличии таких ограничений называется условной (Constrained optimization).

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

Метод штрафных функций (Exterior Penalty Method)

Самым интуитивно понятным подходом является метод штрафных функций (внешних штрафов). Идея невероятно проста: мы создаем новую, искусственную (вспомогательную) целевую функцию. Эта функция равна нашей исходной функции плюс специальный штрафной член. Штраф равен нулю, если точка находится внутри разрешенной зоны (удовлетворяет ограничениям). Но как только алгоритм нарушает ограничение и выходит в запретную зону, штрафной член стремительно возрастает (обычно пропорционально квадрату нарушения).

Численный решатель начинает минимизировать эту вспомогательную функцию обычным безусловным методом. Сначала штрафной коэффициент берется небольшим, и алгоритм может слегка «заступить» за границы. На следующем шаге штрафной коэффициент резко увеличивают. Штрафная функция становится похожей на крутой овраг, дно которого совпадает с границей разрешенной области. Повторяя этот процесс с возрастающим штрафом, алгоритм математически принудительно выталкивается из запретной зоны, а последовательность найденных точек сходится к истинному оптимальному решению, лежащему на границе ограничений.

Барьерные методы (Interior Point Methods)

Метод штрафов хорош, но имеет проблему: во время поиска промежуточные решения могут нарушать физические ограничения (например, алгоритм может предложить отрицательную толщину стенки). Если мы одновременно моделируем физику процесса, программа может вылететь с ошибкой.

Эту проблему решают барьерные методы (методы внутренних точек). Они действуют зеркально: алгоритм всегда строго удерживается внутри разрешенной зоны. К целевой функции прибавляется барьерная функция (часто это логарифм от расстояния до границы). В центре разрешенной области барьер не мешает поиску. Но как только алгоритм пытается приблизиться к опасной границе, барьерная функция устремляется в бесконечность (строит математическую бетонную стену), не позволяя нарушить физические законы. Постепенно ослабляя вес барьера (уменьшая барьерный параметр), алгоритм позволяет решению медленно и безопасно «доползти» до оптимальной точки на границе. Современные алгоритмы прямо-двойственных внутренних точек (Primal-Dual Interior Point Methods), развившие эту концепцию, произвели фурор в 1990-х годах, став абсолютным стандартом решения гигантских задач линейного и нелинейного программирования в логистике, энергетике и финансах.