BFGS is an simple implementation of the Newton' methods in Julia. The main objectives of those methods is to solve convex optimization problem, possibly with constraints and/or limited memory.
Let
possibly under the constraints
The gradient is given by
Loading the package
using NMOpt
Problem to optimize
function F(x::Array{Cdouble,1})
exp(x[1]-1.0) + exp(-x[2]+1.0) + (x[1]-x[2])^2 + 2.0*sin(pi*sum(x))
end
function Fgrad(x::Array{Cdouble,1})
y = Array{Cdouble,1}(undef,length(x))
y[1] = exp(x[1]-1.0) + 2.0(x[1]-x[2]) + 2.0*pi*cos(pi*sum(x))
y[2] = -exp(-x[2]+1.0) - 2.0(x[1]-x[2]) + 2.0pi*cos(pi*sum(x))
y_
end
Initial conditions
X0 = zeros(Cdouble,2)
X0[1] = 2.0
X0[2] = -0.5
p0 = ones(Cdouble,2) # first descent direction
alpha_min = -4.0 # smallest value of the length of the step
alpha_max = 4.0 # largest value of the length of the step
mu = 0.4 # <0.5 parameter for the line search algorithm
Nbfgs = 100 # maximum number of iterations for BFGS main loop
Nsearch = 10 # maximum number of iteration for the line search
Mmemory = 4 # size of the memory
H0 = 0.01*[1.0 0.0; 0.0 1.0] # initial Hessian matrix
BFGS
Xend,Hend,Xpath,Nlast = BFGS(X0,H0,Nbfgs,alpha_min,alpha_max,mu,F,Fgrad,Nsearch)
L-BFGS
Xend,Xpath,Nlast = LBFGS(X0,H0,Nbfgs,alpha_min,alpha_max,mu,Mmemory,F,Fgrad,Nsearch)
BFGS-B
Xend,Hend,Xpath,Nlast = BFGSB(X0,H0,2Nbfgs,alpha_min,alpha_max,mu,lx,ux,F,Fgrad,Nsearch)
L-BFGS-B
Xend,Xpath,Nlast = LBFGSB(X0+[-0.5;0.0],H0,2Nbfgs,alpha_min,alpha_max,mu,Mmemory,lx,ux,F,Fgrad,Nsearch)
Results
The example is implemented in test.jl, and the results are shown in the following figure. The BFGS and L-BFGS results are shown in panel (a), and those of BFGS-B and L-BFGS-B in panel (b). The paths of the algorithm optimal solutions are depicted with scatter dots, and the constraints with straight lines.
] add https://github.com/matthewozon/NMOpt
- More and Sorensen 1982 (Newton's method technical report): BFGS
- More 1994 (Line Search Algorithms Sufficient Decrease): line search
- Nocedal 1980 (Updating Quasi-Newton Matrices With Limited Storage): limited memory BFGS
- Thiébaut (Optimization issues in blind deconvolution algorithms): bounded limited memory BFGS, a.k.a vmlmb