Как найти минимум функции матлаб

fminunc

Description

fun = @(x)3*x(1)^2 + 2*x(1)*x(2) + x(2)^2 - 4*x(1) + 5*x(2);

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

Local minimum found.

Optimization completed because the size of the gradient is less than
the value of the optimality tolerance.

options = optimoptions('fminunc','Algorithm','trust-region','SpecifyObjectiveGradient',true);

x0 = [-1,2];
fun = @rosenbrockwithgrad;
x = fminunc(fun,x0,options)

Local minimum found.

Optimization completed because the size of the gradient is less than
the value of the optimality tolerance.

function [f,g] = rosenbrockwithgrad(x)
% Calculate objective f
f = 100*(x(2) - x(1)^2)^2 + (1-x(1))^2;

if nargout > 1 % gradient required
    g = [-400*(x(2)-x(1)^2)*x(1) - 2*(1-x(1));
        200*(x(2)-x(1)^2)];
end
end

options = optimoptions('fminunc','Algorithm','trust-region','SpecifyObjectiveGradient',true);

problem.options = options;
problem.x0 = [-1,2];
problem.objective = @rosenbrockwithgrad;
problem.solver = 'fminunc';

Local minimum found.

Optimization completed because the size of the gradient is less than
the value of the optimality tolerance.

function [f,g] = rosenbrockwithgrad(x)
% Calculate objective f
f = 100*(x(2) - x(1)^2)^2 + (1-x(1))^2;

if nargout > 1 % gradient required
    g = [-400*(x(2)-x(1)^2)*x(1)-2*(1-x(1));
        200*(x(2)-x(1)^2)];
end
end

fun = @(x)x(1)*exp(-(x(1)^2 + x(2)^2)) + (x(1)^2 + x(2)^2)/20;

x0 = [1,2];
[x,fval] = fminunc(fun,x0)

Local minimum found.

Optimization completed because the size of the gradient is less than
the value of the optimality tolerance.

options = optimoptions(@fminunc,'Display','iter','Algorithm','quasi-newton');

fun = @(x)x(1)*exp(-(x(1)^2 + x(2)^2)) + (x(1)^2 + x(2)^2)/20;

x0 = [1,2];
[x,fval,exitflag,output] = fminunc(fun,x0,options)

                                                        First-order 
 Iteration  Func-count       f(x)        Step-size       optimality
     0           3         0.256738                         0.173
     1           6         0.222149              1          0.131  
     2           9          0.15717              1          0.158  
     3          18        -0.227902       0.438133          0.386  
     4          21        -0.299271              1           0.46  
     5          30        -0.404028       0.102071         0.0458  
     6          33        -0.404868              1         0.0296  
     7          36        -0.405236              1        0.00119  
     8          39        -0.405237              1       0.000252  
     9          42        -0.405237              1       7.97e-07  

Local minimum found.

Optimization completed because the size of the gradient is less than
the value of the optimality tolerance.

output = struct with fields:
       iterations: 9
        funcCount: 42
         stepsize: 2.9343e-04
     lssteplength: 1
    firstorderopt: 7.9721e-07
        algorithm: 'quasi-newton'
          message: 'Local minimum found....'

N = 1e5;
x0 = -2*ones(N,1);
x0(2:2:N) = 2;
[x,fval] = fminunc(@multirosenbrock,x0)

Error using eye
Requested 100000x100000 (74.5GB) array exceeds maximum array size preference (63.9GB). This might cause MATLAB to become
unresponsive.

Error in optim.internal.fminunc.AbstractDenseHessianApproximation (line 21)
        this.Value = eye(nVars);

Error in optim.internal.fminunc.BFGSHessianApproximation (line 14)
        this = this@optim.internal.fminunc.AbstractDenseHessianApproximation(nVars);

Error in fminusub (line 73)
    HessApprox = optim.internal.fminunc.BFGSHessianApproximation(sizes.nVar);

Error in fminunc (line 488)
   [x,FVAL,GRAD,HESSIAN,EXITFLAG,OUTPUT] = fminusub(funfcn,x, ...

N = 1e5;
x0 = -2*ones(N,1);
x0(2:2:N) = 2;
options = optimoptions("fminunc",HessianApproximation="lbfgs",...
    SpecifyObjectiveGradient=true);
[x,fval] = fminunc(@multirosenbrock,x0,options);

Local minimum found.

Optimization completed because the size of the gradient is less than
the value of the optimality tolerance.

function [f,g] = multirosenbrock(x)
% Get the problem size
n = length(x);  
if n == 0, error('Input vector, x, is empty.'); end
if mod(n,2) ~= 0
   error('Input vector, x ,must have an even number of components.');
end
% Evaluate the vector function
odds  = 1:2:n;
evens = 2:2:n;
F = zeros(n,1);
F(odds,1)  = 1-x(odds);
F(evens,1) = 10.*(x(evens)-x(odds).^2); 
f = sum(F.^2);
if nargout >= 2 % Calculate gradient
    g = zeros(n,1);
    g(evens) = 200*(x(evens)-x(odds).^2);
    g(odds) = -2*(1 - x(odds)) - 400*(x(evens)-x(odds).^2).*x(odds);
end
end

function f = myfun(x)
f = ...            % Compute function value at x

x = fminunc(@(x)norm(x)^2,x0);

options = optimoptions('fminunc','SpecifyObjectiveGradient',true)

W = hmfun(Hinfo,Y)

[f,g,Hinfo] = fun(x)

fminbnd

Description

fun = @sin;
x1 = 0;
x2 = 2*pi;
x = fminbnd(fun,x1,x2)

function f = scalarobjective(x)
f = 0;
for k = -10:10
    f = f + (k+1)^2*cos(k*x)*exp(-k^2/2);
end

x = fminbnd(@scalarobjective,1,3)

a = 9/7;
fun = @(x)sin(x-a);
x = fminbnd(fun,1,2*pi)

fun = @sin;
x1 = 0;
x2 = 2*pi;
options = optimset('Display','iter');
x = fminbnd(fun,x1,x2,options)

 
 Func-count     x          f(x)         Procedure
    1        2.39996      0.67549        initial
    2        3.88322     -0.67549        golden
    3        4.79993    -0.996171        golden
    4        5.08984    -0.929607        parabolic
    5        4.70582    -0.999978        parabolic
    6         4.7118           -1        parabolic
    7        4.71239           -1        parabolic
    8        4.71236           -1        parabolic
    9        4.71242           -1        parabolic
 
Optimization terminated:
 the current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-04 

fun = @sin;
[x,fval] = fminbnd(fun,1,2*pi)

fun = @sin;
x1 = 0;
x2 = 2*pi;
options = optimset('PlotFcns',@optimplotfval);
[x,fval,exitflag,output] = fminbnd(fun,x1,x2,options)

output = struct with fields:
    iterations: 8
     funcCount: 9
     algorithm: 'golden section search, parabolic interpolation'
       message: 'Optimization terminated:...'

x = fminbnd(@myfun,x1,x2)

function f = myfun(x)
f = ...            % Compute function value at x

x = fminbnd(@(x)norm(x)^2,x1,x2);

Информация в данной статье относится к релизам программы MATLAB ранее 2016 года, и поэтому может содержать устаревшую информацию в связи с изменением функционала инструментов. С более актуальной информацией вы можете ознакомиться в разделе документация MATLAB на русском языке.

В статье приведено описание основных функций Optimization Toolbox.

Нелинейная оптимизация (функций)

• fminbnd – поиск функции одной переменной для фиксированного интервал 
• fmincon – поиск минимума нелинейной задачи с ограничениями
• fminsearch – поиск минимума функции нескольких переменных без ограничений 
• fminunc – поиск минимума функции нескольких переменных без ограничений 
• fseminf – поиск минимума полубесконечной нелинейной функции нескольких переменных с ограничениями 

Нелинейная минимизация многокритериальных функций

• fgoalattain – решение многокритериальной (векторной) задачи достижения цели
• fminimax – решение задачи минимакса

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

• lsqlin – решение линейной задачи с ограничениями методом наименьших квадратов
• lsqnonneg – решение неотрицательной задачи методом наименьших квадратов

Нелинейный метод наименьших квадратов (для функций)

• lsqcurvefit – решение нелинейной задачи аппроксимации кривых (подбора данных) методом наименьших квадратов
• lsqnonlin – решение нелинейной задачи методом наименьших квадратов (нелинейный подбор данных)

Нелинейный метод определения нуля (решение уравнений)

• fzero – нахождение нулей функции одной переменной
• fsolve – решение системы нелинейных уравнений 

Минимизация матричных задач

• linprog – решение задачи линейного программирования
• quadprog – решить квадратичную задачу математического программирования

Утилиты

• fzmult – умножение при сохранении основного базисом для нуль-пространства.
• gangster – обнуление <небольших> компонентов с учетом структурного ранга.
• optimget – получить значения параметров опций оптимизации
• optimset – создать или отредактировать структуру параметров опций оптимизации

Демонстрация крупно-масштабных методов

• circustent – квадратичное программирование для нахождения формы цирка шапито
• molecule – расчет молекулярной структуры с помощью нелинейной минимизации без ограничений
• optdeblur – устранение размытости изображений с помощью ограниченного линейного метода наименьших квадратов

Демонстрация средне-масштабных методов

• optdemo – меню демонстраций
• tutdemo – учебный прогон
• bandemo – минимизация банановой функции
• goaldemo – достижение цели
• dfildemo – проектирование фильтра с конечной точностью (требует Toolbox Обработки Сигналов)
• datdemo – подбор данных для кривой

Целочисленное программирование

Наверх

fminbnd – поиск функции одной переменной для фиксированного интервал

Синтаксис:

x = fminbnd(fun,x1,x2)
x = fminbnd(fun,x1,x2,options)
x = fminbnd(fun,x1,x2,options,P1,P2,…)
[x,fval] = fminbnd(…)
[x,fval,exitflag] = fminbnd(…)
[x,fval,exitflag,output] = fminbnd(…) 

Описание:

fminbnd находит минимум функции одной переменной для фиксированного интервала.

• x = fminbnd(fun,x1,x2) возвращает значение x, которое является локальным минимумом скалярной функции, представленной как fun в интервале x1 < x < x2.
  that is a local minimizer of the scalar valued function that is described
• x = fminbnd(fun,x1,x2,options) производит оптимизацию с параметрами, заданными в структуре опций
• x = fminbnd(fun,x1,x2,options,P1,P2,…) предусматривает дополнительные аргументы P1, P2, и т.д., которые передаются в целевую функцию fun. Используйте опции =[], как заполнитель, если опции не устанавливаются как таковые.
• [x,fval] = fminbnd(…) возвращает значение целевой функции, вычисленной fun от как x 
• [x,fval,exitflag] = fminbnd(…) возвращает значение exitflag, которое описывает выходные условия fminbnd.
• [x,fval,exitflag,output] = fminbnd(…) возвращает выходную структуру с информацией об оптимизации.

Аргументы:

Входные аргументы.
Таблица, Входные аргументы, содержит общее описание аргументов передаваемых в fminbnd.

Данный раздел содержит детальное описание fun и других опций.

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

Options

Параметры опций оптимизации для fminbnd. Вы можете использовать optimset, для того, что бы установить или изменить поля в структуре параметров options. Для детальной информации смотри Таблицу 4-3. Параметры опций оптимизации.

Пример:

Минимум имеет место для 

x = fminbnd(@sin,0,2*pi)
x = 4.7124

Значение функции в точке минимума будет

y = sin(x)
y =
-1.0000 

Для того, что бы найти минимум функции на интервале (0, 5), сперва запишем М-файл

function f = myfun(x)
f = (x-3).^2 – 1;

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

x = fminbnd(@myfun,0,5)
что дает решение 

x =
3 

Значение в точке минимума будет 

y = f(x)
y =
-1 

Алгоритм:

fminbnd из М-файл. В основу алгоритма положены Метод золотого сечения и параболической интерполяции. Фортран-программа, реализующая точно такой же алгоритм проведена в [1]. 

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

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

Литература:

1. Forsythe, G.E., M.A. Malcolm, and C.B. Moler, Computer Methods for Mathematical Computations, Prentice Hall, 1976.

Наверх

fmincon – поиск минимума нелинейной задачи с ограничениям

Синтаксис:

x = fmincon(fun,x0,A,b)
x = fmincon(fun,x0,A,b,Aeq,beq)
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub)
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2, …)
[x,fval] = fmincon(…)
[x,fval,exitflag] = fmincon(…)
[x,fval,exitflag,output] = fmincon(…)
[x,fval,exitflag,output,lambda] = fmincon(…)
[x,fval,exitflag,output,lambda,grad] = fmincon(…)
[x,fval,exitflag,output,lambda,grad,hessian] = fmincon(…)

Описание:

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

• x = fmincon(fun,x0,A,b) начинает с точки x0 и находит минимум от х для функции представленной как fun при условии выполнения линейных неравенств A*x <= b. x0 может быть скаляром, вектором или матрицей.
• x = fmincon(fun,x0,A,b,Aeq,beq) минимизирует fun при условии выполнения линейных равенств Aeq*x = beq, а так же A*x <= b. Устанавливается A=[] и b=[] в случае отсутствия неравенств.
• x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub) определяет набор нижних и верхних ограничений на конструируемые переменные х так, что решение всегда находится в диапазоне lb <= x <= ub. Устанавливается Aeq=[] and beq=[] в случае отсутствия равенств.
• x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) подчиняет минимизацию определенных в nonlcon fmincon нелинейных неравенств c(x) или равенств ceq(x) такому оптимуму, что c(x) <= 0 и ceq(x) = 0. Устанавливается lb=[] и/илиr ub=[] в случае отсутствия ограничений.
• x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) проводит минимизацию с оптимизационными параметрами, определенными в структурной опции.
• x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,…) передает зависящие от типа задачи параметры непосредственно в функции fun и nonlcon. Передает пустые матрицы заменители для A, b, Aeq, beq, lb, ub, nonlcon и options в случае, если эти аргументы не являются необходимыми.
• [x,fval] = fmincon(…) возвращает значение целевой функции fun как решение от х.
• [x,fval,exitflag] = fmincon(…) возвращает значение exitflag, которое содержит описание выходных условий fmincon.
• [x,fval,exitflag,output] = fmincon(…) возвращает структурный выход с информацией об оптимизации.
• [x,fval,exitflag,output,lambda] = fmincon(…) возвращает структурную lambda с полями, содержащими множители Лагранжа в виде решения от х.
• [x,fval,exitflag,output,lambda,grad] = fmincon(…) возвращает значение градиента от fun в виде решения от х.
• [x,fval,exitflag,output,lambda,grad,hessian] = fmincon(…) возвращает значения матрицы Гессе от fun в виде решения от х.

Аргументы:

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

