LineSearch.java

/*
 * Licensed to the Hipparchus project under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The Hipparchus project licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.hipparchus.optim.nonlinear.vector.constrained;

import org.hipparchus.util.FastMath;

import java.util.LinkedList;
import java.util.Queue;
import org.hipparchus.util.Precision;

/**
 * Robust Line Search strategy.
 * <p>
 * This class manages monotone and non-monotone line search. Switching is
 * automatic after repeated failures of the monotone search.
 * </p>
 *
 * <p>
 * Typical parameter values used in Schittkowski's algorithms:
 * </p>
 * <ul>
 * <li>maxHistory = 5 to 10 (memory for non-monotone search)</li>
 * <li>sigma = 1e-4 or 1e-5 (Armijo sufficient decrease parameter)</li>
 * <li>beta = 0.5 (step reduction factor)</li>
 * <li>alphaMin (minimum allowed step length)</li>
 * <li>alphaMax = 1.0 (maximum allowed step length)</li>
 * <li>maxMonotoneFailures = 20 to 50 (failures before switching to
 * non-monotone)</li>
 * <li>maxBadSteps = 3 to 5 (allowed consecutive bad steps before Hessian
 * reset)</li>
 * </ul>
 *
 * @since 4.1
 */
public class LineSearch {

    /**
     * Maximum penalty history size.
     */
    private final int maxHistory;

    /**
     * Parameter for evaluation of Armijo condition for descend direction.
     */
    private final double sigma;

    /**
     * Step reduction factor.
     */
    private final double beta;

    /**
     * Minimum step length.
     */
    private final double alphaMin;

    /**
     * Max step length.
     */
    private double alphaMax;

    /**
     * Failures before switching to non-monotone.
     */
    private final int maxMonotoneFailures;

    /**
     * Allowed consecutive bad steps before Hessian reset.
     */
    private final int maxBadSteps;

    /**
     * Penalty history.
     */
    private final Queue<Double> history;

    /**
     * Number of iterations in line search.
     */
    private int searchCount;

    /**
     * Number of monotone search failures.
     */
    private int monotoneFailures;

    /**
     * Number of consecutive bad steps.
     */
    private int badStepCount;

    /**
     * Indicator for non-monotone search.
     */
    private boolean nonMonotoneEnabled;

    /**
     * Indicator for detected bad step.
     */
    private boolean badStepDetected;

    /**
     * Indicator for too many consecutive bad steps.
     */
    private boolean badStepFailed;

    /**
     * Simple constructor.
     *
     * @param minAlpha minimum step for line search
     * @param maxHistory maximum penalty history size
     * @param mu parameter for evaluation of Armijo condition for descend
     * direction
     * @param beta step reduction factor
     * @param maxMonotoneFailures failures before switching to non-monotone
     * @param maxBadSteps allowed consecutive bad steps before Hessian reset
     */
    public LineSearch(final double minAlpha, final int maxHistory, final double mu, final double beta,
            final int maxMonotoneFailures, final int maxBadSteps) {
        this.maxHistory = maxHistory;
        this.sigma = mu;
        this.beta = beta;
        this.alphaMin =minAlpha;
        this.maxMonotoneFailures = maxMonotoneFailures;
        this.maxBadSteps = maxBadSteps;
        this.history = new LinkedList<>();
        this.nonMonotoneEnabled = false;
        resetBadStepCount();
    }

    /**
     * Check if bad step has been detected.
     *
     * @return true if bad step has been detected
     */
    public boolean isBadStepDetected() {
        return badStepDetected;
    }

    /**
     * Check if too many consecutive bad step have been detected.
     *
     * @return true if too many consecutive bad step have been detected
     */
    public boolean isBadStepFailed() {
        return badStepFailed;
    }

    /**
     * Get number of iterations in line search.
     *
     * @return number of iterations in line search
     */
    public int getIteration() {
        return searchCount;
    }

    /**
     * Reset bad steps count and indicators.
     */
    public void resetBadStepCount() {
        badStepCount = 0;
        monotoneFailures = 0;
        badStepDetected = false;
        badStepFailed = false;
    }

    /**
     * Save penalty value when step is accepted for reusing in case of
     * non-monotone research.
     *
     * @param fx penalty
     */
    public void updateHistory(final double fx) {
        if (nonMonotoneEnabled) {
            history.add(fx);
            if (history.size() > maxHistory) {
                history.poll();
            }
        }
    }

