Минимизация с шаблоном разреженности градиента и гессиана

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

Проблема состоит в том, чтобы найти x минимизировать

f(x)=i=1n-1((xi2)(xi+12+1)+(xi+12)(xi2+1)),

где n = 1000.

n = 1000;

Использовать trust-region метод в fminunc, необходимо вычислить градиент в целевой функции; это не является дополнительным как в quasi-newton метод.

Функция помощника brownfg в конце этого примера вычисляет целевую функцию и градиент.

Позволить эффективный расчет разреженного приближения конечной разности матрицы Гессиана H(x), структура разреженности H должен быть предопределен. В этом случае, структура Hstr, разреженная матрица, доступно в файле brownhstr.mat. Используя spy команда, вы видите тот Hstr действительно, разреженно (только 2 998 ненулей).

load brownhstr
spy(Hstr)

Figure contains an axes. The axes contains an object of type line.

Установите HessPattern опция к Hstr использование optimoptions. Когда такая большая проблема имеет очевидную структуру разреженности, не устанавливая HessPattern опция использует большой объем памяти и расчет излишне, потому что fminunc попытки использовать конечное дифференцирование на полной матрице Гессиана одного миллиона ненулевых записей.

Чтобы использовать шаблон разреженности Гессиана, необходимо использовать trust-region алгоритм fminunc. Этот алгоритм также требует, чтобы вы установили SpecifyObjectiveGradient опция к true использование optimoptions.

options = optimoptions(@fminunc,'Algorithm','trust-region',...
    'SpecifyObjectiveGradient',true,'HessPattern',Hstr);

Установите целевую функцию на @brownfg. Установите начальную точку на –1 для нечетного x компоненты и +1 для даже x компоненты.

xstart = -ones(n,1); 
xstart(2:2:n,1) = 1;
fun = @brownfg;

Решите задачу путем вызова fminunc использование начальной точки xstart и опции options.

[x,fval,exitflag,output] = fminunc(fun,xstart,options);
Local minimum found.

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

Исследуйте процесс решения и решения.

disp(fval)
   7.4739e-17
disp(exitflag)
     1
disp(output)
         iterations: 7
          funcCount: 8
           stepsize: 0.0046
       cgiterations: 7
      firstorderopt: 7.9822e-10
          algorithm: 'trust-region'
            message: '...'
    constrviolation: []

Функция f(x) сумма степеней квадратов и, поэтому, является неотрицательной. Решение fval почти нуль, таким образом, это - ясно минимум. Выходной флаг 1 также указывает на тот fminunc находит решение. output структура показывает тот fminunc берет только семь итераций, чтобы достигнуть решения.

Отобразите самые большие и самые маленькие элементы решения.

disp(max(x))
   1.9955e-10
disp(min(x))
  -1.9955e-10

Решение около точки где все элементы x = 0.

Функция помощника

Этот код создает brownfg функция помощника.

function [f,g] = brownfg(x)
% BROWNFG Nonlinear minimization test problem
% 
% Evaluate the function
n=length(x); y=zeros(n,1);
i=1:(n-1);
y(i)=(x(i).^2).^(x(i+1).^2+1) + ...
        (x(i+1).^2).^(x(i).^2+1);
  f=sum(y);
% Evaluate the gradient if nargout > 1
  if nargout > 1
     i=1:(n-1); g = zeros(n,1);
     g(i) = 2*(x(i+1).^2+1).*x(i).* ...
              ((x(i).^2).^(x(i+1).^2))+ ...
              2*x(i).*((x(i+1).^2).^(x(i).^2+1)).* ...
              log(x(i+1).^2);
     g(i+1) = g(i+1) + ...
              2*x(i+1).*((x(i).^2).^(x(i+1).^2+1)).* ...
              log(x(i).^2) + ...
              2*(x(i).^2+1).*x(i+1).* ...
              ((x(i+1).^2).^(x(i).^2));
  end
end

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте