View Javadoc
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   */
17  
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;
23  
24  import org.hipparchus.exception.LocalizedCoreFormats;
25  import org.hipparchus.exception.MathIllegalArgumentException;
26  import org.hipparchus.exception.MathIllegalStateException;
27  import org.hipparchus.random.RandomVectorGenerator;
28  
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;
63  
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      public BaseMultiStartMultivariateOptimizer(final BaseMultivariateOptimizer<P> optimizer,
83                                                 final int starts,
84                                                 final RandomVectorGenerator generator) {
85          super(optimizer.getConvergenceChecker());
86  
87          if (starts < 1) {
88              throw new MathIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL,
89                                                     starts, 1);
90          }
91  
92          this.optimizer = optimizer;
93          this.starts = starts;
94          this.generator = generator;
95      }
96  
97      /** {@inheritDoc} */
98      @Override
99      public int getEvaluations() {
100         return totalEvaluations;
101     }
102 
103     /**
104      * Gets all the optima found during the last call to {@code optimize}.
105      * The optimizer stores all the optima found during a set of
106      * restarts. The {@code optimize} method returns the best point only.
107      * This method returns all the points found at the end of each starts,
108      * including the best one already returned by the {@code optimize} method.
109      * <br>
110      * The returned array as one element for each start as specified
111      * in the constructor. It is ordered with the results from the
112      * runs that did converge first, sorted from best to worst
113      * objective value (i.e in ascending order if minimizing and in
114      * descending order if maximizing), followed by {@code null} elements
115      * corresponding to the runs that did not converge. This means all
116      * elements will be {@code null} if the {@code optimize} method did throw
117      * an exception.
118      * This also means that if the first element is not {@code null}, it is
119      * the best point found across all starts.
120      * <br>
121      * The behaviour is undefined if this method is called before
122      * {@code optimize}; it will likely throw {@code NullPointerException}.
123      *
124      * @return an array containing the optima sorted from best to worst.
125      */
126     public abstract P[] getOptima();
127 
128     /**
129      * {@inheritDoc}
130      *
131      * @throws MathIllegalStateException if {@code optData} does not contain an
132      * instance of {@link MaxEval} or {@link InitialGuess}.
133      */
134     @Override
135     public P optimize(OptimizationData... optData) {
136         // Store arguments in order to pass them to the internal optimizer.
137        optimData = optData.clone();
138         // Set up base class and perform computations.
139         return super.optimize(optData);
140     }
141 
142     /** {@inheritDoc} */
143     @Override
144     protected P doOptimize() {
145         // Remove all instances of "MaxEval" and "InitialGuess" from the
146         // array that will be passed to the internal optimizer.
147         // The former is to enforce smaller numbers of allowed evaluations
148         // (according to how many have been used up already), and the latter
149         // to impose a different start value for each start.
150         for (int i = 0; i < optimData.length; i++) {
151             if (optimData[i] instanceof MaxEval) {
152                 optimData[i] = null;
153                 maxEvalIndex = i;
154             }
155             if (optimData[i] instanceof InitialGuess) {
156                 optimData[i] = null;
157                 initialGuessIndex = i;
158                 continue;
159             }
160         }
161         if (maxEvalIndex == -1) {
162             throw new MathIllegalStateException(LocalizedCoreFormats.ILLEGAL_STATE);
163         }
164         if (initialGuessIndex == -1) {
165             throw new MathIllegalStateException(LocalizedCoreFormats.ILLEGAL_STATE);
166         }
167 
168         RuntimeException lastException = null;
169         totalEvaluations = 0;
170         clear();
171 
172         final int maxEval = getMaxEvaluations();
173         final double[] min = getLowerBound();
174         final double[] max = getUpperBound();
175         final double[] startPoint = getStartPoint();
176 
177         // Multi-start loop.
178         for (int i = 0; i < starts; i++) {
179             // CHECKSTYLE: stop IllegalCatch
180             try {
181                 // Decrease number of allowed evaluations.
182                 optimData[maxEvalIndex] = new MaxEval(maxEval - totalEvaluations);
183                 // New start value.
184                 double[] s = null;
185                 if (i == 0) {
186                     s = startPoint;
187                 } else {
188                     int attempts = 0;
189                     while (s == null) {
190                         if (attempts >= getMaxEvaluations()) {
191                             throw new MathIllegalStateException(LocalizedCoreFormats.MAX_COUNT_EXCEEDED,
192                                                                 getMaxEvaluations());
193                         }
194                         s = generator.nextVector();
195                         for (int k = 0; s != null && k < s.length; ++k) {
196                             if ((min != null && s[k] < min[k]) || (max != null && s[k] > max[k])) {
197                                 // reject the vector
198                                 s = null;
199                             }
200                         }
201                         ++attempts;
202                     }
203                 }
204                 optimData[initialGuessIndex] = new InitialGuess(s);
205                 // Optimize.
206                 final P result = optimizer.optimize(optimData);
207                 store(result);
208             } catch (RuntimeException mue) { // NOPMD - caching a RuntimeException is intentional here, it will be rethrown later
209                 lastException = mue;
210             }
211             // CHECKSTYLE: resume IllegalCatch
212 
213             totalEvaluations += optimizer.getEvaluations();
214         }
215 
216         final P[] optima = getOptima();
217         if (optima.length == 0) {
218             // All runs failed.
219             throw lastException; // Cannot be null if starts >= 1.
220         }
221 
222         // Return the best optimum.
223         return optima[0];
224     }
225 
226     /**
227      * Method that will be called in order to store each found optimum.
228      *
229      * @param optimum Result of an optimization run.
230      */
231     protected abstract void store(P optimum);
232     /**
233      * Method that will called in order to clear all stored optima.
234      */
235     protected abstract void clear();
236 }