package jsat.math.optimization;

import jsat.linear.*;
import jsat.math.*;

/**
 * Implementation of the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm for 
 * function minimization. For {@code n} dimensional problems it requires 
 * O(n2) work per iteration and uses first order information 
 * to approximate the Hessian. 
 * 
 * @author Edward Raff
 */
public class BFGS implements Optimizer 
{
    private LineSearch lineSearch;
    private int maxIterations;
    private boolean inftNormCriterion = true;

    /**
     * Creates a new BFGS optimization object that uses a maximum of 250 
     * iterations and a {@link BacktrackingArmijoLineSearch backtracking} line 
     * search. 
     */
    public BFGS()
    {
        this(250, new BacktrackingArmijoLineSearch());
    }

    /**
     * Creates a new BFGS optimization object
     * @param maxIterations the maximum number of iterations to allow before 
     * stopping
     * @param lineSearch the line search method to use on updates
     */
    public BFGS(int maxIterations, LineSearch lineSearch)
    {
        setMaximumIterations(maxIterations);
        setLineSearch(lineSearch);
    }
    
    @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();
        
        Matrix H = Matrix.eye(x0.length());
        Vec x_prev = x0.clone();
        Vec x_cur = x0.clone();
        final double[] f_xVal = new double[1];//store place for f_x
        
        //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();
        
        f_xVal[0] = f.f(x_cur);
        x_grad = fp.f(x_cur, x_grad);
       
        int iter = 0;
        while(gradConvgHelper(x_grad) > tolerance && iter < maxIterations)
        {
            iter++;
            p_k.zeroOut();
            H.multiply(x_grad, -1, p_k);//p_k = −H_k ∇f_k; (6.18)
            
            //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 && iter > 5)//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);
            
            x_grad.copyTo(y_k);
            y_k.mutableSubtract(x_gradPrev);
            //Compute H_k+1 by means of (6.17);
            
            double skyk = s_k.dot(y_k);
            if(skyk <= 0)
            {
                H.zeroOut();
                for(int i = 0; i < H.rows(); i++)
                    H.set(i, i, 1);
                continue;
            }
            if(iter == 0 && skyk > 1e-12)
                for(int i = 0; i < H.rows(); i++)
                    H.set(i, i, skyk/y_k.dot(y_k));
            
            /*
             * From "A Perfect Example for The BFGS Method" equation 1.5
             * aamath:  H_(k+1)=H_k-(s_k*y_k^T*H_k+H_k*y_k*s_k^T)/(s_k^T*y_k)+(1+(y_k^T*H_k*y_k)/(s_k^T*y_k))*((s_k*s_k^T)/(s_k^T*y_k))
             * 
             *                   T             T   /     T      \     T
             *               s  y  H  + H  y  s    |    y  H  y | s  s
             *                k  k  k    k  k  k   |     k  k  k|  k  k
             * H      = H  - ------------------- + |1 + --------| -----
             *  k + 1    k           T             |       T    |  T
             *                      s  y           |      s  y  | s  y
             *                       k  k          \       k  k /  k  k
             * 
             * TODO: y_k^T H_k y_k should be just a scalar constant
             * TODO: exploit the symetry of H_k
             */
            
            Vec Hkyk = H.multiply(y_k);
            Vec ykHk = y_k.multiply(H);
            double b = (1+y_k.dot(Hkyk)/skyk)/skyk;//coef for right rank update

            //update
            Matrix.OuterProductUpdate(H, s_k, ykHk, -1/skyk);
            Matrix.OuterProductUpdate(H, Hkyk, s_k, -1/skyk);
            Matrix.OuterProductUpdate(H, s_k, s_k, b);
        }
        
        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;
    }

    @Override
    public void setMaximumIterations(int iterations)
    {
        if(iterations < 1)
            throw new IllegalArgumentException("Iterations must be a positive value, not " + iterations);
        this.maxIterations = iterations;
    }

    @Override
    public int getMaximumIterations()
    {
        return maxIterations;
    }
    
    /**
     * 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 Optimizer clone()
    {
        return new BFGS(maxIterations, lineSearch.clone());
    }
    
}

 

Ads help maintain this website.