package jsat.math.optimization;

import jsat.linear.Vec;
import jsat.math.Function;
import jsat.math.FunctionVec;
import static java.lang.Math.*;

/**
 * An implementation of the Wolfe Line Search algorithm described by Nocedal and
 * Wright in Numerical Optimization (2nd edition) on pages 59-63. 
 * 
 * @author Edward Raff
 */
public class WolfeNWLineSearch implements LineSearch
{
    //default values that make setting in the constructor simple (shouldn't actually use)
    private double c1 = Math.nextUp(0), c2 = Math.nextAfter(1, Double.NEGATIVE_INFINITY);
    
    /**
     * Creates a new Wolfe line search with {@link #setC1(double) } set to 
     * {@code 1e-4} and {@link #setC2(double) } to {@code 0.9}
     */
    public WolfeNWLineSearch()
    {
        this(1e-4, 0.9);
    }

    /**
     * Creates a new Wolfe line search
     * @param c1 the sufficient decrease condition constant
     * @param c2 the curvature condition constant
     */
    public WolfeNWLineSearch(double c1, double c2)
    {
        setC1(c1);
        setC2(c2);
    }
    
    private AlphaInit initMethod = AlphaInit.METHOD1;
    
    double alpha_prev = -1, f_x_prev = Double.NaN, gradP_prev = Double.NaN;

    public enum AlphaInit
    {
        /**
         * Initializes the new α value via αprev 
         * ∇f(xprev)Tpprev/
         * ∇f(xcur)Tpcur
         */
        METHOD1, 
        /**
         * Initializes the new α value via 
         * 2( f(xcur)-f(xprev))/φ'(0)
         */
        METHOD2
    }