    /**
     * Verify Armijo condition for accept step.
     *
     * @param fxNew penalty at candidate point x+dx*alpha
     * @param fxCurrent penalty at the current point
     * @param alpha step length
     * @param directionalDeriv penalty gradient
     * @return true or false
     */
    public boolean acceptStep(double fxNew, double fxCurrent, double alpha, double directionalDeriv) {
        double ref = fxCurrent;
        if (nonMonotoneEnabled) {
            for (double v : history) {
                ref = FastMath.max(ref, v);
            }

        }
        // alfaPenalty - currentPenalty > getSettings().getMu() * alpha * currentPenaltyGrad
        return fxNew - ref <= sigma * alpha * directionalDeriv;
    }

    /**
     * Mark Good Step if line search worked.
     */
    public void markGoodStep() {
        nonMonotoneEnabled = false;
        monotoneFailures = 0;
        badStepCount = 0;
        badStepDetected = false;
        badStepFailed = false;
    }

    /**
     * Mark Bad Step if line search failed.
     */
    private void markBadStep() {
        nonMonotoneEnabled = false;
        badStepCount++;
        badStepDetected = true;
        monotoneFailures = 0;
        if (badStepCount > maxBadSteps) {
            badStepFailed = true;
        }
    }

    /**
     * Update alpha qith quadratic curvature.
     *
     * @param alpha step length
     * @param fxCurrent penalty at the current point
     * @param fxNew penalty at candidate point x+dx*alpha
     * @param directionalDeriv penalty gradient
     * @return alpha
     */
    private double updateStepLength(final double alpha, final double fxCurrent, final double fxNew,
            final double directionalDeriv) {

        double numerator = alpha * directionalDeriv;
        double denominator = alpha * directionalDeriv - fxNew + fxCurrent;

        if (FastMath.abs(denominator) < Precision.SAFE_MIN) {
            return alpha * beta;
        }

        double alphaStar = 0.5 * alpha * numerator / denominator;

        return FastMath.max( alpha * beta, FastMath.min(alphaStar,0.5*alpha));

    }

    /**
     * Main line search process: tries monotone first, then non-monotone.
     *
     * @param f penalty function
     * @return alpha
     */
    public double search(final MeritFunctionL2 f) {
        searchCount = 0;
        final double fxCurrent        = f.value0();
        final double directionalDeriv = f.getGradient();

        alphaMax = 1.0;

        // Monotone Search
        nonMonotoneEnabled = false;
        double alpha = searchLoop(f, fxCurrent, directionalDeriv);
        if (!Double.isNaN(alpha)) {
            // monotone search succeeded
            return alpha;
        }

        // Non-monotone search
        nonMonotoneEnabled = true;
        alpha = searchLoop(f, fxCurrent, directionalDeriv);
        if (!Double.isNaN(alpha)) {
            // non-monotone search succeeded
            return alpha;
        }

        // last attempt before we declare bad step
        final double fxNew = f.value(alphaMin);
        searchCount++;
        if (acceptStep(fxNew, fxCurrent, alphaMin, directionalDeriv)) {
            markGoodStep();
            updateHistory(fxNew);
        } else {
            markBadStep();
        }
        if (badStepFailed) {
            f.value(0.0);
            return 0.0;
        }

        return alphaMin;
    }

    /**
     * Iterative search (either monotone or non-monotone).
     *
     * @param f penalty function
     * @param fxCurrent penalty function at current point
     * @param directionalDeriv directional derivative
     * @return accepted alpha, or NaN if search failed
     */
    private double searchLoop(final MeritFunctionL2 f, final double fxCurrent,
            final double directionalDeriv) {

        // start value for step length
        double alpha = alphaMax;

        // step length reduction loop
        while (alpha >= alphaMin) {

            final double fxNew = f.value(alpha);
            if (acceptStep(fxNew, fxCurrent, alpha, directionalDeriv)) {
                // we have found an acceptable step length
                markGoodStep();
                updateHistory(fxNew);
                return alpha;
            }

            // step length was not accepted, continue iteration
            alpha = updateStepLength(alpha, fxCurrent, fxNew, directionalDeriv);
            monotoneFailures++;
            if (monotoneFailures >= maxMonotoneFailures) {
                nonMonotoneEnabled = !nonMonotoneEnabled;
                break;
            }
            searchCount++;

        }

        // we failed to find an acceptable step length
        return Double.NaN;

    }

}