MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем

Математика\Optimization Toolbox

Список функций Optimization Toolbox

  В оглавление \ К следующему разделу \ К предыдущему разделу

LSQNONLIN

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

где L константа.

Синтаксис:

x = lsqnonlin(fun,x0)
x = lsqnonlin(fun,x0,lb,ub)
x = lsqnonlin(fun,x0,lb,ub,options)
x = lsqnonlin(fun,x0,eb,ub,options,P1,P2, ... )
[x,resnorm] = lsqnonlin(...)
[x,resnorm,residual] = lsqnonlin(...)
[x,resnorm,residual,exitflag] = lsqnonlin(...)
[x,resnorm,residual,exitflag,output] = lsqnonlin(...)
[x,resnorm,residual,exitflag,output,lambda] = lsqnonlin(...)
[x,resnorm,residual,exitflag,output,lambda,jacobian] = lsqnonlin(...)

Описание:

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

До расчета значений f(x) (“суммы квадратов”), lsqnonlin требует задаваемой пользователем функции для расчета векторозначной функции.

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

где х есть вектор и F(x) есть функция, которая возвращает значение вектора

  • x = lsqnonlin(fun,x0) начинает с точки х0 и находит минимум суммы квадратов описанной в fun функции. fun должна возвращать вектор значений, а не сумму квадратов значений. (В данном алгоритме fun(x) неявно суммируется и возводится в квадрат.)
  • x = lsqnonlin(fun,x0,lb,ub) определяет набор нижних и верхних границ для проектируемых переменных х, так что решение всегда находится в диапазоне lb <= x <= ub.
  • x = lsqnonlin(fun,x0,lb,ub,options) проводит оптимизацию с определенными в структурной опции параметрами оптимизации. Если ограничений нет, то передает пустую матрицу в lb и ub.
  • x = lsqnonlin(fun,x0,lb,ub,options,P1,P2,...) передает зависящие от типа задачи параметры P1, P2 и т.д. непосредственно в функцию fun. Передает пустые матрицы заменители в опции, которые в качестве используемых по умолчанию.
  • [x,resnorm] = lsqnonlin(...) возвращает значение квадрата нормы невязки от х. sum(fun(x).^2).
  • [x,resnorm,residual] = lsqnonlin(...) возвращает значение невязки fun(x), как решение от х.
  • [x,resnorm,residual,exitflag] = lsqnonlin(...) возвращает значение exitflag, которое содержит описание выходных условий.
  • [x,resnorm,residual,exitflag,output] = lsqnonlin(...) возвращает структурный выход с информацией об оптимизации.
  • [x,resnorm,residual,exitflag,output,lambda] = lsqnonlin(...) возвращает структурную lambda с полями, содержащими множители Лагранжа в виде решения от х.
  • [x,resnorm,residual,exitflag,output,lambda,jacobian] = lsqnonlin(...) Возвращает Якобиан от fun как решение от х.

Аргументы:

Входные аргументы.

Таблица 4-1, Входные аргументы, содержит общее описание аргументов, передаваемых в lsqnonlin. Данные подраздел “Аргументы” приводит функционально-специфические детали для fun и options:

fun

Подлежащая минимизации сумма квадратов.

fun есть такая функция, которая принимает вектор х и возвращает вектор F, т.е. целевую функция от х. Функция fun может задаваться с помощью описателя функций

x = lsqnonlin(@myfun,x0)

где myfun есть такая функция MATLAB, что

function F = myfun(x)
F = ... % Вычисление функции в точке х

fun так же может быть и внутренним объектом.

x = lsqnonlin(inline('sin(x.*x)'),x0);
Если к тому же может быть рассчитан Якобиан и установленная с помощью

options = optimset('Jacobian','on')
опция options.Jacobian равна 'on', то функция fun во втором выходном аргументе должна возвращать значение Якобиана J, как матрицы от х.

Отметим, что посредством проверки значения nargout данная функция может обойти расчет J в случае когда fun вызывается только с одним выходным аргументом (случай, когда для оптимизационного алгоритма необходимо только значение F, а не J).

function [F,J] = myfun(x)
F = ... % значения целевой функции от x
if nargout > 1 % два выходных аргумента
J = ... % Якобиан как функция от x
End

