Class BOBYQAOptimizer
java.lang.Object
org.apache.commons.math3.optim.BaseOptimizer<PointValuePair>
org.apache.commons.math3.optim.BaseMultivariateOptimizer<PointValuePair>
org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer
org.apache.commons.math3.optim.nonlinear.scalar.noderiv.BOBYQAOptimizer
Powell's BOBYQA algorithm. This implementation is translated and
adapted from the Fortran version available
here.
See
this paper for an introduction.
BOBYQA is particularly well suited for high dimensional problems where derivatives are not available. In most cases it outperforms the
BOBYQA is particularly well suited for high dimensional problems where derivatives are not available. In most cases it outperforms the
PowellOptimizer
significantly. Stochastic algorithms like
CMAESOptimizer
succeed more often than BOBYQA, but are more
expensive. BOBYQA could also be considered as a replacement of any
derivative-based optimizer when the derivatives are approximated by
finite differences.- Since:
- 3.0
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
Marker for code paths that are not explored with the current unit tests. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate ArrayRealVector
private Array2DRowRealMatrix
Last n columns of matrix H (where n is the dimension of the problem).private double[]
Differences between the upper and lower bounds.private ArrayRealVector
Current best values for the variables to be optimized.static final double
Default value forinitialTrustRegionRadius
: 10.0 .static final double
Default value forstoppingTrustRegionRadius
: 1.0E-8 .private ArrayRealVector
Values of the objective function at the interpolation points.private ArrayRealVector
Gradient of the quadratic model atoriginShift
+trustRegionCenterOffset
.private static final double
Constant 1/2.private double
initialTrustRegionRadius XXXprivate Array2DRowRealMatrix
Coordinates of the interpolation points relative tooriginShift
.private boolean
Goal type (minimize or maximize).private ArrayRealVector
Values of the Lagrange functions at a new point.private ArrayRealVector
DifferencesBaseMultivariateOptimizer.getLowerBound()
-originShift
.static final int
Minimum dimension of the problem: 2private static final double
Constant -1.private ArrayRealVector
Parameters of the implicit second derivatives of the quadratic model.private ArrayRealVector
Explicit second derivatives of the quadratic model.private ArrayRealVector
private final int
numberOfInterpolationPoints XXXprivate static final double
Constant 1.private static final double
Constant 1/1000.private static final double
Constant 1/8.private static final double
Constant 1/4.private static final double
Constant 1/10.private ArrayRealVector
Shift of origin that should reduce the contributions from rounding errors to values of the model and Lagrange functions.private static final double
Constant 16.private final double
stoppingTrustRegionRadius XXXprivate static final double
Constant 10.private ArrayRealVector
private int
Index of the interpolation point at the trust region center.private ArrayRealVector
Displacement fromoriginShift
of the trust region center.private static final double
Constant 2.private static final double
Constant 250.private ArrayRealVector
DifferencesBaseMultivariateOptimizer.getUpperBound()
-originShift
All the components of everytrustRegionCenterOffset
are going to satisfy the bounds
trustRegionCenterOffset
i ≤upperBound
i,
with appropriate equalities whentrustRegionCenterOffset
is on a constraint boundary.private static final double
Constant 0.private Array2DRowRealMatrix
Factorization of the leading npt square submatrix of H, this factorization being Z ZT, which provides both the correct rank and positive semi-definiteness.Fields inherited from class org.apache.commons.math3.optim.BaseOptimizer
evaluations, iterations
-
Constructor Summary
ConstructorsConstructorDescriptionBOBYQAOptimizer
(int numberOfInterpolationPoints) BOBYQAOptimizer
(int numberOfInterpolationPoints, double initialTrustRegionRadius, double stoppingTrustRegionRadius) -
Method Summary
Modifier and TypeMethodDescriptionprivate double[]
altmov
(int knew, double adelt) The arguments N, NPT, XPT, XOPT, BMAT, ZMAT, NDIM, SL and SU all have the same meanings as the corresponding arguments of BOBYQB.private double
bobyqa
(double[] lowerBound, double[] upperBound) This subroutine seeks the least value of a function of many variables, by applying a trust region method that forms quadratic models by interpolation.private double
bobyqb
(double[] lowerBound, double[] upperBound) The arguments N, NPT, X, XL, XU, RHOBEG, RHOEND, IPRINT and MAXFUN are identical to the corresponding arguments in SUBROUTINE BOBYQA.private static String
caller
(int n) protected PointValuePair
Performs the bulk of the optimization algorithm.private void
prelim
(double[] lowerBound, double[] upperBound) SUBROUTINE PRELIM sets the elements of XBASE, XPT, FVAL, GOPT, HQ, PQ, BMAT and ZMAT for the first iteration, and it maintains the values of NF and KOPT.private static void
private static void
printState
(int s) private void
setup
(double[] lowerBound, double[] upperBound) Performs validity checks.private double[]
trsbox
(double delta, ArrayRealVector gnew, ArrayRealVector xbdi, ArrayRealVector s, ArrayRealVector hs, ArrayRealVector hred) A version of the truncated conjugate gradient is applied.private void
update
(double beta, double denom, int knew) The arrays BMAT and ZMAT are updated, as required by the new position of the interpolation point that has the index KNEW.Methods inherited from class org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer
computeObjectiveValue, getGoalType, optimize, parseOptimizationData
Methods inherited from class org.apache.commons.math3.optim.BaseMultivariateOptimizer
getLowerBound, getStartPoint, getUpperBound
Methods inherited from class org.apache.commons.math3.optim.BaseOptimizer
getConvergenceChecker, getEvaluations, getIterations, getMaxEvaluations, getMaxIterations, incrementEvaluationCount, incrementIterationCount, optimize
-
Field Details
-
MINIMUM_PROBLEM_DIMENSION
public static final int MINIMUM_PROBLEM_DIMENSIONMinimum dimension of the problem: 2- See Also:
-
DEFAULT_INITIAL_RADIUS
public static final double DEFAULT_INITIAL_RADIUSDefault value forinitialTrustRegionRadius
: 10.0 .- See Also:
-
DEFAULT_STOPPING_RADIUS
public static final double DEFAULT_STOPPING_RADIUSDefault value forstoppingTrustRegionRadius
: 1.0E-8 .- See Also:
-
ZERO
private static final double ZEROConstant 0.- See Also:
-
ONE
private static final double ONEConstant 1.- See Also:
-
TWO
private static final double TWOConstant 2.- See Also:
-
TEN
private static final double TENConstant 10.- See Also:
-
SIXTEEN
private static final double SIXTEENConstant 16.- See Also:
-
TWO_HUNDRED_FIFTY
private static final double TWO_HUNDRED_FIFTYConstant 250.- See Also:
-
MINUS_ONE
private static final double MINUS_ONEConstant -1.- See Also:
-
HALF
private static final double HALFConstant 1/2.- See Also:
-
ONE_OVER_FOUR
private static final double ONE_OVER_FOURConstant 1/4.- See Also:
-
ONE_OVER_EIGHT
private static final double ONE_OVER_EIGHTConstant 1/8.- See Also:
-
ONE_OVER_TEN
private static final double ONE_OVER_TENConstant 1/10.- See Also:
-
ONE_OVER_A_THOUSAND
private static final double ONE_OVER_A_THOUSANDConstant 1/1000.- See Also:
-
numberOfInterpolationPoints
private final int numberOfInterpolationPointsnumberOfInterpolationPoints XXX -
initialTrustRegionRadius
private double initialTrustRegionRadiusinitialTrustRegionRadius XXX -
stoppingTrustRegionRadius
private final double stoppingTrustRegionRadiusstoppingTrustRegionRadius XXX -
isMinimize
private boolean isMinimizeGoal type (minimize or maximize). -
currentBest
Current best values for the variables to be optimized. The vector will be changed in-place to contain the values of the least calculated objective function values. -
boundDifference
private double[] boundDifferenceDifferences between the upper and lower bounds. -
trustRegionCenterInterpolationPointIndex
private int trustRegionCenterInterpolationPointIndexIndex of the interpolation point at the trust region center. -
bMatrix
Last n columns of matrix H (where n is the dimension of the problem). XXX "bmat" in the original code. -
zMatrix
Factorization of the leading npt square submatrix of H, this factorization being Z ZT, which provides both the correct rank and positive semi-definiteness. XXX "zmat" in the original code. -
interpolationPoints
Coordinates of the interpolation points relative tooriginShift
. XXX "xpt" in the original code. -
originShift
Shift of origin that should reduce the contributions from rounding errors to values of the model and Lagrange functions. XXX "xbase" in the original code. -
fAtInterpolationPoints
Values of the objective function at the interpolation points. XXX "fval" in the original code. -
trustRegionCenterOffset
Displacement fromoriginShift
of the trust region center. XXX "xopt" in the original code. -
gradientAtTrustRegionCenter
Gradient of the quadratic model atoriginShift
+trustRegionCenterOffset
. XXX "gopt" in the original code. -
lowerDifference
DifferencesBaseMultivariateOptimizer.getLowerBound()
-originShift
. All the components of everytrustRegionCenterOffset
are going to satisfy the bounds
lowerBound
i ≤trustRegionCenterOffset
i,
with appropriate equalities whentrustRegionCenterOffset
is on a constraint boundary. XXX "sl" in the original code. -
upperDifference
DifferencesBaseMultivariateOptimizer.getUpperBound()
-originShift
All the components of everytrustRegionCenterOffset
are going to satisfy the bounds
trustRegionCenterOffset
i ≤upperBound
i,
with appropriate equalities whentrustRegionCenterOffset
is on a constraint boundary. XXX "su" in the original code. -
modelSecondDerivativesParameters
Parameters of the implicit second derivatives of the quadratic model. XXX "pq" in the original code. -
newPoint
Point chosen by functiontrsbox
oraltmov
. UsuallyoriginShift
+newPoint
is the vector of variables for the next evaluation of the objective function. It also satisfies the constraints indicated inlowerDifference
andupperDifference
. XXX "xnew" in the original code. -
alternativeNewPoint
Alternative tonewPoint
, chosen byaltmov
. It may replacenewPoint
in order to increase the denominator in theupdating procedure
. XXX "xalt" in the original code. -
trialStepPoint
Trial step fromtrustRegionCenterOffset
which is usuallynewPoint
-trustRegionCenterOffset
. XXX "d__" in the original code. -
lagrangeValuesAtNewPoint
Values of the Lagrange functions at a new point. XXX "vlag" in the original code. -
modelSecondDerivativesValues
Explicit second derivatives of the quadratic model. XXX "hq" in the original code.
-
-
Constructor Details
-
BOBYQAOptimizer
public BOBYQAOptimizer(int numberOfInterpolationPoints) - Parameters:
numberOfInterpolationPoints
- Number of interpolation conditions. For a problem of dimensionn
, its value must be in the interval[n+2, (n+1)(n+2)/2]
. Choices that exceed2n+1
are not recommended.
-
BOBYQAOptimizer
public BOBYQAOptimizer(int numberOfInterpolationPoints, double initialTrustRegionRadius, double stoppingTrustRegionRadius) - Parameters:
numberOfInterpolationPoints
- Number of interpolation conditions. For a problem of dimensionn
, its value must be in the interval[n+2, (n+1)(n+2)/2]
. Choices that exceed2n+1
are not recommended.initialTrustRegionRadius
- Initial trust region radius.stoppingTrustRegionRadius
- Stopping trust region radius.
-
-
Method Details
-
doOptimize
Performs the bulk of the optimization algorithm.- Specified by:
doOptimize
in classBaseOptimizer<PointValuePair>
- Returns:
- the point/value pair giving the optimal value of the objective function.
-
bobyqa
private double bobyqa(double[] lowerBound, double[] upperBound) This subroutine seeks the least value of a function of many variables, by applying a trust region method that forms quadratic models by interpolation. There is usually some freedom in the interpolation conditions, which is taken up by minimizing the Frobenius norm of the change to the second derivative of the model, beginning with the zero matrix. The values of the variables are constrained by upper and lower bounds. The arguments of the subroutine are as follows. N must be set to the number of variables and must be at least two. NPT is the number of interpolation conditions. Its value must be in the interval [N+2,(N+1)(N+2)/2]. Choices that exceed 2*N+1 are not recommended. Initial values of the variables must be set in X(1),X(2),...,X(N). They will be changed to the values that give the least calculated F. For I=1,2,...,N, XL(I) and XU(I) must provide the lower and upper bounds, respectively, on X(I). The construction of quadratic models requires XL(I) to be strictly less than XU(I) for each I. Further, the contribution to a model from changes to the I-th variable is damaged severely by rounding errors if XU(I)-XL(I) is too small. RHOBEG and RHOEND must be set to the initial and final values of a trust region radius, so both must be positive with RHOEND no greater than RHOBEG. Typically, RHOBEG should be about one tenth of the greatest expected change to a variable, while RHOEND should indicate the accuracy that is required in the final values of the variables. An error return occurs if any of the differences XU(I)-XL(I), I=1,...,N, is less than 2*RHOBEG. MAXFUN must be set to an upper bound on the number of calls of CALFUN. The array W will be used for working space. Its length must be at least (NPT+5)*(NPT+N)+3*N*(N+5)/2.- Parameters:
lowerBound
- Lower bounds.upperBound
- Upper bounds.- Returns:
- the value of the objective at the optimum.
-
bobyqb
private double bobyqb(double[] lowerBound, double[] upperBound) The arguments N, NPT, X, XL, XU, RHOBEG, RHOEND, IPRINT and MAXFUN are identical to the corresponding arguments in SUBROUTINE BOBYQA. XBASE holds a shift of origin that should reduce the contributions from rounding errors to values of the model and Lagrange functions. XPT is a two-dimensional array that holds the coordinates of the interpolation points relative to XBASE. FVAL holds the values of F at the interpolation points. XOPT is set to the displacement from XBASE of the trust region centre. GOPT holds the gradient of the quadratic model at XBASE+XOPT. HQ holds the explicit second derivatives of the quadratic model. PQ contains the parameters of the implicit second derivatives of the quadratic model. BMAT holds the last N columns of H. ZMAT holds the factorization of the leading NPT by NPT submatrix of H, this factorization being ZMAT times ZMAT^T, which provides both the correct rank and positive semi-definiteness. NDIM is the first dimension of BMAT and has the value NPT+N. SL and SU hold the differences XL-XBASE and XU-XBASE, respectively. All the components of every XOPT are going to satisfy the bounds SL(I) .LEQ. XOPT(I) .LEQ. SU(I), with appropriate equalities when XOPT is on a constraint boundary. XNEW is chosen by SUBROUTINE TRSBOX or ALTMOV. Usually XBASE+XNEW is the vector of variables for the next call of CALFUN. XNEW also satisfies the SL and SU constraints in the way that has just been mentioned. XALT is an alternative to XNEW, chosen by ALTMOV, that may replace XNEW in order to increase the denominator in the updating of UPDATE. D is reserved for a trial step from XOPT, which is usually XNEW-XOPT. VLAG contains the values of the Lagrange functions at a new point X. They are part of a product that requires VLAG to be of length NDIM. W is a one-dimensional array that is used for working space. Its length must be at least 3*NDIM = 3*(NPT+N).- Parameters:
lowerBound
- Lower bounds.upperBound
- Upper bounds.- Returns:
- the value of the objective at the optimum.
-
altmov
private double[] altmov(int knew, double adelt) The arguments N, NPT, XPT, XOPT, BMAT, ZMAT, NDIM, SL and SU all have the same meanings as the corresponding arguments of BOBYQB. KOPT is the index of the optimal interpolation point. KNEW is the index of the interpolation point that is going to be moved. ADELT is the current trust region bound. XNEW will be set to a suitable new position for the interpolation point XPT(KNEW,.). Specifically, it satisfies the SL, SU and trust region bounds and it should provide a large denominator in the next call of UPDATE. The step XNEW-XOPT from XOPT is restricted to moves along the straight lines through XOPT and another interpolation point. XALT also provides a large value of the modulus of the KNEW-th Lagrange function subject to the constraints that have been mentioned, its main difference from XNEW being that XALT-XOPT is a constrained version of the Cauchy step within the trust region. An exception is that XALT is not calculated if all components of GLAG (see below) are zero. ALPHA will be set to the KNEW-th diagonal element of the H matrix. CAUCHY will be set to the square of the KNEW-th Lagrange function at the step XALT-XOPT from XOPT for the vector XALT that is returned, except that CAUCHY is set to zero if XALT is not calculated. GLAG is a working space vector of length N for the gradient of the KNEW-th Lagrange function at XOPT. HCOL is a working space vector of length NPT for the second derivative coefficients of the KNEW-th Lagrange function. W is a working space vector of length 2N that is going to hold the constrained Cauchy step from XOPT of the Lagrange function, followed by the downhill version of XALT when the uphill step is calculated. Set the first NPT components of W to the leading elements of the KNEW-th column of the H matrix.- Parameters:
knew
-adelt
-
-
prelim
private void prelim(double[] lowerBound, double[] upperBound) SUBROUTINE PRELIM sets the elements of XBASE, XPT, FVAL, GOPT, HQ, PQ, BMAT and ZMAT for the first iteration, and it maintains the values of NF and KOPT. The vector X is also changed by PRELIM. The arguments N, NPT, X, XL, XU, RHOBEG, IPRINT and MAXFUN are the same as the corresponding arguments in SUBROUTINE BOBYQA. The arguments XBASE, XPT, FVAL, HQ, PQ, BMAT, ZMAT, NDIM, SL and SU are the same as the corresponding arguments in BOBYQB, the elements of SL and SU being set in BOBYQA. GOPT is usually the gradient of the quadratic model at XOPT+XBASE, but it is set by PRELIM to the gradient of the quadratic model at XBASE. If XOPT is nonzero, BOBYQB will change it to its usual value later. NF is maintaned as the number of calls of CALFUN so far. KOPT will be such that the least calculated value of F so far is at the point XPT(KOPT,.)+XBASE in the space of the variables.- Parameters:
lowerBound
- Lower bounds.upperBound
- Upper bounds.
-
trsbox
private double[] trsbox(double delta, ArrayRealVector gnew, ArrayRealVector xbdi, ArrayRealVector s, ArrayRealVector hs, ArrayRealVector hred) A version of the truncated conjugate gradient is applied. If a line search is restricted by a constraint, then the procedure is restarted, the values of the variables that are at their bounds being fixed. If the trust region boundary is reached, then further changes may be made to D, each one being in the two dimensional space that is spanned by the current D and the gradient of Q at XOPT+D, staying on the trust region boundary. Termination occurs when the reduction in Q seems to be close to the greatest reduction that can be achieved. The arguments N, NPT, XPT, XOPT, GOPT, HQ, PQ, SL and SU have the same meanings as the corresponding arguments of BOBYQB. DELTA is the trust region radius for the present calculation, which seeks a small value of the quadratic model within distance DELTA of XOPT subject to the bounds on the variables. XNEW will be set to a new vector of variables that is approximately the one that minimizes the quadratic model within the trust region subject to the SL and SU constraints on the variables. It satisfies as equations the bounds that become active during the calculation. D is the calculated trial step from XOPT, generated iteratively from an initial value of zero. Thus XNEW is XOPT+D after the final iteration. GNEW holds the gradient of the quadratic model at XOPT+D. It is updated when D is updated. xbdi.get( is a working space vector. For I=1,2,...,N, the element xbdi.get((I) is set to -1.0, 0.0, or 1.0, the value being nonzero if and only if the I-th variable has become fixed at a bound, the bound being SL(I) or SU(I) in the case xbdi.get((I)=-1.0 or xbdi.get((I)=1.0, respectively. This information is accumulated during the construction of XNEW. The arrays S, HS and HRED are also used for working space. They hold the current search direction, and the changes in the gradient of Q along S and the reduced D, respectively, where the reduced D is the same as D, except that the components of the fixed variables are zero. DSQ will be set to the square of the length of XNEW-XOPT. CRVMIN is set to zero if D reaches the trust region boundary. Otherwise it is set to the least curvature of H that occurs in the conjugate gradient searches that are not restricted by any constraints. The value CRVMIN=-1.0D0 is set, however, if all of these searches are constrained.- Parameters:
delta
-gnew
-xbdi
-s
-hs
-hred
-
-
update
private void update(double beta, double denom, int knew) The arrays BMAT and ZMAT are updated, as required by the new position of the interpolation point that has the index KNEW. The vector VLAG has N+NPT components, set on entry to the first NPT and last N components of the product Hw in equation (4.11) of the Powell (2006) paper on NEWUOA. Further, BETA is set on entry to the value of the parameter with that name, and DENOM is set to the denominator of the updating formula. Elements of ZMAT may be treated as zero if their moduli are at most ZTEST. The first NDIM elements of W are used for working space.- Parameters:
beta
-denom
-knew
-
-
setup
private void setup(double[] lowerBound, double[] upperBound) Performs validity checks.- Parameters:
lowerBound
- Lower bounds (constraints) of the objective variables.upperBound
- Upperer bounds (constraints) of the objective variables.
-
caller
-
printState
private static void printState(int s) -
printMethod
private static void printMethod()
-