метод наименьших модулей реализация

Используемые в сочетании с квазинъютоновским методом процедуры линейного поиска получили свое применение в программе fminunc. Эти методы также используются и в подпрограммах нелинейной оптимизации методом наименьших квадратов, а именно в lsqnonlin и lsqcurvefit. В задачах на метод наименьших квадратов подлежащая минимизации функция f(x) представляет собой сумму квадратов. (3-17) Подобного типа задачи широко распространены и имеют ряд практических применений, особенно при подборе модельной функции для некого набора данных, т.е. подбор нелинейных параметров. Эти задачи также широко распространены в теории управления, где в конечном итоге необходимо получить некую , соответствующую некой непрерывной модельной траектории для вектора х и скаляра t. Данная задача может быть сформулирована как: , (3-18) где и есть некие скалярные функции. При дискретизации интеграла посредством подходящих квадратурных формул уравнение (3-18) может быть сформулировано как задача на метод наименьших квадратов (LS). (3-19) Где - и включают в себя веса квадратичной схемы. Отметим, что в данной задаче под вектором F(x) понимается: В задачах данного типа невязка , по-видимому, должна быть наименьшей в точке оптимума, поскольку согласно общепринятой практике необходимо приближаться как можно к реальной траектории. Хотя приведенная функция для метода LS (уравнение 3-18) может быть минимизирована с помощью общего метода оптимизации без наличия ограничений, как это представлено в разделе Оптимизация без наличия ограничений, то определенные характеристики данной задачи часто могут быть использованы для улучшения итеративной эффективности данной методики решения. Градиент и матрица Гессе для задачи LS (3-18) имеют особую структуру. После обозначения матрицы Якобиана для F(x) размерностью m-х-n через J(x), вектора градиента функции f(x) через , матрицы Гессе для f(x) через и матрицы Гессе для каждой через получим (3-20) Где Матрица Q(x) обладает тем свойством, что когда невязка стремится к нулю при стремлении к точке решения, то и сама матрица стремится к нулю. Таким образом, при небольших значениях в точке решения, одним из наиболее эффективных методов является использование направления Ньютона-Гаусса в качестве основы для процедуры и оптимизации. Метод Ньютона-Гаусса Согласно методу Ньютона-Гаусса направление поиска находится на каждой итерации k так, что бы решение задачи на метод наименьших квадратов будет (3-21) Полученное согласно данному методу направление является эквивалентом направления Ньютона при пренебрежении члена Q(x). Направление поиска может быть использовано в качестве составляющей стратегии линейного поиска, что обеспечивает условие, что на каждой итерации идет уменьшение функции f(x). Рассмотрим возможные преимущества метода Ньютона-Гаусса. На рисунке 3-3 представлена траектория поиска минимума для функции Розенброка (уравнение 3-2) при использовании постановки задачи как метод наименьших квадратов. Метод Ньютона-Гаусса дает сходимость после 48 обращений к расчету функции при конечно-разностном расчете градиента по сравнению с 140 итерациями для BFGS метода без наличия ограничений. Рис. 3-3. Применение метода Ньютона-Гаусса для функции Розенброка В методе Ньютона-Гаусса часто встречается ряд проблем в ситуации, когда член второго порядка Q(x) в уравнении (3-20) достаточно значителен по своей величине. Методом, который преодолевает такие трудности, является метод Левенберга-Марквардта. Метод Левенберга-Марквардта В основу метода Левенбрга-Марквардта [27], [29] положено направление поиска, которое находится при решении системы линейных уравнений: (3-22) Где скаляр задает как величину, так и направление параметра . Когда равен нулю, то направление будет идентично этому же параметру из метода Ньютона-Гаусса. По мере того, как стремится к бесконечности, то стремится к вектору с нулевыми компонентами и направлению наискорейшего спуска. В данном случае предполагается, что для достаточно больших значений остается справедливым. Следовательно, член может контролируемым с целью обеспечения спуска в случае необходимости учета членов второго порядка, которые, в свою очередь, заметно ограничивают эффективность метода Ньютона-Гаусса. Отсюда следует, что метод Левенберга-Марквардта основан на направлении поиска, являющегося сочетанием направления Ньютона-Гаусса и наискорейшего спуска, что и представлено на рисунке 3-4. (Метод Левенберга-Марквардта для функции Розенброка). Решение для функции Розенброка (уравнение 3-2) сходится после 90 обращений к расчету функции по сравнению с 48 для метода Ньютона-Гаусса. Такая низкая эффективность отчасти объясняется тем, что метод Ньютона-Гаусса обычно более эффективен в случае, когда в решении невязка равна нулю. Однако такая информация не всегда является заранее доступной и повышенная устойчивость метода Левенберга-Марквардта компенсирует его иногда имеющую место слабую эффективность. Рис. 3-4. Метод Левенберга-Марквардта для функции Розенброка Реализация нелинейного метода наименьших квадратов Общий обзор нелинейных методов наименьших квадратов можно найти в работе Денниса [10]. Специфические детали метода Левенберга-Марквардта можно найти в работе Мора [30]. Оба метода Ньютона-Гаусса и Левенберга-Марквардта реализованы в тулбоксе Оптимизация. Особенности реализации приведены ниже. Реализация метода Ньютона-Гаусса Метод Ньютона-Гаусса реализован с помощью стратегии полиномиального линейного поиска, аналогичного тому, что было рассмотрено в разделе применительно к оптимизации без ограничений. При решении линейной задачи методом наименьших квадратов (уравнение 3-18) есть возможность избежать усиления возмущений при согласовании параметров уравнений путем использования разложения QR для и применения подобного разложения к (при использовании оператора MATLAB \). Данной подход отличается от применения инверсии явной матрицы , где возможно проявление неожиданных ошибок. Дополнительные меры по обеспечению устойчивости также включены в данный метод. Данные меры включают в себя корректировку алгоритма метода Левенберга-Марквардта в случае, если или длина шага становится ниже некого порогового значения (1e-15 в данном исполнении) или когда число обусловленности будет меньше 1e-10. Под числом обусловленности в данном случае понимается отношение наибольшего сингулярного значения к наименьшему.   Реализация метода Левенберга-Марквардта Основная трудность в реализации метода Левенберга-Марквардта заключается в выборе эффективной стратегии для управления размером для каждой итерации таким образом, что бы она подходила для широкого спектра задач. Принятый в данном методе подход реализации заключается в оценке

А.Г.Трифонов. Оптимизация методом наименьших квадратов