Если fun возвращает вектор (матрицу) из m компонентов и х имеет длину n, где n есть длина х0, то Якобиан J есть матрица m х n и J(i,j) будут частные производные от F(i) по x(j). (Отметим, что Якобиан J есть транспонирование градиента от F.)

options

Опции обеспечивают учет специфических деталей функции виде параметров options.

Выходные аргументы.

Таблица 4-2. “Выходные аргументы” содержат общее описание возвращаемых lsqnonlin аргументов. В этом разделе приводятся общие специфические детали для величин exitflag, lambda, и output:

exitflag

Описывает выходные условия

  • > 0 Описывает выходные условия

  • 0 Максимальное число оценки функции или итерации было превышено

  • < 0 Функция не сходится к некому решению.

lambda

Структура, которая содержит множители Лагранжа при решении по х (разделенном по типам условий). Поле структуры:

  • lower Нижние границы lb

  • upper Верхние границы ub

output

Структура, которая содержит информацию об оптимизации. Поле структуры:

  • iterations Число выполненных итераций
  • funcCount Число оценок функции
  • algorithm Используемый алгоритм
  • cgiterations Число PCG итераций (только для крупно-масштабного алгоритма)
  • stepsize Окончательно принятый размер шага (только для средне-масштабного алгоритма)
  • firstorderopt Измерение оптимальности первого порядка (только для крупно-масштабного алгоритма).

Для крупно-масштабных задач с краевыми ограничениями оптимальностью первого порядка будет бесконечная норма v.*g, где v определяется как Ограничения Бокса и g – градиент g = JTF (смотри Нелинейный Метод Наименьших Квадратов)

Примечание. Сумма квадратов должна быть выражена явным образом.

Взамен этого, Ваша функция должна возвращать вектор значений функции.

Смотри примеры ниже

Options

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

Мы начнем с описания опции LargeScale, поскольку она устанавливает преимущественное право какой алгоритм использовать. Это только преимущественное право, поскольку должны быть выполнены определенные условия для того, что бы можно было использовать крупно-масштабный алгоритм или средне-масштабный алгоритм. Для крупно-масштабного алгортма, поскольку система нелинейных уравнений не может быть недоопределенной, число уравнений (число возвращаемых fun элементов F) должно быть, по крайней мере, длины х. Более того, только крупно-масштабный алгоритм оперирует с граничными ограничениями

LargeScale

В случае установки 'on' используется, если это возможно, крупно-масштабный алгоритм. Для использования средне-масштабного алгоритма устанавливается 'off'.

Medium-Scale and Large-Scale Algorithms. Эти параметры используются как для средне-масштабного, так и крупно-масштабного алгоритмов:

Diagnostics

Проводится печать диагностической информации о минимизируемой функции.

Display

Уровень отображения. 'off' отображение не производится, 'iter' отображение проводится на каждой итерации, 'final' (принимается по умолчанию) отображение только конечной информации.

Jacobian

При установке 'on', fsolve использует заданный пользователем Якобиан (определенный в fun), или информацию об Якобиане (при использовании JacobMult) для целевой функции. При установке 'off', fsolve аппроксимирует Якобиан с помощью конечных разностей.

MaxFunEvals

Максимально число допустимых расчетов функции.

MaxIter

Максимально число допустимых итераций.

TolFun

Конечное допустимое отклонение по значению функции

TolX

Конечное допустимое отклонение по значению х.

Large-Scale Algorithm Only. Эти параметры используются только для крупно-масштабного алгоритма:

JacobMult

Указатель функции для функции множителей Якобиана. В случае крупно-масштабной задачи данная функция вычисляет произведение матриц Якобиана J*Y, J'*Y или J'*(J*Y) без действительного формирования J. Такая функция имеет форму

W = jmfun(Jinfo,Y,flag,p1,p2,...),
где Jinfo и дополнительные параметры p1,p2,... включают в себя используемые для расчета J*Y (или J'*Y или J'*(J*Y)) матрицы. Первый аргумент Jinfo должен быть таким же, что возвращаемый целевой функцией fun второй аргумент.

[F,Jinfo] = fun(x,p1,p2,...)
Параметры p1,p2,... есть дополнительные параметры, передаваемые в lsqnonlin (и в fun).

