Ньютоновские методы в оптимизации и решении систем нелинейных уравнений

Я попросил разъяснений по поводу недавнего вопроса о minpack , и получил следующий комментарий:

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

То, что смущает меня в этом комментарии (и связанные с ним негативные мнения о специализированных нелинейных решателях наименьших квадратов, таких как minpack), лучше всего объяснить на примере метода сопряженных градиентов . Этот метод применим к системам с симметричной положительно определенной матрицы . Его также можно использовать для решения общей задачи наименьших квадратов для произвольной матрицы $Ax=b$ $A$ $\operatorname{min}_x||Ax-b||^2$ $A$ , но делать это не рекомендуется. Одно из объяснений, почему мы не должны этого делать, заключается в том, что число условий системы значительно увеличится.

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

optimization least-squares Томас Климпел
источник

Ответы:

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

Мои возражения против использования MINPACK не имеют ничего общего с алгоритмами, которые использует MINPACK, и не имеют ничего общего с их реализацией. Мое основное возражение заключается в том, что программное обеспечение датируется 1980 годом, а последнее обновление было в 1999 году. Хорхе Море на пенсии; Я сомневаюсь, что он или любой другой автор программного обеспечения больше следят за ним, и нет команды людей, активно поддерживающих его. Единственная документация, которую я могу найти по программному обеспечению, - это оригинальный технический отчет Argonne 1980 года, написанный Хорхе Море и другими авторами MINPACK. (Главы 1-3 можно найти здесь , а главу 4 можно найти здесь.) После поиска в исходном коде MINPACK и просмотра документации (PDF-файлы являются отсканированными изображениями и не могут быть найдены), я не вижу никаких вариантов, чтобы приспособиться к ограничениям. Поскольку первоначальный плакат о нелинейной проблеме наименьших квадратов хотел решить ограниченную нелинейную проблему наименьших квадратов, MINPACK даже не решит эту проблему.

Если вы посмотрите на список рассылки IPOPT, некоторые пользователи отметят, что производительность пакета для задач нелинейного наименьших квадратов (NLS) смешана по сравнению с алгоритмами Левенберга-Марквардта и более специализированными алгоритмами NLS (см. Здесь , здесь и здесь ). Производительность IPOPT относительно алгоритмов NLS, конечно, зависит от проблемы. Учитывая эту обратную связь с пользователем, IPOPT представляется разумной рекомендацией относительно алгоритмов NLS.

Тем не менее, вы делаете хорошее замечание, что алгоритмы NLS должны быть исследованы. Я согласен. Я просто считаю, что следует использовать пакет, более современный, чем MINPACK, потому что я считаю, что он будет работать лучше, будет более удобным и поддерживаться. Ceres кажется интересным кандидатом, но сейчас он не может справиться с ограниченными проблемами. ТАОбудет работать над задачами наименьших квадратов с ограничением по квадратам, хотя он не реализует классический Левенберг-Марквардт, но вместо этого реализует алгоритм без производных. Алгоритм без производных, вероятно, будет хорошо работать для крупномасштабных задач, но я не буду использовать его для мелкомасштабных задач. Я не мог найти никаких других пакетов, которые внушали бы большую уверенность в их разработке программного обеспечения. Например, GALAHAD, похоже, не использует контроль версий или какое-либо автоматическое тестирование, на первый взгляд. МИНПАК, похоже, тоже этого не делает. Если у вас есть опыт работы с MINPACK или рекомендации относительно лучшего программного обеспечения, я весь в ушах.

Имея все это в виду, возвращаясь к цитате моего комментария:

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

Лучший комментарий, вероятно, что-то вроде:

$n$ $n$ $g(x) = 0$

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

Джефф Оксберри
источник

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

Томас Климпел

g (x) = 0

$g(x)=0$

‖ g (x) ‖^{2}

$\lVert g(x) \rVert^2$

@JedBrown: я должен изменить язык вокруг. На мой взгляд, оптимизация без производных (DFO) предпочтительна только тогда, когда оценки функций очень дороги. По какой-то причине на ум приходит случай, когда целью является решение проблемы PDE, поэтому я сказал «крупномасштабный» (конечно, для меня в оптимизации «крупномасштабный PDE» означает нечто иное, чем для вас, кто решает PDE параллельно на регулярной основе). Когда я думаю о «решении уравнений с ограничениями», я имею в виду проблему . (продолжение)

g (x) = 0, x \in S, S \subset R^{n}, S \neq R^{n}

$g(x) = 0, x \in S, S \subset \mathbb{R}^{n}, S \neq \mathbb{R}^{n}$

Джефф Оксберри

@JedBrown: стандартный способ решения этой проблемы - решить . Могут быть и другие пути, но я не знаю ни одного. Я не предполагаю, что один сброс ; минимумы с ненулевыми значениями целевой функции явно не решают решаемую систему уравнений. В невыпуклом случае методы глобальной оптимизации необходимы для подтверждения существования или отсутствия решений. У меня нет большого опыта работы с вариационными неравенствами, поэтому мне не сразу понятно, где ВИ вступают в игру, тем более что не обязательно является конусом.

min_{x \in S} ‖ g (x) ‖^{2}

$\min_{x \in S} \|g(x)\|^2$

g (x) = 0

$g(x) = 0$

S

$S$

Джефф Оксберри

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

S

$S$

Джед Браун

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

f (x) = x^{2} - \exp (- 4 (x - 2)^{2}) [click for Wolfram Alpha]

$f(x) = x^2 - \exp\big(-4(x-2)^2 \big) \qquad \text{[click for Wolfram Alpha]}$

Сюжет оригинальной цели

Это явно имеет уникальный минимум, и мы ожидаем, что наш метод оптимизации найдет его независимо от отправной точки. Но если мы рассмотрим только условия оптимальности первого порядка, мы ищем решение из [Wolfram Alpha] $x$ $\nabla f(x) = 0$

градиент

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

Если переформулирует новую задачу оптимизации для минимизации нормы градиента в квадрате, мы ищем глобальный минимум из [Wolfram Alpha] , который имеет несколько локальных минимумов. $x$ $\lVert\nabla f(x)\rVert^2$

введите описание изображения здесь

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

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

Джед браун
источник

Джед, эти ссылки на WA не совсем соответствуют тому, что, по твоим словам, они делают. Скобки игнорируются или неправильно передаются в URL.

Билл Барт

Странно, ссылки у меня работают. Может ли это зависеть от веб-браузера? Какие-нибудь предложения для альтернативного способа представить это?

Джед Браун

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

Билл Барт

У кого-то еще есть проблемы со ссылками? Я пробовал в нескольких браузерах, и он отлично работает в каждом случае.

Джед Браун

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

Томас Климпел