BaseMultiStartMultivariateOptimizer.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      https://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */

  18. /*
  19.  * This is not the original file distributed by the Apache Software Foundation
  20.  * It has been modified by the Hipparchus project
  21.  */
  22. package org.hipparchus.optim;

  24. import org.hipparchus.exception.LocalizedCoreFormats;
  25. import org.hipparchus.exception.MathIllegalArgumentException;
  26. import org.hipparchus.exception.MathIllegalStateException;
  27. import org.hipparchus.random.RandomVectorGenerator;

  29. /**
  30.  * Base class multi-start optimizer for a multivariate function.
  31.  * <br>
  32.  * This class wraps an optimizer in order to use it several times in
  33.  * turn with different starting points (trying to avoid being trapped
  34.  * in a local extremum when looking for a global one).
  35.  * <em>It is not a "user" class.</em>
  36.  *
  37.  * @param <P> Type of the point/value pair returned by the optimization
  38.  * algorithm.
  39.  *
  40.  */
  41. public abstract class BaseMultiStartMultivariateOptimizer<P>
  42.     extends BaseMultivariateOptimizer<P> {
  43.     /** Underlying classical optimizer. */
  44.     private final BaseMultivariateOptimizer<P> optimizer;
  45.     /** Number of evaluations already performed for all starts. */
  46.     private int totalEvaluations;
  47.     /** Number of starts to go. */
  48.     private int starts;
  49.     /** Random generator for multi-start. */
  50.     private RandomVectorGenerator generator;
  51.     /** Optimization data. */
  52.     private OptimizationData[] optimData;
  53.     /**
  54.      * Location in {@link #optimData} where the updated maximum
  55.      * number of evaluations will be stored.
  56.      */
  57.     private int maxEvalIndex = -1;
  58.     /**
  59.      * Location in {@link #optimData} where the updated start value
  60.      * will be stored.
  61.      */
  62.     private int initialGuessIndex = -1;

  64.     /**
  65.      * Create a multi-start optimizer from a single-start optimizer.
  66.      * <p>
  67.      * Note that if there are bounds constraints (see {@link #getLowerBound()}
  68.      * and {@link #getUpperBound()}), then a simple rejection algorithm is used
  69.      * at each restart. This implies that the random vector generator should have
  70.      * a good probability to generate vectors in the bounded domain, otherwise the
  71.      * rejection algorithm will hit the {@link #getMaxEvaluations()} count without
  72.      * generating a proper restart point. Users must be take great care of the <a
  73.      * href="http://en.wikipedia.org/wiki/Curse_of_dimensionality">curse of dimensionality</a>.
  74.      * </p>
  75.      * @param optimizer Single-start optimizer to wrap.
  76.      * @param starts Number of starts to perform. If {@code starts == 1},
  77.      * the {@link #optimize(OptimizationData[]) optimize} will return the
  78.      * same solution as the given {@code optimizer} would return.
  79.      * @param generator Random vector generator to use for restarts.
  80.      * @throws MathIllegalArgumentException if {@code starts < 1}.
  81.      */
  82.     protected BaseMultiStartMultivariateOptimizer(final BaseMultivariateOptimizer<P> optimizer, final int starts,
  83.                                                   final RandomVectorGenerator generator) {
  84.         super(optimizer.getConvergenceChecker());

  86.         if (starts < 1) {
  87.             throw new MathIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL,
  88.                                                    starts, 1);
  89.         }

  91.         this.optimizer = optimizer;
  92.         this.starts = starts;
  93.         this.generator = generator;
  94.     }

  96.     /** {@inheritDoc} */
  97.     @Override
  98.     public int getEvaluations() {
  99.         return totalEvaluations;
  100.     }

  102.     /**
  103.      * Gets all the optima found during the last call to {@code optimize}.
  104.      * The optimizer stores all the optima found during a set of
  105.      * restarts. The {@code optimize} method returns the best point only.
  106.      * This method returns all the points found at the end of each starts,
  107.      * including the best one already returned by the {@code optimize} method.
  108.      * <br>
  109.      * The returned array as one element for each start as specified
  110.      * in the constructor. It is ordered with the results from the
  111.      * runs that did converge first, sorted from best to worst
  112.      * objective value (i.e in ascending order if minimizing and in
  113.      * descending order if maximizing), followed by {@code null} elements
  114.      * corresponding to the runs that did not converge. This means all
  115.      * elements will be {@code null} if the {@code optimize} method did throw
  116.      * an exception.
  117.      * This also means that if the first element is not {@code null}, it is
  118.      * the best point found across all starts.
  119.      * <br>
  120.      * The behaviour is undefined if this method is called before
  121.      * {@code optimize}; it will likely throw {@code NullPointerException}.
  122.      *
  123.      * @return an array containing the optima sorted from best to worst.
  124.      */
  125.     public abstract P[] getOptima();

  127.     /**
  128.      * {@inheritDoc}
  129.      *
  130.      * @throws MathIllegalStateException if {@code optData} does not contain an
  131.      * instance of {@link MaxEval} or {@link InitialGuess}.
  132.      */
  133.     @Override
  134.     public P optimize(OptimizationData... optData) {
  135.         // Store arguments in order to pass them to the internal optimizer.
  136.        optimData = optData.clone();
  137.         // Set up base class and perform computations.
  138.         return super.optimize(optData);
  139.     }

  141.     /** {@inheritDoc} */
  142.     @Override
  143.     protected P doOptimize() {
  144.         // Remove all instances of "MaxEval" and "InitialGuess" from the
  145.         // array that will be passed to the internal optimizer.
  146.         // The former is to enforce smaller numbers of allowed evaluations
  147.         // (according to how many have been used up already), and the latter
  148.         // to impose a different start value for each start.
  149.         for (int i = 0; i < optimData.length; i++) {
  150.             if (optimData[i] instanceof MaxEval) {
  151.                 optimData[i] = null;
  152.                 maxEvalIndex = i;
  153.             }
  154.             if (optimData[i] instanceof InitialGuess) {
  155.                 optimData[i] = null;
  156.                 initialGuessIndex = i;
  157.                 continue;
  158.             }
  159.         }
  160.         if (maxEvalIndex == -1) {
  161.             throw new MathIllegalStateException(LocalizedCoreFormats.ILLEGAL_STATE);
  162.         }
  163.         if (initialGuessIndex == -1) {
  164.             throw new MathIllegalStateException(LocalizedCoreFormats.ILLEGAL_STATE);
  165.         }

  167.         RuntimeException lastException = null;
  168.         totalEvaluations = 0;
  169.         clear();

  171.         final int maxEval = getMaxEvaluations();
  172.         final double[] min = getLowerBound();
  173.         final double[] max = getUpperBound();
  174.         final double[] startPoint = getStartPoint();

  176.         // Multi-start loop.
  177.         for (int i = 0; i < starts; i++) {
  178.             // CHECKSTYLE: stop IllegalCatch
  179.             try {
  180.                 // Decrease number of allowed evaluations.
  181.                 optimData[maxEvalIndex] = new MaxEval(maxEval - totalEvaluations);
  182.                 // New start value.
  183.                 double[] s = null;
  184.                 if (i == 0) {
  185.                     s = startPoint;
  186.                 } else {
  187.                     int attempts = 0;
  188.                     while (s == null) {
  189.                         if (attempts >= getMaxEvaluations()) {
  190.                             throw new MathIllegalStateException(LocalizedCoreFormats.MAX_COUNT_EXCEEDED,
  191.                                                                 getMaxEvaluations());
  192.                         }
  193.                         s = generator.nextVector();
  194.                         for (int k = 0; s != null && k < s.length; ++k) {
  195.                             if ((min != null && s[k] < min[k]) || (max != null && s[k] > max[k])) {
  196.                                 // reject the vector
  197.                                 s = null;
  198.                             }
  199.                         }
  200.                         ++attempts;
  201.                     }
  202.                 }
  203.                 optimData[initialGuessIndex] = new InitialGuess(s);
  204.                 // Optimize.
  205.                 final P result = optimizer.optimize(optimData);
  206.                 store(result);
  207.             } catch (RuntimeException mue) { // NOPMD - caching a RuntimeException is intentional here, it will be rethrown later
  208.                 lastException = mue;
  209.             }
  210.             // CHECKSTYLE: resume IllegalCatch

  212.             totalEvaluations += optimizer.getEvaluations();
  213.         }

  215.         final P[] optima = getOptima();
  216.         if (optima.length == 0) {
  217.             // All runs failed.
  218.             throw lastException; // Cannot be null if starts >= 1.
  219.         }

  221.         // Return the best optimum.
  222.         return optima[0];
  223.     }

  225.     /**
  226.      * Method that will be called in order to store each found optimum.
  227.      *
  228.      * @param optimum Result of an optimization run.
  229.      */
  230.     protected abstract void store(P optimum);
  231.     /**
  232.      * Method that will called in order to clear all stored optima.
  233.      */
  234.     protected abstract void clear();
  235. }
Created with JaCoCo 0.8.12.202403310830