lsqnonlin (fun,...,options,p1,p2,...)
Y есть матрица с тем же самым числом строк, что и размерность данной задачи.

flag определяет какое произведение нужно вычислять.

If flag == 0 then W = J'*(J*Y).
If flag > 0 then W = J*Y.
If flag < 0 then W = J'*Y.

В каждом случае J явно не формируется. lsqnonlin

использует Jinfo для расчета предварительных данных.

Примечание 'Jacobian' должен быть установлен как 'on' для того, чтобы передать Jinfo из fun в jmfun.

В качестве примера смотри Нелинейную Оптимизацию с Компактной, но Структурированной Матрицей Гессе и Ограничениями Типа Равенств.

JacobPattern

Разреженные шаблоны Якобиана для конечного дифференцирования. В случае, если в fun неразумно вычислять матрицу Якобиана J, то lsqnonlin может аппроксимировать J через заданные разреженные конечные разности и структура J, т.е. расположения не нулей, обеспечиваемую как значения для JacobPattern. В наихудшем случае, когда эта структура неизвестна, можно установить JacobPattern, что бы плотная матрица и полные конечно-разностные аппроксимации вычислялись на каждой итерации (что принимается по умолчанию в случае неустановки JacobPattern). Это может быть чрезвычайно затратным для больших задач, поэтому обычно заслуживает внимания усилие по определению разреженной структуры.

MaxPCGIter

Максимальное число PCG (предварительно сопряженный градиент) итераций (Смотри ниже раздел Алгоритм).

PrecondBandWidth

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

TolPCG

Конечное допустимое число итераций PCG.

TypicalX

Типичные значения х.

Medium-Scale Algorithm Only. Эти параметры используются только для средне-масштабного алгоритма.

DerivativeCheck

Сравнение вводимых пользователем производных (Якобиана) с конечноразностными производными.

DiffMaxChange

Максимальное изменение в переменных для конечных-разностей.

DiffMinChange

Минимальное изменение в переменных для конечных-разностей.

LevenbergMarquardt

Выбор алгоритма Левенберга-Макуарда вместо Гаусса-Ньютона.

LineSearchType

Выбор алгоритма линейного поиска.

Примеры:

Найти х, которые минимизируют

начнем с точки x = [0.3, 0.4].

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

от до 10 (то есть, F должен иметь k компонентов).

Сперва запишем М-файл, который вычисляет к компонентов F

function F = myfun(x)
k = 1:10;
F = 2 + 2*k-exp(k*x(1))-exp(k*x(2));

Далее вызовем подпрограмму оптимизации

x0 = [0.3 0.4]                                     % Начальнон приближение
[x,resnorm] = lsqnonlin(@myfun,x0)    % Запускается оптимизатор

После 24 расчетов функции в данном примере решение будет.

x =
    0.2578    0.2578
resnorm                                               % невязка или сумма квадратов
resnorm =
    124.3622

Алгоритм:

Крупно-масштабная оптимизация. По умолчанию lsqnonlin выберет крупно-масштабный алгоритм. Данный алгоритм является реализацией метода доверительных подпространств и основан на методе внутренних отражений Ньютона, описанного в [1], [2]. Каждая итерация включает в себя приближенное решение крупной линейной системы с помощью метода предварительно сопряженных градиентов(PCG). Смотри Метод Доверительной Области для Нелинейной оптимизации и Предварительно Сопряженных Градиентов в разделе “Крупно-Масштабные Алгоритмы”.

Средне-масштабная оптимизация. lsqnonlin при установке options.LargeScale как 'off' использует метод Левенберга-Макуарда [4], [5], [6] с линейным поиском. В качестве альтернативы может быть выбран метод Гаусса-Ньютона [3] с линейным поиском. Выбор алгоритма проводится при помощи установки опции options.LevenbergMarquardt. Установка options.LevenbergMarquardt как 'off' (и опции options.LargeScale как 'off') выбирается метод Гаусса-Ньютона, который обычно работает быстрее в случае небольшой невязки

.