fun Подлежащая минимизации функция.	fun есть такая функция, которая принимает скаляр х и возвращает скаляр f, т.е. целевая функция от х. Функция fun может задаваться с помощью описателя функций x = fmincon(@myfun,x0,A,b) где myfun есть такая функция MATLAB, что function f = myfun(x) f = …        % Вычисление функции в точке х fun так же может быть и внутренним объектом x = fmincon(inline(‘norm(x)^2’),x0,A,b); Если градиент от 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 по  и .  по определению матрица Гессе является симметричной.
nonlcon Функция, которая вычисляет нелинейные ограничения виде неравенств c(x) <= 0 и нелинейные ограничения виде равенств ceq(x) = 0.	Функция nonlcon принимает вектор х и возвращает два вектора c и ceq. Вектор с содержит нелинейные неравенства при расчете от х и ceq содержит нелинейные равенства при расчете от х. Функция nonlcon может быть определена как описатель функции.  x = fmincon(@myfun,x0,A,b,Aeq,beq,lb,ub,@mycon) где mycon есть функция MATLAB, определенная как function [c,ceq] = mycon(x) c = …      % вычисляет нелинейные ограничения в виде неравенств от х. ceq = …   % вычисляет нелинейные ограничения в виде равенств от х. Если к тому же градиенты ограничений могут быть рассчитаны и опция options.GradConstr равна ‘on’ посредством options = optimset(‘GradConstr’,’on’) то функция nonlcon так же должна возвращаться как третий и четвертый выходные аргументы, GC – как градиент от c(x) и GCeq как как градиент от ceq(x). Отметим, что посредством контроля значения nargout данная функция может обойти расчет GC и GCeq при этом nonlcon вызывается только с двумя выходными аргументами (в данном случае алгоритм оптимизации нуждается только в значениях c и ceq а не GC и GCeq). function [c,ceq,GC,GCeq] = mycon(x) c = …            % Нелинейные неравенства от х ceq = …        % Нелинейные равенства от х if nargout > 2 % Nonlcon вызываентся с 4 выходнымизначениями GC = …         % Градиенты неравенств GCeq = …     % Градиенты равенств end Если nonlcon возвращает вектор с с m компонентами и х имеет длину n, где n есть длина x0, то градиент GC c(x) есть матрица n х m, где GC(i,j) будут частные производные от c(j) по x(i) (т.е. j-ая колонка GC есть градиент j-го ограничения виде неравенств c(j)). Аналогично, если ceq имеет p компонент, то градиент GCeq ceq(x) есть матрица n х p, где GCeq(i,j) будут частные производные от ceq(j) по x(i) (т.е. j-ая колонка GCeq есть градиент j-го ограничения виде равенств ceq(j)).
options	Опции обеспечивают учет специфических деталей функции виде параметров options.

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

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

Options

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

Для детальной информации смотри Таблицу 4-3, Параметры Опций Оптимизации

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

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

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,… являются теми же самыми параметрами, что передаются в fmincon (и в fun). fmincon(fun,…,options,p1,p2,…) Y есть матрица с тем же самым числом строк как и размерности данной задачи. W = H*Y, хотя H явно не формируется. fmincon использует Hinfo для расчета предварительных условий. В качестве примера смотри Нелинейную Оптимизацию с Компактной, но Структурированной Матрицей Гессе и Ограничениями Типа Равенств.
HessPattern	Разреженный образ матрицы Гессе для конечных разностей. Если не является разумным в fun рассчитывать разреженную матрицу Гессе Н, то в fmincon крупно-масштабный метод может аппроксимировать Н через разреженные конечные разности (для градиентов) при условии, что структура разреженности для Н, т.е. местоположения nonzeros, задаются как определенные значения для HessPattern. В наихудшем случае, когда такая структура неизвестна, можно задать HessPattern, что является плотной матрицей, а полная конечноразностная аппроксимация будет рассчитываться на каждой итерации (что принимается по умолчанию). Это может быть очень дорогостоящим для больших задач, поэтому стоит затратить усилия на определение структуры разреженности.
MaxPCGIter	Максимальное число PCG (предварительно сопряженный градиент) итераций (Смотри ниже раздел Алгоритм).
PrecondBandWidth	Верхняя полоса предварительной обработки для PCG. По умолчанию используется диагональная начальная подготовка (верхняя полоса из 0). Для некоторых задач увеличение полосы снижает число итераций PCG.
TolPCG	Конечное допустимое число итераций PCG.
TypicalX	Типичные значения х.

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

Примеры:

Найти значение х, которые минимизируют , начиная с точки x = [10; 10; 10] и с учетом ограничений

Прежде всего, запишем М-файл, который возвращает скалярное значение f как функции от х.

function f = myfun(x)
f = -x(1) * x(2) * x(3);

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

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

……

Далее зададим начальную точку и запустим программу оптимизации.

x0 = [10; 10; 10]; % начальное предположение о решении
[x,fval] = fmincon(@myfun,x0,A,b)

После 66 расчетов функции решение будет

x =
     24.0000
     12.0000
     12.0000

где значение функции будет

fval =
     -3.4560e+03

и оценка ограничений в виде линейных неравенств <= 0 дает

A*x-b= 
     -72
     0

Примечания:

Крупно-масштабная оптимизация. Для того, что бы использовать крупно-масштабный метод в fun необходимо задать градиент (а в опции options.GradObj установить ‘on’). Производится предупреждение (warning) при условии, что градиент не задан, а опция options.LargeScale не равна ‘off’. Допускается, что в функции fmincon значение g(x) будет приближенным градиентом, но, однако, эта опция не рекомендуется, поскольку большинство оптимизационных кодов значительно более грубое, чем истинные значения используемых градиентов.

Крупно-масштабный метод для fmincon наиболее эффективен в том случае, когда также рассчитывается и матрица вторых производных, т.е. матрице Гессе H(x). Однако оценка истинных значений матрицы Гессе не требуется. Например, если можно ввести структуру разреженности матрицы Гессе (используя определенный параметр опции HessPattern), то тогда fmincon рассчитывает разреженную конечноразностную аппроксимацию для H(x).

Если х0 не является строго вычисляемым, то fmincon выбирает новую (центрированную) строго вычисляемую начальную точку. 

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

Следует отметить несколько аспектов относительно линейной условной оптимизации.

• Плотная (или достаточно плотная) колонка матрицы Aeq может привести к значительному переполнению и компьютерным затратам.
• fmincon удаляет (численно) линейно зависимые строки в Aeq; однако такая операция влечет за собой многократно повторяемую матричную факторизацию и, следовательно, может быть затратной в случае большого количества зависимостей.
• Каждая итерация влечет за собой задачу разрежения методом наименьших квадратов для матрицы 
  .

Средне-масштабная оптимизация. По-видимому, если явно определить равенства с помощью Aeq и beq, то будут более лучшие численные результаты, по сравнению с случаем неявного определения с помощью lb и ub.

Если имеются ограничения в виде равенств, а также определяются и удаляются зависимые равенства в квадратичной подзадаче, то печатается ‘dependent’ в заголовке Процедуры (когда запрашивается вывод опции options.Display = ‘iter’). Зависимые равенства удаляются только тогда, когда эти равенства являются непротиворечивыми, при этом задача является недопустимой и в заголовке Процедуры печатается ‘infeasible’. 

Алгоритм:

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

Средне-масштабная оптимизация. fmincon использует метод Последовательного Квадратичного Программирования (SQP). В данном методе на каждой итерации решается подзадача Квадратичного Программирования (QP). Вид матрицы Гессе для функции Лагранжа обновляется на каждой итерации с помощью формулы BFGS (смотри fminunc, литература [7], [8]).

Линейный поиск проводится с помощью функции полезности аналогично тому, как было предложено [4], [5], и [6].

Подзадача QP решается с помощью постоянной активной стратегии, аналогично тому, как было предложено в [3]. Полное описание алгоритма можно найти в разделе Условная Оптимизация в “Введении в Алгоритмы”.

Более подробно об используемом алгоритме смотри Реализация SQP в “Введении в Алгоритмы”.

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

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

lb(2) = = ub(2), то fmincon выдает ошибку

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

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

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

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

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

Если задача является недопустимой, то fmincon пытается минимизировать значение максимального ограничения.

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

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

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

Сопутствующие функции: @ (function_handle), fminbnd, fminsearch, fminunc, 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. Gill, P.E., W. Murray, and M.H. Wright, Practical Optimization, Academic Press, London, 1981.
4. Han, S.P., “A Globally Convergent Method for Nonlinear Programming” Journal of Optimization Theory and Applications, Vol. 22, p. 297, 1977.
5. Powell, M.J.D., “A Fast Algorithm for Nonlineary Constrained Optimization Calculations” Numerical Analysis, ed. G.A. Watson, Lecture Notes in Mathematics, Springer Verlag, Vol. 630, 1978.
6. Powell, M.J.D., “The Convergence of Variable Metric Methods For Nonlinearly Constrained Optimization Calculations” Nonlinear Programming 3, (O.L. Mangasarian, R.R. Meyer, and S.M. Robinson, eds.) Academic Press, 1978.

Наверх

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

Синтаксис:

x = fminsearch(fun,x0)
x = fminsearch(fun,x0,options)
x = fminsearch(fun,x0,options,P1,P2,…)
[x,fval] = fminsearch(…)
[x,fval,exitflag] = fminsearch(…)
[x,fval,exitflag,output] = fminsearch(…)

Описание:

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

• x = fminsearch(fun,x0) начинает с точки x0 и находит локальный минимум от х для описанной в fun функции. x0 может быть скаляром, вектором или матрицей.
• x = fminsearch(fun,x0,options) минимизирует с параметрами оптимизации, определенными в структурной опции.
• x = fminsearch(fun,x0,options,P1,P2,…) передает зависимые от задачи параметры P1, P2 и т.д. непосредственно в функцию fun. Используется опция = [] как структурный ноль, если опции не определены.
• [x,fval] = fminsearch(…) возвращает в fval значение целевой функции fun как решение от x.
• [x,fval,exitflag] = fminsearch(…) возвращает значение exitflag, котрое содержит выходные условия fminsearch.
• [x,fval,exitflag,output] = fminsearch(…) возвращаетструктурный выход с информацией об оптимизации.

Аргументы:

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

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

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

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

Options

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

Примеры:

Минимизировать одномерную функцию f(x) = sin(x) + 3.

Для того, что использовать М-файл, т.е. fun = ‘myfun’, создается файл myfun.m.

function f = myfun(x)
f = sin(x) + 3;

Далее для поиска минимума от fun вблизи 2 вызывается fminsearch

x = fminsearch(@myfun,2)

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

f = inline(‘sin(x)+3’);
x = fminsearch(f,2);

Алгоритмы:

fminsearch использует метод симплексного поиска [1]. Это метод прямого поиска, который в отличие от fminunc не использует численные или аналитические значения градиентов.

Если n есть длина х, то в n-мерном пространстве симплекс характеризуется n+1 различными векторами, являющимися его вершинами. В двумерном пространстве симплекс является треугольником, в трех-мерном пространстве – пирамидой. На каждом шаге поиска генерируется новая точка или текущий симплекс. Значение функции в новой точке сравнивается с значениями функций в вершинах симплекса и, как правило, одна из вершин становится новой точкой. Образующей новый симплекс. Данный шаг повторяется до тех пор, пока диаметр симплекса не будет меньше заданной точности.

В общем, fminsearch является менее эффективным для задач с порядком больше, чем два. Однако, если задача является существенно разрывной, то fminsearch может быть более устойчивым.

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

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

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

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

@ (function_handle), fminbnd, fminunc, inline, optimset

Литература:

1. Lagarias, J.C., J. A. Reeds, M. H. Wright, and P. E. Wright, “Convergence Properties of the Nelder-Mead Simplex Method in Low Dimensions,” SIAM Journal of Optimization, Vol. 9 Number 1, pp.112-147, 1998.

Наверх

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

Синтаксис:

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 и опций:

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

Options

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

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

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

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

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

Примеры:

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

Для использования М-файла, построим файл 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.

Наверх

fseminf – поиск минимума полубесконечной нелинейной функции нескольких переменных с ограничениями&nbsp

Поиск минимума полубесконечной нелинейной функции нескольких переменных с ограничениями при условии
где x, b, beq, lb и ub – векторы, A и Aeq – матрицы, и c(x) и ceq(x) и K_i(x,w_i) есть возвращающие векторы функции, f(x) – функция, которая возвращает скаляр. f(x), c(x) и ceq(x) могут быть нелинейными функциями. Эти векторы (или матрицы) есть непрерывные функции как от х, так и от дополнительного набора переменных . Переменные являются векторами, как правило, длины два.

Синтаксис:

x = fseminf(fun,x0,ntheta,seminfcon)
x = fseminf(fun,x0,ntheta,seminfcon,A,b)
x = fseminf(fun,x0,ntheta,seminfcon,A,b,Aeq,beq)
x = fseminf(fun,x0,ntheta,seminfcon,A,b,Aeq,beq,lb,ub)
x = fseminf(fun,x0,ntheta,seminfcon,A,b,Aeq,beq,lb,ub,options)
x = fseminf(fun,x0,ntheta,seminfcon,A,b,Aeq,beq,…
lb,ub,options,P1,P2,…)
[x,fval] = fseminf(…)
[x,fval,exitflag] = fseminf(…)
[x,fval,exitflag,output] = fseminf(…)
[x,fval,exitflag,output,lambda] = fseminf(…)

Описание:

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

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

• x = fseminf(fun,x0,ntheta,seminfcon) начинает с точки х0 и находит минимум функции fun с полубесконечными ограничениями ntheta, определенными в seminfcon.
• x = fseminf(fun,x0,ntheta,seminfcon,A,b) аналогично пытается удовлетворить линейным неравенствам A*x <= b.
• x = fseminf(fun,x0,ntheta,seminfcon,A,b,Aeq,beq) минимизирует объект с учетом линейных равенств. При отсутствии неравенств устанавливается A=[] и b=[].
• x = fseminf(fun,x0,ntheta,seminfcon,A,b,Aeq,beq,lb,ub) определяет набор нижних и верхних ограничений на конструируемые переменные х так, что решение всегда находится в диапазоне lb <= x <= ub.
• x = fseminf(fun,x0,ntheta,seminfcon,A,b,Aeq,beq,lb,ub,options) проводит минимизацию с учетом определенных в структурных опциях оптимизационных параметров.
• x = fseminf(fun,x0,ntheta,seminfcon,A,b,Aeq,beq,lb,ub,options, P1,P2,…) передает зависящие от типа задачи параметры непосредственно в функции fun и seminfcon. Передает пустые матрицы заменители для A, b, Aeq, beq, lb, ub, nonlcon и options в случае, если эти аргументы не являются необходимыми.
• [x,fval] = fseminf(…) возвращает значение целевой функции fun как решение от х.
• [x,fval,exitflag] = fseminf(…) возвращает значение exitflag, которое содержит описание выходных условий.
• [x,fval,exitflag,output] = fseminf(…) возвращает структурный выход с информацией об оптимизации.
• [x,fval,exitflag,output,lambda] = fseminf(…)возвращает структурную lambda с полями, содержащими множители Лагранжа в виде решения от х.