    /**
     * Sets the constant used for the sufficient decrease condition 
     * f(x+α p) ≤ f(x) + c1 α pT∇f(x)
     * 
*
* This value must always be less than {@link #setC2(double) } * @param c1 the sufficient decrease condition */ public void setC1(double c1) { if(c1 <= 0) throw new IllegalArgumentException("c1 must be greater than 0, not " + c1); else if(c1 >= c2) throw new IllegalArgumentException("c1 must be less than c2"); this.c1 = c1; } /** * Returns the sufficient decrease condition constant * @return the sufficient decrease condition constant */ public double getC1() { return c1; } /** * Sets the constant used for the curvature condition * pT ∇f(x+α p) ≥ c2 pT∇f(x) * @param c2 the curvature condition constant */ public void setC2(double c2) { if(c2 >= 1) throw new IllegalArgumentException("c2 must be less than 1, not " + c2); else if(c2 <= c1) throw new IllegalArgumentException("c2 must be greater than c1"); this.c2 = c2; } /** * Returns the curvature condition constant * @return the curvature condition constant */ public double getC2() { return c2; } @Override public double lineSearch(double alpha_max, Vec x_k, Vec x_grad, Vec p_k, Function f, FunctionVec fp, double f_x, double gradP, Vec x_alpha_pk, double[] fxApRet, Vec grad_x_alpha_pk, boolean parallel) { if(Double.isNaN(f_x)) f_x = f.f(x_k, parallel); if(Double.isNaN(gradP)) gradP = x_grad.dot(p_k); final double phi0 = f_x, phi0P = gradP; double alpha_cur = 1; if(!Double.isNaN(gradP_prev) && initMethod == AlphaInit.METHOD1) { alpha_cur = alpha_prev*gradP_prev/gradP; } else if(!Double.isNaN(f_x_prev) && initMethod == AlphaInit.METHOD2) { alpha_cur = 2*(f_x-f_x_prev)/phi0P; alpha_cur = min(1, 1.01*(alpha_cur)); } alpha_cur = max(alpha_cur, 1e-13); //2.5.13 from OPTIMIZATION THEORY AND METHODS Nonlinear Programming alpha_prev = 0; double phi_prev = phi0; double phi_prevP = phi0P; double valToUse = 0; x_k.copyTo(x_alpha_pk); for(int iter = 1; iter <= 10 && valToUse == 0; iter++) { //Evaluate φ(αi ); x_alpha_pk.mutableAdd(alpha_cur-alpha_prev, p_k); double phi_cur = f.f(x_alpha_pk, parallel); if(fxApRet != null) fxApRet[0] = phi_cur; double phi_curP = fp.f(x_alpha_pk, grad_x_alpha_pk, parallel).dot(p_k);//computed early b/c used in interpolation in zoom //if φ(αi)>φ(0)+c1 αi φ'(0) or[φ(αi)≥φ(αi−1) and i >1] if(phi_cur > phi0 + c1*alpha_cur*phi0P || (phi_cur >= phi_prev && iter > 1) ) { //α∗ ←zoom(αi−1,αi) and stop; valToUse = zoom(alpha_prev, alpha_cur, phi_prev, phi_cur, phi_prevP, phi_curP, phi0, phi0P, x_k, x_alpha_pk, p_k, f, fp, fxApRet, grad_x_alpha_pk, parallel); break; } //Evaluate φ'(αi ); //if |φ'(αi )| ≤ −c2φ'(0) if(abs(phi_curP) <= -c2*phi0P) { valToUse = alpha_cur;//set α∗ ← αi and stop; break; } //if φ'(αi ) ≥ 0 if(phi_curP >= 0) { //set α∗ ←zoom(αi,αi−1) and stop; valToUse = zoom(alpha_cur, alpha_prev, phi_cur, phi_prev, phi_curP, phi_prevP, phi0, phi0P, x_k, x_alpha_pk, p_k, f, fp, fxApRet, grad_x_alpha_pk, parallel); break; } //Choose αi+1 ∈(αi,αmax); ///err, just double it? alpha_prev = alpha_cur; phi_prev = phi_cur; phi_prevP = phi_curP; alpha_cur *= 2; if(alpha_cur >= alpha_max)//hit the limit { valToUse = alpha_max; break; } } alpha_prev = valToUse; f_x_prev = f_x; gradP_prev = gradP; return valToUse; } /** * * * @param alphaLow the value of alphaLow * @param alphaHi the value of alphaHi * @param phi_alphaLow the value of phi_alphaLow * @param phi_alphaHigh the value of phi_alphaHigh * @param phi_alphaLowP the value of phi_alphaLowP * @param phi_alphaHighP the value of phi_alphaHighP * @param phi0 the value of phi0 * @param phi0P the value of phi0P * @param x the value of x * @param x_alpha_p the value of x_alpha_p * @param p the value of p * @param f the value of f * @param fp the value of fp * @param fxApRet the value of fxApRet * @param grad_x_alpha_pk the value of grad_x_alpha_pk * @param parallel * @return the double */ private double zoom(double alphaLow, double alphaHi, double phi_alphaLow, double phi_alphaHigh, double phi_alphaLowP, double phi_alphaHighP, double phi0, double phi0P, Vec x, Vec x_alpha_p, Vec p, Function f, FunctionVec fp, double[] fxApRet, Vec grad_x_alpha_pk, boolean parallel) { double alpha_j = alphaLow; for(int iter = 0; iter < 10; iter++) { //try cubic interp eq (3.59) { double d1 = phi_alphaLowP+phi_alphaHighP-3*(phi_alphaLow-phi_alphaHigh)/(alphaLow-alphaHi); double d2 = signum(alphaHi-alphaLow)*pow(d1*d1-phi_alphaLowP*phi_alphaHighP, 0.5); alpha_j = alphaHi-(alphaHi-alphaLow)*(phi_alphaHighP+d2-d1)/(phi_alphaHighP-phi_alphaLowP+2*d2); } //check if we were too close to the edge if(alpha_j-(alphaHi-alphaLow)/2*0.1 < alphaLow || alpha_j > alphaHi*0.9) alpha_j = min(alphaLow, alphaHi) + abs(alphaHi-alphaLow)/2; x.copyTo(x_alpha_p); x_alpha_p.mutableAdd(alpha_j, p); //Evaluate φ(αj ); double phi_j = f.f(x_alpha_p, parallel); if(fxApRet != null) fxApRet[0] = phi_j; double phi_jP = fp.f(x_alpha_p, grad_x_alpha_pk, parallel).dot(p);//computed early //if φ(αj ) > φ(0) + c1αj φ'(0) or φ(αj ) ≥ φ(αlo) if(phi_j > phi0 + c1*alpha_j*phi0 || phi_j >= phi_alphaLow) { //αhi ←αj; alphaHi = alpha_j; phi_alphaHigh = phi_j; phi_alphaHighP = phi_jP; } else { //Evaluate φ'(αj ); //if |φ'(αj )| ≤ −c2φ'(0) if(abs(phi_jP) <= c2*phi0P) return alpha_j;//Set α∗ ← αj and stop; //if φ'(αj)(αhi −αlo)≥0 if(phi_jP*(alphaHi-alphaLow) >= 0) { //αhi ← αlo; alphaHi = alphaLow; phi_alphaHigh = phi_alphaLow; phi_alphaHighP = phi_alphaLowP; } //αlo ←αj; alphaLow = alpha_j; phi_alphaLow = phi_j; phi_alphaLowP = phi_jP; } } return alpha_j; } @Override public boolean updatesGrad() { return true; } @Override public WolfeNWLineSearch clone() { WolfeNWLineSearch clone = new WolfeNWLineSearch(c1, c2); clone.initMethod = this.initMethod; clone.alpha_prev = this.alpha_prev; clone.f_x_prev = this.f_x_prev; clone.gradP_prev = this.gradP_prev; return clone; } }

Ads help maintain this website.