Учитывая множество n нелинейных функций Fi (x), где n - число компонентов в векторе x, целью решения уравнения является поиск вектора x, который делает все Fi ( x) = 0.
fsolve пытается решить систему уравнений путем минимизации суммы квадратов составляющих. Если сумма квадратов равна нулю, система уравнений решается. fsolve имеет три алгоритма:
Доверительный регион
Траст-регион-доглег
Левенберг-Марквардт
Все алгоритмы масштабны; см. Крупномасштабные и среднемасштабные алгоритмы.
fzero функция решает одно одномерное уравнение.
mldivide функция решает систему линейных уравнений.
Многие методы, используемые в решателях Optimization Toolbox™, основаны на областях доверия, простой, но мощной концепции оптимизации.
Чтобы понять подход доверительной области к оптимизации, рассмотрим задачу неограниченной минимизации, минимизируйте f (x), где функция принимает векторные аргументы и возвращает скаляры. Предположим, что текущей точкой является x в n-пространстве, и вы хотите улучшить, переместившись в точку с меньшим значением функции. Для этого алгоритм аппроксимирует f более простой функцией q, которая разумно отражает поведение функции f в окрестности N вокруг точки x. Эта окрестность является областью доверия. Решатель вычисляет пробный шаг s путем минимизации (или приблизительно минимизации) по N. Подпроблема области доверия
}.
Решатель обновляет текущую точку до x + s, если f ( x + s ) < f (x); в противном случае текущая точка остается неизменной, и решатель сжимает N (область доверия) и повторяет вычисление пробного шага.
Ключевые вопросы при определении конкретного подхода области доверия к минимизации f (x) заключаются в том, как выбрать и вычислить аппроксимацию q (определенную в текущей точке x), как выбрать и изменить область доверия N и как точно решить подпроблему области доверия.
В стандартном способе доверительной области ([48]) квадратичная аппроксимация q определяется первыми двумя слагаемыми аппроксимации Тейлора до F при x. Окрестность N обычно имеет сферическую или эллипсоидальную форму. Математически подпроблема области доверия обычно указывается
| }, | (1) |
где g - градиент f в текущей точке x, H - гессеновская матрица (симметричная матрица вторых производных), D - диагональная масштабная матрица, Δ - положительный скаляр, а ∥. ∥ - 2-норма. Для решения уравнения 1 алгоритм (см. [48]) может вычислить все собственные значения H и затем применить процесс Ньютона к светскому уравнению.
Такой алгоритм обеспечивает точное решение уравнения 1. Однако это требует времени, пропорционального нескольким факторизациям Н. Следовательно, проблемы области доверия требуют другого подхода. Несколько аппроксимационных и эвристических стратегий, основанных на уравнении 1, были предложены в литературе ([42] и [50]). Решатели Optimization Toolbox используют подход аппроксимации, который ограничивает подпроблему области доверия двумерным подпространством S ([39] и [42]). После вычисления решателем подпространства S работа по решению уравнения 1 тривиальна, поскольку в подпространстве задача является только двумерной. Доминирующая работа теперь переходит к определению подпространства.
Решатель определяет двумерное подпространство S с помощью предварительно обработанного метода сопряженного градиента (описанного в следующем разделе). Решатель определяет S как линейное пространство, охватываемое s1 и s2, где s1 находится в направлении градиента g, а s2 является либо приближенным направлением Ньютона, то есть решением
или направление отрицательной кривизны,
Философия, лежащая в основе этого выбора S, состоит в том, чтобы форсировать глобальную сходимость (через самое крутое направление спуска или отрицательное направление кривизны) и достичь быстрой локальной сходимости (через шаг Ньютона, когда она существует).
Процесс неограниченной минимизации с использованием подхода «доверительный регион» теперь легко определить:
Сформулируйте двухмерную подпроблему области доверия.
Решите уравнение 1, чтобы определить пробный этап s.
Если f (x + s) < f (x), то x = x + s.
Отрегулируйте Δ.
Решатель повторяет эти четыре шага до сходимости, настраивая измерение Δ области доверия в соответствии со стандартными правилами. В частности, решатель уменьшает размер области доверия, если он не принимает пробный этап, когда f (x + s) ≥ f (x). Для обсуждения этого аспекта см. [46] и [49].
Решатели Optimization Toolbox рассматривают важные случаи f со специализированными функциями: нелинейными наименьшими квадратами, квадратичными функциями и линейными наименьшими квадратами. Однако лежащие в основе алгоритмические идеи те же, что и для общего случая.
Популярным способом решения больших, симметричных, положительных определённых систем линейных уравнений Hp = -g является метод Предварительно кондиционированных сопряжённых градиентов (PCG). Этот итеративный подход требует возможности вычисления матрично-векторных произведений формы H· v, где v - произвольный вектор. Симметричная положительная определенная матрица М является предварительным условием для Н. То есть М = C2, где C-1HC-1 является хорошо кондиционированной матрицей или матрицей с кластеризованными собственными значениями .
В контексте минимизации можно предположить, что матрица Гессена H симметрична. Однако H гарантированно является положительным определенным только в районе сильного минимизатора. Алгоритм PCG выходит, когда он сталкивается с направлением отрицательной (или нулевой) кривизны, то есть dTHd ≤ 0. Направление р выхода PCG является либо направлением отрицательной кривизны, либо приближенным решением для системы Ньютона Hp = -g. В любом случае p помогает определить двумерное подпространство, используемое в подходе «доверительная область», обсуждаемом в документе «Методы доверительной области для нелинейной минимизации».
Другой подход заключается в решении линейной системы уравнений для нахождения направления поиска. Метод Ньютона определяет решение для направления поиска dk так, что
J (xk) dk = -F (xk)
xk + 1 = xk + dk,
где J (xk) - n-by-n якобиана
(xk) T].
Метод Ньютона может быть проблематичным. J (xk) может быть единственным, и в этом случае шаг Ньютона dk даже не определен. Кроме того, точный шаг Ньютона dk может быть дорогостоящим для вычисления. Кроме того, метод Ньютона может не сходиться, если начальная точка далека от решения.
Использование методов доверительной области (представленных в Trust-Region Methods for Nonlinear Minimization) обрабатывает случай, когда J (xk) является единственным и повышает надежность, когда начальная точка далека от решения. Чтобы использовать стратегию доверительного региона, вам нужна функция качества, чтобы решить, является ли xk + 1 лучше или хуже xk. Возможный выбор -
(xk + d).
Но минимум f (d) не обязательно является корнем F (x).
Шаг Ньютона dk является корнем
M (xk + d) = F (xk) + J (xk) d,
таким образом, это также минимум m (d), где
| xk) + 12dTJ (xk) TJ (xk) d. | (2) |
m (d) является лучшим выбором функции оценки заслуг, чем f (d), поэтому подпроблема области доверия является
| xk) TJ (xk) d], | (3) |
такой, что ∥D·d∥ ≤ Δ. Эту подпроблему можно эффективно решить с помощью стратегии dogleg.
Обзор методов доверительного региона см. в разделах Conn [4] и Nocedal [31].
Ключевой особенностью алгоритма trust-region-dogleg является использование процедуры доглега Пауэлла для вычисления шага d, который минимизирует уравнение 3. Подробное описание см. в разделе Пауэлл [34].
Алгоритм строит шаг d из выпуклой комбинации шага Коши (шаг вдоль самого крутого направления спуска) и шага Гаусса-Ньютона для f (x). Шаг Коши рассчитывается как
dC = -αJ (xk) TF (xk),
где α минимизирует уравнение 2.
Шаг Гаусса - Ньютона вычисляется решением
J (xk)· dGN = -F (xk),
использование MATLAB
®mldivide (матричное левое деление) оператор.
Алгоритм выбирает шаг d так, чтобы
d = dC + λ (dGN - dC),
где λ - наибольшее значение в интервале [0,1], такое, что ∥d∥ ≤ Δ. Если Jk является (почти) единственным, d является только направлением Коши.
Алгоритм trust-region-dogleg эффективен, поскольку требует только одного линейного решения на одну итерацию (для вычисления шага Гаусса-Ньютона). Кроме того, алгоритм может быть более надежным, чем использование метода Гаусса-Ньютона с поиском строк.
Алгоритм Левенберга - Марквардта ([25] и [27]) использует направление поиска, которое является решением линейного множества уравнений
| xk) TF (xk), | (4) |
или, необязательно, уравнений
| J (xk) TF (xk), | (5) |
где скаляр λ k управляет как величиной, так и направлением dk. Установите fsolve выбор ScaleProblem кому 'none' чтобы использовать уравнение 4, или задайте для этой опции значение 'jacobian' для использования уравнения 5.
Когда λ k равно нулю, направление dk является методом Гаусса-Ньютона. Поскольку λ k стремится к бесконечности, dk стремится к самому крутому направлению спуска, а величина стремится к нулю. Подразумевается, что для некоторых достаточно больших λ k верен термин F (xk + dk) < F (xk). Поэтому алгоритм может управлять термином λ k для обеспечения спуска несмотря на члены второго порядка, которые ограничивают эффективность метода Гаусса - Ньютона. Алгоритм Левенберга - Марквардта, таким образом, использует направление поиска, являющееся пересечением между направлением Гаусса - Ньютона и наиболее крутым направлением спуска. Дополнительные сведения см. в разделе Метод Левенберга-Марквардта в документации по наименьшим квадратам.
fzero пытается найти корень скалярной функции f скалярной переменной x.
fzero ищет интервал вокруг начальной точки, так что f (x) меняет знак. Если указать начальный интервал вместо начальной точки ,fzero проверяет наличие различных знаков f (x) в конечных точках интервала. Начальный интервал должен быть конечным; он не может содержать ±Inf.
fzero использует комбинацию биссекции интервала, линейной интерполяции и обратной квадратичной интерполяции для определения местоположения корня f (x). Посмотритеfzero для получения дополнительной информации.
\ алгоритм описан в разделе арифметических операторов MATLAB для mldivide.