lsqnonlin

Страница в процессе разработки.

Решатель задач нелинейных наименьших квадратов.

Библиотека

EngeeOptimization

Описание

Функция lsqnonlin решает задачу нелинейных наименьших квадратов вида:

где

Функция вызывается при решении задачи оптимизации optimize или создании настроек оптимизации OptimizeOptions.

Настройки решателя

Все алгоритмы

Algorithm

Выберите один из алгоритмов: "trust-region-reflective" или "levenberg-marquardt" (по умолчанию).

Аргумент Algorithm определяет предпочтительный алгоритм для решения задачи.

Diagnostics

Отображать диагностическую информацию о функции, подлежащей минимизации или решению. Доступные варианты: false (по умолчанию) или true.

DiffMaxChange

Максимальное изменение переменных для конечно-разностных градиентов (положительный скаляр). Значение по умолчанию — nothing.

DiffMinChange

Минимальное изменение переменных для конечно-разностных градиентов (положительный скаляр). Значение по умолчанию — nothing.

Display

Уровень вывода:

"off" или "none" — вывод отсутствует.
"iter" (по умолчанию) — вывод данных на каждой итерации и стандартное сообщение о завершении.
"iter-detailed" — вывод данных на каждой итерации и техническое сообщение о завершении.
"final" — вывод только итоговых данных и стандартное сообщение о завершении.
"final-detailed" — вывод только итоговых данных и техническое сообщение о завершении.

FiniteDifferenceStepSize

Скалярный или векторный коэффициент размера шага для метода конечных разностей. Если аргумент FiniteDifferenceStepSize задан в виде вектора v, то приращения delta для односторонних конечных разностей вычисляются по формуле:

delta = v.*sign′(x).*max(abs(x),TypicalX);

где sign′(x) = sign(x), за исключением случая sign′(0) = 1. Для центральных конечных разностей:

delta = v.*max(abs(x),TypicalX);

Скалярное значение FiniteDifferenceStepSize преобразуется в вектор. Значение по умолчанию — sqrt(eps) для односторонних конечных разностей и eps^(1/3) для центральных конечных разностей.

FiniteDifferenceType

Конечные разности, используемые для оценки градиентов, могут быть "forward" (по умолчанию) или "central". Вычисление "central" разностей требует вдвое большего числа обращений к функции, но обеспечивает более высокую точность.

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

FunctionTolerance

Допуск по значению функции для завершения работы алгоритма; неотрицательный скаляр. Значение по умолчанию — 0.001.

FunValCheck

Проверка корректности значений функции. При выборе true выводится сообщение об ошибке, если функция возвращает комплексное значение, Inf или NaN. По умолчанию используется режим false, при котором ошибка не выводится.

MaxFunctionEvaluations

Максимально допустимое число вычислений функции, заданное как неотрицательное целое число. Значение по умолчанию составляет 100 * numberOfVariables для алгоритма "trust-region-reflective", 200 * numberOfVariables для алгоритма "levenberg-marquardt".

MaxIterations

Максимально допустимое число итераций, заданное как неотрицательное целое число. Значение по умолчанию составляет 100 для алгоритмов "trust-region-reflective" и "levenberg-marquardt".

OptimalityTolerance

Допуск для условия остановки по критерию оптимальности первого порядка, заданный как неотрицательный скаляр. Значение по умолчанию — 0.001.

Алгоритм "levenberg-marquardt" использует допуск оптимальности (критерий остановки), равный 1e−4, умноженный на аргумент FunctionTolerance, и не использует аргумент OptimalityTolerance.

OutputFcn

Укажите одну или несколько пользовательских функций, которые функция оптимизации будет вызывать на каждой итерации. Передайте указатель на функцию или массив с указателями на функции. По умолчанию — отсутствие функций (nothing).

PlotFcn

Построение различных графиков, отражающих ход выполнения алгоритма; можно выбрать готовые графики или создать собственные. В качестве аргумента передается имя, указатель на функцию или массив, содержащий имена или указатели на функции. Для пользовательских функций построения графиков следует передавать указатели на функции. По умолчанию построение графиков отключено (значение nothing).

