package jsat.math.optimization;

import java.util.ArrayList;
import java.util.List;

import jsat.linear.*;
import jsat.math.*;
import jsat.utils.DoubleList;

/**
 * Implementation of the Limited memory variant of {@link BFGS}. It uses a 
 * history of {@link #setM(int) m} items to solve {@code n} dimension problems 
 * with {@code O(m n)} work per iteration. 
 * 
 * @author Edward Raff
 */
public class LBFGS implements Optimizer 
{
    private int m;
    private int maxIterations;
    private LineSearch lineSearch;
    private boolean inftNormCriterion = true;

    /**
     * Creates a new L-BFGS optimization object that uses a maximum of 500 
     * iterations and a {@link BacktrackingArmijoLineSearch Backtracking} line 
     * search. A {@link #setM(int) history} of 10 items will be used
     */
    public LBFGS()
    {
        this(10);
    }

    /**
     * Creates a new L-BFGS optimization object that uses a maximum of 500 
     * iterations and a {@link BacktrackingArmijoLineSearch Backtracking} line 
     * search. 
     * @param m the number of history items
     */
    public LBFGS(int m)
    {
        this(m, 500, new BacktrackingArmijoLineSearch());
    }
    
    /**
     * Creates a new L-BFGS optimization object
     * @param m the number of history items
     * @param maxIterations the maximum number of iterations before stopping
     * @param lineSearch the line search method to use for optimization
     */
    public LBFGS(int m, int maxIterations, LineSearch lineSearch)
    {
        setM(m);
        setMaximumIterations(maxIterations);
        setLineSearch(lineSearch);
    }
    
    /**
     * See Algorithm 7.4 (L-BFGS two-loop recursion). 
     * @param x_grad the initial value ∇ fk
     * @param rho
     * @param s
     * @param y
     * @param q the location to store the value of Hk ∇ fk
     * @param alphas temp space to do work, should be as large as the number of history vectors
     */
    public static void twoLoopHp(Vec x_grad, List rho, List s, List y, Vec q, double[] alphas)
    {
        //q ← ∇ fk;
        x_grad.copyTo(q);
        if(s.isEmpty())
            return;//identity, we are done
        //for i = k−1,k−2,...,k−m
        for(int i = 0; i < s.size(); i++)
        {
            Vec s_i = s.get(i);
            Vec y_i = y.get(i);
            double alpha_i = alphas[i] = rho.get(i)*s_i.dot(q);
            q.mutableSubtract(alpha_i, y_i);
        }
        
        //r ← Hk0q;  and see eq (7.20), done in place in q
        q.mutableMultiply(s.get(0).dot(y.get(0))/y.get(0).dot(y.get(0)));
        //for i = k−m,k−m+1,...,k−1
        for(int i = s.size()-1; i >= 0; i--)
        {
            //β ← ρ_i y_i^T r ;
            double beta = rho.get(i)*y.get(i).dot(q);
            //r ← r + si (αi − β)
            q.mutableAdd(alphas[i]-beta, s.get(i));
        }
    }
    
