Квазиньютоновские методы - это методы, используемые для поиска нулей или локальных максимумов и минимумов функций в качестве альтернативы методу Ньютона. Их можно использовать, если якобиан или гессиан недоступны или слишком дороги для вычисления на каждой итерации. «Полный» метод Ньютона требует якобиана для поиска нулей или гессиана для поиска экстремумов.
Поиск нулей: поиск корней
Метод Ньютона для нахождения нулей функции нескольких переменных задается , где является левым обратным к матрице Якоби из оценивается для .
Строго говоря, любой метод, заменяющий точный якобиан с приближением - это квазиньютоновский метод. [1] Например, метод аккорда (где заменяется на для всех итераций) - простой пример. Приведенные ниже методы оптимизации относятся к важному подклассу квазиньютоновских методов - методам секущих. [2]
Использование методов, разработанных для поиска экстремумов, для поиска нулей не всегда является хорошей идеей, поскольку большинство методов, используемых для поиска экстремумов, требуют, чтобы используемая матрица была симметричной. Хотя это верно в контексте поиска экстремумов, это редко выполняется при поиске нулей. «Хороший» и «плохой» методы Бройдена - это два метода, обычно используемых для поиска экстремумов, которые также могут применяться для поиска нулей. Другие методы , которые могут быть использованы , являются колонного обновления метод , то метод обратной колонного обновление , то квазиньютоновский метод наименьших квадратов и квазиньютоновский обратным методом наименьших квадратов .
Совсем недавно квазиньютоновские методы стали применяться для поиска решения множественных связанных систем уравнений (например, задач взаимодействия жидкость-структура или задач взаимодействия в физике). Они позволяют найти решение, решая каждую составляющую систему отдельно (что проще, чем глобальная система) циклическим, итеративным способом, пока не будет найдено решение глобальной системы. [2] [3]
Поиск экстремумов: оптимизация
Отметив, что поиск минимума или максимума скалярнозначной функции - это не что иное, как поиск нулей градиента этой функции, квазиньютоновские методы могут быть легко применены для поиска экстремумов функции. Другими словами, если это градиент , затем поиск нулей вектор-функции соответствует поиску экстремумов скалярнозначной функции ; якобиан теперь становится гессенской . Основное отличие состоит в том, что матрица Гессе является симметричной матрицей , в отличие от якобиана при поиске нулей . Большинство квазиньютоновских методов, используемых при оптимизации, используют это свойство.
В оптимизации , методы квазиньютоновские (частный случай из методов переменных-метрики ) являются алгоритмами для нахождения локального максимума и минимума из функций . Квазиньютоновские методы основаны на методе Ньютона для поиска стационарной точки функции, где градиент равен 0. Метод Ньютона предполагает, что функция может быть локально аппроксимирована квадратичной функцией в области около оптимума, и использует первый и второй производные, чтобы найти стационарную точку. В более высоких измерениях метод Ньютона использует градиент и матрицу Гессе вторых производных функции, которую необходимо минимизировать.
В квазиньютоновских методах вычисление матрицы Гессе не требуется. Гессен обновляется путем анализа последовательных векторов градиента. Квазиньютоновские методы являются обобщением метода секущих для нахождения корня первой производной для многомерных задач. В нескольких измерениях секущее уравнения недоопределенное , а также методы квазиньютоновские отличаются тем , как они ограничивают решение, как правило , путем добавления простого обновления низкого ранга с текущей оценкой гессиана.
Первый квазиньютоновский алгоритм был предложен Уильямом К. Дэвидоном , физиком, работающим в Аргоннской национальной лаборатории . Он разработал первый квазиньютоновский алгоритм в 1959 году: формулу обновления DFP , которая позже была популяризирована Флетчером и Пауэллом в 1963 году, но сегодня используется редко. Наиболее распространенными квазиньютоновскими алгоритмами в настоящее время являются формула SR1 (для «симметричного ранга один»), метод BHHH , широко распространенный метод BFGS (независимо предложенный Бройденом, Флетчером, Голдфарбом и Шанно в 1970 году) и его низкий -расширение памяти L-BFGS . Класс Бройдена представляет собой линейную комбинацию методов DFP и BFGS.
Формула SR1 не гарантирует, что матрица обновления будет поддерживать положительную определенность, и может использоваться для неопределенных проблем. Метод Бройдена не требует, чтобы матрица обновления была симметричной, и используется для нахождения корня общей системы уравнений (а не градиента) путем обновления якобиана (а не гессиана).
Одним из главных преимуществ квазиньютоновских методов перед методом Ньютона является то, что матрица Гессе (или, в случае квазиньютоновских методов, ее аппроксимация)переворачивать не нужно. Метод Ньютона и его производные, такие как методы внутренней точки , требуют инвертирования гессиана, что обычно реализуется путем решения системы линейных уравнений и часто является довольно дорогостоящим. Напротив, квазиньютоновские методы обычно дают оценку напрямую.
Как и в методе Ньютона, для нахождения минимума функции используется приближение второго порядка.. Ряд Тейлора из вокруг итерации
где () - градиент , априближение к матрице Гессе . [4] Градиент этого приближения (относительно) является
и установка этого градиента на ноль (что является целью оптимизации) обеспечивает шаг Ньютона:
Гессенское приближение выбран, чтобы удовлетворить
которое называется секущим уравнением (ряд Тейлора самого градиента). Более чем в одном измеренииявляется недоопределенной . В одном измерении решение дляи применение шага Ньютона с обновленным значением эквивалентно методу секущей . Различные квазиньютоновские методы различаются выбором решения секущего уравнения (в одном измерении все варианты эквивалентны). Большинство методов (но с исключениями, такими как метод Бройдена ) ищут симметричное решение (); кроме того, варианты, перечисленные ниже, могут быть мотивированы поиском обновления это как можно ближе к в какой-то норме ; это,, где - некоторая положительно определенная матрица , определяющая норму. Примерное начальное значение часто бывает достаточно для достижения быстрой сходимости, хотя нет общей стратегии выбора . [5] Обратите внимание, чтодолжно быть положительно-определенным. Неизвестный обновляется с применением шага Ньютона, рассчитанного с использованием текущей приближенной матрицы Гессе :
- , с участием выбран так, чтобы удовлетворять условиям Вульфа ;
- ;
- Градиент, вычисленный в новой точке , а также
используется для обновления приблизительного гессенского , или прямо обратное по формуле Шермана – Моррисона .
- Ключевым свойством обновлений BFGS и DFP является то, что если положительно определен, и выбирается так, чтобы выполнялись условия Вульфа, то также положительно определен.
Наиболее популярные формулы обновления:
Метод BFGS Broyden Семья Бройден DFP SR1
Другие методы - это метод Пирсона, метод Маккормика, симметричный метод Пауэлла Бройдена (PSB) и метод Гринштадта. [2]
Связь с обращением матрицы
Когда выпуклая квадратичная функция с положительно определенным гессианом , можно было бы ожидать, что матрицы генерируется квазиньютоновским методом, чтобы сходиться к обратному гессиану . Это действительно так для класса квазиньютоновских методов, основанных на обновлениях с наименьшими изменениями. [6]
Известные реализации
Реализации квазиньютоновских методов доступны на многих языках программирования. Известные реализации включают:
- GNU Octave в своей
fsolve
функции использует форму BFGS с расширениями доверенной области .
- Научная библиотека GNU реализует алгоритм Бройдена-Флетчера-Гольдфарба-Шанно ( BFGS ).
- Mathematica включает в себя квазиньютоновские решатели. [7]
- NAG библиотека содержит несколько подпрограмм [8] для минимизации или максимизации функции [9] , которые используют алгоритмов квазиньютоновских.
- В MATLAB в Optimization Toolbox , то
fminunc
функция использует (среди других методов) BFGS квазиньютоновский метод. [10] Многие методы с ограничениями из набора инструментов Оптимизация используют BFGS и вариант L-BFGS . [11] - R «ы
optim
общего назначения подпрограмма оптимизатор использует BFGS метод с помощьюmethod="BFGS"
. [12] - Scipy .optimize имеет fmin_bfgs. В SciPy расширение Python , то
scipy.optimize.minimize
функция включает в себя, наряду с другими методами, в BFGS реализации. [13]
Смотрите также
- Метод BFGS
- L-BFGS
- OWL-QN
- Метод Бройдена
- Формула обновления DFP
- Метод Ньютона
- Метод Ньютона в оптимизации
- Формула SR1
Рекомендации
- ^ Бройдена, CG (1972). «Квазиньютоновские методы». В Мюррей, W. (ред.). Численные методы безусловной оптимизации . Лондон: Academic Press. С. 87–106. ISBN 0-12-512250-0.
- ^ а б в Хельтерман, Роб (2009). «Аналитическое исследование квазиньютоновского метода наименьших квадратов для задач взаимодействия» . Докторская диссертация, Гентский университет . Проверено 14 августа 2014 .
- ^ Роб Хэлтерман, Дирк Ван Эстер, Даан Верлейен (2015). «Ускорение решения физической модели внутри токамака с помощью (обратного) метода обновления столбцов» . Журнал вычислительной и прикладной математики . 279 : 133–144. DOI : 10.1016 / j.cam.2014.11.005 .CS1 maint: использует параметр авторов ( ссылка )
- ^ https://mathinsight.org/taylors_theorem_multivariable_introduction
- ^ Нокедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация . Нью-Йорк: Спрингер. С. 142 . ISBN 0-387-98793-2.
- ^ Роберт Мансел Гауэр; Питер Рихтарик (2015). «Рандомизированные квазиньютоновские обновления представляют собой алгоритмы обращения линейно сходящейся матрицы». arXiv : 1602.01768 [ math.NA ].
- ^ http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationQuasiNewtonMethods.html
- ^ Группа численных алгоритмов. «Указатель ключевых слов: квазиньютон» . Руководство библиотеки NAG, Марк 23 . Проверено 9 февраля 2012 .
- ^ Группа численных алгоритмов. «E04 - Минимизация или максимизация функции» (PDF) . Руководство библиотеки NAG, Марк 23 . Проверено 9 февраля 2012 .
- ^ http://www.mathworks.com/help/toolbox/optim/ug/fminunc.html
- ^ http://www.mathworks.com/help/toolbox/optim/ug/brnoxzl.html
- ^ [1]
- ^ http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html
дальнейшее чтение
- Боннанс, JF; Gilbert, J. Ch .; Lemaréchal, C .; Сагастизабал, Калифорния (2006). Численная оптимизация: теоретические и численные аспекты (второе изд.). Springer. ISBN 3-540-35445-Х.
- Флетчер, Роджер (1987), Практические методы оптимизации (2-е изд.), Нью-Йорк: John Wiley & Sons , ISBN 978-0-471-91547-8.
- Нокедаль, Хорхе; Райт, Стивен Дж. (1999). «Квазиньютоновские методы» . Численная оптимизация . Нью-Йорк: Спрингер. С. 192–221. ISBN 0-387-98793-2.
- Нажмите, WH; Теукольский, С.А. Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 10.9. Квазиньютон или методы переменной метрики в многомерности» . Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.
- Весы, LE (1985). Введение в нелинейную оптимизацию . Нью-Йорк: Макмиллан. С. 84–106. ISBN 0-333-32552-4.