BFGSUpdater.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.linear.Array2DRowRealMatrix;
import org.hipparchus.linear.MatrixUtils;
import org.hipparchus.linear.RealMatrix;
import org.hipparchus.linear.RealVector;
import org.hipparchus.util.FastMath;
import org.hipparchus.util.Precision;

/**
 * BFGS Hessian updater with dynamic damping and robustness improvements.
 * <p>
 * Manages Hessian updates for SQP solvers by:
 * </p>
 * <ul>
 * <li>Checking curvature condition</li>
 * <li>Applying dynamic damping if necessary</li>
 * <li>Skipping update if curvature still fails after damping</li>
 * <li>Soft regularization of diagonal entries on repeated failures</li>
 * <li>Automatic Hessian reset after configurable failures</li>
 * </ul>
 *
 * @since 4.1
 */
public class BFGSUpdater {

    /**
     * Damping factor.
     */
    private static final double GAMMA = 0.2;

    /**
     * trigger skip update for diagonal of Hessian.
     */
    private static final double SQRT_EPS = FastMath.sqrt(Precision.EPSILON);

    /** Reducing factor. */
    private static final double TH = 1.0e-3;

    /**
     * AutoScaling Flag.
     */
    private final boolean scale;

    /**
     * EPS.
     */
    private final double eps;

    /**
     * Tolerance for symmetric matrices decomposition.
     *
     * @since 4.1
     */
    private final double decompositionEpsilon;

    /**
     * Stored initial Hessian for resets.
     */
    private final RealMatrix initialH;

    /**
     * Current Cholesky factor L such that H = L·Lᵀ.
     */
    private RealMatrix L;

    /** Dimension. */
    private final int dim;

    /** Hessian factor. */
    private double    factor;

    /**
     * Creates a new updater.
     *
     * @param initialHess initial positive‐definite Hessian matrix
     * @param eps treshold to apply auto scale sty &lt; sqrt(eps)
     * @param autoScale true apply auto hessian rescaling
     * @param decompositionEpsilon tolerance for symmetric matrices
     * decomposition
     */
    public BFGSUpdater(final RealMatrix initialHess, final double eps, final boolean autoScale, final double decompositionEpsilon) {
        this.initialH = new Array2DRowRealMatrix(initialHess.getData());
        this.eps      = eps;
        this.scale    = autoScale;
        this.dim      = initialHess.getColumnDimension();
        this.factor   = 1.0;
        this.decompositionEpsilon = decompositionEpsilon;
        resetHessian();
    }

    /**
     * Returns the current Hessian matrix H = L·Lᵀ.
     *
     * @return current Hessian
     */
    public RealMatrix getHessian() {
        return L.multiplyTransposed(L);
    }

    /**
     * Updates the Hessian approximation using the BFGS formula.
     * <p>
     * If curvature condition fails, applies damping or regularization.
     * </p>
     *
     * @param s displacement vector (x<sub>k+1</sub> − x<sub>k</sub>)
     * @param y1 gradient difference (∇f<sub>k+1</sub> − ∇f<sub>k</sub>)
     * @return type of update:
     * <ul>
     *  <li>0: update is done</li>
     *  <li>1: sHs not positive (zero step), Hessian reset to identity</li>
     *  <li>2: sty not positive even after damping (non-finite input), skipped update</li>
     *  <li>3: downdate would lose positive definiteness, Hessian reset to factor*I</li>
     * </ul>
     */
    public int update(final RealVector s, final RealVector y1) {
        final RealVector Hs = L.operate(L.preMultiply(s));
        final double sHs = s.dotProduct(Hs);
        double sty = s.dotProduct(y1);
        if (sHs <= 0.0) {
            resetHessian();
            return 1;
        }

        boolean damped = false;
        RealVector y = y1;
        if (sty < GAMMA * sHs) {
            damped = true;
            final double denominator = sHs - sty;
            final double phi = (sHs - GAMMA * sHs) / denominator;
            y = y1.mapMultiply(phi).add(Hs.mapMultiply(1.0 - phi));
            sty = s.dotProduct(y);
        }

        if (!(sty > 0.0)) {
            return 2;
        }


        final double yy = y.dotProduct(y);
        factor =1.0;
        if (!damped && sty > Precision.SAFE_MIN) {
             factor = yy / sty;
        }
        factor = FastMath.max(TH, FastMath.min(1.0 / TH, factor));

        if (!rankOneUpdate(s, y, Hs, sHs, sty)) {
            return 3;
        }

        return 0;
    }

