Наименьшие квадраты, в целом, являются задачей нахождения векторный 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:
Все алгоритмы кроме lsqlin активный набор является крупномасштабным; смотрите Крупномасштабный по сравнению с Алгоритмами Средней шкалы. Для общего обзора методов нелинейного метода наименьших квадратов смотрите Денниса [8]. Определенные детали о методе Levenberg-Marquardt могут быть найдены в Moré [28].
lsqlin
'interior-point' алгоритм использует выпуклый внутренней точкой quadprog Алгоритм, и lsqlin
'active-set' алгоритм использует активный набор quadprog алгоритм. quadprog описание задачи должно минимизировать квадратичную функцию
подвергните линейным ограничениям и связанным ограничениям. lsqlin функция минимизирует квадратичную норму векторного Cx – d, удовлетворяющего линейным ограничениям и связанным ограничениям. Другими словами, lsqlin минимизирует
Это помещается 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. Это - подпроблема доверительной области,
| (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 является любой аппроксимированным направлением Ньютона, i.e., решение
| (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) не используются.
В каждой итерации метод предобусловленных методов сопряженных градиентов используется, чтобы приблизительно решить нормальные уравнения, i.e.,
несмотря на то, что нормальные уравнения явным образом не формируются.
В этом случае функциональный f (x), который будет решен,
возможно подвергните линейным ограничениям. Алгоритм генерирует строго выполнимый, выполняет итерации схождения, в пределе, к локальному решению. Каждая итерация включает приближенное решение большой линейной системы (порядка n, где n является длиной x). Матрицы итерации имеют структуру матричного C. В частности, метод предобусловленных методов сопряженных градиентов используется, чтобы приблизительно решить нормальные уравнения, i.e.,
несмотря на то, что нормальные уравнения явным образом не формируются.
Метод доверительной области подпространства используется, чтобы определить поисковое направление. Однако вместо того, чтобы ограничить шаг (возможно) одним отражательным шагом, как в нелинейном случае минимизации, кусочный отражающий поиск линии проводится в каждой итерации, как в квадратичном случае. См. [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 явным образом. Для примера смотрите функцию умножения якобиана с Линейным методом наименьших квадратов.
Задача наименьших квадратов минимизирует функциональный f (x), который является суммой квадратов.
| (7) |
Проблемы этого типа происходят в большом количестве практических применений, особенно те, которые включают подходящие функции модели к данным, такие как нелинейная оценка параметра. Этот проблемный тип также появляется в системах управления, где цель для выхода y (x,t), чтобы следовать за непрерывной траекторией модели φ (t) для векторного x и скалярного t. Эта проблема может быть описана как
| (8) |
где y (x,t) и φ (t) является скалярными функциями.
Дискретизируйте интеграл, чтобы получить приближение
| (9) |
где ti равномерно расположен с интервалами. В этой проблеме векторный F (x)
В этом типе проблемы невязка ∥F (x) ∥, вероятно, будет мала в оптимуме, потому что общая практика должна установить реалистично достижимые целевые траектории. Несмотря на то, что можно минимизировать функцию в уравнении 7 с помощью общего метода безусловной минимизации, как описано в Основах Оптимизации без ограничений, определенные характеристики проблемы могут часто использоваться, чтобы повысить итеративную эффективность процедуры решения. Градиент и матрица Гессиана уравнения 7 имеют специальную структуру.
Обозначая m-by-n якобиевская матрица F (x) как J (x), вектор градиента из f (x) как G (x), матрица Гессиана f (x) как H (x) и матрица Гессиана каждого Fi (x) как Di (x),
| (10) |
где
Свойство матричного Q (x) состоит в том, что, когда невязка ∥F (x) ∥ стремится по направлению к нулю, когда xk приближается к решению, затем Q (x) также стремится по направлению к нулю. Так, когда ∥F (x) ∥ мал в решении, эффективный метод состоит в том, чтобы использовать направление Ньютона Гаусса в качестве базиса для процедуры оптимизации.
В каждой главной итерации k метод Ньютона Гаусса получает поисковое направление dk, который является решением проблемы линейного метода наименьших квадратов
| (11) |
Направление, выведенное из этого метода, эквивалентно направлению Ньютона когда термины Q (x) = 0. Алгоритм может использовать поисковое направление dk в качестве части стратегии поиска линии гарантировать, что функциональный f (x) уменьшается в каждой итерации.
Метод Ньютона Гаусса часто сталкивается с проблемами, когда термин второго порядка Q (x) ненезначителен. Метод Levenberg-Marquardt преодолевает эту проблему.
Метод Levenberg-Marquardt (см. [25] и [27]) использует поисковое направление, которое является решением линейной системы уравнений
| (12) |
или, опционально, уравнений
| (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 на функции Розенброка
Для большего количества полного описания этого рисунка, включая скрипты, которые генерируют итеративные точки, смотрите Банановую Минимизацию Функции.
Когда проблема содержит связанные ограничения, lsqcurvefit и lsqnonlin измените итерации Levenberg-Marquardt. Если предложенная итеративная точка, x находится за пределами границ, алгоритм, проектирует шаг на самую близкую допустимую точку. Другими словами, с P, заданным как оператор projection, что проекты неосуществимые точки на выполнимую область, алгоритм изменяет предложенную точку x к P (x). По определению оператор проекции P работает с каждым xi компонента независимо согласно
или, эквивалентно,
Алгоритм изменяет останавливающийся критерий меры оптимальности первого порядка. Позвольте x быть предложенной итеративной точкой. В неограниченном случае останавливающийся критерий
| (14) |
где tol является значением допуска оптимальности, которое является 1e-4*FunctionTolerance. В ограниченном случае останавливающийся критерий
| (15) |
Чтобы изучить этот критерий, сначала обратите внимание что, если x находится во внутренней части выполнимой области, то оператор P не оказывает влияния. Так, останавливающийся критерий становится
который совпадает с исходным неограниченным критерием остановки, . Если граничное ограничение активно, означая, что x – ∇f (x) не выполним, то в точке, где алгоритм должен остановиться, градиент в точке на контуре перпендикулярен контуру. Поэтому точка x равна P (x – ∇f (x)), проекция шага наискорейшего спуска, как показано в следующем рисунке.
Levenberg-Marquardt останавливающееся условие
quadprog | lsqlin | lsqcurvefit | lsqnonlin | lsqnonneg
