Наименьшие квадраты (подбор кривой модели) алгоритмы

Определение наименьших квадратов

Наименьшие квадраты, в целом, являются задачей нахождения векторный x, который является локальным минимизатором к функции, которая является суммой квадратов, возможно подвергните некоторым ограничениям:

minxF(x)22=minxiFi2(x)

таким образом, что A·x ≤ b, Aeq·x = beq,     lb ≤ x ≤ ub.

Существует несколько решателей Optimization Toolbox™, доступных для различных типов F (x) и различные типы ограничений:

РешательF (x)Ограничения
mldivide d'none'
lsqnonneg dx ≥ 0
lsqlin dСвязанный, линейный
lsqnonlinОбщий F (x)Связанный
lsqcurvefitF (x, xdata) – ydataСвязанный

Существуют алгоритмы на четыре наименьших квадрата в решателях Optimization Toolbox, в дополнение к алгоритмам, используемым в mldivide:

  • "Доверительная отражающая область"

  • Levenberg-Marquardt

  • lsqlin внутренняя точка

  • Алгоритм используется lsqnonneg

Все алгоритмы являются крупномасштабными; смотрите Крупномасштабный по сравнению с Алгоритмами Средней шкалы. Для общего обзора методов нелинейного метода наименьших квадратов смотрите Денниса [8]. Определенные детали о методе Levenberg-Marquardt могут быть найдены в Moré [28].

Доверительная область отражающие наименьшие квадраты

Доверительная область отражающий алгоритм наименьших квадратов

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

Чтобы изучить подход доверительной области к оптимизации, рассмотрите проблему безусловной минимизации, минимизируйте f (x), где функция берет аргументы вектора и возвращает скаляры. Предположим, что вы - в точке x в n - пробел, и вы хотите улучшиться, т.е. переместиться в точку с более низким значением функции. Основная идея состоит в том, чтобы аппроксимировать f более простым функциональным q, который обоснованно отражает поведение функционального f в окружении N вокруг точки x. Это окружение является доверительной областью. Испытательный шаг s вычисляется путем минимизации (или приблизительно минимизации) по N. Это - подпроблема доверительной области,

mins{q(s), sN}.(1)

Текущая точка обновляется, чтобы быть x + s если f (x + s) < f (x); в противном случае текущая точка остается неизменной, и N, область доверия, уменьшается, и испытательный расчет шага повторяется.

Ключевые вопросы в определении определенного подхода доверительной области к минимизации f (x) состоят в том, как выбрать и вычислить приближение q (заданный в текущей точке x), как выбрать и изменить доверительную область N, и как точно решить подпроблему доверительной области. Этот раздел фокусируется на неограниченной проблеме. Более поздние разделы обсуждают дополнительные осложнения из-за присутствия ограничений на переменные.

В стандартном методе доверительной области ([48]), квадратичное приближение q задан первыми двумя сроками приближения Тейлора к F в x; окружение N является обычно сферическим или эллипсоидальным в форме. Математически подпроблема доверительной области обычно утверждается

min{12sTHs+sTg  таким образом , что  DsΔ},(2)

где g является градиентом f в текущей точке x, H является матрицей Гессиана (симметрическая матрица вторых производных), D является диагональной матрицей масштабирования, Δ является положительной скалярной величиной и ∥. ∥ является 2-нормой. Хорошие алгоритмы существуют для решения уравнения 2 (см. [48]); такие алгоритмы обычно включают расчет всех собственных значений H, и процесс Ньютона применился к характеристическому уравнению

1Δ1s=0.

Такие алгоритмы предоставляют точное решение уравнения 2. Однако они требуют времени, пропорционального нескольким факторизациям H. Поэтому для проблем доверительной области другой подход необходим. Несколько приближений и эвристических стратегий, на основе уравнения 2, были предложены в литературе ([42] и [50]). Подход приближения, сопровождаемый в решателях Optimization Toolbox, должен ограничить подпроблему доверительной области двумерным подпространством S ([39] и [42]). Однажды подпространство S был вычислен, работа, чтобы решить уравнение 2 тривиальна, даже если полная информация о собственном значении/собственном векторе необходима (поскольку в подпространстве, проблема только двумерна). Доминирующая работа теперь переключила к определению подпространства.

