14. Минимизация функции нескольких переменных

Минимизация функции нескольких переменных

Значительно сложнее задача минимизации функций нескольких переменных f(х ₁ ,...). При этом значения переменных представляются вектором х, причем начальные значения задаются вектором х ₀ Для минимизации функций ряда переменных MATLAB обычно использует разновидности симплекс-метода Нелдера-Мида.

Этот метод является одним из лучших прямых методов минимизации функций ряда переменных, не требующим вычисления градиента или производных функции. Он сводится к построению симплекса в n-мерном пространстве, заданного n+1 вершиной. В двумерном пространстве симплекс является треугольником, а в трехмерном — пирамидой. На каждом шаге итераций выбирается новая точка решения внутри или вблизи симплекса. Она сравнивается с одной из вершин симплекса. Ближайшая к этой точке вершина симплекса обычно заменяется этой точкой. Таким образом, симплекс перестраивается и обычно позволяет найти новое, более точное положение точки решения. Решение повторяется, пока размеры симплекса по всем переменным не станут меньше заданной погрешности решения.

Реализующая симплекс-методы Нелдера-Мида функция записывается в виде:

• fminsearch(@fun,xO) — возвращает вектор х, который является локальным минимумом функции fun(x) вблизи хО.хО может быть скаляром, вектором (отрезком) при минимизации функции одной переменной или матрицей (для функции нескольких переменных);

• fminsearch(@fun,xO,options) — аналогична описанной выше функции, но использует вектор параметров options точно так же, как функция fminbnd;

• fminsearch(@fun,xO,options.P1.P2,...) — сходна с описанной выше функцией, но передает в минимизируемую функцию нескольких переменных fun(x.P1,P2....) ее дополнительные аргументы Р1. Р2,.... Если требуется использовать параметры вычислений по умолчанию, то вместо options перед Р1, Р2 необходимо ввести [ ].;

• [x.fval] = fminsearchC...) — дополнительно возвращает значение целевой функции fval в точке минимума;

• [x.fval .exitflag] = fminsearchC...) —дополнительно возвращает параметр exitflag, положительный, если процесс итераций сходится с использованием options. tol X, отрицательный, если итерационный процесс не сходится к полученному решению х, и 0, если превышено максимальное число итераций options. maxi ten;

• [х. fval .exitflag.output] - fminsearch(...) возвращает структуру (запись) output,

• output.algorithm — использованный алгоритм;

• output. funcCount — число оценок целевой функции;

• output.Iterations — число проведенных итераций.

Классическим примером применения функции fminsearch является поиск минимума тестовой функции Розенброка, точка минимума которой находится в «овраге» с «плоским дном»: rb(x ₁ ,x ₂ ,а) = 100*(x ₂ - x ₁ ) ² + (а - x ₁ ) ² .

Минимальное значение этой функции равно нулю и достигается в точке [ а а ² ]. В качестве примера уточним значения x ₁ и х ₂ в точке [-1.2 1]. Зададим функцию (в файле rb.m):

% Тестовая функция Розенброка 

function f=rb(x.a) 

if nargin<2 a=l: end 

f=100*(x(2)-x(i^2) ^{^} 2+(a-x(l)^2:

Теперь решим поставленную задачу:

»options=optimset( 'tolX',1.e-6):

[xmin. opt, rosexflag, rosout]=fminsearch(@rb.[-1.2 1],options) 

xmin =

1.0000 1.0000 

opt =

4.1940e-014 

rosexflag =

1 rosout =

iterations: 101

funcCount: 189

algorithm: 'Nelder-Mead simplex direct search' .

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

Для минимизации функций нескольких переменных можно использовать также функцию MATLAB fminunc и функцию Isqnonlin из пакета Optimization Toolbox. Первая из них позволяет использовать предварительно заданные командой optimset порог сходимости для значения целевой функции, вектор градиентов opt ions, grad-obj, матрицу Гесса, функцию умножения матрицы Гесса или график разреженности матрицы Гесса целевой функции. Isqnonl in реализует метод наименьших квадратов и, как правило, дает наименьшее число итераций при минимизации. Ограничимся приведением примеров их применения для минимизации функции Розенброка:

» options=optimset('tolX',le-6.'To!Fun'.le-6);

» [xmin. opt. exflag. out, grad, hessian ]=fminunc(@rb,[-1.2 1].options)

Warning: Gradient must be provided for trust-region method;

using line-search method instead. 

> In C:\MATLABR12\toolbox\optim\fminunc.m at line 211 

Optimization terminated successfully:

Current search direction is a descent direction, and magnitude of directional derivative in search direction less than 2*options.TolFun 

xmin =

1.0000 1.0000

opt =

1.9116e-011 

exflag=

1 

out =

iterations: 26

funcCount: 162

stepsize: 1.2992

firstorderopt: 5.0020e-004

algorithm: 'medium-scale: Quasi-Newton line search' 

grad=

l.Oe-003 *

-0.5002

-0.1888 

hessian =

820.4028 -409.5496

-409.5496 204.7720

firstorderopt - мера оптимальности для первой нормы градиента целевой функции в найденной точке минимума; 

»options=optimset('tolX' Gе-6. 'maxFunEvals' .162): 

» [xmin. opt]=lsqnonlin(@rb,[-1.2 1].[0 le-6].[0 le-6],options) 

Warning: Large-scale method requires at least as many equations as variables:

switching to line-search method instead. Upper and lower bounds will be ignored.

> In C:\MATLABR12\toolbox\optim\private\lsqncommon.m at line 155 

In C:\MATLABR12\toolbox\optim\lsqnonlin.m at line 121 

Maximum number of function evaluations exceeded Increase 

OPTIONS.maxFunEvals 

xmin =

0.6120 0.3715 

opt =

0.1446