Matlab library for gradient descent algorithms: Version 1.0.1
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
data Version 1.0.1 Apr 18, 2017
gd_solver Version 1.0.1 Apr 24, 2017
gd_test Version 1.0.1 Apr 24, 2017
line_search Version 1.0.1 Apr 24, 2017
plotter Version 1.0.1 Apr 24, 2017
problem Version 1.0.1 Apr 24, 2017
tool Version 1.0.1 Apr 18, 2017
.gitignore Version 1.0.1 Apr 21, 2017
LICENSE.txt Version 1.0.0 Nov 4, 2016
README.md Version 1.0.1 Jul 2, 2018
demo.m Version 1.0.0 Nov 4, 2016
run_me_first.m Version 1.0.1 Apr 24, 2017

README.md

GDLibrary : Gradient Descent Library in MATLAB


Authors: Hiroyuki Kasai

Last page update: April 19, 2017

Latest library version: 1.0.1 (see Release notes for more info)

Introduction

The GDLibrary is a pure-Matlab library of a collection of unconstrained optimization algorithms. This solves an unconstrained minimization problem of the form, min f(x).

Note that the SGDLibrary internally contains this GDLibrary.

List of gradient algorithms available in GDLibrary

  • GD (gradient descent)
    • Standard GD
    • Scaled GD
  • CG (linear conjugate gradient)
    • Standard GD
    • Preconditioned CG
  • NCG (non-linear conjugate gradient)
    • Fletcher-Reeves (FR), Polak-Ribiere (PR)
  • Newton (Netwon's algorithm)
    • Standard Netwon's algorithm
    • Damped Newton's algorithm
    • Cholesky factorizaion based Newton's algorithm
  • BFGS (Broyden-Fletcher-Goldfarb-Shanno algorithm)
    • Standard BFGS
    • Damped BFGS
  • LBFGS (limited-memory BFGS)
    • Standard LBFGS
  • AGD (Accelerated gradient descent, i.e., Nesterov AGD)
    • Standard AGD

List of line-search algorithms available in GDLibrary

Supported problems

Folders and files

./                      - Top directory.
./README.md             - This readme file.
./run_me_first.m        - The scipt that you need to run first.
./demo.m                - Demonstration script to check and understand this package easily. 
|plotter/               - Contains plotting tools to show convergence results and various plots.
|tool/                  - Some auxiliary tools for this project.
|problem/               - Problem definition files to be solved.
|gd_solver/             - Contains various gradient descent optimization algorithms.
|gd_test/               - Some helpful test scripts to use this package.

First to do

Run run_me_first for path configurations.

%% First run the setup script
run_me_first; 

Usage example 1 (Rosenbrock problem)

Now, just execute demo for demonstration of this package.

%% Execute the demonstration script
demo; 

The "demo.m" file contains below.

%% define problem definitions
% set number of dimensions
d = 2;    
problem = rosenbrock(d);


%% calculate solution 
w_opt = problem.calc_solution(); 


%% general options for optimization algorithms   
options.w_init = zeros(d,1);
% set verbose mode        
options.verbose = true;  
% set optimal solution    
options.f_opt = problem.cost(w_opt);  
% set store history of solutions
options.store_w = true;


%% perform GD with backtracking line search 
options.step_alg = 'backtracking';
[w_gd, info_list_gd] = gd(problem, options); 

%% perform NCG with backtracking line search 
options.step_alg = 'backtracking';
[w_ncg, info_list_ncd] = ncg(problem, options);     

%% perform L-BFGS with strong wolfe line search
options.step_alg = 'strong_wolfe';                  
[w_lbfgs, info_list_lbfgs] = lbfgs(problem, options);                  


%% plot all
close all;

% display epoch vs cost/gnorm
display_graph('iter','cost', {'GD-BKT', 'NCG-BKT', 'LBFGS-WOLFE'}, {w_gd, w_ncg, w_lbfgs}, {info_list_gd, info_list_ncd, info_list_lbfgs});
% display optimality gap vs grads
display_graph('iter','gnorm', {'GD-BKT', 'NCG-BKT', 'LBFGS-WOLFE'}, {w_gd, w_ncg, w_lbfgs}, {info_list_gd, info_list_ncd, info_list_lbfgs});

% draw convergence sequence
w_history = cell(1);
cost_history = cell(1);
w_history{1} = info_list_gd.w;
w_history{2} = info_list_ncd.w;  
w_history{3} = info_list_lbfgs.w;      
cost_history{1} = info_list_gd.cost;
cost_history{2} = info_list_ncd.cost;  
cost_history{3} = info_list_lbfgs.cost;      
draw_convergence_sequence(problem, w_opt, {'GD-BKT', 'NCG-BKT', 'LBFGS-WOLFE'}, w_history, cost_history);          
  • Output results





License

The GDLibrary is free and open source for academic/research purposes (non-commercial).

Problems or questions

If you have any problems or questions, please contact the author: Hiroyuki Kasai (email: kasai at is dot uec dot ac dot jp)

Release Notes

  • Version 1.0.1 (Apr. 19, 2017)
    • New solvers and problems are added.
  • Version 1.0.0 (Nov. 04, 2016)
    • Initial version.