Ограниченная оптимизация и условия KKT

Оптимизация с ограничениями и условия Куна-Таккера

Взгляд на функцию Лагранжа

Оптимизация является неотъемлемой частью компьютерной науки, физики, математики и экономики. Она является важным инструментом для AI и специалистов по машинному обучению (ML) и применяется в различных областях, включая принятие решений, планирование маршрутов и настройку параметров в моделях ML, таких как метод опорных векторов (SVM) и нейронные сети. Самой общей формой оптимизации является поиск минимума/максимума функции относительно ее независимых переменных, что может быть достигнуто применением основных концепций дифференциального исчисления. Математически, на этих экстремумах наклон (первая производная) функции равен нулю, что называется стационарными точками. Определение того, представляет ли такая точка максимум или минимум, производится путем оценки кривизны (второй производной).

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

Ограничения равенства

Задачи оптимизации с ограничениями равенства имеют следующий вид

• Настало ли время начать говорить о быстрой архитектуре в магистратуре по юриспруденции?
• Исследователи из Северо-Западного университета предложили революционную систему машинного обучения для классификации медицинских данных в условиях отсутствия электросети, сокращая энергопотребление искусственного интеллекта на 99%.
• Революционизация обработки данных с помощью «Smart Fill» ИИ-система Google Sheets

где f(x) – функция, которую мы стремимся минимизировать, а ограничение g(x) = 0 определяет область, в пределах которой должна быть выполнена минимизация. В таких случаях минимизация сосредоточена в заданной области, определенной ограничением. Тем не менее, как было отмечено ранее, традиционное применение дифференциального исчисления для определения стационарных точек не учитывает ограничение, требуя альтернативного подхода.

Функция Лагранжа

Поскольку это задача минимизации, один из подходов для адаптации традиционного метода – назначить бесконечное значение функции вне указанной области. Для этого мы вводим новую функцию f'(x), характеризующуюся следующим выражением:

Такая модификация исключает возможность появления минимума за пределами области, тем самым гарантируя, что оптимальная точка находится внутри нее. В результате мы можем переформулировать задачу с ограничениями в задачу оптимизации без ограничений.

Однако с этим подходом появляется определенная сложность. Использование дифференциального исчисления для оптимизации вышеуказанной задачи невозможно, так как функция f'(x) не является дифференцируемой из-за резкого разрыва на границе области. Именно здесь в игру вступает функция Лагранжа. Вместо определения функции f'(x) как в (2), мы формулируем ее как задачу максимизации.

Выражение с правой стороны называется функцией Лагранжа, а новая переменная 𝞴 является множителем Лагранжа. Из (4) ясно, что в областях, где {g(x)<0, g(x)>0}, 𝞴 может принимать значения {-∞, ∞}, чтобы максимизировать выражение до ∞.

В результате оптимизация в (3) принимает следующую форму.

Следует отметить, что проблема недифференцируемости все еще существует, так как внутренняя максимизация приводит к той же разрывной функции. Однако, с помощью лагранжевого представления мы можем использовать неравенство max-min для преобразования проблемы максимум-минимум в проблему минимум-максимума и преодолеть эту проблему.

Здесь мы сначала оптимизируем относительно независимой переменной x, а затем относительно множителя Лагранжа 𝞴.

Неравенственные ограничения

Теперь мы рассмотрим сценарии, когда ограничение представляет собой не уравнение, а неравенство. Такие оптимизации имеют следующий вид:

Мы можем решить это с помощью аналогичного подхода: мы определяем f’(x) так же, как и f(x) в пределах области, определенной ограничениями, и бесконечным везде, где ограничения не выполняются:

И соответственно, лагранжева функция определяется как:

Множители Лагранжа, соответствующие неравенственным ограничениям, обозначаются 𝝻. Уравнение (9) отличается тем, что оно также имеет ограничения на множители Лагранжа, которых не было в (4). Теперь оптимизационная проблема в (7) принимает форму:

Применяя неравенство min-max,

Условия KKT (Karush-Kuhn-Tucker)

Оптимизация в (10) называется примарной версией, а (11) ее двойственной версией. Согласно неравенству min-max, двойственная версия ограничивает снизу примарную версию, что подразумевает, что две версии не обязательно равны. Однако существуют условия, при которых примарная и двойственная версии равны, что называется условием регулярности. Предполагая регулярность, чтобы (x*, 𝝻*) была точкой решения, она должна удовлетворять следующим условиям KKT:

1. Примарная выполнимость

Это следует из определения проблемы.

2. Двойственная выполнимость

Двойная выполнимость следует из (9).

3. Стационарность

Это интересное свойство. Поскольку 𝞴* является нулем или положительным числом, условие стационарности в основном означает, что в оптимальной точке градиенты f(x) и g(x) должны быть ориентированы в противоположных направлениях. Рационал за этим заключается в следующем: если градиенты f(x) и g(x) были бы выровнены в одном направлении в точке x = x*, то и f(x), и g(x) одновременно уменьшались бы в направлении, противоположном их градиентам. В этом случае f(x) могло бы продолжать уменьшаться за значение f(x*) без нарушения ограничения, и в таком случае x* уже не является оптимальной точкой. Поэтому для того, чтобы точка была оптимальной, должно быть выполнено условие стационарности.

4. Дополнительное отождествление

Это еще одно интересное свойство, которое непосредственно следует из уравнения (9). Когда ограничение g(x*) < 0, множитель Лагранжа 𝝻* должен быть равен нулю. Поскольку множитель Лагранжа также указывает на то, насколько чувствительным является наше решение к связанному ограничению, значение 𝝻* = 0 означает, что связанное ограничение не оказывает влияния на определение решения. Другими словами, будь то решение с учетом ограничения или без него, результат остается неизменным. Один очевидный пример – это случай, когда f(x) имеет глобальный минимум в области, где g(x) ≤ 0. В качестве другого примера рассмотрим минимизацию функции f(x) с двумя ограничениями: g¹(x) < 5 и g²(x) < -1. В этом случае множитель Лагранжа 𝝻²*, соответствующий ограничению g², равен нулю, поскольку g¹ уже удовлетворяет условиям g², что делает g² незначительным в качестве ограничения.

Применение: Метод опорных векторов (SVM)

Примером задачи условной оптимизации с неравенственными ограничениями в машинном обучении является метод опорных векторов (SVM). Когда имеется набор данных точек {(x¹, y¹), (x², y²), …} с y ∈ {-1, 1}, представляющих два класса, целью является определить классификатор, максимизирующий разрыв между классами. В частности, формулируется следующая задача минимизации SVM:

Термин ||w|| в уравнении представляет обратное значение разрыва. Очевидно, что здесь присутствуют многочисленные ограничения неравенства: на самом деле у нас есть ограничение для каждой точки данных. Однако на практике решение определяется только небольшим количеством точек данных, которые находятся рядом с границей классификатора; их называют опорными векторами. Как мы обсудили в разделе дополнительное отождествление, только множители Лагранжа, соответствующие ограничениям, связанным с опорными векторами, имеют ненулевые значения. Для всех остальных точек данных соответствующие им ограничения имеют множители Лагранжа со значением нуля, что делает их незначительными при определении границы классификатора.

Заключение

Мы начали с краткого введения в задачу безусловной оптимизации и постепенного расширения ее, чтобы учесть равенственные и неравенственные ограничения. Более того, мы обсудили, как функция Лагранжа решает проблемы, возникающие из-за ограничений. Исследуя оптимальность функции Лагранжа, мы получили представление о условиях KKT. Наконец, мы кратко рассмотрели, как SVM формулируется как задача условной оптимизации и кратко обсудили ее решения.