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

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

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

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

FMINUNC

поиск минимума функции нескольких переменных без ограничений;

где х есть вектор, а f(x) – возвращающая скаляр функция/

Синтаксис:

x = fminunc(fun,x0)
x = fminunc(fun,x0,options)
x = fminunc(fun,x0,options,P1,P2,...)
[x,fval] = fminunc(...)
[x,fval,exitflag] = fminunc(...)
[x,fval,exitflag,output] = fminunc(...)
[x,fval,exitflag,output,grad] = fminunc(...)
[x,fval,exitflag,output,grad,hessian] = fminunc(...)

Описание:

  • fminunc находит минимум скалярной функции нескольких переменных, стартуя с некоторой начальной точки. В общем, задача относится к нелинейной оптимизации без ограничений

  • x = fminunc(fun,x0) начинает с точки x0 и находит локальный минимум от х для описанной в fun функции. x0 может быть скаляром, вектором или матрицей.

  • x = fminunc(fun,x0,options) минимизирует с параметрами оптимизации, определенными в структурной опции.

  • x = fminunc(fun,x0,options,P1,P2,...) передает зависимые от задачи параметры P1, P2 и т.д. непосредственно в функцию fun. Передается пустая матрица в случае опции по использованию значений по умолчанию

  • [x,fval] = fminunc(...) возвращает в fval значение целевой функции fun как решение от x.

  • [x,fval,exitflag] = fminunc возвращает значение exitflag, которое содержит выходные условия.

  • [x,fval,exitflag,output] = fminunc(...) возвращает структурный выход с информацией об оптимизации.

  • [x,fval,exitflag,output,grad] = fminunc(...) возвращает в grad значение градиента fun как решение от х.

  • [x,fval,exitflag,output,grad,hessian] = fminunc(...) возвращает в hessian значение матрицы Гессе целевой функции fun как решение от х.

Аргументы:

Входные аргументы.
Таблица 4-1, Входные аргументы, содержит общее описание передаваемых в to fminunc аргументов. Данный раздел включает детали функционирования для fun и опций:

fun
Подлежащая минимизацифункция.

fun есть некая функция, которая принимает вектор х и возвращает скаляр f, как целевую функцию от х. Функция fun может быть определена, как описатель функции.
x = fminunc (@myfun,x0)

где myfun есть некая функция MATLAB, такая что function f = myfun(x)
f = ... % Расчет значения функции от х

fun также может быть внутренним объектом
x = fminunc (inline('norm(x)^2'),x0);

Если градиент от fun может быть вычислен и опция options.GradObj равна 'on' посредством установки
options = optimset('GradObj','on'),

то функция fun должна во втором выходном аргументе возвращать значение аргумента g, как вектора от х.

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

function [f,g] = myfun(x)
f = ... % Вычисление функции в точке х
if nargout > 1 % fun вызывается с двумя выходными аргументами
g = ... % Расчет градиента как функции от х
end

Градиент состоит из частных производных от f в точке x. Т.е. i-ая компонента g есть частная производная от f по i-ой компоненте от х.

Если матрица Гессе к тому же может быть рассчитана и опция options.Hessian есть 'on', т.е. options = optimset('Hessian','on'), то функция fun должна возвращать значения матрицы Гессе Н в виде симметричной матрицы от х на месте третьего аргумента. Отметим, что посредством контроля значения nargout можно обойти расчет Н, тогда fun вызывается только с одним или двумя выходными аргументами (случай, когда для оптимизационного алгоритма необходимо только значение f и g, а не Н).

function [f,g,H] = myfun(x)
f = ... % Расчет значения целевой функции от х
if nargout > 1 % fun вызывается с двумя выходными аргументами
g = ... % Расчет градиента как функции от х
if nargout > 2
H = ... % расчет матрицы Гессе от х
End

Матрица Гессе являются матрицей вторых частных производных от f в точке x. Т.е. (i,j)-ая компонента Н есть вторая частная производная от f по xi и xj.

По определению матрица Гессе является симметричной.

options

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

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

exitflag

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

  • > 0 Данная функция сходится к решению по х.

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

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

output

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

  • iterations Число выполненных итераций

  • funcCount Число оценок функции

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

  • cgiterations Число PCG итераций (только для крупно-масштабного алгоритма)

  • stepsize Окончательно принятый размер шага (только для средне-масштабного алгоритма)

  • firstorderopt Измерение оптимальности первого порядка: норма градиента как решение от х.

Options

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

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

LargeScale

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

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

Diagnostics

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

Display

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

GradObj

Градиент определенный пользователем целевой функции. Смотри выше описание функции fun как в ней определить градиент. Для того, что бы использовать крупно-масштабный метод необходимо задавать указанный градиент. Это необязательно для средне-масштабного метода.

MaxFunEvals

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

MaxIter

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

TolFun

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

TolX

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

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

Hessian

В случае установки 'on' в fmincon используется заданная пользователем матрица Гессе (задается в fun) или информация о матрице Гессе (при использовании HessMult) для целевой функции. В случае установки 'off' в fmincon используется матрице Гессе из расчета конечных разностей.

HessMult

Указатель функции для умножения на матрицу Гессе. Для типа крупно-масштабных задач, эта функция рассчитывает произведение матрицы Гессе H*Y без реального формирования Н. Эта функция имеет форму
W = hmfun(Hinfo,Y,p1,p2,...)

Где Hinfo и дополнительные параметры p1,p2,...включают в себя матрицы для расчета H*Y. Первый аргумент должен быть тот же самый, как и третий аргумент, возвращаемый целевой функцией fun.
[f,g,Hinfo] = fun(x,p1,p2,...)

