MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем

Optimization Toolbox 2.2 Руководство пользователя

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

Используемые в сочетании с квазинъютоновским методом процедуры линейного поиска получили свое применение в программе 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. Под числом обусловленности в данном случае понимается отношение наибольшего сингулярного значения к наименьшему.

 

Реализация метода Левенберга-Марквардта

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

Линейно прогнозируемых сумма квадратов рассчитывается как

 

(3-23)

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

Рис. 3-5: Корректировка lambdak, где No - Нет; Yes - Да; Increase - Увеличить; Reduce - Уменьшить

Далее, вслед за корректировкой , результаты решения уравнения (3-22) используется для нахождения направления поиска . Затем в направлении длина шага принимается равной единице с последующим применением процедуры линейного поиска аналогично тому, что было рассмотрено в разделе о реализации оптимизации без наличия ограничений. Процедура линейного поиска обеспечивает выполнение условия для каждой основной итерации и, таким образом, данный метод становится методом спуска.

Данный способ реализации был успешно тестирован для большого числа нелинейных задач. Было получено, что этот метод более устойчив, чем метод Ньютона-Гаусса и во много раз более эффективен метода без наличия ограничений. Для команды lsqnonlin по умолчанию применяется метод Левенберга-Марквардта. При желании можно использовать метод Ньютона-Гаусса посредством установки параметра Левенберга-Марквардта как 'off'.


Поиск по сайту:

Система Orphus

Яндекс.Метрика