Наименьшие квадраты, в целом, являются задачей нахождения векторный x, который является локальным минимизатором к функции, которая является суммой квадратов, возможно подвергните некоторым ограничениям:
таким образом, что A·x ≤ b, Aeq·x = beq, lb ≤ x ≤ ub.
Существует несколько решателей Optimization Toolbox™, доступных для различных типов F (x) и различные типы ограничений:
| Решатель | F (x) | Ограничения |
|---|---|---|
mldivide | C· – d | 'none' |
lsqnonneg | C· – d | x ≥ 0 |
lsqlin | C· – d | Связанный, линейный |
lsqnonlin | Общий F (x) | Связанный |
lsqcurvefit | F (x, xdata) – ydata | Связанный |
Существуют алгоритмы на четыре наименьших квадрата в решателях Optimization Toolbox, в дополнение к алгоритмам, используемым в mldivide:
Все алгоритмы являются крупномасштабными; смотрите Крупномасштабный по сравнению с Алгоритмами Средней шкалы. Для общего обзора методов нелинейного метода наименьших квадратов смотрите Денниса [8]. Определенные детали о методе Levenberg-Marquardt могут быть найдены в Moré [28].
Многие методы, используемые в решателях Optimization Toolbox, основаны на доверительных областях, простой все же мощной концепции в оптимизации.
Чтобы изучить подход доверительной области к оптимизации, рассмотрите проблему безусловной минимизации, минимизируйте f (x), где функция берет аргументы вектора и возвращает скаляры. Предположим, что вы - в точке x в n - пробел, и вы хотите улучшиться, т.е. переместиться в точку с более низким значением функции. Основная идея состоит в том, чтобы аппроксимировать f более простым функциональным q, который обоснованно отражает поведение функционального f в окружении N вокруг точки x. Это окружение является доверительной областью. Испытательный шаг s вычисляется путем минимизации (или приблизительно минимизации) по N. Это - подпроблема доверительной области,
| (1) |
Текущая точка обновляется, чтобы быть x + s если f (x + s) < f (x); в противном случае текущая точка остается неизменной, и N, область доверия, уменьшается, и испытательный расчет шага повторяется.
Ключевые вопросы в определении определенного подхода доверительной области к минимизации f (x) состоят в том, как выбрать и вычислить приближение q (заданный в текущей точке x), как выбрать и изменить доверительную область N, и как точно решить подпроблему доверительной области. Этот раздел фокусируется на неограниченной проблеме. Более поздние разделы обсуждают дополнительные осложнения из-за присутствия ограничений на переменные.
В стандартном методе доверительной области ([48]), квадратичное приближение q задан первыми двумя сроками приближения Тейлора к F в x; окружение N является обычно сферическим или эллипсоидальным в форме. Математически подпроблема доверительной области обычно утверждается
| (2) |
где g является градиентом f в текущей точке x, H является матрицей Гессиана (симметрическая матрица вторых производных), D является диагональной матрицей масштабирования, Δ является положительной скалярной величиной и ∥. ∥ является 2-нормой. Хорошие алгоритмы существуют для решения уравнения 2 (см. [48]); такие алгоритмы обычно включают расчет всех собственных значений H, и процесс Ньютона применился к характеристическому уравнению
Такие алгоритмы предоставляют точное решение уравнения 2. Однако они требуют времени, пропорционального нескольким факторизациям H. Поэтому для проблем доверительной области другой подход необходим. Несколько приближений и эвристических стратегий, на основе уравнения 2, были предложены в литературе ([42] и [50]). Подход приближения, сопровождаемый в решателях Optimization Toolbox, должен ограничить подпроблему доверительной области двумерным подпространством S ([39] и [42]). Однажды подпространство S был вычислен, работа, чтобы решить уравнение 2 тривиальна, даже если полная информация о собственном значении/собственном векторе необходима (поскольку в подпространстве, проблема только двумерна). Доминирующая работа теперь переключила к определению подпространства.
Двумерное подпространство S определяется при помощи предобусловленного процесса метода сопряженных градиентов, описанного ниже. Решатель задает S как линейный пробел, заполненный s 1 и s 2, где s 1 является в направлении градиента g, и s 2 является любой аппроксимированным направлением Ньютона, т.е. решением
| (3) |
или направление отрицательного искривления,
| (4) |
Философия позади этого выбора S должна обеспечить глобальную сходимость (через направление быстрейшего спуска или отрицательное направление искривления) и достигнуть быстро локальной сходимости (через шаг Ньютона, когда это существует).
Эскиз безусловной минимизации с помощью идей доверительной области теперь легко дать:
Сформулируйте двумерную подпроблему доверительной области.
Решите уравнение 2, чтобы определить испытательный шаг s.
Если f (x + s) <f (x), то x = x + s.
Настройте Δ.
Эти четыре шага повторяются до сходимости. Размерность доверительной области Δ настроена согласно стандартным правилам. В частности, это уменьшено, если испытательный шаг не принят, т.е. f (x + s) ≥ f (x). См. [46] и [49] для обсуждения этого аспекта.
Решатели Optimization Toolbox обрабатывают несколько важных особых случаев f со специализированными функциями: нелинейный метод наименьших квадратов, квадратичные функции и линейный метод наименьших квадратов. Однако базовые алгоритмические идеи эквивалентны для общего случая. Эти особые случаи обсуждены в более поздних разделах.
Важный особый случай для f (x) является проблемой нелинейного метода наименьших квадратов
| (5) |
где F (x) является функцией с векторным знаком с i компонента F (x), равный fi (x). Основной метод, используемый, чтобы решить эту задачу, эквивалентен в общем случае, описанном в Методах Доверительной области для Нелинейной Минимизации. Однако структура проблемы нелинейного метода наименьших квадратов используется, чтобы улучшить КПД. В частности, аппроксимированное направление Ньютона Гаусса, т.е. решение s к
| (6) |
(где J является якобианом F (x)), используется, чтобы помочь задать двумерное подпространство S. Вторые производные функционального fi компонента (x) не используются.
В каждой итерации метод предобусловленных методов сопряженных градиентов используется, чтобы приблизительно решить нормальные уравнения, т.е.
несмотря на то, что нормальные уравнения явным образом не формируются.
В этом случае функциональный f (x), который будет решен,
возможно подвергните линейным ограничениям. Алгоритм генерирует строго выполнимый, выполняет итерации схождения, в пределе, к локальному решению. Каждая итерация включает приближенное решение большой линейной системы (порядка n, где n является длиной x). Матрицы итерации имеют структуру матричного C. В частности, метод предобусловленных методов сопряженных градиентов используется, чтобы приблизительно решить нормальные уравнения, т.е.
несмотря на то, что нормальные уравнения явным образом не формируются.
Метод доверительной области подпространства используется, чтобы определить поисковое направление. Однако вместо того, чтобы ограничить шаг (возможно) одним отражательным шагом, как в нелинейном случае минимизации, кусочный отражающий поиск линии проводится в каждой итерации, как в квадратичном случае. См. [45] для деталей поиска линии. В конечном счете линейные системы представляют подход Ньютона, получая условия оптимальности первого порядка в решении, приводя к сильным локальным уровням сходимости.
Якобиан умножает функцию. lsqlin может решить задачу линейно-метода-наименьших-квадратов-с-ограничениями, не используя матричный C явным образом. Вместо этого это использует якобиан, умножают функциональный jmfun,
W = jmfun(Jinfo,Y,flag)
то, что вы обеспечиваете. Функция должна вычислить следующие продукты для матричного Y:
Если flag == 0 затем W = C'*(C*Y).
Если flag > 0 затем W = C*Y.
Если flag < 0 затем W = C'*Y.
Это может быть полезно, если C является большим, но содержит достаточно структуры, что можно записать jmfun не формируя C явным образом. Для примера смотрите, что якобиан Умножает Функцию с Линейным методом наименьших квадратов.
lsqlin 'interior-point' алгоритм использует выпуклый внутренней точкой quadprog Алгоритм. quadprog описание задачи должно минимизировать квадратичную функцию
подвергните линейным ограничениям и связанным ограничениям. lsqlin функция минимизирует квадратичную норму векторного Cx – d, удовлетворяющего линейным ограничениям и связанным ограничениям. Другими словами, lsqlin минимизирует
Это помещается в quadprog среда путем установки матрицы H на 2CTC и вектора c к (–2CTd). (Вектор свободных членов dTd не оказывает влияния на местоположение минимума.) После этой переформулировки lsqlin проблема, quadprog 'interior-point-convex' алгоритм вычисляет решение.
quadprog
'interior-point-convex' алгоритм имеет два пути выполнения кода. Это берет тот, когда матрица Гессиана, из которой H является обычной (полной) матрицей, удваивается, и это берет другой, когда H является разреженной матрицей. Для получения дополнительной информации разреженного типа данных, смотрите Разреженные матрицы (MATLAB). Обычно алгоритм быстрее для больших проблем, которые имеют относительно немного ненулевых условий, когда вы задаете H как sparse. Точно так же алгоритм быстрее для небольших или относительно плотных проблем, когда вы задаете H как full.
В задаче наименьших квадратов функциональный f (x) минимизирован, который сумма квадратов.
| (7) |
Проблемы этого типа происходят в большом количестве практических применений, особенно когда подходящие функции модели к данным, т.е. нелинейная оценка параметра. Они также распространены в управлении, где вы хотите выход, y (x,t), чтобы следовать за некоторой непрерывной траекторией модели, φ (t), для векторного x и скалярного t. Эта проблема может быть выражена как
| (8) |
где y (x,t) и φ (t) является скалярными функциями.
Когда интеграл дискретизируется с помощью подходящей формулы квадратуры, вышеупомянутое может быть сформулировано как задача наименьших квадратов:
| (9) |
где и включайте веса квадратурной схемы. Обратите внимание на то, что в этой проблеме векторный F (x)
В проблемах этого вида невязка ∥F (x) ∥, вероятно, будет мала в оптимуме, поскольку это - общая практика, чтобы установить реалистично достижимые целевые траектории. Несмотря на то, что функция в LS может быть минимизирована с помощью общего метода безусловной минимизации, как описано в Основах Неограниченной Оптимизации, определенные характеристики проблемы могут часто использоваться, чтобы повысить итеративную эффективность процедуры решения. Градиент и матрица Гессиана LS имеют специальную структуру.
Обозначая m-by-n якобиевская матрица F (x) как J (x), вектор градиента f (x) как G (x), матрица Гессиана f (x) как H (x) и матрица Гессиана каждого Fi (x) как Hi (x), вы имеете
| (10) |
где
Матричный Q (x) имеет свойство, что, когда невязка ∥F (x) ∥ имеет тенденцию обнулять, когда xk приближается к решению, затем Q (x) также имеет тенденцию обнулять. Таким образом, когда ∥F (x) ∥ мал в решении, очень эффективный метод состоит в том, чтобы использовать направление Ньютона Гаусса в качестве основания для процедуры оптимизации.
В методе Ньютона Гаусса поисковое направление, dk, получено в каждой главной итерации, k, который является решением проблемы линейного метода наименьших квадратов:
| (11) |
Направление, выведенное из этого метода, эквивалентно направлению Ньютона, когда условия Q (x) могут быть проигнорированы. Поисковый dk направления может использоваться в качестве части стратегии поиска линии гарантировать, что в каждой итерации функциональный f (x) уменьшается.
Метод Ньютона Гаусса часто сталкивается с проблемами, когда термин второго порядка Q (x) является значительным. Метод, который преодолевает эту проблему, является методом Levenberg-Marquardt.
Levenberg-Marquardt [25], и [27] метод использует поисковое направление, которое является решением линейной системы уравнений
| (12) |
или, опционально, уравнений
| (13) |
где скалярный λk управляет и величиной и направлением dk. Установите опцию ScaleProblem к 'none' выбрать Equation 12 и установить ScaleProblem к 'Jacobian' выбрать Equation 13.
Вы устанавливаете начальное значение параметра λ 0 использований InitDamping опция. Иногда, 0.01 значение по умолчанию этой опции может быть неподходящим. Если вы находите, что алгоритм Levenberg-Marquardt делает мало начальных успехов, попробуйте установку InitDamping к различному значению, чем значение по умолчанию, возможно, 1e2.
Когда λk является нулем, направление, dk идентичен тому из метода Ньютона Гаусса. Когда λk стремится к бесконечности, dk стремится к направлению быстрейшего спуска с величиной, имеющей тенденцию обнулять. Это подразумевает, что для некоторого достаточно большого λk, термин F (xk + dk) < F (xk) сохраняется. Термином λk можно поэтому управлять, чтобы гарантировать спуск, даже когда с условиями второго порядка, которые ограничивают КПД метода Ньютона Гаусса, сталкиваются. То, когда шаг успешен (дает более низкое значение функции), алгоритм устанавливает λ k +1 = λk/10. Когда шаг неудачен, алгоритм устанавливает λ k +1 = λk *10.
Внутренне, алгоритм Levenberg-Marquardt использует допуск оптимальности (останавливающий критерий) 1e-4 времена функциональный допуск.
Метод Levenberg-Marquardt поэтому использует поисковое направление, которое является пересечением направления Ньютона Гаусса и направления быстрейшего спуска. Это проиллюстрировано в рисунке 12-1, Методе Levenberg-Marquardt на Функции Розенброка. Решение для функции Розенброка сходится после 90 функциональных оценок по сравнению с 48 для метода Ньютона Гаусса. Более плохой КПД частично, потому что метод Ньютона Гаусса является обычно более эффективным, когда невязка является нулем в решении. Однако такая информация не всегда доступна заранее, и увеличенная робастность метода Levenberg-Marquardt компенсирует свой случайный более плохой КПД.
Рисунок 12-1, метод Levenberg-Marquardt на функции Розенброка
Для большего количества полного описания этого рисунка, включая скрипты, которые генерируют итеративные точки, смотрите Банановую Минимизацию Функции.