Аргументы:

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

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

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

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

Options

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

Замечания:

Установленный в seminfcon рекомендованный выборочный интервал S на протяжении расчета может быть изменен с помощью оптимизационной подпрограммы fseminf, поскольку отличные от рекомендованного интервала значения могут оказаться более подходящими для эффективности или точности. Кроме того, для конечной области, во всем диапазоне допускается изменять заданный тип оптимизации, что не приводит к существенным изменениям в числе локальных минимумов для .

Примеры:

Одномерный пример

Найти значения х при которых будет минимальным выражение

where

для всех значений  и  и по всему диапазону

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

В первую очередь запишем М-файл для расчетов целевой функции

function f = myfun(x,s)
% Целевая функция
f = sum((x-0.5).^2);

Во-вторых, составим М-файл для ограничений под названием mycon.m. Введем в программу рисование поверхностного графика полубесконечных ограничений всякий раз, как вызывается mycon. Это дает возможность увидеть изменения ограничений по мере минимизации Х.

function [c,ceq,K1,s] = mycon(X,s)
% Начальный выборочный интервал
if isnan(s(1,1)),
   s = [2 2];
end

% Набор выборок
w1x = 1:s(1,1):100;
w1y = 1:s(1,2):100;
[wx,wy] = meshgrid(w1x,w1y);

% Полубесконечное ограничение
K1 = sin(wx*X(1)).*cos(wx*X(2))-1/1000*(wx-50).^2 -…
   sin(wx*X(3))-X(3)+sin(wy*X(2)).*cos(wx*X(1))-…
   1/1000*(wy-50).^2-sin(wy*X(3))-X(3)-1.5;

% не имеющие предела нелинейные ограничения 
c = []; ceq=[];
% Mesh plot
m = surf(wx,wy,K1,’edgecolor’,’none’,’facecolor’,’interp’);
camlight headlight
title(‘Semi-infinite constraint’)
drawnow

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

x0 = [0.25, 0.25, 0.25]; % Начальное предположение
[x,fval] = fseminf(@myfun,x0,1,@mycon)

После девяти итераций решение будет

x =
   0.2926   0.1874   0.2202

и значение функции для данного решения

fval =
   0.0091

Цель заключалась в том, что бы минимизировать целевую функцию с выполнением полубесконечных ограничений. Оценка mycon как решение от х анализ максимального элемента матрицы К1 показывает, что ограничение легко выполняется.

[c,ceq,K1] = mycon(x,[0.5,0.5]); % Выборочный интервал 0.5
max(max(K1))
ans =
   -0.0027

Данный вызов mycon производит surf plot, что демонстрирует полубесконечное ограничение от х.

Двухмерный пример

Найти значения х при которых будет минимальным выражение

где

для всех значений  и  и по всему диапазону

Стартовая точка x=[0.25, 0.25, 0.25].

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

В первую очередь запишем М-файл для расчетов целевой функции

function f = myfun(x,s)
% Целевая функция
f = sum((x-0.2).^2);

Алгоритм:

fseminf использует методы кубической и квадратичной интерполяции для расчета пиковых значений для полубесконечных ограничений. Данные значения пиков используются для формирования набора ограничений, что передается в метод SQP так же как для функции fmincon. Когда число ограничений изменяется, то множители Лагранжа перераспределяются в новый набор ограничений.

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

Рекомендованный выборочный интервал снижается в случае, если значения пиков берутся вблизи границ ограничений, т.е. около нуля.

Для большей детализации используемого алгоритма и типов процедур, распечатываемых под заголовком Процедуры при установке опции options.Display = ‘iter’ смотри реализация SQP в разделе “Ведении в Алгоритмы”. 

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

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

Если задача является недопустимой, то fseminf пытается минимизировать значение максимального ограничения.

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

@ (function_handle), fmincon, optimset

Наверх

fgoalattain – решение многокритериальной (векторной) задачи достижения цел

Найти  y при условии, что

где x, weight (вес), goal (цель), b, beq, lb и ub – векторы; A и Aeq – матрицы; с(x), сeq(x), и F(x) есть функции, которые возвращают вектора. F(x),с(x) и сeq(x) могут быть нелинейными функциями.

Синтаксис:

x = fgoalattain(fun,x0,goal,weight)
x = fgoalattain(fun,x0,goal,weight,A,b)
x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq)
x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub)
x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)
x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options)
x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,…)
[x,fval] = fgoalattain(…)
[x,fval,attainfactor] = fgoalattain(…)
[x,fval,attainfactor,exitflag] = fgoalattain(…)
[x,fval,attainfactor,exitflag,output] = fgoalattain(…)
[x,fval,attainfactor,exitflag,output,lambda] = fgoalattain(…)

Описание:

fgoalattain решает задачу достижения цели, которая является одной из формулировок задач для векторной оптимизации.

• x = fgoalattain(fun,x0,goal,weight) пытается создать целевую функцию задаваемую как fun и принимающую определенные целевые значения goal путем изменения x, начиная с х0, с весом weight.
• x = fgoalattain(fun,x0,goal,weight,A,b) решает задачу достижения цели, соответствующую системе линейных неравенств A*x <= b.
• x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq) решает задачу достижения цели, соответствующую так же системе линейных равенств Aeq*x = beq. Устанавливает определенные A=[] и b=[], если неравенства отсутствуют.
• x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub) определяет набор нижних и верхних ограничений на конструируемые переменные х, так что бы искомое решение находилось в диапазоне lb <= x <= ub.
• x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) подгоняет задачу достижения цели под условия нелинейных неравенств c(x) или нелинейных равенств ceq(x) задаваемых в nonlcon. fgoalattain проводит такую оптимизацию, что c(x) <= 0 и ceq(x) = 0. Устанавливает lb=[] и/или ub=[], если нет ограничений.
• x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,… options) проводит минимизацию при параметрах оптимизации, задаваемых в структуре options.
• x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,…) переводит связанные с задачей параметры P1, P2 и т.д. непосредственно в функции fun и nonlcon. Переводит пустые матрицы в структурные нули для A, b, Aeq, beq, lb, ub, nonlcon и options, если эти переменные не являются необходимыми. 
• [x,fval] = fgoalattain(…) возвращает значения целевых функций, вычисляемых для fun при расчете х.
• [x,fval,attainfactor] = fgoalattain(…) возвращает коэффициент достижения при расчете х.
• [x,fval,attainfactor,exitflag] = fgoalattain(…) возвращает значение exitflag, которое характеризует условия задачи fgoalattain.
• [x,fval,attainfactor,exitflag,output] = fgoalattain(…) возвращает структурный выход, который содержит информацию о процессе оптимизации.
• [x,fval,attainfactor,exitflag,output,lambda] = fgoalattain(…) возвращает структурную lambda, поля которой содержат множители Лагранжа при расчете х.

Аргументы:

Входные аргументы. 
Таблица 4-1, Входные аргументы, содержит общее описание аргументов передаваемых в fgoalattain. Этот раздел определяет детали описания функций fun, goal, nonlcon, options, и weight: 

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

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

Options

Параметры опций оптимизации, используемые в fgoalattain. Можно использовать optimset, для что бы установить или изменить значения поля параметров опций оптимизации. Для детальной информации смотри Таблицу 4-3. “Параметры опций оптимизации”.

Примеры

Рассмотрим линейную систему дифференциальных уравнений.

Автоматический регулятор по выходу обратной связи, К, сконструирован так, что бы была система с замкнутым контуром

Характеристические значения системы с замкнутым контуром определяются из матриц A, B, C и K по использованию команды eig(A+B*K*C). Характеристические значения замкнутого контура должны быть на реальных осях в комплексной области слева от точек [-5,-3,-1]. Для того, что бы не переполнялись входные значения, ни один из элементов К не может быть больше чем 4 или меньше чем -4.

Система является двух входной, двух выходной, с разомкнутым контуром, неустойчивой системой, матрицы анализа состояний будут 

Установка значений цели (goal) для характеристических значений замкнутого контура инициализируется как

goal = [-5,-3,-1];

Для обеспечения одинаковой доли для пере- или недостижения в активных целях в данном решении весовая матрица weight устанавливается как abs(goal).

Начиная с регулятора K = [-1,-1; -1,-1] сперва напишем М-файл eigfun.m.

function F = eigfun(K,A,B,C)
F = sort(eig(A+B*K*C)); % Оценка целей

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

A = [-0.5 0 0; 0 -2 10; 0 1 -2];
B = [1 0; -2 2; 0 1];
C = [1 0 0; 0 0 1]; 
K0 = [-1 -1; -1 -1]; % Инициализирует матрицу регулятора
goal = [-5 -3 -1]; % устанавливает значения goal для характеристических значений
weight = abs(goal) % устанавливает вес по одинаковой доле
lb = -4*ones(size(K0)); % устанавливает нижнюю границу для регулятора
ub = 4*ones(size(K0)); % устанавливает верхнюю границу для регулятора
options = optimset(‘Display’,’iter’); % установка параметров отображения
[K,fval,attainfactor] = fgoalattain(@eigfun,K0,…
goal,weight,[],[],[],[],lb,ub,[],options,A,B,C)

Данные пример может быть выполнен при помощи демонстрационной программы goaldemo. После 12 итераций решение будет 

Активные условия ограничений:

1
2
4
9
10

Обсуждение

Коэффициент достижения указывает, что каждая цель достигнута, по крайней мере, с вероятностью свыше 38.63% от исходных расчетных целей (goals). Активные ограничения, в случае 1 и 2, являются такими ограничениями, которые устанавливают барьер дальнейшему улучшению и для которых доля передостижения точно удовлетворена. Три ограничения по нижней границе также являются активными.

В приведенном выше расчете оптимизатор пытается получить цель меньше, чем goal. В наихудшем случае, для задачи, когда цели должны быть как можно ближе goal, задаются опции options.GoalsExactAchieve с учетом числа требуемых целей. 

Рассмотрим приведенную задачу так, как если бы нужно было, что бы все характеристические значения были равны значениям целей (goal). Решение данной задачи осуществляется запуском fgoalattain с опцией options.GoalsExactAchieve, равной 3.

options = optimset(‘GoalsExactAchieve’,3);
[K,fval,attainfactor] = fgoalattain(…
@eigfun,K0,goal,weight,[],[],[],[],lb,ub,[],options,A,B,C)

После порядка семи итераций решение будет:

В данном случае оптимизатор пытался подогнать цели к goal. Коэффициент достижения (1.0859e-20) указывает, что цели точно были достигнуты. 

Примечания:

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

Алгоритм:

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

Одна из формулировок данной задачи, что и реализовано в fgoalattain, есть задача достижения цели по Gembicki [3]. Это положено в основу структуры набора значений цели для целевой функции. Полное обсуждение многокритериальной оптимизации находится в разделе Стандартный Алгоритм.

В данной версии, дополнительная переменная используется как некая фиктивный параметр, для того, что бы одновременно минимизировать вектор цели F(x), а цель (goal) есть такой набор значений, что цели являются достижимыми. В общем случае, до начала оптимизации, не известно достигнуты ли цели goal (недостижение) или будут минимизированы меньше, чем goal (передостижение). Вектор веса (weight) контролирует относительное недостижение или передостижение целей. 

Fgoalattain использует метод Последовательного Квадратичного Программирования (SQP), который достаточно подробно описан в разделе Стандартные Алгоритмы. Модификации реализованы для линейного поиска и определителя матрицы Гессе. В случае линейного поиска функция полезности (см. [1] и [4]) используется в сочетании с предложенной в [5], [6] функцией полезности. Линейный поиск заканчивается, если какая либо из функций полезности демонстрирует улучшение. Так же используется модифицированный определитель матрицы Гессе (см. [1] и [4]), что дает преимущества для специальных типов задач. Полное описание используемых модификаций в разделе Метод Достижения Цели “Введения в Алгоритмы”. Установка опции options.MeritFunction = ‘singleobj’ задает использование функции полезности и определителя матрицы Гессе в программе fmincon.

Коэффициент достижения g определяется в данном решении. Отрицательные значения g указывают на передостижение цели (goal). Более детально используемый алгоритм можно посмотреть в разделе Реализация SQP в “Введении в Алгоритмы”, а типы процедур распечатываются под заголовком Процедуры при установке опции options.Display = ‘iter’.

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

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

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

Ссылки

1. Brayton, R.K., S.W. Director, G.D. Hachtel, and L.Vidigal, “A New Algorithm for Statistical Circuit Design Based on Quasi-Newton Methods and Function Splitting,” IEEE Transactions on Circuits and Systems, Vol. CAS-26, pp. 784-794, Sept. 1979.
2. Fleming, P.J. and A.P. Pashkevich, Computer Aided Control System Design Using a Multi-Objective Optimisation Approach, Control 1985 Conference, Cambridge, UK, pp. 174-179.
3. Gembicki, F.W., “Vector Optimization for Control with Performance and Parameter Sensitivity Indices,” Ph.D. Dissertation, Case Western Reserve Univ., Cleveland, OH, 1974.
4. Grace, A.C.W., “Computer-Aided Control System Design Using Optimization Techniques,” Ph.D. Thesis, University of Wales, Bangor, Gwynedd, UK, 1989.
5. Han, S.P., “A Globally Convergent Method For Nonlinear Programming,” Journal of Optimization Theory and Applications, Vol. 22, p. 297, 1977.
6. Powell, M.J.D., “A Fast Algorithm for Nonlineary Constrained Optimization Calculations,” Numerical Analysis, ed. G.A. Watson, Lecture Notes in Mathematics, Springer Verlag, Vol. 630, 1978.

Наверх

fminimax – решение задачи минимакс

Синтаксис:

x = fminimax(fun,x0)
x = fminimax(fun,x0,A,b)
x = fminimax(fun,x0,A,b,Aeq,beq)
x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub)
x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)
x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)
x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,…)
[x,fval] = fminimax(…)
[x,fval,maxfval] = fminimax(…)
[x,fval,maxfval,exitflag] = fminimax(…)
[x,fval,maxfval,exitflag,output] = fminimax(…)
[x,fval,maxfval,exitflag,output,lambda] = fminimax(…)

Описание:

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

