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    *      http://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  package org.apache.commons.math.optimization;
19  
20  import java.util.Arrays;
21  import java.util.Comparator;
22  
23  import org.apache.commons.math.ConvergenceException;
24  import org.apache.commons.math.FunctionEvaluationException;
25  import org.apache.commons.math.MathRuntimeException;
26  import org.apache.commons.math.analysis.DifferentiableMultivariateRealFunction;
27  import org.apache.commons.math.random.RandomVectorGenerator;
28  
29  /** 
30   * Special implementation of the {@link DifferentiableMultivariateRealOptimizer} interface adding
31   * multi-start features to an existing optimizer.
32   * <p>
33   * This class wraps a classical optimizer to use it several times in
34   * turn with different starting points in order to avoid being trapped
35   * into a local extremum when looking for a global one.
36   * </p>
37   * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
38   * @since 2.0
39   */
40  public class MultiStartDifferentiableMultivariateRealOptimizer
41      implements DifferentiableMultivariateRealOptimizer {
42  
43      /** Underlying classical optimizer. */
44      private final DifferentiableMultivariateRealOptimizer optimizer;
45  
46      /** Maximal number of iterations allowed. */
47      private int maxIterations;
48  
49      /** Number of iterations already performed for all starts. */
50      private int totalIterations;
51  
52      /** Maximal number of evaluations allowed. */
53      private int maxEvaluations;
54  
55      /** Number of evaluations already performed for all starts. */
56      private int totalEvaluations;
57  
58      /** Number of gradient evaluations already performed for all starts. */
59      private int totalGradientEvaluations;
60  
61      /** Number of starts to go. */
62      private int starts;
63  
64      /** Random generator for multi-start. */
65      private RandomVectorGenerator generator;
66  
67      /** Found optima. */
68      private RealPointValuePair[] optima;
69  
70      /**
71       * Create a multi-start optimizer from a single-start optimizer
72       * @param optimizer single-start optimizer to wrap
73       * @param starts number of starts to perform (including the
74       * first one), multi-start is disabled if value is less than or
75       * equal to 1
76       * @param generator random vector generator to use for restarts
77       */
78      public MultiStartDifferentiableMultivariateRealOptimizer(final DifferentiableMultivariateRealOptimizer optimizer,
79                                                               final int starts,
80                                                               final RandomVectorGenerator generator) {
81          this.optimizer                = optimizer;
82          this.totalIterations          = 0;
83          this.totalEvaluations         = 0;
84          this.totalGradientEvaluations = 0;
85          this.starts                   = starts;
86          this.generator                = generator;
87          this.optima                   = null;
88          setMaxIterations(Integer.MAX_VALUE);
89          setMaxEvaluations(Integer.MAX_VALUE);
90      }
91  
92      /** Get all the optima found during the last call to {@link
93       * #optimize(DifferentiableMultivariateRealFunction, GoalType, double[])
94       * optimize}.
95       * <p>The optimizer stores all the optima found during a set of
96       * restarts. The {@link #optimize(DifferentiableMultivariateRealFunction,
97       * GoalType, double[]) optimize} method returns the best point only. This
98       * method returns all the points found at the end of each starts,
99       * including the best one already returned by the {@link
100      * #optimize(DifferentiableMultivariateRealFunction, GoalType, double[])
101      * optimize} method.
102      * </p>
103      * <p>
104      * The returned array as one element for each start as specified
105      * in the constructor. It is ordered with the results from the
106      * runs that did converge first, sorted from best to worst
107      * objective value (i.e in ascending order if minimizing and in
108      * descending order if maximizing), followed by and null elements
109      * corresponding to the runs that did not converge. This means all
110      * elements will be null if the {@link #optimize(DifferentiableMultivariateRealFunction,
111      * GoalType, double[]) optimize} method did throw a {@link
112      * ConvergenceException ConvergenceException}). This also means that
113      * if the first element is non null, it is the best point found across
114      * all starts.</p>
115      * @return array containing the optima
116      * @exception IllegalStateException if {@link #optimize(DifferentiableMultivariateRealFunction,
117      * GoalType, double[]) optimize} has not been called
118      */
119     public RealPointValuePair[] getOptima() throws IllegalStateException {
120         if (optima == null) {
121             throw MathRuntimeException.createIllegalStateException("no optimum computed yet");
122         }
123         return optima.clone();
124     }
125 
126     /** {@inheritDoc} */
127     public void setMaxIterations(int maxIterations) {
128         this.maxIterations = maxIterations;
129     }
130 
131     /** {@inheritDoc} */
132     public int getMaxIterations() {
133         return maxIterations;
134     }
135 
136     /** {@inheritDoc} */
137     public int getIterations() {
138         return totalIterations;
139     }
140 
141     /** {@inheritDoc} */
142     public void setMaxEvaluations(int maxEvaluations) {
143         this.maxEvaluations = maxEvaluations;
144     }
145 
146     /** {@inheritDoc} */
147     public int getMaxEvaluations() {
148         return maxEvaluations;
149     }
150 
151     /** {@inheritDoc} */
152     public int getEvaluations() {
153         return totalEvaluations;
154     }
155 
156     /** {@inheritDoc} */
157     public int getGradientEvaluations() {
158         return totalGradientEvaluations;
159     }
160 
161     /** {@inheritDoc} */
162     public void setConvergenceChecker(RealConvergenceChecker checker) {
163         optimizer.setConvergenceChecker(checker);
164     }
165 
166     /** {@inheritDoc} */
167     public RealConvergenceChecker getConvergenceChecker() {
168         return optimizer.getConvergenceChecker();
169     }
170 
171     /** {@inheritDoc} */
172     public RealPointValuePair optimize(final DifferentiableMultivariateRealFunction f,
173                                          final GoalType goalType,
174                                          double[] startPoint)
175         throws FunctionEvaluationException, OptimizationException {
176 
177         optima                   = new RealPointValuePair[starts];
178         totalIterations          = 0;
179         totalEvaluations         = 0;
180         totalGradientEvaluations = 0;
181 
182         // multi-start loop
183         for (int i = 0; i < starts; ++i) {
184 
185             try {
186                 optimizer.setMaxIterations(maxIterations - totalIterations);
187                 optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations);
188                 optima[i] = optimizer.optimize(f, goalType,
189                                                (i == 0) ? startPoint : generator.nextVector());
190             } catch (FunctionEvaluationException fee) {
191                 optima[i] = null;
192             } catch (OptimizationException oe) {
193                 optima[i] = null;
194             }
195 
196             totalIterations          += optimizer.getIterations();
197             totalEvaluations         += optimizer.getEvaluations();
198             totalGradientEvaluations += optimizer.getGradientEvaluations();
199 
200         }
201 
202         // sort the optima from best to worst, followed by null elements
203         Arrays.sort(optima, new Comparator<RealPointValuePair>() {
204             public int compare(final RealPointValuePair o1, final RealPointValuePair o2) {
205                 if (o1 == null) {
206                     return (o2 == null) ? 0 : +1;
207                 } else if (o2 == null) {
208                     return -1;
209                 }
210                 final double v1 = o1.getValue();
211                 final double v2 = o2.getValue();
212                 return (goalType == GoalType.MINIMIZE) ?
213                         Double.compare(v1, v2) : Double.compare(v2, v1);
214             }
215         });
216 
217         if (optima[0] == null) {
218             throw new OptimizationException(
219                     "none of the {0} start points lead to convergence",
220                     starts);
221         }
222 
223         // return the found point given the best objective function value
224         return optima[0];
225 
226     }
227 
228 }