Почему алгоритмы оптимизации определяются с точки зрения других задач оптимизации?

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

Например, https://arxiv.org/pdf/1511.05133v1.pdf.

Все выглядит красиво и хорошо , но тогда есть это в обновление .... так что алгоритм , который решает для ? Мы не знаем, и это не говорит. Так волшебным образом мы должны решить еще одну задачу оптимизации, которая заключается в том, чтобы найти минимизирующий вектор так, чтобы внутренний продукт был минимальным - как это можно сделать?$\text{argmin}_x$$z^{k+1}$$\text{argmin}$

Возьмем другой пример: https://arxiv.org/pdf/1609.05713v1.pdf

Все выглядит хорошо и хорошо, пока вы не нажмете этот проксимальный оператор в середине алгоритма, и каково определение этого оператора?

Boom:

Теперь, пожалуйста, скажите, как мы решаем этот в проксимальном операторе? Это не говорит. В любом случае, эта проблема оптимизации выглядит сложной (NP HARD) в зависимости от того, что .$\text{argmin}_x$$f$

Может кто-нибудь, пожалуйста, просветите меня, чтобы:

1. Почему так много алгоритмов оптимизации определены в терминах других задач оптимизации?

(Разве это не какая-то проблема курицы и яйца: для решения проблемы 1 необходимо решить проблему 2, используя метод решения проблемы 3, который основан на решении проблемы ....)

2. Как вы решаете эти проблемы оптимизации, которые встроены в эти алгоритмы? Например, , как найти минимизатор справа?$x^{k+1} = \text{argmin}_x \text{really complicated loss function}$

3. В конечном счете, я озадачен тем, как эти алгоритмы могут быть реализованы численно. Я понимаю, что добавление и умножение векторов - это простые операции в python, но как насчет , есть ли какая-либо функция (скрипт), которая волшебным образом дает вам минимизатор функции?$\text{argmin}_x$

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

Вы смотрите на блок-схемы алгоритма верхнего уровня. Некоторые из отдельных шагов в блок-схеме могут иметь свои собственные подробные блок-схемы. Тем не менее, в опубликованных работах, в которых делается акцент на краткость, многие детали часто опускаются. Детали стандартных внутренних проблем оптимизации, которые считаются «старой шляпой», могут не предоставляться вообще.

Общая идея заключается в том, что алгоритмы оптимизации могут потребовать решения ряда, как правило, более простых задач оптимизации. Нередко в алгоритме верхнего уровня есть 3 или даже 4 уровня алгоритмов оптимизации, хотя некоторые из них являются внутренними для стандартных оптимизаторов.

Даже решение о том, когда завершить алгоритм (на одном из уровней иерархии), может потребовать решения проблемы побочной оптимизации. Например, не отрицательно ограниченная линейная задача наименьших квадратов может быть решена для определения множителей Лагранжа, используемых для оценки показателя оптимальности KKT, используемого для принятия решения, когда объявлять оптимальность.

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

Вот пример. Последовательное квадратичное программирование (SQP). Первоначальная задача оптимизации решается путем итеративного решения условий оптимальности Каруша-Куна-Таккера, начиная с начальной точки с целью, являющейся квадратичным приближением лагранжиана задачи, и линеаризации ограничений. Результирующая квадратичная программа (QP) решена. QP, который был решен, либо имеет ограничения области доверия, либо поиск строки проводится от текущей итерации до решения QP, которое само по себе является проблемой оптимизации, чтобы найти следующую итерацию. Если используется метод Квазиньютона, необходимо решить задачу оптимизации, чтобы определить обновление квазиньютоновского гессиана Лагранжиана - обычно это оптимизация закрытой формы с использованием формул закрытой формы, таких как BFGS или SR1, но это может быть численная оптимизация. Затем решается новый QP и т. Д. Если QP когда-либо невозможно, в том числе для начала, решается задача оптимизации, чтобы найти реальную точку. Между тем, внутри решателя QP могут вызываться один или два уровня внутренних проблем оптимизации. В конце каждой итерации может быть решена неотрицательная линейная задача наименьших квадратов для определения показателя оптимальности. И т.п.

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

Это должно начать давать вам представление.

Изменить : В ответ на вопрос о курице и яйце, который был добавлен к вопросу после моего ответа: если есть проблема курицы и яйца, то это не является четко определенным практическим алгоритмом. В приведенных мной примерах нет курицы и яйца. Шаги алгоритма более высокого уровня вызывают решатели оптимизации, которые либо определены, либо уже существуют. SQP итеративно вызывает решатель QP для решения подзадач, но решатель QP решает более простую проблему, QP, чем исходная проблема. Если существует алгоритм глобальной оптимизации еще более высокого уровня, он может вызывать решатель SQP для решения локальных подзадач нелинейной оптимизации, а решатель SQP, в свою очередь, вызывает решатель QP для решения подзадач QP. Нет курицы и яйца.

Примечание: возможности оптимизации есть «везде». Эксперты по оптимизации, такие как те, кто разрабатывает алгоритмы оптимизации, чаще видят эти возможности оптимизации и рассматривают их как таковые, чем средний Джо или Джейн. И будучи склонными к алгоритму, вполне естественно, что они видят возможности для построения алгоритмов оптимизации из алгоритмов оптимизации более низкого уровня. Постановка и решение задач оптимизации служат строительными блоками для других (более высокого уровня) алгоритмов оптимизации.

Изменить 2 : В ответ на запрос щедрости, который был только что добавлен ОП. В документе, описывающем нелинейный оптимизатор SQP SNOPT https://web.stanford.edu/group/SOL/reports/snopt.pdf, конкретно упоминается решатель QP SQOPT, который отдельно документируется как используемый для решения подзадач QP в SNOPT.

Мне нравится ответ Марка, но я хотел бы упомянуть «Имитационный отжиг», который в принципе может работать поверх любого алгоритма оптимизации. На высоком уровне это работает так:

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

Интуиция заключается в том, что вначале он будет широко искать пространство в поисках «лучших мест» для поиска оптимумов.

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

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

TL; DR - они обсуждают проксимальные методы. Одним из преимуществ таких методов является разделение - вы можете найти решение, оптимизировав более простые подзадачи. Много раз (или, по крайней мере, иногда) вы можете найти в литературе специализированный алгоритм для оценки конкретной проксимальной функции. В их примере они делают шумоподавление изображения. Одним из шагов является очень успешный и широко цитируемый алгоритм Шамболя.

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

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

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

Наконец, в качестве примера возьмем оригинальный алгоритм классического алгоритма FISTA. Они выводят алгоритм для двух очень специфических функций - квадрата потерь и l1-нормы. Тем не менее, они отмечают, что к ним не могут применяться никакие функции, если они удовлетворяют некоторым предварительным условиям, одна из которых заключается в том, что проксимальная часть регуляризованного может быть эффективно вычислена. Это не теоретическое требование, а практическое.

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