• x = fminimax(fun,x0) начинает с точки x0 и находит решение минимакса от х для функции, описанной в fun.
• x = fminimax(fun,x0,A,b) решает задачу минимакса с условием линейных неравенств A*x <= b.
• x = fminimax(fun,x,A,b,Aeq,beq) ) решает задачу минимакса с условием линейных равенств Aeq*x = beqas well. Устанавливается A=[] и b=[] в случае отсутствия неравенств.
• x = fminimax(fun,x,A,b,Aeq,beq,lb,ub) определяет набор нижней и верхней границ для расчетных параметров так, что решение всегда находится в диапазоне lb <= x <= ub.
• x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) накладывает на задачу минимакса ограничения типа неравенств c(x) или равенств ceq(x), задаваемых в nonlcon. fminimax минимизирует таким образом, что c(x) <= 0 и ceq(x) = 0. Устанавливается lb=[] и/илиr ub=[] в случае отсутствия границ.
• x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) проводит оптимизацию с учетом параметров оптимизации, определенных в опциях структур
• x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,…) передает зависимые от задачи параметры P1, P2 и т.д., непосредственно в функции fun и nonlcon. Передает пустые матрицы в виде структурных нулей для A, b, Aeq, beq, lb, ub, nonlcon и опцийв случае, если эти аргументы не являются необходимыми.
• x,fval] = fminimax(…) возвращает значение целевой функции как решение от x.
• [x,fval,maxfval] = fminimax(…) возвращает максимальное значение функции как решение от x.
• [x,fval,maxfval,exitflag] = fminimax(…) возвращает значение exitflag, которое содержит выходные условия для fminimax.
• [x,fval,maxfval,exitflag,output] = fminimax(…) возвращает структурный выход с информацией об оптимизации.
• [x,fval,maxfval,exitflag,output,lambda] = fminimax(…) возвращает структурную lambda поля которой содержат множители Лагранжа, как решение от х.

Аргументы:

Входные аргументы.
Таблица 4-1. Входные аргументы. Содержит общее описание передаваемых в fminimax аргументов 

Данный раздел включает детали функционирования для fun, nonlcon и options:

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

Options

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

Примеры

Найти значения х, которые минимизирую максимальное значение

где

Сперва запишем М-файл, в котором рассчитываются пять функций от х.

function f = myfun(x)
f(1)= 2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304; % Цели
f(2)= -x(1)^2 – 3*x(2)^2;
f(3)= x(1) + 3*x(2) -18;
f(4)= -x(1)- x(2);
f(5)= x(1) + x(2) – 8;

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

x0 = [0.1; 0.1]; % задается начальное предположение о решении
[x,fval] = fminimax(@myfun,x0)

После семи итераций решение будет

x =
4.0000
4.0000
fval =
-64.0000 -2.0000 -8.0000 -0.0000

Примечания

Число целей в наихудшем случае для абсолютного значения от минимизируемого F задается в опции options.MinAbsMax. такие цели следует разделять в первых элементах F.

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

Такая задача решается запуском fminimax с следующими командами

x0 = [0.1; 0.1]; % задается начальное предположение о решении
options = optimset(‘MinAbsMax’,5); % Минимизируются абсолютные значения
[x,fval] = fminimax(@myfun,x0,[],[],[],[],[],[],[],options);

После семи итераций решение будет

x =
4.9256
2.0796
fval = 
37.2356 -37.2356 -6.8357 -7.0052 -0.9948

Если ограничения в виде равенств присутствуют, а зависимые равенства могут быть определены и удалены с помощью квадратичной подзадачи, то под заголовком Процедуры печатается ‘dependent’ (в случае если используется выходная опция options.Display=’iter’).

Зависимые равенства удаляются только тогда, когда эти равенства являются непротиворечивыми. Если система равенств является противоречивой, то подзадача будет неразрешимой и под заголовком Процедуры печатается ‘infeasible’

Алгоритм:

fminimax использует метод последовательного квадратичного программирования (SQP) [1]. Модификации касаются линейного поиска и матрицы Гессе. В случае линейного поиска используется точное значение функции полезности (смотри [2] и [4]) совместно с функцией полезности, предложенной в [3] и [5]. Линейный поиск заканчивается, когда функция полезности показывает улучшение. Так же используется модифицированная матрица Гессе, что дает выигрыш для специализированной структуры данной задачи. При установке опции options.MeritFunction = ‘singleobj’ используется функция полезности и матрица Гессе в fmincon.

Для большей детализации используемого алгоритма и типов процедур, распечатываемых под заголовком Процедуры при установке опции options.Display=’iter’, смотри Реализация SQP в “Введении в Алгоритмы”. 

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

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

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

@ (function_handle), fgoalattain, lsqnonlin, optimset

Литература:

1. Brayton, R.K., S.W. Director, G.D. Hachtel, and L.Vidigal, “A New Algorithm for Statistical Circuit Design Based on Quasi-Newton Methods and Function Splitting,” IEEE Trans. Circuits and Systems, Vol. CAS-26, pp. 784-794, Sept. 1979.
2. Grace, A.C.W., “Computer-Aided Control System Design Using Optimization Techniques,” Ph.D. Thesis, University of Wales, Bangor, Gwynedd, UK, 1989.
3. Han, S.P., “A Globally Convergent Method For Nonlinear Programming,” Journal of Optimization Theory and Applications, Vol. 22, p. 297, 1977.
4. Madsen, K. and H. Schjaer-Jacobsen, “Algorithms for Worst Case Tolerance Optimization,” IEEE Transactions of Circuits and Systems, Vol. CAS-26, Sept. 1979.
5. Powell, M.J.D., “A Fast Algorithm for Nonlineary Constrained Optimization Calculations,” Numerical Analysis, ed. G.A. Watson, Lecture Notes in Mathematics, Springer Verlag, Vol. 630, 1978.

Наверх

lsqlin – решение линейной задачи с ограничениями методом наименьших квадрато

такие, что
где С, A и Aeq есть матрицы d, b, beq, lb, ub и x есть векторы.

Синтаксис:

x = lsqlin(C,d,A,b)
x = lsqlin(C,d,A,b,Aeq,beq)
x = lsqlin(C,d,A,b,Aeq,beq,lb,ub)
x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0)
x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options)
x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options,p1,p2,…)
[x,resnorm] = lsqlin(…)
[x,resnorm,residual] = lsqlin(…)
[x,resnorm,residual,exitflag] = lsqlin(…)
[x,resnorm,residual,exitflag,output] = lsqlin(…)
[x,resnorm,residual,exitflag,output,lambda] = lsqlin(…)

Описание:

• x = lsqlin(C,d,A,b) решает систему C*x=d с точки зрения метода наименьших квадратов при условии A*x<=b, где C имеет размерность m-х-n.
• x = lsqlin(C,d,A,b,Aeq,beq) решает указанные выше задачу при условии дополнительного выполнения ограничений в виде равенств Aeq*x = beq. Если нет неравенств, то устанавливается A=[] и b=[].
• x = lsqlin(C,d,A,b,Aeq,beq,lb,ub) определяет набор нижних и верхних границ для проектируемых переменных х, так что решение всегда находится в диапазоне lb <= x <= ub. Если нет неравенств, то устанавливается Aeq=[] и beq=[].
• x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0) устанавливает начальную точку как х0. В случае отсутствия границ устанавливается lb=[] и b=[].
• x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options) проводит оптимизацию с определенными в структурной опции параметрами оптимизации.
• x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options,p1,p2,…) передает зависящие от типа задачи параметры р1, р2 и т.д. непосредственно в множители функции Якобина, если она существует. Необходимо определить множители функции Якобина с помощью параметра JacobMult в options.
• [x,resnorm] = lsqlin(…) возвращает значение квадрата нормы невязки от х. norm(C*x-d)^2.
• [x,resnorm,residual] = lsqlin(…) возвращает значение невязки, C*x-d.
• [x,resnorm,residual,exitflag] = lsqlin(…) возвращает значение exitflag, которое содержит описание выходных условий.
• [x,resnorm,residual,exitflag,output] = lsqlin(…) возвращает структурный выход с информацией об оптимизации
• [x,resnorm,residual,exitflag,output,lambda] = lsqlin(…) возвращает структурную lambda с полями, содержащими множители Лагранжа в виде решения от х.

Аргументы:

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

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

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

Options

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

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

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

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

Примеры:

Найти решение метод наименьших квадратов для переопределенной системы при условии, что  и .

Сперва введем коэффициенты матриц и верхние и нижние границы.

C = [
    0.9501    0.7620    0.6153    0.4057
    0.2311    0.4564    0.7919    0.9354
    0.6068    0.0185    0.9218    0.9169
    0.4859    0.8214    0.7382    0.4102
    0.8912    0.4447    0.1762    0.8936];
d = [
    0.0578
    0.3528
    0.8131
    0.0098
    0.1388];
A =[
    0.2027    0.2721    0.7467    0.4659
    0.1987    0.1988    0.4450    0.4186
    0.6037    0.0152    0.9318    0.8462];
b =[
    0.5251
    0.2026
    0.6721];
lb = -0.1*ones(4,1);
ub = 2*ones(4,1);

Далее обратимся к программе метода наименьших квадратов с линейными ограничениями

[x,resnorm,residual,exitflag,output,lambda] = …

lsqlin(C,d,A,b,[ ],[ ],lb,ub);

Введя x, lambda.ineqlin, lambda.lower, lambda.upper получим

x =
   -0.1000
   -0.1000
    0.2152
    0.3502
lambda.ineqlin =
         0
    0.2392
         0
lambda.lower =
    0.0409
    0.2784
         0
         0
lambda.upper =
         0
         0
         0
         0

Ненулевые элементы векторов в полях lambda указывают на активные ограничения при решении. В нашем случае, второе ограничения в виде неравенств (в lambda.ineqlin) и первое нижнее и второе нижнее граничные ограничения (в lambda.lower) являются активными ограничениями (т.е. решение находится на ограничительных условиях).

Примечания:

В случае отсутствия ограничений следует использовать оператор . Смотри, например, x= Ab.

В общем, lsqlin определяет локальное решение.

По-видимому, более точные численные результаты будут, если с помощью Aeq и beq явно определить равенства вместо неявного использования lb и ub.

Крупно-масштабная оптимизация. Если х0 не является строго допустимым, то lsqlin выберет новую строго допустимую (центрированную) стартовую точку.

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

Алгоритм:

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

Средне-масштабная оптимизация. lsqlin при установке options.LargeScale как ‘off’, или когда приводятся линейные неравенства или равенства, базируется на методе quadprog, который использует метод активной системы, аналогично тому, что описано в [2]. Этот метод находит начальные решения путем решения задачи линейного программирования. Смотри Квадратичное Программирование в разделе “Введении в Алгоритмы”

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

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

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

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

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

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

         Предупреждение. Данная постановка задачи является пока недопустимой для разреженных матриц. Для разрешимости производится преобразование до полных.

Lsqlin дает предупреждение, если задача является недопустимой

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

Нет допустимого решения

В этом случае lsqlin проводит минимизацию для ограничения с наибольшим нарушением.

Когда ограничения типа равенств являются недопустимыми, то lsqlin дает предупреждение

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

Нет допустимого решения

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

К настоящему времени имеются только уровни отображения, при использовании опции параметров Отображения, ‘off’ и ‘final’; итерационный вывод с опцией ‘iter’ отсутствует.

Смотри также: lsqnonneg, quadprog

Литература:

1. Coleman, T.F. and Y. Li, “A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on Some of the Variables”, SIAM Journal on Optimization, Vol. 6, Number 4, pp. 1040-1058, 1996.
2. Gill, P.E., W. Murray, and M.H. Wright, Practical Optimization, Academic Press, London, UK, 1981.

Наверх

lsqnonneg – решение неотрицательной задачи методом наименьших квадрато

, такие, что,

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

Синтаксис:

x = lsqnonneg(C,d)
x = lsqnonneg(C,d,x0)
x = lsqnonneg(C,d,x0,options)
[x,resnorm] = lsqnonneg(…)
[x,resnorm,residual] = lsqnonneg(…)
[x,resnorm,residual,exitflag] = lsqnonneg(…)
[x,resnorm,residual,exitflag,output] = lsqnonneg(…)
[x,resnorm,residual,exitflag,output,lambda] = lsqnonneg(…)

Описание:

• x = lsqnonneg(C,d) возвращает вектор х, который является минимумом нормы (C*x-d) при условии x >= 0. С и d должны быть реальными.
• x = lsqnonneg(C,d,x0) использует точку х0 как стартовую при условии, что все x0 >= 0, в противном, используется вариант по умолчанию. Принимаемая по умолчанию точка есть начало координат (вариант по умолчанию принимается когда x0==[] или заданы только два входных аргумента).
• x = lsqnonneg(C,d,x0,options) проводит оптимизацию с определенными в структурной опции параметрами оптимизации.
• [x,resnorm] = lsqnonneg(…) возвращает значение квадрата удвоенной нормы невязки, norm(C*x-d)^2.
• [x,resnorm,residual] = lsqnonneg(…) возвращает значение невязки, C*x-d.
• [x,resnorm,residual,exitflag] = lsqnonneg(…) возвращает значение exitflag, которое содержит описание выходных условий для lsqnonneg.
• [x,resnorm,residual,exitflag,output] = lsqnonneg(…) возвращает структурный выход с информацией об оптимизации.
• [x,resnorm,residual,exitflag,output,lambda] = lsqnonneg(…) возвращает множители Лагранжа как вектор lambda.

Аргументы:

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

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

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

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

Примеры:

Сравнение решения безусловной задачи методом наименьших квадратов с решением с помощью lsqnonneg для случая 4 на 2.

C = [
     0.0372    0.2869
     0.6861    0.7071
     0.6233    0.6245
     0.6344    0.6170];
d = [
     0.8587
     0.1781
     0.0747
     0.8405];
[Cd, lsqnonneg(C,d)] =
    -2.5627    0
     3.1108 0.6929

[norm(C*(Cd)-d), norm(C*lsqnonneg(C,d)-d)] =
        0.6674 0.9118

Решение с помощью lsqnonneg не подходит достаточно хорошо как с помощью метода наименьших квадратов. Однако неотрицательное решение методом наименьших квадратов имеет неотрицательные компоненты.

Алгоритм:

lsqnonneg использует описанный в [1] алгоритм. Данный алгоритм стартует с некого набора возможных базовых векторов и вычисляет соотнесенный двойной вектор lambda. Далее выбирается базовый вектор, соответствующий максимальному значению lambda для того, что бы обменять это базис взамен другого возможного кандидата. Так продолжается до тех пор, пока не станет .

Примечания:

Задача с методом наименьших квадратов для неотрицательных значений есть подмножество задач с методом наименьших квадратов и линейными ограничениями. 

Таким образом, когда С имеет больше строк, чем колонок (т.е. система является переопределенной)

эквивалентно тому, что

за исключением того, что .

Для задач с порядком больше 20 lsqlin может быть быстрее, чем lsqnonneg, с другой стороны lsqnonneg обычно является боле эффективной программой.

Смотри так же lsqlin, optimset

Литература:

1. Lawson, C.L. and R.J. Hanson, Solving Least Squares Problems, Prentice-Hall, Chapter 23, p. 161, 1974.

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

т.е при заданном массиве аргументов xdata и массиве функций ydata найти коэффициенты х, которые “лучше всего” удовлетворяют уравнению F(x, xdata);

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

Функция lsqcurvefit использует тот же самый алгоритм, что и lsqnonlin. Ее назначение состоит в том, что бы получить интерфейс, спроектированной специально для задач подбора данных. 

Синтаксис