    /**
     * Resets the Hessian approximation to its initial value.
     */
    public void resetHessian() {
        L = MatrixUtils.createRealIdentityMatrix(dim);
    }

    /**
     * Resets the Hessian approximation with information on the curvature.
     *
     * @param gamma scale factor
     */
    public void resetHessian(double gamma) {
        final double sqrtGAMMA = FastMath.sqrt(gamma);
        L = MatrixUtils.createRealIdentityMatrix(dim).scalarMultiply(sqrtGAMMA);
    }

    /**
     * Resets the Hessian approximation with information on the curvature for external usage
     *
     */
    public void resetHessianFactor() {
        final double sqrtGAMMA = FastMath.sqrt(factor);
        L = MatrixUtils.createRealIdentityMatrix(dim).scalarMultiply(sqrtGAMMA);
    }

    /**
     * Performs a BFGS rank‐one update on L.
     *
     * @param s displacement vector
     * @param y gradient difference vector
     * @param Hs vector
     * @param sHs value
     * @param sty Sᵀ.y
     * @return true if update succeeded, false otherwise
     */
    private boolean rankOneUpdate(final RealVector s, final RealVector y, final RealVector Hs,
                                  final double sHs, final double sty) {

        final double rho = 1.0 / FastMath.sqrt(sty);
        final double theta = 1.0 / FastMath.sqrt(sHs);

        cholupdateLower(y, rho, +1);

        if (!cholupdateLower(Hs, theta, -1)) {

            resetHessian(factor);

            return false;
        }

        return true;
    }

    /**
     * Performs a rank-one Cholesky update/downdate on L.
     * <p>
     * Updates L such that A' = A + sigma * alpha² * u * uᵀ, without refactorization.
     * Uses a numerically robust variant based on Givens/hyperbolic rotations.
     * </p>
     *
     * @param u direction vector
     * @param alpha scaling factor applied to {@code u}
     * @param sigma +1 for update, -1 for downdate
     * @return true if resulting matrix remains SPD, false otherwise
     */
    private boolean cholupdateLower(final RealVector u, final double alpha, final int sigma) {
        final int n = u.getDimension();
        final double[] work = u.toArray();
        for (int i = 0; i < n; ++i) {
            work[i] *= alpha;
        }
        // --- Single global guard for downdate ---
    if (sigma < 0) {
        final double[] z = new double[n];

        // Solve L z = work
        for (int i = 0; i < n; ++i) {
            double sum = work[i];
            for (int j = 0; j < i; ++j) {
                sum -= L.getEntry(i, j) * z[j];
            }
            final double lii = L.getEntry(i, i);
            z[i] = sum / lii;
        }

        double znorm2 = 0.0;
        for (int i = 0; i < n; ++i) {
            znorm2 += z[i] * z[i];
        }

        if (znorm2 >= 1.0 - Precision.EPSILON) {
            return false;
        }
    }

        for (int k = 0; k < n; ++k) {
            final double lkk = L.getEntry(k, k);
            final double xk = work[k];

            double r;
            if (sigma > 0) {
                r = FastMath.hypot(lkk, xk);
            } else {
                double radicand = (lkk - xk) * (lkk + xk);
                r = radicand <= Precision.EPSILON ? SQRT_EPS : FastMath.sqrt(radicand);
            }


            final double c = r / lkk;
            final double s = xk / lkk;
            final double invC = 1.0 / c;

            L.setEntry(k, k, r);

            for (int i = k + 1; i < n; ++i) {
                final double lik = L.getEntry(i, k);
                final double xi = work[i];
                final double newLik = (lik + sigma * s * xi) * invC;
                final double newXi = c * xi - s * newLik;
                L.setEntry(i, k, newLik);
                work[i] = newXi;
            }
        }
        return true;
    }



    /**
     * Scales the Hessian H = L*L^T by a positive factor gamma,
     * by scaling the Cholesky factor L in-place.
     *
     * H_new = gamma * H
     * L_new = sqrt(gamma) * L
     *
     * @param gamma scaling factor (must be > 0)
     */
    private void scaleHessian(final double gamma) {

        final double s = FastMath.sqrt(gamma);

        final int n = L.getRowDimension();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                L.setEntry(i, j, s * L.getEntry(i, j));
            }
        }
    }

    /**
     * Returns the current lower-triangular Cholesky factor L.
     *
     * @return current lower-triangular Cholesky factor
     */
    public RealMatrix getL() {
        return L;
    }


}