Градиентный спуск с ограничениями (множители Лагранжа)

Я пытаюсь найти min функции в N параметрах, используя градиентный спуск. Однако я хочу сделать это, ограничив сумму абсолютных значений параметров 1 (или

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

В данный момент я использую Python (scipy) реализацию CG, поэтому я бы действительно предпочел предложения, которые не требуют от меня переписывать / настраивать CG код сам, но использовать существующий метод.

2 10
machine-learning gradient-descent

2 ответа:

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

Обычно существует три решения:

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

Кроме того, вы не совсем ясно выражаетесь в своем вопросе - используете ли вы градиентный спуск или CG (сопряженные градиенты)?

22

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

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

Например, рассмотрим задачу 1:

Найти (x1, x2), минимизирующее f(x1, x2) с учетом нелинейного ограничения |x1|+|x2|

Существует версия линейного ограничения, Задача 2:

Найти (x1,x2,x3,x4), которая минимизирует f (x1, x2) при следующих линейных ограничениях:

  1. x1
  2. - x1
  3. x2
  4. - x2
  5. x3+x4

Примечание:

  • Если (x1, x2, x3, x4) удовлетворяет ограничениям для задачи 2, то (x1, x2) удовлетворяет ограничениям для задачи 1 (поскольку x3 >= abs(x1), x4 >= abs (x2))
  • Если (x1,x2) удовлетворяет ограничениям для задачи 1, то мы можем расширить до (x1,x2,x3,x4) удовлетворяющих ограничениям для Задача 2 путем задания x3=abs(x1), x4=abs (x2)
  • x3, x4 не влияют на целевую функцию
Из этого следует, что нахождение оптимума для задачи 2 даст вам оптимум для задачи 1, и наоборот.
4