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

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

Наименьшие квадраты, в целом, являются задачей нахождения векторный 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:

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

  • lsqlin активный набор

  • "Доверительная область, отражающая" (нелинейный или линейный метод наименьших квадратов)

  • Levenberg-Marquardt (нелинейный метод наименьших квадратов)

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

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

Линейный метод наименьших квадратов: внутренняя точка или Активный Набор

lsqlin 'interior-point' алгоритм использует выпуклый внутренней точкой quadprog Алгоритм, и lsqlin 'active-set' алгоритм использует активный набор 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 вычисляет решение.

Примечание

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

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

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

Многие методы, используемые в решателях 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 является любой аппроксимированным направлением Ньютона, i.e., решение

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) не используются.

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

JTJs=JTF,

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

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

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

f(x)=Cx+d22,

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

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 явным образом. Для примера смотрите функцию умножения якобиана с Линейным методом наименьших квадратов.

Метод 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)

где ti равномерно расположен с интервалами. В этой проблеме векторный F (x)

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

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

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

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

где

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

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

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

mindknJ(xk)dk+F(xk)22.(11)

Направление, выведенное из этого метода, эквивалентно направлению Ньютона когда условия Q (x) = 0. Алгоритм может использовать поисковое направление 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 и diag(A) означает матрицу диагональных терминов в A. Установите опцию 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, поэтому, использует поисковое направление, которое является пересечением направления Ньютона Гаусса и направления наискорейшего спуска.

Другое преимущество для метода Levenberg-Marquardt состоит в том, когда якобиевский J имеет неполный ранг. В этом случае метод Ньютона Гаусса может иметь числовые проблемы, потому что проблема минимизации в  уравнении 11 плохо изложена. В отличие от этого метод Levenberg-Marquardt имеет полный ранг в каждой итерации, и, поэтому, избегает этих проблем.

Следующий рисунок показывает итерации метода Levenberg-Marquardt при минимизации функции Розенброка, известно трудная проблема минимизации, которая находится в форме наименьших квадратов.

Метод Levenberg-Marquardt на функции Розенброка

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

Связанные ограничения в методе Levenberg-Marquardt

Когда проблема содержит связанные ограничения, lsqcurvefit и lsqnonlin измените итерации Levenberg-Marquardt. Если предложенная итеративная точка, x находится за пределами границ, алгоритм, проектирует шаг на самую близкую допустимую точку. Другими словами, с P, заданным как оператор projection, что проекты неосуществимые точки на выполнимую область, алгоритм изменяет предложенную точку x к P (x). По определению оператор проекции P работает с каждым xi компонента независимо согласно

P(xi)={lbiесли xi<lbiubiесли xi>ubixiв противном случае

или, эквивалентно,

P(xi)=min(max(xi,lbi),ubi).

Алгоритм изменяет останавливающийся критерий меры оптимальности первого порядка. Позвольте x быть предложенной итеративной точкой. В неограниченном случае останавливающийся критерий

f(x)tol,(14)

где tol является значением допуска оптимальности, которое является 1e-4*FunctionTolerance. В ограниченном случае останавливающийся критерий

xP(xf(x))2tol f(x).(15)

Чтобы изучить этот критерий, сначала обратите внимание что, если x находится во внутренней части выполнимой области, то оператор P не оказывает влияния. Так, останавливающийся критерий становится

xP(xf(x))2=f(x)2tol f(x),

который совпадает с исходным неограниченным критерием остановки, f(x)tol. Если граничное ограничение активно, означая, что x – ∇f (x) не выполним, то в точке, где алгоритм должен остановиться, градиент в точке на контуре перпендикулярен контуру. Поэтому точка x равна P (x – ∇f (x)), проекция шага наискорейшего спуска, как показано в следующем рисунке.

Levenberg-Marquardt останавливающееся условие

Sketch of x minus the projection of x minus gradient of f(x)

Смотрите также

| | | |

Похожие темы