Пользовательские функции построения графиков используют тот же синтаксис, что и функции вывода.

SpecifyObjectiveGradient

Если установлено значение false, решатель аппроксимирует якобиан с помощью метода конечных разностей. Если установлено значение true (по умолчанию), решатель использует якобиан, заданный пользователем (в функции ), или информацию о якобиане (при использовании JacobMult) для целевой функции.

StepTolerance

Допуск по переменной , заданный как неотрицательный скаляр, для завершения работы алгоритма. Значение по умолчанию составляет 0.001 для алгоритмов "trust-region-reflective" и "levenberg-marquardt".

TypicalX

Типичные значения . Количество элементов в TypicalX равно количеству элементов в (начальной точке). Значение по умолчанию — ones(numberofvariables, 1). Решатель использует TypicalX для масштабирования конечных разностей при оценке градиента.

UseParallel

Опция использования параллельных вычислений для оценки градиентов, заданная одним из следующих значений:

true — оценка градиентов выполняется параллельно. Если пул параллельных процессов не открыт, решатель запускает его, используя профиль кластера, заданный по умолчанию.
false (значение по умолчанию) — оценка градиентов выполняется последовательно.

Алгоритм "trust-region-reflective"

JacobianMultiplyFcn

Функция умножения на матрицу Якоби, заданная как указатель на функцию. Для крупномасштабных задач со специальной структурой эта функция вычисляет произведение J*Y, J'*Y или J'*(J*Y), не формируя при этом саму матрицу J в явном виде. Для lsqnonlin функция имеет вид:

W = jmfun(Jinfo, Y, flag)

где Jinfo содержит данные, необходимые для вычисления J*Y (или J'*Y или J'*(J*Y)).

Функция lsqnonlin передает данные Jinfo, Y, flag, а ваша функция jmfun вычисляет результат согласно приведенным ниже правилам. Y — это матрица, размер которой зависит от значения flag. Пусть — количество компонент целевой функции fun, а — количество переменных задачи в векторе x. Матрица Якоби имеет размер на (как описано в ). Функция jmfun возвращает один из следующих результатов:

Если flag == 0, то W = J' * (J * Y) и матрица Y имеет размер на .
Если flag > 0, то W = J * Y и матрица Y имеет размер на .
Если flag < 0, то W = J' * Y и матрица Y имеет размер на .

Во всех случаях матрица J не формируется явно. Решатель использует Jinfo для выполнения операций умножения.

Для того чтобы решатель передавал Jinfo из функции fun в функцию jmfun, аргумент SpecifyObjectiveGradient должен быть установлен в значение true.

JacobPattern

Шаблон разреженности якобиана для метода конечных разностей. Установите JacobPattern(i,j) = 1, если fun(i) зависит от x(j); в противном случае установите JacobPattern(i,j) = 0. Иными словами, JacobPattern(i,j) = 1, если частная производная ∂fun(i)/∂x(j) может быть отлична от нуля.

Используйте JacobPattern в тех случаях, когда вычисление матрицы Якоби J внутри функции fun затруднительно, но при этом можно определить (например, путем анализа), зависит ли fun(i) от x(j). При наличии JacobPattern решатель может аппроксимировать J с помощью метода разреженных конечных разностей.

Если структура матрицы неизвестна, не задавайте JacobPattern. По умолчанию используется поведение, соответствующее плотной матрице, состоящей из единиц; в этом случае на каждой итерации решатель вычисляет полную конечно-разностную аппроксимацию. Для задач большой размерности это может быть ресурсоемким процессом, поэтому обычно предпочтительнее определить структуру разреженности.

SubproblemAlgorithm

Определяет способ вычисления шага итерации. При использовании варианта по умолчанию ("factorization") шаг вычисляется медленнее, но точнее, чем в методе "cg".

Алгоритм "levenberg-marquardt"

InitDamping

Начальное значение параметра Левенберга — Марквардта — положительный скаляр. Значение по умолчанию — 0.01.