    @Override
    public void optimize(double tolerance, Vec w, Vec x0, Function f, FunctionVec fp, boolean parallel)
    {
        if(fp == null)
            fp = Function.forwardDifference(f);
        LineSearch search = lineSearch.clone();
        final double[] f_xVal = new double[1];//store place for f_x
        
        //history for implicit H
        List Rho = new DoubleList(m);
        List S = new ArrayList<>(m);
        List Y = new ArrayList<>(m);
        
        Vec x_prev = x0.clone();
        Vec x_cur = x0.clone();
        f_xVal[0] = f.f(x_prev, parallel);
        //graidnet
        Vec x_grad = x0.clone();
        x_grad.zeroOut();
        Vec x_gradPrev = x_grad.clone();
        //p_l
        Vec p_k = x_grad.clone();
        Vec s_k = x_grad.clone();
        Vec y_k = x_grad.clone();
        
        x_grad = fp.f(x_cur, x_grad, parallel);
       
        double[] alphas = new double[m];
        int iter = 0;
        
        while(gradConvgHelper(x_grad) > tolerance && iter < maxIterations)
        {
            //p_k = −H_k ∇f_k; (6.18)
            twoLoopHp(x_grad, Rho, S, Y, p_k, alphas);
            p_k.mutableMultiply(-1);

            //Set x_k+1 = x_k + α_k p_k where α_k is computed from a line search
            x_cur.copyTo(x_prev);
            x_grad.copyTo(x_gradPrev);
            
            double alpha_k = search.lineSearch(1.0, x_prev, x_gradPrev, p_k, f, fp, f_xVal[0], x_gradPrev.dot(p_k), x_cur, f_xVal, x_grad, parallel);
            if(alpha_k < 1e-12)//if we are making near epsilon steps consider it done
                break;
            
            if(!search.updatesGrad())
                fp.f(x_cur, x_grad, parallel);
            
            //Define s_k =x_k+1 −x_k and y_k = ∇f_k+1 −∇f_k;
            x_cur.copyTo(s_k);
            s_k.mutableSubtract(x_prev);
            S.add(0, s_k.clone());
            
            x_grad.copyTo(y_k);
            y_k.mutableSubtract(x_gradPrev);
            Y.add(0, y_k.clone());
            
            Rho.add(0, 1/s_k.dot(y_k));
            if(Double.isInfinite(Rho.get(0)) || Double.isNaN(Rho.get(0)))
            {
                Rho.clear();
                S.clear();
                Y.clear();
            }
            while(Rho.size() > m)
            {
                Rho.remove(m);
                S.remove(m);
                Y.remove(m);
            }
            
            iter++;
        }
        
        x_cur.copyTo(w);
    }

    /**
     * By default the infinity norm is used to judge convergence. If set to 
     * {@code false}, the 2 norm will be used instead. 
     * @param inftNormCriterion 
     */
    public void setInftNormCriterion(boolean inftNormCriterion)
    {
        this.inftNormCriterion = inftNormCriterion;
    }

    /**
     * Returns whether or not the infinity norm ({@code true}) or 2 norm 
     * ({@code false}) is used to determine convergence. 
     * @return {@code true} if the infinity norm is in use, {@code false} for 
     * the 2 norm
     */
    public boolean isInftNormCriterion()
    {
        return inftNormCriterion;
    }
    
    private double gradConvgHelper(Vec grad)
    {
        if(!inftNormCriterion)
            return grad.pNorm(2);
        double max = 0;
        for(IndexValue iv : grad)
            max = Math.max(max, Math.abs(iv.getValue()));
        return max;
    }

    /**
     * Sets the number of history items to keep that are used to approximate the 
     * Hessian of the problem
     * @param m the number of history items to keep
     */
    public void setM(int m)
    {
        if(m < 1)
            throw new IllegalArgumentException("m must be positive, not " + m);
        this.m = m;
    }

    /**
     * Returns the number of history items that will be used
     * @return the number of history items that will be used
     */
    public int getM()
    {
        return m;
    }

    /**
     * Sets the line search method used at each iteration
     * @param lineSearch the line search method used at each iteration
     */
    public void setLineSearch(LineSearch lineSearch)
    {
        this.lineSearch = lineSearch;
    }

    /**
     * Returns the line search method used at each iteration
     * @return the line search method used at each iteration
     */
    public LineSearch getLineSearch()
    {
        return lineSearch;
    }
    
    @Override
    public void setMaximumIterations(int iterations)
    {
        if(iterations < 1)
            throw new IllegalArgumentException("Number of iterations must be positive, not " + iterations);
        this.maxIterations = iterations;
    }

    @Override
    public int getMaximumIterations()
    {
        return maxIterations;
    }

    @Override
    public LBFGS clone()
    {
        return new LBFGS(m, maxIterations, lineSearch.clone());
    }
    
}

 

Ads help maintain this website.