Минимизация с градиентом и Гессианской разреженностью Шаблона

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

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

где $$n$$ = 1000.

n = 1000;

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

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

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

load brownhstr
spy(Hstr)

Установите 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 находит решение. The output структура показывает, что fminunc Для достижения решения требуется только семь итераций.

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

disp(max(x))

   1.9955e-10

disp(min(x))

  -1.9955e-10

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

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

Похожие темы

• Минимизация с градиентом и Гессианом