ScaleProblem

Значение "jacobian" иногда позволяет улучшить сходимость плохо масштабированной задачи; по умолчанию используется значение "none".

Информация, выводимая решателем

# resnorm — квадрат нормы невязки
неотрицательное вещественное число

Details

Квадрат нормы невязки, возвращаемый как неотрицательное вещественное число. resnorm — это квадрат второй нормы невязки в точке : .

# residual — значение целевой функции в точке решения
массив

Details

Значение целевой функции в точке решения, возвращаемое как массив. В общем случае: .

# exitflag — причина остановки решателя
целое число

Details

Причина остановки решателя, возвращаемая как целое число.

Значение Причина

Значение	Причина
`1`	Функция сошлась к решению .
`2`	Изменение меньше заданного допуска, или якобиан в точке не определен.
`3`	Изменение невязки меньше заданного допуска.
`4`	Относительная величина направления поиска меньше допуска на шаг.
`0`	Количество итераций превысило значение `MaxIterations`, либо количество вычислений функции превысило значение `MaxFunctionEvaluations`.
`−1`	Функция построения графика или функция вывода остановила работу решателя.
`−2`	Допустимая точка не найдена. Границы и противоречивы, либо решатель остановился в недопустимой точке.

1

Функция сошлась к решению .

2

Изменение меньше заданного допуска, или якобиан в точке не определен.

3

Изменение невязки меньше заданного допуска.

4

Относительная величина направления поиска меньше допуска на шаг.

0

Количество итераций превысило значение MaxIterations, либо количество вычислений функции превысило значение MaxFunctionEvaluations.

−1

Функция построения графика или функция вывода остановила работу решателя.

−2

Допустимая точка не найдена. Границы и противоречивы, либо решатель остановился в недопустимой точке.

# output — информация о процессе оптимизации
структура

Details

Информация о процессе оптимизации, возвращаемая как структура с полями:

Название поля Содержимое

Название поля	Содержимое
`firstorderopt`	Мера оптимальности первого порядка.
`iterations`	Количество выполненных итераций.
`funcCount`	Количество вычислений функции.
`cgiterations`	Общее количество итераций метода сопряженных градиентов (PCG) (для алгоритма `"trust-region-reflective"`).
`stepsize`	Конечное смещение в `x`.
`algorithm`	Используемый алгоритм оптимизации.
`message`	Сообщение о выходе.

firstorderopt

Мера оптимальности первого порядка.

iterations

Количество выполненных итераций.

funcCount

Количество вычислений функции.

cgiterations

Общее количество итераций метода сопряженных градиентов (PCG) (для алгоритма "trust-region-reflective").

stepsize

Конечное смещение в x.

algorithm

Используемый алгоритм оптимизации.

message

Сообщение о выходе.

# lambda — множители Лагранжа в точке решения
структура

Details

Множители Лагранжа в точке решения, возвращаемые как структура с полями:

Название поля Содержимое

Название поля	Содержимое
`lower`	Нижние границы, соответствующие .
`upper`	Верхние границы, соответствующие .

lower

Нижние границы, соответствующие .

upper

Верхние границы, соответствующие .

# jacobian — якобиан в точке решения
вещественная матрица

Details

Якобиан в точке решения, возвращаемый как вещественная матрица. Элемент jacobian(i,j) представляет собой частную производную функции по переменной в точке решения .

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

Дополнительно

Локальный и глобальный минимум

Details

Локальный минимум функции — это точка, в которой значение функции меньше, чем в соседних точках, но, возможно, больше, чем в какой-либо удаленной точке.

Глобальный минимум — это точка, в которой значение функции меньше, чем во всех остальных допустимых точках.

lsqnonlin 1 ru

Алгоритмы решателей пытаются найти локальный минимум. Результатом может стать глобальный минимум.

Мера оптимальности первого порядка

Details

Для задач безусловной оптимизации мерой оптимальности первого порядка является максимальное абсолютное значение компонент вектора градиента (также называемое бесконечной нормой градиента). В точке минимума эта величина должна быть равна нулю.