Принимаемый по умолчанию алгоритм линейного поиска, т.е. опция options.LineSearchType установлена как 'quadcubic', обеспечивается методом смешанной квадратичной и кубической полиноминальной интерполяции и экстраполяции. Защищенный кубической полиномиальный метод может быть выбран установкой опции LineSearchType как 'cubicpoly'. В общем, данный метод требует меньшего расчета функций, но большего обращения к расчету градиента. Таким образом, если градиенты приведены и могут быть вычислены без больших затрат, то метод с кубическим полиномиальным линейным поиском является предпочтительным. Используемые алгоритмы полностью описаны в разделе Стандартные Алгоритмы.

Диагностика:

Крупно-масштабная оптимизация. Коды крупно-масштабного метода не допускают равенства верхней и нижней границ. Например, если lb(2) == ub(2), то lsqlin дает ошибку

Равные верхние и нижние границы не допустимы в данном крупно-масштабном методе.

(lsqcurvefit не управляет ограничениями типа равенств, имеется иная возможность формулировки границ в виднее равенств. В случае наличия ограничений типа равенств в качестве альтернативной формулировки используются fmincon, fminimax или fgoalattain, где ограничения типа равенств могут быть включены.)

Ограничения:

Минимизируемая функция должна быть непрерывной. lsqnonlin может давать только локальные решения.

lsqnonlin оперирует только с реальными переменными. Если х имеет комплексные значения, то эти переменные должны быть разделены на мнимую и реальные части.

Крупно-масштабная оптимизация. Крупно-масштабный метод не разрешает недоопределенные системы, он требует, что бы число уравнений, т.е. число строк в F было, по крайней мере, больше, чем число переменных. Взамен этого в недоопределенном случае используется средне-масштабный алгоритм. (Если граничные ограничения все же имеются, то выдается предупреждение и задача решается с игнорированием границ). Относительно большей информации о постановке задачи, области применения и задания исходных данных смотри таблицу 1-4, Область Определения и Требования к Крупно-Масштабным Задачам.

В части предварительно сопряженных градиентов для формирования JTJ крупно-масштабного метода (где J есть матрица Якоби) используется предварительный расчет перед подготовкой данных, поэтому, строки матрицы J с большим числом ненулевых значений могут привести к особенно плотным произведениям JTJ, что, в свою очередь, может привести к усложнению расчетов для больших задач.

Если компоненты х не имеют верхних (или нижних) границ, то lsqnonlin выберет, что соответствующие компоненты ub (или lb) были установлены в бесконечность (или –бесконечность для нижних границ) в противоположность произвольному, но очень большому положительному (или отрицательному для нижних границ) числу.

В настоящее время, если в fun аналитически задан градиент, то для сравнения аналитического градиента с его конечно-разностным значением в крупно-масштабном методе нельзя использовать параметр опции DerivativeCheck. Вместо этого, для контроля производной следует использовать средне-масштабный метод с установкой опционного параметра MaxIter как 0 итераций. Затем запустить задачу с крупно-масштабным методом.

Средне-масштабная оптимизация. Средне-масштабный алгоритм не оперирует с ограничениями в виде границ.

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

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

@ (function_handle), lsqcurvefit, lsqlin, optimset

Литература:

  1. Coleman, T.F. and Y. Li, "An Interior, Trust Region Approach for Nonlinear Minimization Subject to Bounds," SIAM Journal on Optimization, Vol. 6, pp. 418-445, 1996.
  2. 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, pp. 189-224, 1994.
  3. Dennis, J.E., Jr., "Nonlinear Least Squares," State of the Art in Numerical Analysis, ed. D. Jacobs, Academic Press, pp. 269-312, 1977.
  4. Levenberg, K.,"A Method for the Solution of Certain Problems in Least Squares," Quarterly Applied Math. 2, pp. 164-168, 1944.
  5. Marquardt, D.,"An Algorithm for Least Squares Estimation of Nonlinear Parameters," SIAM Journal Applied Math. Vol. 11, pp. 431-441, 1963.
  6. More, J.J., "The Levenberg-Marquardt Algorithm: Implementation and Theory," Numerical Analysis, ed. G. A. Watson, Lecture Notes in Mathematics 630, Springer Verlag, pp. 105-116, 1977.

  В оглавление \ К следующему разделу \ К предыдущему разделу


Поиск по сайту:

Система Orphus

Яндекс.Метрика