Квазиньютоновский алгоритм BFGS не вычисляет размер шага - PullRequest
Новая
       7

Квазиньютоновский алгоритм BFGS не вычисляет размер шага

0 голосов
/ 17 декабря 2018

Я пишу алгоритм для реализации метода BFGS для оптимизации неограниченных проблем.Он работает для 1-D задач, но когда я запускаю его с функцией Rosenbrock (или аналогичной), он запускает несколько итераций и затем не возвращает альфа нового размера шага.Куда я иду не так?Ниже приводится квазиньютоновский сегмент: 

% Quasi-Newton algorithm: BFGS
% Rosenbrock function
func = @(z) (1-z(1)^2)^2 + 100*(z(2)- z(1)^2)^2;
dfunc = @(z) [4*z(1)*(101*z(1)^2 - 100*z(2) - 1); 200*(z(2) - z(1)^2)];
x = [20 1];

nvar = length(x);

% Initialize H0 to identity
H = eye(nvar);

eps = 10e-6;        % relative epsilon
k = 1;

while norm(dfunc(x(k, :))) > eps
    % compute search direction p- don't need to keep pk's
    p = -H*dfunc(x(k, :))

    % get a(k) from line search that satisfies Wolfe conditions
    a = linesearch(p, func, dfunc, x(k, :))

    % get new x, keep x values
    x(k+1, :) = x(k, :) + a*p';

    % define s, y, rho
    s = a*p;
    y = dfunc(x(k+1, :)) - dfunc(x(k, :));
    rho = 1/(transpose(y)*s);

    % compute H(k+1) from 6.17
    I = eye(nvar);
    H_new = (I - rho*s*transpose(y))*H*(I - rho*y*transpose(s)) + rho*s*transpose(s)

    % increment k
    k = k+1;
    H = H_new;
end

, и он использует эту функцию поиска строки: 

function a_star = linesearch(p, func, dfunc, x0)
% function: use a line search to find alpha 
% input: 
%     p is a descent direction
%     func is the function being optimized
%     dfunc is the gradient of the function
%     x0 is the initial x value
% output: alpha that satisfies wolfe conditions

alpha_old = 0;         % initial alpha is zero
alpha = 1;             % first alpha is one
alpha_max = 1000;      % depends on problem

c1 = 1e-4;             % constant values for quasi-Newton problems
c2 = 0.9;

iter_max = 1000;

for i = 1:iter_max
if (calcPhi(alpha) > (calcPhi(0) + c1*alpha*calcdPhi(0))) || (calcPhi(alpha) >= calcPhi(alpha_old) && i>1)
    a_star = zoom(alpha_old, alpha);
    break;
end

if (abs(calcdPhi(alpha)) <= -c2*calcdPhi(0))
   a_star = alpha;
   break;
end

if (calcdPhi(alpha) >= 0)
    a_star = zoom(alpha, alpha_old);
    break;
end

alpha_old = alpha;      % update alpha values
alpha = 2*alpha;
end

function [phi] = calcPhi(a)
% function: calculate phi from alpha 
% input: step size alpha
% output: phi 
    phi = func(x0 + p.*a);
end

function [dphi] = calcdPhi(a)
% function: calculate the derivative of phi from alpha 
% input: step size alpha
% output: dphi 
    dphi = dot(p,dfunc(x0 + p.*a));      % dot product
end

function a_star = zoom(a_lo, a_hi)
% function: zoom
% inputs: low and high values for alpha
% output: alpha star
for j = 1:iter_max
    % interpolate trial step a_j between a_lo and a_hi
    a_j = (a_hi + a_lo) / 2;

    if (calcPhi(a_j) > (calcPhi(0) + c1*a_j*calcdPhi(0)) || calcPhi(a_j) >= calcPhi(a_lo))
        a_hi = a_j;
    else
        if (abs(calcdPhi(a_j)) <= -c2*calcdPhi(0))
            a_star = a_j;
            break;
        end

        if (calcdPhi(a_j)*(a_hi-a_lo) >= 0)
            a_hi = a_lo;
        end
        a_lo = a_j;
    end
end
end

end

В частности, он выдаст ошибку «Выходной аргумент« a_star »(иможет быть, другие) не назначены во время вызова "linesearch / zoom". "Я пытался увеличить iter_max до больших значений, таких как 100000, но безрезультатно.Идеи, почему это может происходить?

...