% ArmijoLineSearch.m Implementation of Armijo line search
%-----------------------------------------------------------------------
% [alpha,j] = ArmijoLineSearch( x, dx, g, ObjFun, varargin )
%
% INPUT ARGUMENTS:
% x              point from whih we perform the search
% dx             search direction
% g              gradient of objective at x
% ObjFun         is a function to evaluate the objective f(x)
% varargin       is a number of parameters that are passed to ObjFun
%
% OUTPUT ARGUMENTS:
% alpha          is the step size
% j              is the iteration number at the final step
% info           is an indication of exit
%                   0 = optimal
%                   1 = too many backtracks
%                   2 = dx is not a search direction
%
% Author: Sven Leyffer, Argonne National Laboratory, 2016.
%-----------------------------------------------------------------------
function [alpha, j, info] = ArmijoLineSearch( x, dx, g, ObjFun, varargin )

% ... define the constants of the search
t     = 1.0;      % ... initial step size
beta  = 0.5 ;     % ... back-tracking factor
maxf  = 10;       % ... maximum number of function evaluations  
sigma = 0.1;      % ... sufficient reduction parameter

% ... initialization
j     = 0;
xnew  = x + t*dx;
f     = feval( ObjFun, x,    varargin{:} );
fnew  = feval( ObjFun, xnew, varargin{:} );
alpha = t;
gTdx  = g'*dx;
info  = 0;

% ... start backtracking linesearch.
while (j < maxf) & ((f - fnew) < -alpha*sigma*gTdx)
  alpha = alpha*beta;
  xnew  = x + alpha*dx;
  fnew  = feval( ObjFun, xnew, varargin{:} );
  j     = j+1;
end % while (j < maxf) && ((f - fnew) < -alpha*sigma*gTdx)

% ... set output parameter if we failed
if (j >= maxf) & ((f - fnew) < -alpha*sigma*gTdx)
  info = 1;
end % if