x = lsqcurvefit(fun,x0,xdata,ydata) 
x = lsqcurvefit(fun,x0,xdata,ydata,lb,ub)
x = lsqcurvefit(fun,x0,xdata,ydata,lb,ub,options) 
x = lsqcurvefit(fun,x0,xdata,ydata,lb,ub,options,P1,P2,…)
[x,resnorm] = lsqcurvefit(…) 
[x,resnorm,residual] = lsqcurvefit(…)
[x,resnorm,residual,exitflag] = lsqcurvefit(…) 
[x,resnorm,residual,exitflag,output] = lsqcurvefit(…)
[x,resnorm,residual,exitflag,output,lambda] = lsqcurvefit(…) 
[x,resnorm,residual,exitflag,output,lambda,jacobian] = lsqcurvefit(…) 

Описание.

lsqcurvefit решает задачи нелинейного подбора данных. Для lsqcurvefit вводится задаваемая пользователем функция F(x, xdata), которая производит значение вектора. Размер вектора в задаваемой пользователем функции должен иметь тот же самый размер, что и ydata. 

x = lsqcurvefit(fun,x0,xdata,ydata) начинает с точки х0 и находит коэффициенты х, которые наилучшим образом подбирают нелинейную функцию fun(x,xdata) по данным ydata (в смысле метода наименьших квадратов). ydata должно иметь тот же самый размер, что и возвращаемый в fun.вектор F (или матрица). 

x = lsqcurvefit(fun,x0,xdata,ydata,lb,ub) ) определяет набор нижних и верхних границ для проектируемых переменных х, так что решение всегда находится в диапазоне lb <= x <= ub. 

x = lsqcurvefit(fun,x0,xdata,ydata,lb,ub,options) проводит оптимизацию с определенными в структурной опции параметрами оптимизации. Если ограничений нет, то эта команда передает пустую матрицу в lb и ub 

x = lsqcurvefit(fun,x0,xdata,ydata,lb,ub,options,P1,P2,…) передает зависящие от типа задачи параметры P1, P2 и т.д. непосредственно в функцию fun. Передает пустые матрицы заменители в опции, которые в качестве используемых по умолчанию парамктров. 

[x,resnorm] = lsqcurvefit(…) возвращает значение квадрата нормы невязки от х.
sum{(fun(x,xdata)-ydata).^2}. 

[x,resnorm,residual] = lsqcurvefit(…) возвращает значение невязки fun(x,xdata)-ydata, как решение от х. 

[x,resnorm,residual,exitflag] = lsqcurvefit(…) возвращает значение exitflag, которое содержит описание выходных условий. 

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

[x,resnorm,residual,exitflag,output,lambda] = lsqcurvefit(…) возвращает структурную lambda с полями, содержащими множители Лагранжа в виде решения от х. 

[x,resnorm,residual,exitflag,output,lambda,jacobian] = 99 99lsqcurvefit(…) Возвращает Якобиан от fun как решение от х. 

Аргументы

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

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

Options

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

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

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

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

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

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

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

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,… есть дополнительные параметры, передаваемые в lsqcurvefit (и в fun).

lsqcurvefit (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 явно не формируется.

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

Векторы xdata и ydata имеют длину n. Требуется найти такие коэффициенты х, что бы они лучше всего подходили к уравнению

то есть нужно минимизировать 

где F(x,xdata) = x(1)*xdata.^2 + x(2)*sin(xdata) + x(3)*xdata.^3, начнем с точки x0 = [0.3, 0.4, 0.1].

Сперва запишем М-файл, который возвращает F (F имеет n компонентов)

function F = myfun(x,xdata)

F = x(1)*xdata.^2 + x(2)*sin(xdata) + x(3)*xdata.^3;

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

% Предположим, что xdata и ydata определены экспериментально

xdata = [3.6 7.7 9.3 4.1 8.6 2.8 1.3 7.9 10.0 5.4];

ydata = [16.5 150.6 263.1 24.7 208.5 9.9 2.7 163.9 325.0 54.3];

x0 = [10, 10, 10] % Начальное предположение

[x,resnorm] = lsqcurvefit(@myfun,x0,xdata,ydata)

Отметим, во время вызова lsqcurvefit предполагается, что xdata и ydata и являются векторами одного и того же размера. Они должны иметь один и тот же размер, поскольку возвращаемое в fun значение F должно иметь тот же самый размер, что и ydata.

После 33 оценок функции данный пример дает решение

x = 

0.2269 0.3385 0.3021

% невязка или сумма квадратов

resnorm = 

6.2950

Невязка не равна нулю, потому что в данном случае имеет место некоторый шум (экспериментальные ошибки) в представленных данных

Алгоритм

Оптимизация алгоритмов большой размерности.

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

Оптимизация алгоритмов средней размерности.

lsqcurvefit при установке 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, (где ограничения типа равенств уже могут быть включены.)

Ограничения

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

lsqcurvefit оперирует только с реальными переменными (задаваемая пользователем функция должна возвращать только реальные значения). Если х имеет комплексные значения, то эти переменные должны быть разделены на мнимую и реальные части.

Оптимизация алгоритмов большой размерности.

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

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

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

Смотри также

@ (function_handle), , lsqlin, lsqnonlin, lsqnonneg, 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.

Наверх

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:

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

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

Options

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

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

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

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

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

Примеры:

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

начнем с точки 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.

Наверх

fzero – нахождение нулей функции одной переменно

Синтаксис:

x = fzero(fun,x0)
x = fzero(fun,x0,options)
x = fzero(fun,x0,options,P1,P2,…)
[x,fval] = fzero(…)
[x,fval,exitflag] = fzero(…)
[x,fval,exitflag,output] = fzero(…)

Описание:

x = fzero(fun,x0) Пытается найти ноль для fun вблизи x0, если x0 есть скаляр. Возвращаемое в fzero значение х находится около точки, где fun меняет знак, или NaN в случае неудачи поиска. В этом случае поиск заканчивается, если интервал поиска расширяется до значений бесконечность, NaN или будут найдены комплексные значения.

Если вектор х0 имеет длину два, то fzero полагает, что х0 есть некий интервал, где знак fun(x0(1)) отличается от знака fun(x0(2)). Если это не верно, то будет иметь место ошибка. Вызов fzero с таким интервалом гарантирует, что fzero возвратит значение, где функция fun меняет знак. 

Примечание. Вызов fzero с неким интервалом (х0 имеет два элемента) часто решается быстрее, чем его вызов со скаляром х0.

• x = fzero(fun,x0,options) проводит оптимизацию с определенными в структурной опции параметрами оптимизации.
• x = fzero(fun,x0,options,P1,P2,…) задает дополнительные аргументы P1, P2 и т.д., которые передаются в целевую функцию fun. Если опции не установлены, то в качестве заменителя используется options = [].
• [x,fval] = fzero(…) возвращает значение целевой функции fun как решение от х.
• [x,fval,exitflag] = fzero(…)возвращает значение exitflag, которое содержит описание выходных условий.
• [x,fval,exitflag,output] = fzero(…) возвращает структурный выход с информацией об оптимизации.

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

Аргументы:

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

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

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

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

Примеры:

Найти значение нуля функции sin в точке вблизи 3

x = fzero(@sin,3)
x =
    3.1416

Найти значение нуля функции cos между 1 и 2

x = fzero(@cos,[1 2])
x =
    1.5708

Отметим, что cos(1) и cos(2) отличаются по знаку.

Найти ноль для функции

;

запишем М-файл под именем f.m.

function y = f(x)
y = x.^3-2*x-5;

Найти ноль вблизи точки 2

z = fzero(@f,2)
z =
    2.0946

Поскольку данная функция является полиноминальной, то основные корни ([1 0 -2 -5]) определяют один и тот же реальный ноль, а так же будет еще комплексно сопряженная паря нулей:

    2.0946
    -1.0473 + 1.1359i
    -1.0473 – 1.1359i

Алгоритм:

Команда fzero использует М-файл. Первоначально предложенный Деккером алгоритм основан на комбинации методов двоичного поиска, метода секущих и обратной квадратичной интерполяции. Версия на Алголе-60 (с некоторыми улучшениями) приведена в [1]. Версия на Фортране, что оставляет основу М-файла для fzero, приведена в [2].

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

Коканда fzero определяет точку, где функция меняет знак. Если функция непрерывная, то это так же точка, где данная функция имеет близкое к нулю значение. Если функция не является непрерывной, то fzero может вместо нулей возвращать значения, которые являются разрывными точками. Например, fzero(@tan,1) возвращает 1.5708, что является точкой разрыва для тангенса.

Более того, команда fzero определяет ноль как точку, функция пересекает ось х. Точки, где функция касается, но не пересекает, оси х, не являются достоверными нулями. Например, y = x.^2 есть парабола, которая касается оси х в точке 0. Однако, поскольку функция нигде не пересекает ось х, то нулей не будет найдено. В случае функций без достоверных нулей, fzero работает до тех пор, пока не встретятся Inf, NaN или комплексное значение.

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

@ (function_handle), , fminbnd, fsolve, inline, optimset, roots

Литература:

• [1] Brent, R., Algorithms for Minimization Without Derivatives, Prentice-Hall, 1973.
• [2] Forsythe, G. E., M. A. Malcolm, and C. B. Moler, Computer Methods for Mathematical Computations, Prentice-Hall, 1976.

Наверх

fsolve – решение системы нелинейных уравнений

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

Синтаксис:

x = fsolve(fun,x0)
x = fsolve(fun,x0,options)
x = fsolve(fun,x0,options,P1,P2, … )
[x,fval] = fsolve(…)
[x,fval,exitflag] = fsolve(…)
[x,fval,exitflag,output] = fsolve(…)
[x,fval,exitflag,output,jacobian] = fsolve(…)

Описание:

fsolve находит корни (нули) системы нелинейных уравнений.

• x = fsolve(fun,x0) начинает с точки x0 и пытается решить описанные в fun уравнения.
• x = fsolve(fun,x0,options) проводит оптимизацию с определенными в структурной опции параметрами оптимизации.
• x = fsolve(fun,x0,options,P1,P2,…) передает зависящие от типа задачи параметры P1, P2 и т.д. непосредственно в функции fun. Передает пустые матрицы для опций для того, что бы использовать принимаемые по умолчанию значения опций.
• [x,fval] = fsolve(fun,x0) возвращает значение целевой функции fun как решение от х.
• [x,fval,exitflag] = fsolve(…) возвращает значение exitflag, которое содержит описание выходных условий.
• [x,fval,exitflag,output] = fsolve(…) возвращает структурный выход с информацией об оптимизации
• [x,fval,exitflag,output,jacobian] = fsolve(…) возвращает Якобиан от fun как решение от x.

Аргументы:

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

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

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

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

Для крупно-масштабной или большой размерности задачи оптимальность первого порядка есть бесконечная норма градиента g = JTF (смотри нелинейный среднеквадратичный метод) 

Options

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

Для детальной информации смотри Таблицу 4-3, Параметры Опций Оптимизации.

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

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

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

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

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

Примеры:

Пример 1. В данном примере находятся нули для системы из двух уравнений и двух неизвестных

Таким образом, необходимо решить следующую систему уравнений от х

Начнем с точки x0 = [-5 -5].

Сперва запишем М-файл для расчета F или значений уравнений от х

function F = myfun(x)
F = [2*x(1) – x(2) – exp(-x(1));
   -x(1) + 2*x(2) – exp(-x(2))];

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

x0 = [-5; -5]; % примем начальное приближение за решение
options=optimset(‘Display’,’iter’); %Опция выходного отображения
[x,fval] = fsolve(@myfun,x0,options) % вызов оптимизатора

после 28 обращений к функциям нули будут найдены.

Оптимизация завершена успешно:

Относительное изменение значений функции меньше, чем в OPTIONS.TolFun

x =
    0.5671
    0.5671

fval =
    1.0e-008 *
    -0.5320
    -0.5320

Оптимизация завершена успешно:

Относительное изменение значений функции меньше, чем в OPTIONS.TolFun

x =
    0.5671
    0.5671

fval =
    1.0e-08 *
    -0.5320
    -0.5320

Пример 2. Найти матрицу x, которая удовлетворяет уравнению

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

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

function F = myfun(x)
F = x*x*x-[1,2;3,4];

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

x0 = ones(2,2); % примем начальное приближение за решение
options = optimset(‘Display’,’off’); % Выключим отображение
[x,Fval,exitflag] = fsolve(@myfun,x0,options) 

Решение будет

x =
    -0.1291    0.8602
    1.2903    1.1612 

Fval =
    1.0e-03 *
    0.1541    -0.1163
    0.0109    -0.0243

exitflag =
    1

и остаток будет близок к нулю.

sum(sum(Fval.*Fval))
ans =
    3.7974e-008

Примечания:

Если система уравнений является линейной, то для ускорения и повышения точности следует использовать (оператор обратный слэш – смотри help slash). Например. Необходимо решить следующую систему линейных уравнений

Данная задача формулируется и решается как

A = [ 3 11 -2; 1 1 -2; 1 -1 1];
b = [ 7; 4; 19];
x = Ab
x =
    13.2188
    -2.3438
    3.4375

Алгоритм:

Данный метод основан на алгоритме метода нелинейных среднеквадратичных отклонений, используемого в lsqnonlin. Достоинство используемого метода среднеквадратичных отклонений состоит в том, что данная система уравнений не равна нулю вследствие малых погрешностей и потому, что она как раз не имеет нулей, кстати алгоритм приходит в точку с малым остатком. Однако, если Якобиан системы является вырожденным, то алгоритм может сходиться в точку, неявляющуюся решением системы уравнений (Смотри ниже Ограничения и Диагностика). 

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

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

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

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

fsolve может сходиться к ненулевой точке и давать следующие сообщения:

Оптимизатор затормозился в точке, которая не является минимумом.

Повторите расчет с новой начальной точки. 

В этом случае снова выполните fsolve но с другой начальной точки.

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

Разрешаемая функция должна быть непрерывной. В случае успеха fsolve дает только один корень. fsolve может сходиться к ненулевой точке, то в этом случае необходимо пытаться стартовать с другой точки. 

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

Крупно-масштабная оптимизация. В настоящее время, если Якобиан задан аналитически в fun, то параметр опции DerivativeCheck нельзя использовать в крупно-масштабном методе для проведения сравнения аналитического Якобиана с конечно-разностным Якобианом. Вместо этого, для контроля производных используется средне-масштабный метод при установке опции MaxIter как 0 итераций. Далее, задача запускается снова уже с крупно-масштабным методом. Смотри Таблицу 1-4, Область Определения и Требования к Крупо-Масштабным Задачам относительно формулировки задачи и требуемой информации. 

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

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

inline, lsqcurvefit, lsqnonlin, optimset

Литература:

1. [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. [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. [3] Dennis, J. E. Jr., “Nonlinear Least Squares,” State of the Art in Numerical Analysis, ed. D. Jacobs, Academic Press, pp. 269-312.
4. [4] Levenberg, K., “A Method for the Solution of Certain Problems in Least Squares,” Quarterly Applied Mathematics 2, pp. 164-168, 1944.
5. [5] Marquardt, D., “An Algorithm for Least-squares Estimation of Nonlinear Parameters,” SIAM Journal Applied Mathematics, Vol. 11, pp. 431-441, 1963.
6. [6] More, J. J., “The Levenberg-Marquardt Algorithm: Implementation and Theory,” Numerical Analysis, ed. G. A.
7. Watson, Lecture Notes in Mathematics 630, Springer Verlag, pp. 105-116, 1977.

Наверх

linprog – решение задачи линейного программировани

 такие, что 

где f, x, b, beq, lb и ub есть векторы и A и Aeq есть матрицы.

Синтаксис:

x = linprog(f,A,b,Aeq,beq)
x = linprog(f,A,b,Aeq,beq,lb,ub)
x = linprog(f,A,b,Aeq,beq,lb,ub,x0)
x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
[x,fval] = linprog(…)
[x,fval,exitflag] = linprog(…)
[x,fval,exitflag,output] = linprog(…)
[x,fval,exitflag,output,lambda] = linprog(…)

Описание:

Linprog решает задачу линейного программирования.

• x = linprog(f,A,b) находит min f’*x при условии, что A*x <= b.
• x = linprog(f,A,b,Aeq,beq) решает указанные выше задачу при условии дополнительного выполнения ограничений в виде равенств Aeq*x = beq. Если нет неравенств, то устанавливается A=[] и b=[].
• x = linprog(f,A,b,Aeq,beq,lb,ub) определяет набор нижних и верхних границ для проектируемых переменных х, так что решение всегда находится в диапазоне lb <= x <= ub. Если нет неравенств, то устанавливается Aeq=[] и beq=[].
• x = linprog(f,A,b,Aeq,beq,lb,ub,x0) устанавливает начальную точку как х0. Эта опция имеет место только для средне-масштабного алгоритма (options.LargeScale равна ‘off’). Принимаемый по умолчанию крупно-масштабный алгоритм игнорирует любую стартовую точку.
• x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) проводит оптимизацию с определенными в структурной опции параметрами оптимизации.
• [x,fval] = linprog(…) возвращает значение целевой функции fun как решение от х: fval = f’*x.
• [x,lambda,exitflag] = linprog(…) возвращает значение exitflag, которое содержит описание выходных условий.
• [x,lambda,exitflag,output] = linprog(…) возвращает структурный выход с информацией об оптимизации
• [x,fval,exitflag,output,lambda] = linprog(…) Возвращает структурную lambda, чьи поля включают в себя множители Лагранжа как решение от х. 

Аргументы:

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

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

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

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

Options:

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

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

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

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

Примеры:

Найти такое х, что является минимумом от

при условии, что

Сперва введем коэффициенты

f = [-5; -4; -6]
A = [1 -1  1
    3    2    4
    3    2    0];
b = [20; 42; 30];
lb = zeros(3,1);

Далее обратимся к программе линейного программирования

[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb);

Вводя x, lambda.ineqlin и lambda.lower получим

x = 
    0.0000
    15.0000
    3.0000

lambda.ineqlin =
    0
    1.5000
    0.5000

lambda.lower =
    1.0000
    0
    0

Ненулевые элементы векторов в полях lambda указывают на активные ограничения при решении. В нашем случае, второе и третье ограничения в виде неравенств (в lambda.ineqlin) и первое нижнее граничное ограничение (в lambda.lower) являются активными ограничениями (т.е. решение находится на ограничительных условиях).

Алгоритм:

Крупно-масштабная оптимизация. Крупно-масштабный метод основан на LIPSOL (Линейное Решение для Внутренней Точки, [3]), которое является вариантом алгоритма предиктор-корректор Меротра ([2]), метод одновременного решения прямой и двойственной задач с внутренней точкой. Перед тем, как алгоритм начнет итерации, выполняется ряд подготовительных шагов. Смотри Крупно-Масштабное Линейное Программирование. 

Средне-масштабная оптимизация. Linprog использует основанный на алгоритме квадратичного программирования метод проекций. linprog имеет активный набор методов и, таким образом, является вариантом хорошо известного симплексного метода для линейного программирования [1]. Он находит начальное допустимое решение путем первоначального решения задачи линейного программирования. 

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

Крупно-масштабная оптимизация. На первой стадии алгоритм может включать некоторую предподготовку ограничений (смотри Крупно-Масштабное Линейное Программирование в разделе “Крупно-Масштабный Алгоритм”). При этом может иметь место несколько ситуаций, когда linprog выдает сообщения о недопустимости. В каждом случае возвращаемый в linprog аргумент exitflag устанавливается в отрицательное значение, что указывает на ошибку. 

Если в строке Aeq определены все нули, а соответствующий элемент beq не равен нулю, то выходное сообщение будет

Если для одного из элементов х обнаружено, что он не ограничен снизу, то выходное сообщение будет

Если одна из строк Aeq имеет только один ненулевой элемент, то присваиваемое значение для х вызывается как одноэлементное значение. В этом случае значение данной компоненты х может быть вычислено из Aeq и beq. Если вычисленное значение противоречит другому ограничивающему условию, то выходное сообщение будет

Если одноэлементная переменная может быть найдена, но решение противоречит верхней и нижней границам, то выходное сообщение будет

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

Сразу после окончания предпроцессорной подготовки начинает работать итеративный раздел алгоритма до тех пор, пока не встретится какой-нибудь критерий останова. (Относительно большей информации о невязках, двойственной проблеме и связанных критериях останова смотри Крупно-Масштабное Линейное Программирование в разделе “Крупно-Масштабный Алгоритм”). Если невязки растут, вместо того, что бы становиться меньше, или невязки ни растут, ни сжимаются, то, соответственно, проявляется одно из следующих завершающих сообщений.

или

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

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

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

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

Когда ограничения типа равенств являются противоречивыми, linprog дает

Решения без ограничений привели к предупреждению.

В этом случае linprog возвращает значение х, которое удовлетворяет условиям ограничения

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

Средне-масштабная оптимизация. К настоящему времени имеются только уровни отображения ‘off’ и ‘final’, по применению параметров отображения, итерационный выход по ‘iter’ не установлен.

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

quadprog

Литература:

• [1] Dantzig, G.B., A. Orden, and P. Wolfe, “Generalized Simplex Method for Minimizing a Linear from Under Linear Inequality Constraints,” Pacific Journal Math. Vol. 5, pp. 183-195.
• [2] Mehrotra, S., “On the Implementation of a Primal-Dual Interior Point Method,” SIAM Journal on Optimization, Vol. 2, pp. 575-601, 1992.
• [3] Zhang, Y., “Solving Large-Scale Linear Programs by Interior-Point Methods Under the MATLAB Environment,” 
• Technical Report TR96-01, Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, MD, July 1995.

Наверх

quadprog – решить квадратичную задачу математического программировани

, такую что

где H, A и Aeq есть матрицы, а f, b, beq, lb, ub и x есть векторы.

Синтаксис

x = quadprog(H,f,A,b)
x = quadprog(H,f,A,b,Aeq,beq)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options,p1,p2,…)
[x,fval] = quadprog(…)
[x,fval,exitflag] = quadprog(…)
[x,fval,exitflag,output] = quadprog(…)
[x,fval,exitflag,output,lambda] = quadprog(…)

Описание

• x = quadprog(H,f,A,b) возвращает вектор х, который минимизирует 1/2*x’*H*x + f’*x при условии A*x <= b.
• x = quadprog(H,f,A,b,Aeq,beq) решает указанную выше задачу с дополнительным выполнением ограничений типа равенства Aeq*x = beq.
• x = quadprog(H,f,A,b,Aeq,beq,lb,ub) определяет набор нижних и верхних границ для проектируемой переменной х, так что бы решение находилось в диапазоне lb <= x <= ub. 
• x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) устанавливает стартовую точку как x0.
• x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) ) проводит оптимизацию с определенными в структурной опции параметрами оптимизации.
• x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options,p1,p2,…) передает параметры p1,p2,… в функцию множителей матрицы Гессе, определенную с помощью, если он имеется, параметра HessMult в данной структуре опций.
• [x,fval] = quadprog(…) возвращает значение целевой функции от х. fval = 0.5*x’*H*x + f’*x.
• [x,fval,exitflag] = quadprog(…) возвращает значение exitflag, который описывает выходные условия в quadprog.
• [x,fval,exitflag,output] = quadprog(…) возвращает структурный выход с информацией об оптимизации.
• [x,fval,exitflag,output,lambda] = quadprog(…) возвращает структурную lambda с полями, содержащими множители Лагранжа в виде решения от х.

