Оптимизация

Теоремы двойственности и их доказательства

Часть 1: Слабая теорема двойственности

  • Чтобы увидеть код, который я написал для этого проекта, вы можете проверить его репозиторий на Github
  • Для других частей проекта: часть 1, часть 2

Вступление

Оптимизация проявляется повсюду в машинном обучении, от повсеместного градиентного спуска до квадратичного программирования в SVM и до алгоритма ожидания-максимизации в моделях гауссовской смеси.

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

Поэтому в этом проекте я буду:

  • Просмотрите прямую и двойную формы для самой простой задачи оптимизации: линейное программирование.
  • Покажите, что, решив одну форму задачи оптимизации, мы решим и другую. Это требует от нас доказать две фундаментальные теоремы двойственности в линейном программировании: слабую теорему двойственности и сильную теорему двойственности. Первая теорема будет доказана в этой части, а вторая - в следующей части проекта.
  • Объясните, почему нам следует заботиться о двойственности, продемонстрировав ее применение к некоторым задачам науки о данных.

Линейное программирование

Определение

Все задачи оптимизации (с ограничениями) состоят из трех компонентов:

1. Целевая функция: функция, значение которой мы пытаемся оптимизировать, что может означать минимизировать или максимизировать в зависимости от проблемы. С этого момента значение целевой функции будет называться целевым значением.

2. Переменные решения: переменные в целевой функции, значение которых будет точно настроено, чтобы дать целевой функции ее оптимальное значение.

3. Ограничения: дополнительные уравнения или неравенства, которым должны соответствовать переменные решения.

С помощью этих компонентов мы можем определить линейное программирование как таковое:

Линейное программирование - это задача оптимизации, в которой целевая функция и ограничения являются линейными функциями переменных решения.

Этот принцип можно увидеть в следующей формулировке линейной программы:

куда

x: вектор, содержащий переменные решения

c: вектор, содержащий коэффициенты для каждой переменной решения в целевой функции. Для простоты мы будем называть эти коэффициенты здесь объективными коэффициентами.

A: матрица, в которой каждая строка содержит коэффициенты каждого ограничения

b: вектор, содержащий предельные значения каждого ограничения

Обратите внимание, что векторные неравенства в приведенной выше формуле влекут поэлементные неравенства. Например, x ≥ 0 означает, что каждый элемент x должен быть больше или равен нулю.

Геометрическая интерпретация линейной программы

Хотя приведенная выше формула линейной программы кажется довольно абстрактной, давайте посмотрим, как она выглядит, на простом примере.

  • Предположим, у нас есть только 2 переменные решения, x₁ и x₂. Следовательно, наш вектор x просто [x₁, x₂]

  • Кроме того, предположим, что матрица A и векторы b & c принимают следующие значения:

В результате наша линейная программа представляет собой не что иное, как линейные функции и неравенства переменных решения x₁ и x₂:

Эти линейные функции и неравенства можно визуализировать на двухмерном графике ниже. В этом графике есть несколько важных компонентов, поэтому давайте рассмотрим их один за другим:

1. Объективная ценность

Интенсивность синего цвета на фоне графика показывает, насколько высоко целевое значение в каждой точке [x₁, x₂] на графике. Например:

  • При x₁ = -0,5 и x₂ = -0,5 в нижнем левом углу объективное значение x₁ + x₂ будет низким -1. Таким образом, он представлен очень светло-голубым цветом.
  • Напротив, в правом верхнем углу x₁ = 2,5 и x₂ = 2,5. Это соответствует объективному значению 5, что объясняет, почему фон в правом верхнем углу имеет темно-синий цвет.

2. Кривые уровня

Что еще более интересно, мы видим, что цветовой градиент целевых значений перпендикулярен вектору коэффициентов c из [1, 1].

  • Фактически, если вы проведете любую линию, перпендикулярную c, все точки на этой линии будут иметь одинаковое целевое значение. Мы называем их кривыми уровня целевой функции. На приведенном выше графике показаны две такие кривые уровня, одна из которых имеет целевое значение 0, а другая - 1.
  • Из этих двух линий мы видим, что чем больше мы перемещаем кривую уровня в направлении c, тем выше будет целевое значение. Это пригодится позже при решении этой линейной программы.

3. Возможный регион

Четыре ограничения нашей линейной программы создали серый многоугольник около начала координат.

  • Другими словами, все точки [x₁, x₂] в этом многоугольнике удовлетворяют всем 4 линейным ограничениям.
  • Это объясняет, почему эту область часто называют допустимой областью, поскольку только точки в этой области удовлетворяют всем ограничениям и могут быть приемлемым решением проблемы оптимизации.

Решение линейной программы: графический метод

Остается один вопрос:

Как мы можем найти точку в допустимой области, где целевая функция является наивысшей?

Есть несколько способов решить линейную программу, в частности симплексный алгоритм. Однако для двумерных линейных программ, таких как эта, мы можем просто использовать графический метод, чтобы найти оптимальное решение, то есть точку [x₁, x₂] с наивысшим целевым значением:

1. Мы сдвигаем кривую уровня в направлении c, пока она не выйдет из допустимой области.

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

Для нашего двумерного примера:

  • Когда мы перемещаем кривую уровня в направлении c, кривая уровня входит в допустимую область в начале координат и выходит в точке [2/7, 3/7]. Следовательно, точка x₁ = 2/7, x₂ = 3/7 - оптимальное решение. Это соответствует оптимальному значению 2/7 + 3/7 = 5/7.
  • Это имеет смысл, поскольку все другие точки в допустимой области соприкасались с кривой уровня до этой точки. В результате все их значения целевой функции меньше, чем у оптимального решения (5/7).

Верхняя граница целевой функции

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

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

Это связано с тем, что целевая функция не может подниматься выше этой верхней границы, следовательно, верхняя граница сама по себе является максимально возможным значением, которого может достичь целевая функция, т. Е. Своим максимумом.

Верхняя граница объективных коэффициентов

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

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

Или в векторной форме:

Мы находим взвешенную комбинацию строк A, которая поэлементно больше или равна c.

Это эквивалентно выбору вектора y таким, чтобы Aᵀy ≥ c. Еще одно важное требование: все элементы y должны быть неотрицательными - y ≥ 0— , как будет объяснено позже.

Вот пример такого y, который создает верхнюю границу целевых коэффициентов c, что переводится в верхнюю границу целевой функции:

Верхняя граница целевой функции (с x)

Обратите внимание, что на предыдущем шаге верхняя граница целевых коэффициентов будет преобразована в верхнюю границу целевой функции , только если x₁ и x₂ неотрицательны. Для разнообразия попробуйте x₁ = -3 и x₂ = -4, и вы увидите, что верхняя граница целевой функции - 1,25 x₁ + x₂ - становится меньше, чем сама целевая функция - x₁ + x₂.

Формально это то же самое, что умножить x на обе стороны c ≤ Aᵀy неравенства. Поскольку все элементы x положительны, знак неравенства - меньше или равен - сохраняется:

В результате верхняя граница целевой функции равна yᵀAx.

Верхняя граница целевой функции (без x)

Однако эта верхняя граница по-прежнему включает x, что мы пытаемся оптимизировать в первую очередь. Один из способов удалить x из этого выражения - использовать исходное ограничение Ax ≤ b. Здесь, поскольку все элементы y были выбраны ранее неотрицательными, мы сохраняем знак неравенства:

Короче говоря, объединение всех вышеперечисленных шагов дает нам верхнюю границу целевой функции cᵀx, которая равна просто bᵀy.

Минимизация верхней границы

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

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

Это делается путем минимизации bᵀy с учетом требований y, выбранных ранее: Aᵀy ≥ c и y ≥ 0.

Из приведенной выше формулировки мы видим, что минимизация верхней границы сама по себе является линейной программой - ее целевая функция является линейной функцией переменных решения y, а ее ограничения представляют собой линейные неравенства, включающие y.

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

Слабая теорема двойственности

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

Основная целевая функция всегда меньше или равна двойной целевой функции.

Более формально:

Другими словами, двойная целевая функция bᵀy всегда является верхней границей основной целевой функции cᵀx.

Подожди, это оно ?!

Некоторые из вас могут почесать затылок и подумать: «А разве не cᵀx ≤ bᵀy то, что мы только что показали ранее?». Честно говоря, когда я впервые узнал о слабой теореме двойственности, я также обнаружил, что она довольно противоречива.

Однако это неудивительно, поскольку теорема о слабой двойственности является прямым следствием того, что мы выбрали подходящие y - Aᵀy ≥ c и y ≥ 0—, чтобы создать верхнюю границу bᵀy первичной целевой функции cᵀx. Другими словами, теорема верна только потому, что мы сделали это так.

Доказательство слабой теоремы двойственности

Фактически, «доказательство» слабой теоремы двойственности в точности совпадает с нашей предыдущей конструкцией верхней границы для прямой целевой функции, которая кратко излагается ниже:

Следствие из теоремы слабой двойственности

Несмотря на тавтологический характер слабой теоремы двойственности, она дает нам довольно интересное следствие:

Если нам удастся получить одно и то же объективное значение для первичного и двойственного, то мы пришли к оптимальным решениям для обеих проблем.

Более формально:

где x* и y* - точки в соответствующих возможных областях первичной и двойственной, так что объективные значения двух форм равны в этих точках.

Доказательство следствия