Для задач с ограничениями мерой оптимальности первого порядка является максимум по индексу величины . Здесь — -я компонента градиента, — текущая точка, а

Если находится на границе, то равно нулю. Если не находится на границе, то в точке минимума градиент должен быть равен нулю. Следовательно, в точке минимума мера оптимальности первого порядка должна быть равна нулю.

Допуски

Details

Как правило, допуск — это пороговое значение, при превышении которого итерационный процесс решателя останавливается.

OptimalityTolerance — определяет допустимое отклонение для меры оптимальности первого порядка. Итерационный процесс завершается, когда значение меры оптимальности первого порядка становится меньше величины OptimalityTolerance.
FunctionTolerance — определяет величину последнего изменения значения целевой функции.

lsqnonlin 2 ru

Величина градиента

Details

Вектор градиента представляет собой градиент суммы квадратов. Для задач безусловной оптимизации величиной градиента считается максимальное абсолютное значение компонентов вектора градиента (также называемое бесконечной нормой градиента). В точке минимума эта величина должна быть равна нулю.

Для задач с ограничениями величина градиента определяется как максимум по индексу величины . Здесь — -я компонента градиента, — текущая точка, а

Если находится на границе, то равно нулю. Если не находится на границе, то в точке минимума градиент должен быть равен нулю. Следовательно, в точке минимума величина градиента должна быть равна нулю.

Размер текущего шага

Details

Размер текущего шага — это величина изменения положения текущей точки на последней итерации.

Локальная сингулярность

Details

Параметр регуляризации Левенберга — Марквардта связан с величиной, обратной радиусу доверительного региона. Он принимает большие значения, когда сумма квадратов значений функции существенно отличается от квадратичной модели.

Когда вычисление якобиана невозможно

Details

Алгоритмы оценивают якобиан целевой вектор-функции методом конечных разностей. Если в процессе вычисления конечной разности расчетная точка вышла за пределы области, где целевая функция определена корректно, то это может привести к получению Inf, NaN или комплексного числа.

Алгоритмы

Методы Левенберга — Марквардта и доверительного региона с отражением основаны на алгоритмах нелинейного метода наименьших квадратов.

Алгоритм доверительного региона с отражением по умолчанию представляет собой метод доверительного региона в подпространстве и основан на методе Ньютона с внутренним отражением, описанном в [1] и [2]. Каждая итерация включает приближенное решение большой линейной системы с использованием метода предварительно обусловленных сопряженных градиентов (PCG).
Метод Левенберга — Марквардта описан в [4], [5] и [6].

Литература

Coleman, T.F. and Y. Li. An Interior, Trust Region Approach for Nonlinear Minimization Subject to Bounds. SIAM Journal on Optimization, Vol. 6, 1996, pp. 418–445.
Coleman, T.F. and Y. Li. On the Convergence of Reflective Newton Methods for Large-Scale Nonlinear Minimization Subject to Bounds. Mathematical Programming, Vol. 67, Number 2, 1994, pp. 189–224.
Dennis, J. E. Jr. Nonlinear Least-Squares. State of the Art in Numerical Analysis, ed. D. Jacobs, Academic Press, pp. 269–312.
Levenberg, K. A Method for the Solution of Certain Problems in Least-Squares. Quarterly Applied Mathematics 2, 1944, pp. 164–168.
Marquardt, D. An Algorithm for Least-squares Estimation of Nonlinear Parameters. SIAM Journal Applied Mathematics, Vol. 11, 1963, pp. 431–441.
Moré, J. J. The Levenberg-Marquardt Algorithm: Implementation and Theory. Numerical Analysis, ed. G. A. Watson, Lecture Notes in Mathematics 630, Springer Verlag, 1977, pp. 105–116.
Moré, J. J., B. S. Garbow, and K. E. Hillstrom. User Guide for MINPACK 1. Argonne National Laboratory, Rept. ANL–80–74, 1980.
Powell, M. J. D. A Fortran Subroutine for Solving Systems of Nonlinear Algebraic Equations. Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, ed., Ch.7, 1970.