Package elki.math.linearalgebra

Class ConstrainedQuadraticProblemSolver

  • public class ConstrainedQuadraticProblemSolver
extends java.lang.Object
    Solve a constrained quadratic equation in the form \( \tfrac12 x^T A x + b^T x + c \) constrained by a bounding box.

    Works by recursion over the dimensions, searches the different possible outcomes until it finds the best solution.

    Since:
    0.8.0
    Author:
    Robert Gehde

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void calculateLinearDerivativeLimits​(double[][] a, double[] b, double[] min, double[] max, int dim, double[] buf)
      Calculates the min and max value of a linear derivative of a quadratic function in the bounding box.
      private double computeMaximumPossibleFuncValue​(double[][] a, double[] b, double c, double[] min, double[] max)
      Calculates the maximum possible function value for a constrained quadratic function.
      private static boolean contains​(double[] min, double[] max, double[] point)
      Checks if the point is inside or on the bounds of this bounding box
      private double evaluateConstrainedQuadraticFunction​(double[][] a, double[] b, double c, double[] min, double[] max, ConstrainedQuadraticProblemSolver.DimensionState[] dimensionStates, boolean cutoffCheck, double[] result, double resultValue)
      Main recursive function.
      private double evaluateConstrainedQuadraticFunction1D​(double a, double b, double c, double lowerBound, double upperBound, double[] result, double resultValue)
      Finds the maximum for a 1d constrained quadratic function.
      private static double evaluateQuadraticFormula​(double[][] a, double[] b, double c, double[] point)
      calculate \( \tfrac12 x^T A x + x^t b + c \) for the given values.
      private void expandNewSolution​(double[] outbox, double[] inbox, int insert, double insertValue)
      Expands the redRes to a problem with dim+1 and saves it into result
      private int findLimitedDimensionWithDerivative​(double[][] a, double[] b, double[] min, double[] max)
      Find the first dimension where the partial derivative wrt. that dimension is nonnegative or nonpositive.
      private double[] findMaximumWithFunctionValue​(double[][] a, double[] b)
      Finds the argmax for \( \tfrac12 A x^2 + b x \).
      private static void reduceConstraints​(double[] inmin, double[] inmax, double[] outmin, double[] outmax, ConstrainedQuadraticProblemSolver.DimensionState[] instates, ConstrainedQuadraticProblemSolver.DimensionState[] outstates, int omit)
      Reduces the constrains to a problem with dim-1
      private static double reduceEquation​(double[][] a, double[] b, double c, double[][] redA, double[] redB, int reducedDim, double reduceToValue)
      Reduces the equation/function the a problem with dim-1
      private double[] reduceSolution​(double[] result, int omit)
      Reduce the solution to a problem with dim-1
      double solve​(double[][] a, double[] b, double c, double[] min, double[] max, double[] argmaxPoint)
      Calculate \( 0.5 x^T A x + b + c \) we use it in KDTrees with \( b = (0)^d \) and \( c = 0 \).
      private double startReducedProblem​(double[][] a, double[] b, double c, double[] min, double[] max, ConstrainedQuadraticProblemSolver.DimensionState[] dimStates, int reducedDim, ConstrainedQuadraticProblemSolver.DimensionState reducedTo, double[] result, double resultValue)
      This function reduces the quadratic problem (given with a,b,c, bounds and dimState) with the information given in reducedDim and reducedTo.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • ConstrainedQuadraticProblemSolver

        public ConstrainedQuadraticProblemSolver​(int dim)
        Constructor.
        Parameters:
        dim - Maximum dimensionality (for the cache).

    • Method Detail

      • solve

        public double solve​(double[][] a,
                    double[] b,
                    double c,
                    double[] min,
                    double[] max,
                    double[] argmaxPoint)
        Calculate \( 0.5 x^T A x + b + c \) we use it in KDTrees with \( b = (0)^d \) and \( c = 0 \). If you use it like this you can multiply the result with 2 to get \( x^T A x + b + c \).
        Parameters:
        a - a coefficient matrix of the function
        b - b coefficient vector of the function
        c - c coefficient of the function
        min - Lower constraints
        max - Upper constraints
        argmaxPoint - point with the maximum

      • findLimitedDimensionWithDerivative

        private int findLimitedDimensionWithDerivative​(double[][] a,
                                               double[] b,
                                               double[] min,
                                               double[] max)
        Find the first dimension where the partial derivative wrt. that dimension is nonnegative or nonpositive. If the derivative is nonnegative (lo ≥0) it will be driven to the upper limit and vice versa.

        This does NOT mean that the non-found dimensions are not driven to a limit. This is just an implication, not an equivalence

        Parameters:
        a - a coefficient matrix of the function
        b - b coefficient vector of the function
        min - Lower constraints
        max - Upper constraints
        Returns:
        0 if none, dim + 1 if lo, -dim-1 if hi

      • calculateLinearDerivativeLimits

        private void calculateLinearDerivativeLimits​(double[][] a,
                                             double[] b,
                                             double[] min,
                                             double[] max,
                                             int dim,
                                             double[] buf)
        Calculates the min and max value of a linear derivative of a quadratic function in the bounding box. The function is of the form \( 0.5 A x^2 + b x + c \).
        Parameters:
        a - gradient/slope
        b - y axis crossing
        min - Lower constraints
        max - Upper constraints
        dim - dimension of interest
        buf - Return buffer

      • computeMaximumPossibleFuncValue

        private double computeMaximumPossibleFuncValue​(double[][] a,
                                               double[] b,
                                               double c,
                                               double[] min,
                                               double[] max)
        Calculates the maximum possible function value for a constrained quadratic function. This function value does not need to exist, it is just an upper limit.
        Parameters:
        a - a coefficient matrix of the function
        b - b coefficient vector of the function
        c - c coefficient of the function
        min - Lower constraints
        max - Upper constraints
        Returns:
        The maximum Function value

      • evaluateConstrainedQuadraticFunction

        private double evaluateConstrainedQuadraticFunction​(double[][] a,
                                                    double[] b,
                                                    double c,
                                                    double[] min,
                                                    double[] max,
                                                    ConstrainedQuadraticProblemSolver.DimensionState[] dimensionStates,
                                                    boolean cutoffCheck,
                                                    double[] result,
                                                    double resultValue)
        Main recursive function. We calculate \( \frac12 x^T A x + bx + c \) and only update the result array if we have a better result
        Parameters:
        a - a coefficient matrix of the function
        b - b coefficient vector of the function
        c - c coefficient of the function
        min - Lower constraints
        max - Upper constraints
        dimensionStates - Current calculation state of the dimensions
        cutoffCheck - Flag if a cutoff check should be performed

      • evaluateConstrainedQuadraticFunction1D

        private double evaluateConstrainedQuadraticFunction1D​(double a,
                                                      double b,
                                                      double c,
                                                      double lowerBound,
                                                      double upperBound,
                                                      double[] result,
                                                      double resultValue)
        Finds the maximum for a 1d constrained quadratic function. If a new maximum is found, the argmax contained in result will be overwritten with the new argmax.
        Parameters:
        a - a coefficient matrix of the function
        b - b coefficient vector of the function
        c - c coefficient of the function
        lowerBound - lower bound of valid input
        upperBound - upper bound of valid input
        result - the - so far - argmax
        resultValue - the - so far - max
        Returns:
        the new max

      • expandNewSolution

        private void expandNewSolution​(double[] outbox,
                               double[] inbox,
                               int insert,
                               double insertValue)
        Expands the redRes to a problem with dim+1 and saves it into result
        Parameters:
        outbox - the result
        inbox - the the reduced result
        insert - the dimension that was reduced to gain redRes
        insertValue - the value the dimension was reduced to to gain redRes

      • reduceSolution

        private double[] reduceSolution​(double[] result,
                                int omit)
        Reduce the solution to a problem with dim-1
        Parameters:
        result - result of the array
        omit - dimension to omit
        Returns:
        reduced result

      • reduceConstraints

        private static void reduceConstraints​(double[] inmin,
                                      double[] inmax,
                                      double[] outmin,
                                      double[] outmax,
                                      ConstrainedQuadraticProblemSolver.DimensionState[] instates,
                                      ConstrainedQuadraticProblemSolver.DimensionState[] outstates,
                                      int omit)
        Reduces the constrains to a problem with dim-1
        Parameters:
        inmin - Input minima
        inmax - Input maxima
        outmin - Output minima
        outmax - Output maxima
        instates - dimension states of the problem
        outstates - result array for dimension states
        omit - dimension to omit

      • reduceEquation

        private static double reduceEquation​(double[][] a,
                                     double[] b,
                                     double c,
                                     double[][] redA,
                                     double[] redB,
                                     int reducedDim,
                                     double reduceToValue)
        Reduces the equation/function the a problem with dim-1
        Parameters:
        a - a coefficient matrix of the function
        b - b coefficient vector of the function
        c - c coefficient of the function
        redA - reduced a result array
        redB - reduced b result array
        reducedDim - dimension to reduce
        reduceToValue - state to reduce the dimension to
        Returns:
        reduced c

      • findMaximumWithFunctionValue

        private double[] findMaximumWithFunctionValue​(double[][] a,
                                              double[] b)
        Finds the argmax for \( \tfrac12 A x^2 + b x \).
        Parameters:
        a - coefficient matrix A of the function
        b - coefficient vector b of the function
        Returns:
        the argmax of the given function

      • evaluateQuadraticFormula

        private static double evaluateQuadraticFormula​(double[][] a,
                                               double[] b,
                                               double c,
                                               double[] point)
        calculate \( \tfrac12 x^T A x + x^t b + c \) for the given values.
        Parameters:
        a - coefficient matrix A of the function
        b - coefficient vector b of the function
        c - coefficient scalar c of the function
        point - x to calculate the function at
        Returns:
        function value

      • contains

        private static boolean contains​(double[] min,
                                double[] max,
                                double[] point)
        Checks if the point is inside or on the bounds of this bounding box
        Parameters:
        min - Lower constraints
        max - Upper constraints
        point - point to check
        Returns:
        true if point is weakly inside bounds