• java.lang.Object

• 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
• ### Nested Class Summary

Nested Classes
Modifier and Type Class Description
private static class  ConstrainedQuadraticProblemSolver.DimensionState
Describes the calculation state of a Dimension
private static class  ConstrainedQuadraticProblemSolver.ProblemData
Contains arrays for a specific size needed for the problem calculation using this object saves the creation of all those arrays, because we can just reuse them.
• ### Field Summary

Fields
Modifier and Type Field Description
private ConstrainedQuadraticProblemSolver.ProblemData[] cache
Cache object
• ### Constructor Summary

Constructors
Constructor Description
ConstrainedQuadraticProblemSolver​(int dim)
Constructor.
• ### Method Summary

All 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
• ### Field Detail

• #### cache

private ConstrainedQuadraticProblemSolver.ProblemData[] cache
Cache object
• ### Constructor Detail

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

private double evaluateConstrainedQuadraticFunction​(double[][] a,
double[] b,
double c,
double[] min,
double[] max,
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

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
• #### startReducedProblem

private double startReducedProblem​(double[][] a,
double[] b,
double c,
double[] min,
double[] max,
int reducedDim,
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. It will then call evaluateConstrainedQuadraticFunction(double[][],double[],double,double[],double[],elki.math.linearalgebra.ConstrainedQuadraticProblemSolver.DimensionState[],boolean,double[],double) to continue evaluation.
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
dimStates - Current calculation state of the dimensions
reducedDim - the dimension to reduce
reducedTo - the state the dimension is reduced to
result - the current argmax
resultValue - the current max
Returns:
the new max value
• #### 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,
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

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