Аргументы:

Входные аргументы.
Таблица 4-1, Входные аргументы, содержит общее описание аргументов, передаваемых в quadprog. Options задает функционально-специфические детали для параметров опций.

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

Options

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

Параметры для установки алгоритмического предпочтения

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

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

Примеры:

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

при условии, что

Сперва отметим, что данная в матичной записи будет как

где

, , 

Введем эти коэффициенты матриц

Далее запустим программу квадратичного программирования.

Что генерирует решение

x =
     0.6667
     1.3333
fval =
    -8.2222
exitflag =
     1
output =
       iterations: 3
        algorithm: ‘medium-scale: active-set’
    firstorderopt: []
     cgiterations: []
lambda.ineqlin
ans =
    3.1111
    0.4444
         0
lambda.lower
ans =
     0
     0

Ненулевые элементы вектора в полях lambda указывают на активные ограничения в данной задаче. В данном случае, первый и второй ограничения в виде неравенств (lambda.ineqlin) являются активными ограничениями (т.е. решение находится в пределах таких границ). Для данной задачи, все нижние границы являются неактивными.

Примечания:

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

Вероятно, более лучшие численные результаты будут, если с помощью Aeq и beq явно специфицировать данные равенства вместо неявного использования lb и ub.

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

Крупно-масштабная оптимизация. Если х0 не задано или х0 не является строго допустимым, то quadprog выберет новую строго допустимую (центрированную) стартовую точку

Если поставлена задача с ограничениями типа равенств и quadprog выявит отрицательную кривизну, то оптимизация заканчивается потому, что ограничения не достаточно выделяют область. В данном случае, exitflag возвратит значение -1, отобразится сообщение (даже не смотря на то, параметр отображения установлен как ‘off’), а возвращаемый х не будет решением, а направлением отрицательной кривизны по отношению к H.

Для задач с просто нижними и верхними границами (lb, ub), quadprog выходит на основе значения TolFun. Для задач только с ограничениями типа равенств (Aeq, beq), то выход на основе TolPCG. Корректировка TolFun и TolPCG влияет на выходные результаты. TolX используется в обоих типах задач.

Алгоритм:

Крупно-масштабная оптимизация. В случае если приведенная в lsqlin имеет только верхние и нижние границы, т.е. не определены линейные неравенства или равенства, то по умолчанию принимается крупно-масштабный алгоритм. Или, если приведенная в quadprog задача имеет только линейные равенства, т.е. не специфицированы ни верхние и нижние границы, ни линейные неравенства, то по умолчанию принимается крупно-масштабный алгоритм.

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

Средне-масштабная оптимизация. lsqlin при установке options. quadprog использует метод активной системы, который также является проекционным методом, аналогично тому, что описано в [2]. Этот метод находит начальные решения путем решения задачи линейного программирования. Данный метод так же обсуждается в разделе Стандартные Алгоритмы.

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

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

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

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

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

Средне-масштабная оптимизация. Если решение является недопустимым, то quadprog дает предупреждение

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

В этом случае quadprog проводит минимизацию для ограничения с наибольшим нарушением 

Когда ограничения типа равенств являются противоречащими, то quadprog дает предупреждение

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

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

        Предупреждение. Решение не ограничено и бесконечно
        Ограничения не являются достаточно жесткими.

В данном случае quadprog возвращает значение х, которое удовлетворяет данным ограничениям.

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

К настоящему времени имеются только уровни отображения, при использовании опции параметров Отображения, ‘off’ и ‘final’; итерационный вывод с опцией ‘iter’ отсутствует.

Решение для задач с бесконечностью или отрицательной бесконечностью часто является задачей без ограничений (в данном случае exitflag возвращается с отрицательным значением, что отмечает, что минимум не найден), а когда конечное решение все же существует, то quadprog может давать только локальный минимум, поскольку такая задача может быть невыпуклой.

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

Литература:

1. Coleman, T.F. and Y. Li, “A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on some of the Variables,” SIAM Journal on Optimization, Vol. 6, Number 4, pp. 1040-1058, 1996.
2. Gill, P. E. and W. Murray, and M.H. Wright, Practical Optimization, Academic Press, London, UK, 1981.

Наверх

fzmult – умножение при сохранении основного базисом для нуль-пространства

Синтаксис:

W = fzmult(A,V)
W = fzmult(A,V,’transpose’)
[W,L,U,pcol,P] = fzmult(A,V)
W = fzmult(A,V,TRANSPOSE,L,U,pcol,P)

Описание:

W = fzmult(A,V) – проводит расчет произведения W от матрицы Z на V, W = Z*V, где Z есть основной базис для нуль-пространства матрицы A. A должна быть разреженной матрицей m-х-n, где m < n, rank (A) = m и rank(A(1:m,1:m)) = m. V должна быть матрицей p-х-q, где p = n-m. Если V является разреженной, то W так же будет разреженной матрицей, в противном случае естественно, что матрица W будет полностью заполненной.

W = fzmult(A,V,’transpose’) – проводит расчет произведения для транспонированного основного базиса V, то есть W = Z’*V. V должна быть матрицей p-х-q, где q = n-m. fzmult(A,V) есть то же самое, что и fzmult(A,V,[]). 

[W,L,U,pcol,P] = fzmult(A,V) возвращает разреженный результат LU-факторизации матрицы A(1:m,1:m), то есть, A1 = A(1:m,1:m) и P*A1(:,pcol) = L*U.

W = fzmult(A,V,transpose,L,U,pcol,P) использует предварительно рассчитанную разреженную LU факторизацию матрицы x A(1:m,1:m), то есть, A1 = A(1:m,1:m) и P*A1(:,pcol) = L*U. операция транспонирования или производится в случае ‘transpose’ или нет в случае использования в командной строке символа [].

Базис нуль-пространства матрицы Z явным образом не формируется. Его неявное представление используется на основе разреженной факторизации матрицы A(1:m,1:m).

Наверх

gangster – обнуление <небольших> компонентов с учетом структурного ранга

Синтаксис:

A = gangstr(M,tol)

Описание:

A = gangstr(M,tol) создает матрицу А с полным структурным рангом, таким, что А есть тоже, что и только за исключением относительно <небольших> элементов с заданной точностью tol, которые в А будут равны нулю. В случае необходимости в данном алгоритме проводится уменьшение точности tol, до тех пор пока не будет справедливо sprank(A) = sprank(M). В матрице М должна быть, по крайней мере, столько же колонок, что и число строк. По умолчанию принимается, что точность tol равна 1e-2.

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