Параметры p1,p2,... являются теми же самыми параметрами, что передаются в fminunc (и в fun).
fminunc(fun,...,options,p1,p2,...)

Y есть матрица с тем же самым числом строк как и размерности данной задачи. W = H*Y, хотя H явно не формируется. fminunc использует Hinfo для расчета предварительных условий.

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

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

HessPattern

Разреженный шаблон матрице Гессе для конечных разностей. Если не является разумным в fun рассчитывать разреженную матрицу Гессе Н, то в fminunc крупно-масштабный метод может аппроксимировать Н через разреженные конечные разности (для градиентов) при условии, что структура разреженности для Н, т.е. местоположения nonzeros, задаются как определенные значения для HessPattern. В наихудшем случае, когда такая структура неизвестна, можно задать HessPattern, что является плотной матрицей, а полная конечноразностная аппроксимация будет рассчитываться на каждой итерации (что принимается по умолчанию). Это может быть очень дорогостоящим для больших задач, поэтому стоит затратить усилия на определение структуры разреженности.

MaxPCGIter

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

PrecondBandWidth

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

TolPCG

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

TypicalX

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

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

DerivativeCheck

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

DiffMaxChange

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

DiffMinChange

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

LineSearchType

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

Примеры:

Найти минимальное значение функции

Для использования М-файла, построим файл myfun.m.

function f = myfun(x)
f = 3*x(1)^2 + 2*x(1)*x(2) + x(2)^2; % Стоимостная функция

Далее для нахождения минимума myfun вблизи [1,1] вызовем fminunc.

x0 = [1,1];
[x,fval] = fminunc(@myfun,x0)

После нескольких итераций будут возвращены решение от х и fval, значение функции в точке х.

x =
  1.0e-008 *
    -0.7914    0.2260
fval =
  1.5722e-016

Для минимизации данной функции с заданным градиентом модифицируем М-файл myfun.m так, что бы градиент был вторым выходным аргументом.

function [f,g] = myfun(x)
f = 3*x(1)^2 + 2*x(1)*x(2) + x(2)^2; % функция стоимости
if nargout > 1
  g(1) = 6*x(1)+2*x(2);
  g(2) = 2*x(1)+2*x(2);
end

также отметим, что значение градиента будут доступным только, если построить структуру опций оптимизации посредством использования optimset для установки опции options.GradObj как 'on'.

options = optimset('GradObj','on');
x0 = [1,1];
[x,fval] = fminunc(@myfun,x0,options)

После нескольких итераций будут возвращены решение от х и fval, значение функции в точке х.

x =
  1.0e-015 *
    -0.6661    0
fval2 =
  1.3312e-030

Для минимизации функции f(x) = sin(x) + 3 используем внутренний объект

f = inline('sin(x)+3');
x = fminunc(f,4)

который возвращает решение

x =
    4.7124

Примечания:

Отметим, fminsearch не является предпочтительным выбором для решения задач с суммами квадратов, т.е. в виде:

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

Для использования крупно-масштабного метода градиент необходимо задавать в fun (а опция options.GradObj устанавливается как 'on'). Если градиент не задан и опция options.LargeScale не равна 'off', то выдается предупреждение.

Алгоритмы:

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

Средне-масштабная оптимизация. fminunc при установке опции options.LargeScale как 'off' использует квази-Ньютоновский метод с смешанной процедурой квадратичного и кубического поиски. Данный квази-Ньютоновский метод использует формулу BFGS ([1],[5],[8],[9]) для модернизации приближенного значения матрицы Гессе. Формула DFP ([4],[6],[7]), которая аппроксимирует обратную матрицу Гессе, задается с помощью установки опции options.HessUpdate как 'dfp' (и опции options.LargeScale как 'off'). Метод наискорейшего спуска выбирается при установке опции options.HessUpdate как 'steepdesc' и (опции options.LargeScale как 'off'), хотя это и не рекомендуется.

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

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

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

fminunc минимизирует только реальные числа, то есть х должно состоять только из реальной части f(x) должна возвращать только реальные числа. В случае, если х содержит комплексные переменные, то они должны быть разделены на реальную и мнимую части.

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

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

Сопутствующие функции: @ (function_handle), fminsearch, inline, optimset

Литература:

  1. Broyden, C.G., "The Convergence of a Class of Double-Rank Minimization Algorithms," Journal Inst. Math. Applic., Vol. 6, pp. 76-90, 1970.
  2. 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.
  3. 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.
  4. Davidon, W.C., "Variable Metric Method for Minimization," A.E.C. Research and Development Report, ANL-5990, 1959.
  5. Fletcher, R.,"A New Approach to Variable Metric Algorithms," Computer Journal, Vol. 13, pp. 317-322, 1970.
  6. Fletcher, R., "Practical Methods of Optimization," Vol. 1, Unconstrained Optimization, John Wiley and Sons, 1980.
  7. Fletcher, R. and M.J.D. Powell, "A Rapidly Convergent Descent Method for Minimization," Computer Journal, Vol. 6, pp. 163-168, 1963.
  8. Goldfarb, D., "A Family of Variable Metric Updates Derived by Variational Means," Mathematics of Computing, Vol. 24, pp. 23-26, 1970.
  9. Shanno, D.F., "Conditioning of Quasi-Newton Methods for Function Minimization," Mathematics of Computing, Vol. 24, pp. 647-656, 1970.

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


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

Система Orphus

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