Двумерное подпространство S определяется при помощи предобусловленного процесса метода сопряженных градиентов, описанного ниже. Решатель задает S как линейный пробел, заполненный s 1 и s 2, где s 1 является в направлении градиента g, и s 2 является любой аппроксимированным направлением Ньютона, т.е. решением

Hs2=g,(3)

или направление отрицательного искривления,

s2THs2<0.(4)

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

Эскиз безусловной минимизации с помощью идей доверительной области теперь легко дать:

  1. Сформулируйте двумерную подпроблему доверительной области.

  2. Решите уравнение 2, чтобы определить испытательный шаг s.

  3. Если f (x + s) <f (x), то x = x + s.

  4. Настройте Δ.

Эти четыре шага повторяются до сходимости. Размерность доверительной области Δ настроена согласно стандартным правилам. В частности, это уменьшено, если испытательный шаг не принят, т.е. f (x + s) ≥ f (x). См. [46] и [49] для обсуждения этого аспекта.

Решатели Optimization Toolbox обрабатывают несколько важных особых случаев f со специализированными функциями: нелинейный метод наименьших квадратов, квадратичные функции и линейный метод наименьших квадратов. Однако базовые алгоритмические идеи эквивалентны для общего случая. Эти особые случаи обсуждены в более поздних разделах.

Крупномасштабный нелинейный метод наименьших квадратов

Важный особый случай для f (x) является проблемой нелинейного метода наименьших квадратов

minxifi2(x)=minxF(x)22,(5)

где F (x) является функцией с векторным знаком с i компонента F (x), равный fi (x). Основной метод, используемый, чтобы решить эту задачу, эквивалентен в общем случае, описанном в Методах Доверительной области для Нелинейной Минимизации. Однако структура проблемы нелинейного метода наименьших квадратов используется, чтобы улучшить КПД. В частности, аппроксимированное направление Ньютона Гаусса, т.е. решение s к

minJs+F22,(6)

(где J является якобианом F (x)), используется, чтобы помочь задать двумерное подпространство S. Вторые производные функционального fi компонента (x) не используются.

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

JTJs=JTF,

несмотря на то, что нормальные уравнения явным образом не формируются.

Крупномасштабный линейный метод наименьших квадратов

В этом случае функциональный f (x), который будет решен,

f(x)=Cx+d22,

возможно подвергните линейным ограничениям. Алгоритм генерирует строго выполнимый, выполняет итерации схождения, в пределе, к локальному решению. Каждая итерация включает приближенное решение большой линейной системы (порядка n, где n является длиной x). Матрицы итерации имеют структуру матричного C. В частности, метод предобусловленных методов сопряженных градиентов используется, чтобы приблизительно решить нормальные уравнения, т.е.

CTCx=CTd,

несмотря на то, что нормальные уравнения явным образом не формируются.