Наверх

optimget – получить значения параметров опций оптимизаци

Синтаксис:

val = optimget(options,’param’)
val = optimget(options,’param’,default)

Описание:

val = optimget(options,’param’) возвращает значения специализированного параметра в структуре опции оптимизации. Для того, что бы однозначно определить имя параметра, необходимо только напечатать достаточное количество определяющих символов. Это случай игнорируется для параметрических имен.

val = optimget(options,’param’,default) по умолчанию возвращает, если в оптимизационных опциях не определены специализированные параметры, структуру опции. Отметим, что эта функциональная форма в первую очередь используется для оптимизационных функций.

Примеры:

Данный оператор возвращает значение параметра опции для отображения оптимизации в структуре, называемой как my_options.

val = optimget(my_options,’Display’)

Данный оператор возвращает значение опционного параметра для отображения оптимизации в структуре называемой, как my_options (как и в предыдущем примере), за исключением того, что если параметр отображения не определен, то он возвращает значение ‘final’.

optnew = optimget(my_options,’Display’,’final’);

Наверх

optimset – создать или отредактировать структуру параметров опций оптимизаци

Синтаксис:

options = optimset(‘param1′,value1,’param2’,value2,…)
optimset
options = optimset
options = optimset(optimfun)
options = optimset(oldopts,’param1′,value1,…)
options = optimset(oldopts,newopts)

Описание:

• options = optimset(‘param1′,value1,’param2’,value2,…) Создает структуру параметров опций оптимизации, называемую как options и в которой специфицированные параметры (param) имеют специфицированные значения. Любой неспецифицированный параметр устанавливается как [] (параметры со значением [] указывают что, когда опция передаются в оптимизационную функцию, то для данных параметров используются принимаемые по умолчанию значения). Для того, что бы однозначно определить имя параметра, достаточно только набрать определяющие начальные символы. Такая операция не допускается для имен параметров.
• optimset без входных и выходных параметров отображает полный список параметров с их разрешенными значениями.
• options = optimset (без входных аргументов) создает опции из опционных структур, где все поля устанавливаются как [].
• options = optimset(optimfun) создает опции из опционных структур со всеми именами параметров и принимаемыми по умолчанию значениями, относящимися к оптимизационной функции optimfun.
• options = optimset(oldopts,’param1′,value1,…) создает копию для oldopts, модифицируя специфицированные параметры с помощью специфицированных значений.
• options = optimset(oldopts,newopts) сочетает существующую опционную структуру oldopts с новой опционной структурой newopts. Всякий параметр в newopts с непустыми значениями перезаписывается на соответствующие старые параметры в oldopts.

Параметры:

Относительно более подробной информации об отдельных параметрах смотри страницы ссылок для функций оптимизации, использующих эти параметры, или Таблицу 4-3, Параметры Опций Оптимизации.

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

Также можно просмотреть параметры оптимизации и принимаемые по умолчанию значения, если набрать optimset на командной линии. 

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

Параметры оптимизации, используемые только в крупно-масштабном алгоритме

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

Примеры:

Данная команда вызывается как options и создает структуру опций оптимизации, где параметр отображения Display устанавливается как ‘iter’ и параметр TolFun принимает значение 1e-8.

Данная команда вызывается как options и создает копию структуры опций, изменяя при этом значение параметра TolX и сохраняя новое значение в optnew.

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

Если нужно только просмотреть принимаемые по умолчанию значения fminbnd, то можно просто набрать

или тоже самое 

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

Наверх

bintprog – Решение задачи целочисленного программирования вида при условии

Синтаксис:

x = bintprog(f)
x = bintprog(f, A, b)
x = bintprog(f, A, b, Aeq, beq)
x = bintprog(f, A, b, Aeq, beq, x0)
x = bintprog(f, A, b, Aeq, beq, x0, options)
[x, fval] = bintprog(…)
[x,fval, exitflag] = bintprog(…)
[x, fval, exitflag, output] = bintprog(…)

Описание:

·     x = bintprog(f)

·     x = bintprog(f, A, b)

·     x = bintprog(f, A, b, Aeq, beq)

·     x = bintprog(f, A, b, Aeq, beq, x0)

·     x = bintprog(f, A, b, Aeq, beq, x0, options)

·     [x, fval] = bintprog(...)

·     [x,fval, exitflag] = bintprog(...)

·     [x, fval, exitflag, output] = bintprog(...)

Описание

x = bintprog(f) решает задачу целочисленного программирования

x = bintprog(f, A, b) задачу целочисленного программирования

 при условии

x = bintprog(f, A, b, Aeq, beq) решает предыдущую задачу при дополнительных условиях типа равенств

x = bintprog(f, A, b, Aeq, beq, x0) устанавливает начальную точку поиска в x0. Если точка x0 находится в недопустимой области, то команда bintprog принимает произвольную начальную точку. 

x = bintprog(f, A, b, Aeq, Beq, x0, options) при оптимизации используется принимаемая по умолчанию опция из структуры options, которую можно задать с помощью функции optimset.

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

[x,fval, exitflag] = bintprog(…) возвращает параметр exitflag с описанием выходных условий команды bintprog. Более подробно описание даннлй функции и значения отдельных аргументов можно найти в разделе Выходные агументы. 

[x, fval, exitflag, output] = bintprog(…) возвращает структуру output, которая содержит информацию о данных результатах оптимизации. См. радел Выходные агументы.

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

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

f	Вектор с коэффициентами линейной целевой функции.
A	Матрица с коэффициентами линейных ограничений типа неравенств
b	Вектор правой части линейных ограничений типа неравенств.
Aeq	Матрица с коэффициентами линейных ограничений типа равенств.
beq	Вектор правой части линейных ограничений типа равенств.
x0	Начальная точка поиска по данному алгоритму.
options	Структура опций для данного алгоритма.

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

Выходные параметры exitflag и output имеет ряд особенностей.

Опции

Далее приводится описание опций команды bintprog. Для установки или изменения значений поля данной структуры используется команда optimset.

Алгоритм

В функции bintprog для решения задачи целочисленного программирования используется алгоритм линейного программирования (LP) на основе метода ветвей и границ. В данном алгоритме проводится перебор оптимальных решений задачи целочисленного программирования путем решения некого набора задач LP релаксации, в котором требование целочисленности переменных заменяется на более слабое ограничение . Данный алгоритм включает в себя:

1. Перебор целочисленных допустимых решений.
2. Корректировка наилучшей целочисленной допустимой точки по мере продвижения по дереву поиска.
3. Проверка невозможности достижения более лучших целочисленных решений посредством рядя задач линейного программирования.

Далее приводится более детальное описание метода ветвей и границ.

Ветвление

Предложенный алгоритм образует дерево поиска путем многократного добавления ограничений на данную задачу, т.е. “ветвления”. На этапе ветвления в алгоритме проводится выбор некой переменной х, чье текущее значение не является целым и, далее, накладываются ограничение  x_j = 0 для формирования одной ветви и ограничение x_j = 1 для формирования другой ветви. Весь этот процесс может быть представлен в виде некоего двоичного дерева, узлы которого представляют собой дополнительно налагаемые ограничения. Далее на графике приводится иллюстрация законченного бинарного дерева для задачи с тремя переменными x₁, x₂  и x₃. Отметим, что в общем случае порядок переменных при снижении уровней дерева может не соответствовать обычному порядку индексов переменных. 

Решение о ветвлении

На каждом узле в данном алгоритме проводится решение задачи LP релаксации с учетом ограничений для данного узла и принимается решение о необходимости или ветвления или движения к другому узлу в зависимости от полученного результата. Имеются три возможности:

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

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

Если задача LP-релаксации является оптимальной, но не целочисленной, то значение оптимальной целевой функции задачи LP-релаксации является меньшим, чем в наилучшей целой точке, а алгоритм переходит на новую ветвь согласно методу, заданному опцией BranchStrategy.

Границы

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

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

Ограничения по алгоритму

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

MaxRLPIter – Максимальное число итераций решателя LP для некого узла при решении задачи LP-релаксации.

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

Более подробно информацию по данному разделу можно найти в разделе Опции.

Пример

Необходимо минимизировать функцию 

при наличии ограничений

,

где x₁, x₂, x₃ и x₄ являются бинарными целыми. Выполним следующие команды:

f = [-9; -5; -6; -4];
A = [6 3 5 2; 0 0 1 1; -1 0 1 0; 0 -1 0 1];
b = [9; 1; 0; 0];
x = bintprog(f,A,b)

Optimization terminated successfully.

x =

     1
     1
     0
     0

Литература

[1]  Wolsey, Laurence A., Integer Programming, John Wiley & Sons, 1998. 
[2]  Nemhauser, George L. and Laurence A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988. 
[3]  Hillier, Frederick S. and Lieberman Gerald J., Introduction to Operations Research, McGraw-Hill, 2001.

Здравствуйте, уважаемые читатели. Продолжаем разбираться в Matlab. И сегодня наша тема связанна с численной оптимизацией — нахождением локальных и глобальных экстремумов функций одной или нескольких переменных в среде Matlab.

Общие сведения

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

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

Если не понятно — вот простой пример с всеми известной параболой:

У этой функции есть один минимум, и он находится в точке x = 0. Эта точка называется точкой минимума, а само значение этой функции есть минимум (он тоже равен 0). Максимумов у этой функции нет, но если бы функцию перевернули вверх ногами, то он бы появился.

Часто встречаются сложные функции, у которых есть несколько и минимумов и максимумов. И в таком случае, разделяют понятия локального и глобального экстремума. Локальный — это тот экстремум, который определен в некоторой области, а глобальный — на всей области определения функции. На рисунке выше представлен глобальный минимум параболы.

И теперь, когда вы хоть как то познакомились с понятиями оптимизации и нахождения экстремумов функции, можем перейти к нахождению максимумов и минимумов в Matlab. Далее, как обычно мы будем разбирать примеры различной сложности. Часть примеров будет содержать в себе стандартные команды Matlab для нахождения минимума и максимума функции, а другая часть — это реализация метода с нуля.

Стандартные методы Matlab

Разберем 2 задачи нахождения минимума в Matlab:

1 пример. Вычислить минимум функции f(x)=-x^1/x, определив графически интервал его локализации. Вычисления провести с минимальным шагом по аргументу 1*10^-5

Для начала создадим скрипт, который отобразит эту функцию. Вот код для этого:

x = 0.00001:0.00001:10;
y = -x.^(x.^(-1));
plot (x,y);
hold on;
grid on;

Запускаем скрипт и получаем:
По графику функции делаем вывод, что имеется один минимум, и его координаты находятся в интервале 2.5 — 3, то есть мы сократим интервал поиска минимума.

Теперь создадим еще один скрипт, дадим ему название first.m и пропишем в него функцию:

function fun=first(x)
fun = -x.^(x.^(-1));
end

Таким образом в этом m-файле мы определили функцию. Теперь в командном окне мы пропишем следующий код:

>> [x,y] = fminbnd(@first,2.5,3)

И получаем такие значения:
x = 2.7183 — координата точки минимума
y = -1.4447 — значение минимума

В этой части кода мы использовали стандартный метод Matlab для нахождения минимума функции — fminbnd. мы передаем 3 параметра — саму функцию и интервалы для поиска минимума. Стоит отметить, что этот метод подходит только для функций, зависящих от одной переменной.

Итак, для этой задачи мы создали 2 скрипт-файла, которые вы можете скачать в конце статьи.

2 пример. Вычислить минимум функции двух переменных x⁴+y⁴-2x²+4xy-2y²+1 с точность 1*10-5.
Координаты начальной точки поиска [1.0,-1.0].

Для начала построим график функции от двух переменных — для этого создадим новый скрипт и пропишем там этот код:

[x y] = meshgrid(-2:0.1:2, -2:0.1:2);
z = x.^4 + y.^4 - 2*x.^2 + 4 * x.*y - 2*y.^2 + 1;
surf(x,y,z);

Функция surf позволяет строить трехмерные графики и отображать глубину значений функции для лучшего понимания. Запускаем скрипт — в итоге получился такой график:
Как видно из графика, имеется два участка, где присутствует локальный минимум (темно-синие участки), и наша задача найти координаты и значения двух этих точек. Воспользуемся стандартными инструментами Matlab и создадим новый скрипт с именем second.m, в котором и пропишем код:

function fun=second(x)
fun = x(1)^4 + x(2)^4 - 2*x(1)^2 + 4 * x(1)*x(2) - 2*x(2)^2 + 1;
end

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

>> [z,f,exitflag,output] = fminsearch(@second, [1.0,-1.0], optimset('TolX',1e-5))

Получаем такой вывод:

z = 1.4142   -1.4142
f = -7.0000
exitflag = 1
output = 
    iterations: 40
    funcCount: 74
    algorithm: 'Nelder-Mead simplex direct search'
    message: [1x196 char]

Для нахождение минимумов в Matlab на этот раз мы использовали функцию fminsearch. Эта функция реализует симплекс — метод Нелдера-Мида. В выводе мы получили несколько переменных: в z записались значения координат точек минимума, в f само значение этого минимума. А в переменных exitflag и output помещены условия прерывания процесса поиска и информация об оптимизации соответственно.

В итоге у нас опять получилось 2 m-файла.

Метод Ньютона Matlab

А теперь попробуем сами реализовать метод Ньютона для оптимизации функции.

3 пример. Методом Ньютона найти точку минимума x* и минимальное значение f* функции f(x)=(x-2)⁴-lnx на отрезке xє[2;3] c точностью 10^-7

Начнем с того, что создадим новый скрипт и назовем его Newton.m. Затем пропишем в нем код:

function [Xk, Yk] = Newton(f,diap)
    a = diap(1); % границы
    b = diap(2);
    df = char(diff(sym(f))); % символьно ищем первую 
    ddf = char(diff(sym(df))); % и вторую производные
    F = inline(f); % преобразуем в функции
    F1 = inline(df);
    F2 = inline(ddf);
    eps = 0.0000001; % задаем точность
    if F(a)*F2(a) > 0 % проверка с какой границы начинать искать
        Xk = b;
    else
        Xk = a;
    end
    while abs(F1(Xk)) > eps
        X0 = Xk; % X0 - значение предыдущего шага
        Xk =  X0 - (F1(X0)/(F2(X0))); % расчет нового значения
        Yk = F(Xk);
    end
end

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

>> fun = '(x-2)^4 - log(x)';
>> diap = [2,3];
>> [Xk, Yk] = Newton(fun, diap);

В итоге получилось:
Xk = 2.4663
Yk = -0.8554

Не будем приводить график, но вы сами можете проверить, что значения найдены правильно. Важно сказать, что этот метод позволяет найти только локальный экстремум, и если на выбранном диапазоне есть несколько экстремумов, то метод может найти не тот, который нужен вам.

Также, очень важно задавать как можно узкий диапазон поиска, иначе метод может работать некорректно, особенно это проявляется с периодическими функциями по типу cos(x) и т.п.

