Class BOBYQAOptimizer

All Implemented Interfaces:
BaseMultivariateOptimizer<MultivariateFunction>, BaseMultivariateSimpleBoundsOptimizer<MultivariateFunction>, BaseOptimizer<PointValuePair>, MultivariateOptimizer

Deprecated.
As of 3.1 (to be removed in 4.0).
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 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
  • Field Details

    • MINIMUM_PROBLEM_DIMENSION

      public static final int MINIMUM_PROBLEM_DIMENSION
      Deprecated.
      Minimum dimension of the problem: 2
      See Also:
    • DEFAULT_INITIAL_RADIUS

      public static final double DEFAULT_INITIAL_RADIUS
      Deprecated.
      Default value for initialTrustRegionRadius: 10.0 .
      See Also:
    • DEFAULT_STOPPING_RADIUS

      public static final double DEFAULT_STOPPING_RADIUS
      Deprecated.
      Default value for stoppingTrustRegionRadius: 1.0E-8 .
      See Also:
    • ZERO

      private static final double ZERO
      Deprecated.
      Constant 0.
      See Also:
    • ONE

      private static final double ONE
      Deprecated.
      Constant 1.
      See Also:
    • TWO

      private static final double TWO
      Deprecated.
      Constant 2.
      See Also:
    • TEN

      private static final double TEN
      Deprecated.
      Constant 10.
      See Also:
    • SIXTEEN

      private static final double SIXTEEN
      Deprecated.
      Constant 16.
      See Also:
    • TWO_HUNDRED_FIFTY

      private static final double TWO_HUNDRED_FIFTY
      Deprecated.
      Constant 250.
      See Also:
    • MINUS_ONE

      private static final double MINUS_ONE
      Deprecated.
      Constant -1.
      See Also:
    • HALF

      private static final double HALF
      Deprecated.
      Constant 1/2.
      See Also:
    • ONE_OVER_FOUR

      private static final double ONE_OVER_FOUR
      Deprecated.
      Constant 1/4.
      See Also:
    • ONE_OVER_EIGHT

      private static final double ONE_OVER_EIGHT
      Deprecated.
      Constant 1/8.
      See Also:
    • ONE_OVER_TEN

      private static final double ONE_OVER_TEN
      Deprecated.
      Constant 1/10.
      See Also:
    • ONE_OVER_A_THOUSAND

      private static final double ONE_OVER_A_THOUSAND
      Deprecated.
      Constant 1/1000.
      See Also:
    • numberOfInterpolationPoints

      private final int numberOfInterpolationPoints
      Deprecated.
      numberOfInterpolationPoints XXX
    • initialTrustRegionRadius

      private double initialTrustRegionRadius
      Deprecated.
      initialTrustRegionRadius XXX
    • stoppingTrustRegionRadius

      private final double stoppingTrustRegionRadius
      Deprecated.
      stoppingTrustRegionRadius XXX
    • isMinimize

      private boolean isMinimize
      Deprecated.
      Goal type (minimize or maximize).
    • currentBest

      private ArrayRealVector currentBest
      Deprecated.
      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[] boundDifference
      Deprecated.
      Differences between the upper and lower bounds.
    • trustRegionCenterInterpolationPointIndex

      private int trustRegionCenterInterpolationPointIndex
      Deprecated.
      Index of the interpolation point at the trust region center.
    • bMatrix

      private Array2DRowRealMatrix bMatrix
      Deprecated.
      Last n columns of matrix H (where n is the dimension of the problem). XXX "bmat" in the original code.
    • zMatrix

      private Array2DRowRealMatrix zMatrix
      Deprecated.
      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

      private Array2DRowRealMatrix interpolationPoints
      Deprecated.
      Coordinates of the interpolation points relative to originShift. XXX "xpt" in the original code.
    • originShift

      private ArrayRealVector originShift
      Deprecated.
      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

      private ArrayRealVector fAtInterpolationPoints
      Deprecated.
      Values of the objective function at the interpolation points. XXX "fval" in the original code.
    • trustRegionCenterOffset

      private ArrayRealVector trustRegionCenterOffset
      Deprecated.
      Displacement from originShift of the trust region center. XXX "xopt" in the original code.
    • gradientAtTrustRegionCenter

      private ArrayRealVector gradientAtTrustRegionCenter
      Deprecated.
      Gradient of the quadratic model at originShift + trustRegionCenterOffset. XXX "gopt" in the original code.
    • lowerDifference

      private ArrayRealVector lowerDifference
      Deprecated.
      Differences BaseAbstractMultivariateOptimizer.getLowerBound() - originShift. All the components of every trustRegionCenterOffset are going to satisfy the bounds
      lowerBounditrustRegionCenterOffseti,
      with appropriate equalities when trustRegionCenterOffset is on a constraint boundary. XXX "sl" in the original code.
    • upperDifference

      private ArrayRealVector upperDifference
      Deprecated.
      Differences BaseAbstractMultivariateOptimizer.getUpperBound() - originShift All the components of every trustRegionCenterOffset are going to satisfy the bounds
      trustRegionCenterOffsetiupperBoundi,
      with appropriate equalities when trustRegionCenterOffset is on a constraint boundary. XXX "su" in the original code.
    • modelSecondDerivativesParameters

      private ArrayRealVector modelSecondDerivativesParameters
      Deprecated.
      Parameters of the implicit second derivatives of the quadratic model. XXX "pq" in the original code.
    • newPoint

      private ArrayRealVector newPoint
      Deprecated.
      Point chosen by function trsbox or altmov. Usually originShift + newPoint is the vector of variables for the next evaluation of the objective function. It also satisfies the constraints indicated in lowerDifference and upperDifference. XXX "xnew" in the original code.
    • alternativeNewPoint

      private ArrayRealVector alternativeNewPoint
      Deprecated.
      Alternative to newPoint, chosen by altmov. It may replace newPoint in order to increase the denominator in the updating procedure. XXX "xalt" in the original code.
    • trialStepPoint

      private ArrayRealVector trialStepPoint
      Deprecated.
      Trial step from trustRegionCenterOffset which is usually newPoint - trustRegionCenterOffset. XXX "d__" in the original code.
    • lagrangeValuesAtNewPoint

      private ArrayRealVector lagrangeValuesAtNewPoint
      Deprecated.
      Values of the Lagrange functions at a new point. XXX "vlag" in the original code.
    • modelSecondDerivativesValues

      private ArrayRealVector modelSecondDerivativesValues
      Deprecated.
      Explicit second derivatives of the quadratic model. XXX "hq" in the original code.
  • Constructor Details

    • BOBYQAOptimizer

      public BOBYQAOptimizer(int numberOfInterpolationPoints)
      Deprecated.
      Parameters:
      numberOfInterpolationPoints - Number of interpolation conditions. For a problem of dimension n, its value must be in the interval [n+2, (n+1)(n+2)/2]. Choices that exceed 2n+1 are not recommended.
    • BOBYQAOptimizer

      public BOBYQAOptimizer(int numberOfInterpolationPoints, double initialTrustRegionRadius, double stoppingTrustRegionRadius)
      Deprecated.
      Parameters:
      numberOfInterpolationPoints - Number of interpolation conditions. For a problem of dimension n, its value must be in the interval [n+2, (n+1)(n+2)/2]. Choices that exceed 2n+1 are not recommended.
      initialTrustRegionRadius - Initial trust region radius.
      stoppingTrustRegionRadius - Stopping trust region radius.
  • Method Details

    • doOptimize

      protected PointValuePair doOptimize()
      Deprecated.
      Perform the bulk of the optimization algorithm.
      Specified by:
      doOptimize in class BaseAbstractMultivariateOptimizer<MultivariateFunction>
      Returns:
      the point/value pair giving the optimal value of the objective function.
    • bobyqa

      private double bobyqa(double[] lowerBound, double[] upperBound)
      Deprecated.
      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)
      Deprecated.
      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)
      Deprecated.
      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)
      Deprecated.
      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)
      Deprecated.
      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)
      Deprecated.
      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)
      Deprecated.
      Performs validity checks.
      Parameters:
      lowerBound - Lower bounds (constraints) of the objective variables.
      upperBound - Upperer bounds (constraints) of the objective variables.
    • caller

      private static String caller(int n)
      Deprecated.
    • printState

      private static void printState(int s)
      Deprecated.
    • printMethod

      private static void printMethod()
      Deprecated.