Метод доверительной области подпространства используется, чтобы определить поисковое направление. Однако вместо того, чтобы ограничить шаг (возможно) одним отражательным шагом, как в нелинейном случае минимизации, кусочный отражающий поиск линии проводится в каждой итерации, как в квадратичном случае. См. [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 описание задачи должно минимизировать квадратичную функцию

minx12xTHx+cTx

подвергните линейным ограничениям и связанным ограничениям. lsqlin функция минимизирует квадратичную норму векторного   Cx – d, удовлетворяющего линейным ограничениям и связанным ограничениям. Другими словами, lsqlin минимизирует

Cxd22=(Cxd)T(Cxd)=(xTCTdT)(Cxd)=(xTCTCx)(xTCTddTCx)+dTd=12xT(2CTC)x+(2CTd)Tx+dTd.

Это помещается в quadprog среда путем установки матрицы H на 2CTC и вектора c к (–2CTd). (Вектор свободных членов dTd не оказывает влияния на местоположение минимума.) После этой переформулировки lsqlin проблема, quadprog 'interior-point-convex' алгоритм вычисляет решение.

Примечание

quadprog 'interior-point-convex' алгоритм имеет два пути выполнения кода. Это берет тот, когда матрица Гессиана, из которой H является обычной (полной) матрицей, удваивается, и это берет другой, когда H является разреженной матрицей. Для получения дополнительной информации разреженного типа данных, смотрите Разреженные матрицы (MATLAB). Обычно алгоритм быстрее для больших проблем, которые имеют относительно немного ненулевых условий, когда вы задаете H как sparse. Точно так же алгоритм быстрее для небольших или относительно плотных проблем, когда вы задаете H как full.

Метод Levenberg-Marquardt

В задаче наименьших квадратов функциональный f (x) минимизирован, который сумма квадратов.

minxf(x)=F(x)22=iFi2(x).(7)

Проблемы этого типа происходят в большом количестве практических применений, особенно когда подходящие функции модели к данным, т.е. нелинейная оценка параметра. Они также распространены в управлении, где вы хотите выход, y (x,t), чтобы следовать за некоторой непрерывной траекторией модели, φ (t), для векторного x и скалярного t. Эта проблема может быть выражена как

minxnt1t2(y(x,t)φ(t))2dt,(8)

где y (x,t) и φ (t) является скалярными функциями.

Когда интеграл дискретизируется с помощью подходящей формулы квадратуры, вышеупомянутое может быть сформулировано как задача наименьших квадратов:

minxnf(x)=i=1m(y¯(x,ti)φ¯(ti))2,(9)

где y¯ и φ¯ включайте веса квадратурной схемы. Обратите внимание на то, что в этой проблеме векторный F (x)

F(x)=[y¯(x,t1)φ¯(t1)y¯(x,t2)φ¯(t2)...y¯(x,tm)φ¯(tm)].

В проблемах этого вида невязка F (x) ∥, вероятно, будет мала в оптимуме, поскольку это - общая практика, чтобы установить реалистично достижимые целевые траектории. Несмотря на то, что функция в LS может быть минимизирована с помощью общего метода безусловной минимизации, как описано в Основах Неограниченной Оптимизации, определенные характеристики проблемы могут часто использоваться, чтобы повысить итеративную эффективность процедуры решения. Градиент и матрица Гессиана LS имеют специальную структуру.

Обозначая m-by-n якобиевская матрица F (x) как J (x), вектор градиента f (x) как G (x), матрица Гессиана f (x) как H (x) и матрица Гессиана каждого Fi (x) как Hi (x), вы имеете

G(x)=2J(x)TF(x)H(x)=2J(x)TJ(x)+2Q(x),(10)

где

Q(x)=i=1mFi(x)Hi(x).

Матричный Q (x) имеет свойство, что, когда невязка F (x) ∥ имеет тенденцию обнулять, когда xk приближается к решению, затем Q (x) также имеет тенденцию обнулять. Таким образом, когда F (x) ∥ мал в решении, очень эффективный метод состоит в том, чтобы использовать направление Ньютона Гаусса в качестве основания для процедуры оптимизации.

В методе Ньютона Гаусса поисковое направление, dk, получено в каждой главной итерации, k, который является решением проблемы линейного метода наименьших квадратов:

minxnJ(xk)F(xk)22.(11)

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

Метод Ньютона Гаусса часто сталкивается с проблемами, когда термин второго порядка Q (x) является значительным. Метод, который преодолевает эту проблему, является методом Levenberg-Marquardt.

 Levenberg-Marquardt [25], и [27] метод использует поисковое направление, которое является решением линейной системы уравнений

(J(xk)TJ(xk)+λkI)dk=J(xk)TF(xk),(12)

или, опционально, уравнений

(J(xk)TJ(xk)+λkdiag(J(xk)TJ(xk)))dk=J(xk)TF(xk),(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 на функции Розенброка

Для большего количества полного описания этого рисунка, включая скрипты, которые генерируют итеративные точки, смотрите Банановую Минимизацию Функции.

Для просмотра документации необходимо авторизоваться на сайте