Доказательство этого следствия на самом деле довольно интуитивно понятно. Чтобы доказать, что cᵀx* = bᵀy* подразумевает, что x* является оптимальным решением для первичного:

  1. Предположим, вы можете найти другой x такой, что cᵀx больше cᵀx*. Это означает, что x* не должно быть оптимальным решением для первичной формы, поскольку существует другой x с еще более высоким значением цели.
  2. Это означает, что cᵀx больше bᵀy*, учитывая cᵀx* = bᵀy*.
  3. Однако это нарушает теорему слабой двойственности, которая диктует, что cᵀx ≤ bᵀy для любых x и y в соответствующих первичных и двойственных возможных областях.
  4. Другими словами, более оптимального x, чем x*, найти невозможно. Это означает, что x* действительно является оптимальным решением первичного.

Интуитивно это имеет смысл, поскольку слабая теорема двойственности утверждает, что двойственное - это верхняя граница прямого. Следовательно, когда первичное равно дуальному, мы уверены, что первичное достигло максимально возможного значения.

Доказательство в обратном направлении - cᵀx* = bᵀy* подразумевает, что y* является оптимальным решением для двойственного - в точности противоположно приведенному выше доказательству:

Обратите внимание, что в двух приведенных выше доказательствах:

1. Мы начинаем с отрицания самого утверждения, которое пытаемся доказать: мы утверждаем, что x* не является оптимальным решением для первичной формы или y* не оптимальное решение двойственной формы.

2. Затем мы показываем, что это отрицание приводит к ужасному противоречию: они нарушают слабую теорему двойственности.

3. Это означает, что отрицательное утверждение ложно, а это значит, что исходное утверждение должно быть правдой.

Этот метод доказательства называется доказательство от противного, и он чрезвычайно эффективен. Фактически, это будет суть доказательства сильной теоремы двойственности в следующей части.

Применение следствия

Это следствие из теоремы слабой двойственности дает нам один метод, чтобы проверить, сходится ли наш алгоритм оптимизации.

Вернемся к нашему двухмерному примеру, чтобы увидеть, как мы можем выполнить эту проверку. Ниже представлены наша простая форма (слева) и двойственная форма (справа) одной и той же линейной программы:

А теперь давайте представим, что мы вообще не умеем решать линейные программы, ни с помощью более раннего графического метода, ни с помощью более сложных методов, таких как симплекс.

  • Однако одна вещь, которую мы можем сделать - очень наивно - это случайным образом выбрать две точки в соответствующих первичных и двойственных возможных областях и проверить, совпадает ли первичная точка с двойственной в этих точках.
  • Если да, то эти точки гарантированно будут оптимальными решениями для соответствующих проблем, как это диктуется следствием слабой теоремы двойственности. Затем мы можем прекратить оптимизацию.

Например, в нашем двумерном случае:

  • Выберем точку [x₁, x₂] = [2/7, 3/7] в прямой допустимой области. Значение первичной цели в этой точке равно x₁ + x₂ = 2/7 + 3/7 = 5/7.
  • Затем мы выбираем точку [y₁, y₂] = [1/7, 3/7] в дуальной допустимой области. Значение двойной цели в этой точке равно 2y₁ + y₂ = 2 × 1/7 + 3/7 = 5/7.
  • Поскольку значение первичного равно двойному в этих двух точках, они являются оптимальными решениями соответствующих проблем. А именно, оптимальное решение для прямой формы - это x₁ = 2/7 и x₂ = 3/7, а оптимальное решение для двойственной формы - y₁ = 1/7 и y₂ = 3/7.

Двойная проверка графическим методом

Чтобы подтвердить, что эти две точки действительно являются оптимальными решениями для соответствующих проблем, мы можем оптимизировать прямую и двойственную по отдельности, используя графический метод:

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

Предварительный просмотр сильной теоремы двойственности

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

Однако здесь возникает более серьезный вопрос:

Почему?!

Если решение одной задачи оптимизации достаточно сложно, зачем нам нужно решать две проблемы, чтобы прийти к оптимальному решению?

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

использованная литература

Есть много интернет-ресурсов, посвященных двойственности линейных программ. Однако то, что я считаю наиболее понятным и на чем я основывал большинство своих выводов в форме сообщения в блоге, - это серия лекций по линейному программированию профессора Тима Рафгардена для его курса алгоритмов.

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

Подтверждение

Это семинар в действии, проведенный в сотрудничестве с Phuc Su. Спасибо Phuc за ваш вклад в проект, особенно в отношении слабой теоремы двойственности! Я также хотел бы поблагодарить доктора Хашимото за то, что он направил нас для исследования этой интересной темы, а также команду ИИ в MTI за прослушивание нашей презентации по проекту 🙏