Заключение

Ну что ж, в этой статье мы рассмотрели некоторые методы для нахождения экстремумов в Matlab. Мы использовали как стандартные методы, так и реализовали метод Ньютона в среде Matlab. Их исходники чуть ниже.
Скачать исходники

На этом сегодня все, оставляйте ваши комментарии и задавайте вопросы.

Introduction

This page discusses two different ways of getting MATLAB to find the minimum of a function (versus a data set) – fminbnd and fminsearch. The fminbnd command can find a single independent value that will minimize a one-dimensional function over a specific domain. The fminsearch command can find a single vector of values that will minimize a multi-dimensional function given some initial guess.

fminbnd

The fminbnd command in MATLAB can be used to find the value of a single parameter of a function that will minimize the value of the function on some bounded domain. The command can only find one minimum at a time and can only find minima based on one variable at a time. If there is a single local minimum over the domain, fminbnd should find it. If there are several, it should find one of them, though it may not find the most minimum of the minima. If there is no local minimum in the range, fminbnd will return one of the boundary values, depending on where the function is at its minimum value for the domain.
There are several different ways to present fminbnd with the specific function and variable.

Examples

Different Function Calls

Most General Case

The following examples show a method that will work regardless of how many input variables your function has or how you define your function – whether it is built-in, a variable containing an anonymous function, an anonymous function generated on the fly, or a .m file function. The paradigm is:

[INDEP_AT_MIN, FUNCTION_MIN] = fminbnd(@(DUMMY_VAR) FUNCTION_THING, LEFT_INDEP, RIGHT_INDEP)

where

• INDEP_AT_MIN is the calculated value of the requested variable when the function is at a minimum in the domain
• FUNCTION_MIN is the minimum value of the function at the INDEP_AT_MIN location
• DUMMY_VAR is the variable you want to use in this FUNCTION_THING to indicate which of the various inputs fminbnd is allowed to alter
• FUNCTION_THING can be a built-in function, the name of an anonymous function, the name of a .m file function, or a calculation – whatever it is that you are trying to minimize; note that DUMMY_VAR must appear somewhere in this expression for fminbnd to be able to do anything
• LEFT_INDEP, RIGHT_INDEP represent the minimum and maximum value of the range over which you want to minimize the function.

The example is based on wanting to determine minimum (and later, maximum) values of:

(f(x, y, z)=frac{x}{10}+cos(x)+sin(y)+z,!)

We will assume that two of the three variables ((y) and (z)) are known and that we want to find (x) given those values. We will further assume that (y=1) and (z=pi). A graph of this function for values of (x) between -10 and 10 is shown at right.

Function on the Fly

If you only want to solve this problem once, and the calculation only requires one line of code, the process with the least “overhead” involves creating the function on the fly inside the fminbnd command. All you have to do is put your expression in for the FUNCTION_THING, making sure the DUMMY_VAR is appropriately used. You will also need to specify the boundary values.

The line:

[xValue, fValue] = fminbnd(@(xDummy) xDummy/10 + cos(xDummy) + sin(1) + pi, 0, 5)

will produce

xValue =
   3.0414e+00
fValue =
   3.2922e+00

which has found the local minimum between (x=0) and (x=5).

Running the code:

[xValue, fValue] = fminbnd(@(xDummy) xDummy/10 + cos(xDummy) + sin(1) + pi, 5, 7)

will produce

xValue =
   5.0000e+00
fValue =
   4.7668e+00

since, for (x) values between 5 and 7, there is no local minimum. The value of the function at 5 is less than the value of the function at 7, so the 5 is returned.

Finally, for

[xValue, fValue] = fminbnd(@(xDummy) xDummy/10 + cos(xDummy) + sin(1) + pi, -9, 10)

MATLAB returns:

xValue =
   3.0414e+00
fValue =
   3.2922e+00

Note that this is not actually the “minimum” minimum – that would be at (x=-3.2418), where the function is 2.6639, as given by

[xValue, fValue] = fminbnd(@(xDummy) xDummy/10 + cos(xDummy) + sin(1) + pi, -4, -2)

Furthermore, the actual minimum value of the function over the domain from -9 to 10 is given at (x=-9), where (f=2.1719); since MATLAB was able to find at least one local minimum, however, it did not check the boundary values.

A slightly “longer” version of this would have you pre-define the (y) and (z) variables first, then use the variables in the function definition:
expression in for the FUNCTION_THING, making sure the DUMMY_VAR is appropriately used. The line:

y = 1;
z = pi;
[xValue, fValue] = fminbnd(@(xDummy) xDummy/10 + cos(xDummy) + sin(y) + z, -4, -2)

This works the same as the last example above – recall that when anonymous functions are created, they can take “snapshots” of the workspace. In the case above, the FUNCTION_THING is able to “see” what the variables y and z contain.

Pre-Defined Functions

If you want to solve the same problem multiple times, perhaps by altering initial guesses or altering one or more of the constant parameters in the function, you should first define the function. If the expression can be calculated all on one line, you may choose to use a variable with an anonymous function – for example:

MyFun = @(xa, ya, za) xa/10 + cos(xa) + sin(ya) + za

On the other hand, if the expression is more complicated or if you just want to put it in a .m file, you can certainly do that as well. For example, instead of the MyFun variable above, you could write a MyFun.m file containing:

function out = MyFun(xb, yb, zb)
out = xb/10 + cos(xb) + sin(yb) + zb;

In either case, you would use fminbnd by properly building the FUNCTION_THING using the name of the function. As in the previous example, you can hard-code the values for the (x) and (y) values:

[xValue, fValue] = fminbnd(@(xDummy) MyFun(xDummy, 1, pi), -4, 2)

or you can use variables to transmit the information:

y = 1;
z = pi;
[xValue, fValue] = fminbnd(@(xDummy) MyFun(xDummy, y, z), -4, 2)

In any event, note again that the FUNCTION_THING only has one unknown, and that unknown is named as the DUMMY_VAR.

Single-Variable Anonymous Functions

For single-variable anonymous functions, there is a slightly simpler way to run fminbnd – all you need to do is give the name of the variable to FUNCTION_THING rather than setting up the DUMMY_VAR. For example, to find the minimum value of (x^2-cos(x)) on the domain from (x) going from -2 to 3, you can set up an anonymous function for it as:

MyAnonCalc = @(x) x.^2-cos(x)

and then solve with:

[xValue, fValue] = fminbnd(MyAnonCalc, -2, 3)

to get

xValue =
  -4.5124e-07
fValue =
  -1.0000e+00

Single-Variable Built-in Functions and .m Functions

The following method works for both built-in single-input functions and .m file single-input functions (i.e. not variables containing anonymous functions). The first argument is the name of the function in single quotes and the second argument is the initial guess or initial bracket for the one variable of the function. For example, to find the minimum value of (cos(x)) for the domain of (x) going from 0 to 4, you can type

[xValue, fValue] = fminbnd('cos', 0, 4)

and get

xValue =
   3.1416e+00
fValue =
  -1.0000e+00

If you have a .m file function of one variable, the process is the same. For example, to find the minimum value of (y=x^2-cos(x)) on a domain from -2 to 3, you could first create a .m file called MyCalc.m with:

function out = MyCalc(in)
out = in.^2 - cos(in);

then use fminbnd:

[xValue, fValue] = fminbnd('MyCalc', -2, 3)

and get

xValue =
  -4.5124e-07
fValue =
  -1.0000e+00

Finding Maximum Values

There is no fmaxbnd command. Conveniently, all you need to do to figure out the value and location of the maximum values would be to give fminbnd your function multiplied by -1. The only problem here is that the value of the function fminbnd returns will be the opposite of what you want. For example:

[xValue, fValueSignWrong] = fminbnd(@(xDummy) -(xDummy/10 + cos(xDummy) + sin(1) + pi), 5, 7)

will return

xValue =
   6.3834e+00
fValueSignWrong =
  -5.6164e+00

in order to get the actual value of the function at a maximum, you would need to re-run the calculation or just create a new variable that is equal to -1 multiplied by the function value MATLAB gave:

[xValue, fValueSignWrong] = fminbnd(@(xDummy) -(xDummy/10 + cos(xDummy) + sin(1) + pi), 5, 7)
fValue = -1*fValueSignWrong

to get

xValue =
   6.3834e+00
fValueSignWrong =
  -5.6164e+00
fValue =
   5.6164e+00

Where the Mins Are

As noted above, if you give MATLAB a domain with multiple local minima, it will not always find the most-minimum minima; here are two graphs showing 19,900 runs of fminbnd with different boundaries. The x axis represents the left boundary and the y axis represents the right boundary.

The black regoins indicate left and right values that will not work since “Right” would be to the left of “Left” there.
There are four local minima over the entire domain from -10 to 10. In the left graph, with the locations, these are represented by

• Dark blue: (-9.5250, 2.0356)
• Cyan: (-3.2418, 2.6639)
• Yellow: (3.0414, 3.2922)
• Red: (9.4246, 3.9205)

In the right graph, with the values of the minimum, these are represented by:

• Dark blue: (-9.5250, 2.0356)
• Medium blue: (-3.2418, 2.6639)
• Cyan: (3.0414, 3.2922)
• Green: (9.4246, 3.9205)

For large enough – or well-placed enough – domains, MATALAB will find one of the local minima; if the domain does not span a minimum, it will report back the minimum value at either the left or right boundary. If the domain spans multiple minima, it will report back one of the minima, though not always the minimum one. Notice when the domain is [-10 -4] the dark blue minimum is found, but when the domain is [-10 0], the cyan/medium blue minimum at -3.2418 is found — even though its value (2.6639) is greater than the value at -9.5250. These graphs show that you need to make sure your domain is large enough to include the minimum you are trying to find but not so large as to include multiple minima.

clear; format short e

MyFun = @(xa, ya, za) xa/10 + cos(xa) + sin(ya) + za
N = 200;
[xl, xr] = meshgrid(linspace(-10, 10, N));
MyMinLoc = zeros(size(xl))-20;
MyMinVal = MyMinLoc;

for k=1:(N-1)
    for l=(k+1):N
        [MyMinLoc(l, k), MyMinVal(l, k)] = ...
            fminbnd(@(xD) MyFun(xD, 1, pi), xl(l, k), xr(l, k));
    end
end

MyMap = jet;

figure(1); clf
%surfc(xl, xr, MyMinLoc)
imagesc(xl(1,:), xr(:,1), MyMinLoc, [-10 10])
set(gca, 'YDir', 'Normal'), xlabel('Left'), ylabel('Right')
title('Locations of Minimum Found by fminbnd')
view(2), shading interp
colormap([0 0 0; MyMap]); BarH = colorbar;
set(BarH, 'YLim', [-10 max(MyMinLoc(:))])
print -dpng -r0 BasinLocations

figure(2); clf
%surfc(xl, xr, MyMinLoc)
imagesc(xl(1,:), xr(:,1), MyMinVal, [2, 5.7])
set(gca, 'YDir', 'Normal'), xlabel('Left'), ylabel('Right')
title('Values of Minimum Found by fminbnd')
view(2), shading interp
colormap([0 0 0; MyMap]); BarH = colorbar;
set(BarH, 'YLim', [2 5.6])
print -dpng -r0 BasinValues

fminsearch

The fminsearch command in MATLAB can be used to find the value of a single vector input of a multivariable function that will minimize the value of the function on some unbounded domain. The command can only find one minimum at a time and can only find minima based on one variable at a time – but that variable can be a vector instead of a single entry.

Most General Case

The following examples show a method that will work regardless of how many input variables your function has or how you define your function – whether it is built-in, a variable containing an anonymous function, an anonymous function generated on the fly, or a .m file function. The paradigm is:

[INDEP_AT_MIN, FUNCTION_MIN] = fminsearch(@(DUMMY_VAR) FUNCTION_THING, INIT_GUESS)

where

• INDEP_AT_MIN is the calculated value of the requested variable when the function is at a minimum in the domain
• FUNCTION_MIN is the minimum value of the function at the INDEP_AT_MIN location
• DUMMY_VAR is the variable you want to use in this FUNCTION_THING to indicate which of the various inputs fminbnd is allowed to alter
• FUNCTION_THING can be a built-in function, the name of an anonymous function, the name of a .m file function, or a calculation – whatever it is that you are trying to minimize; note that DUMMY_VAR must appear somewhere in this expression for fminbnd to be able to do anything
• INIT_GUESS represents an initial guess for where the minimum value is on the surface. There need to be as many values in the initial guess as there are entries in the dummy variable.

Examples

One Value

If you want to find the location of the minimum of some function (f(x)) where (x) is a single value (a scalar), all you need is a function and an initial guess. For example, to find the minimum of:

(f(x)=(x+3)(x)(x-1)(x-3))

you can run:

f1 = @(x) (x+3).*(x).*(x-1).*(x-3);
[xval, fval] = fminsearch(@(xDummy) f1(xDummy), 0)

and MATLAB will find a minimum of (f(-2.0234)=-30.01). Note, however, if you make an initial guess of 1:

[xval2, fval2] = fminsearch(@(xDummy) f1(xDummy), 1)

will return the local – but not global – minimum of (f(2.2873)=-11.10). Since there is no way to force fminsearch to find a minimum within a particular set of boundaries, either you should use fminbnd if you only have one parameter or you should be extremely careful in picking your initial conditions. The code below demonstrates that MATLAB finds different locations and values for the minimum depending on initial condition:

clear;
f1 = @(x) (x+3).*(x).*(x-1).*(x-3);
xinit = linspace(-40, 40, 1000);
for k = 1:length(xinit)
    [xval(k), fval(k)] = fminsearch(@(xDummy) f1(xDummy), xinit(k));
end

figure(1); clf
plot(xinit, xval)
xlabel('Initial x'), ylabel('Final x')

figure(2); clf
plot(xinit(fval>-20), f1(xinit(fval>-20)), 'b.', ...
     xinit(fval<-20), f1(xinit(fval<-20)), 'r.')
legend('Basin for min near -11', 'Basin for min of near -30', 'location', 'best')

Multiple Value Vector

Imagine if you were to want to find the minimum of some function

(f(x, y)=(x-1)^2+(y-2)^2,!)

which has a discernible minimum at (1, 2); you could use:

[rval, fval] = fminsearch(@(rDummy) (rDummy(1)-1).^2+(rDummy(2)-2).^2, [0 0])

to have MATLAB start at the origin and find the value of the vector rDummy that has the x and y coordinate in it.
Since this function only has one minimum, MATLAB should be able to find it as long as the initial guess is somewhat reasonable.

Questions

Post your questions by editing the discussion page of this article. Edit the page, then scroll to the bottom and add a question by putting in the characters *{{Q}}, followed by your question and finally your signature (with four tildes, i.e. ~~~~). Using the {{Q}} will automatically put the page in the category of pages with questions – other editors hoping to help out can then go to that category page to see where the questions are. See the page for Template:Q for details and examples.

External Links

References