001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    
018    package org.apache.commons.math.optimization;
019    
020    import java.util.Arrays;
021    import java.util.Comparator;
022    
023    import org.apache.commons.math.FunctionEvaluationException;
024    import org.apache.commons.math.MathRuntimeException;
025    import org.apache.commons.math.analysis.DifferentiableMultivariateRealFunction;
026    import org.apache.commons.math.random.RandomVectorGenerator;
027    
028    /**
029     * Special implementation of the {@link DifferentiableMultivariateRealOptimizer} interface adding
030     * multi-start features to an existing optimizer.
031     * <p>
032     * This class wraps a classical optimizer to use it several times in
033     * turn with different starting points in order to avoid being trapped
034     * into a local extremum when looking for a global one.
035     * </p>
036     * @version $Revision: 811685 $ $Date: 2009-09-05 13:36:48 -0400 (Sat, 05 Sep 2009) $
037     * @since 2.0
038     */
039    public class MultiStartDifferentiableMultivariateRealOptimizer
040        implements DifferentiableMultivariateRealOptimizer {
041    
042        /** Underlying classical optimizer. */
043        private final DifferentiableMultivariateRealOptimizer optimizer;
044    
045        /** Maximal number of iterations allowed. */
046        private int maxIterations;
047    
048        /** Number of iterations already performed for all starts. */
049        private int totalIterations;
050    
051        /** Maximal number of evaluations allowed. */
052        private int maxEvaluations;
053    
054        /** Number of evaluations already performed for all starts. */
055        private int totalEvaluations;
056    
057        /** Number of gradient evaluations already performed for all starts. */
058        private int totalGradientEvaluations;
059    
060        /** Number of starts to go. */
061        private int starts;
062    
063        /** Random generator for multi-start. */
064        private RandomVectorGenerator generator;
065    
066        /** Found optima. */
067        private RealPointValuePair[] optima;
068    
069        /**
070         * Create a multi-start optimizer from a single-start optimizer
071         * @param optimizer single-start optimizer to wrap
072         * @param starts number of starts to perform (including the
073         * first one), multi-start is disabled if value is less than or
074         * equal to 1
075         * @param generator random vector generator to use for restarts
076         */
077        public MultiStartDifferentiableMultivariateRealOptimizer(final DifferentiableMultivariateRealOptimizer optimizer,
078                                                                 final int starts,
079                                                                 final RandomVectorGenerator generator) {
080            this.optimizer                = optimizer;
081            this.totalIterations          = 0;
082            this.totalEvaluations         = 0;
083            this.totalGradientEvaluations = 0;
084            this.starts                   = starts;
085            this.generator                = generator;
086            this.optima                   = null;
087            setMaxIterations(Integer.MAX_VALUE);
088            setMaxEvaluations(Integer.MAX_VALUE);
089        }
090    
091        /** Get all the optima found during the last call to {@link
092         * #optimize(DifferentiableMultivariateRealFunction, GoalType, double[])
093         * optimize}.
094         * <p>The optimizer stores all the optima found during a set of
095         * restarts. The {@link #optimize(DifferentiableMultivariateRealFunction,
096         * GoalType, double[]) optimize} method returns the best point only. This
097         * method returns all the points found at the end of each starts,
098         * including the best one already returned by the {@link
099         * #optimize(DifferentiableMultivariateRealFunction, GoalType, double[])
100         * optimize} method.
101         * </p>
102         * <p>
103         * The returned array as one element for each start as specified
104         * in the constructor. It is ordered with the results from the
105         * runs that did converge first, sorted from best to worst
106         * objective value (i.e in ascending order if minimizing and in
107         * descending order if maximizing), followed by and null elements
108         * corresponding to the runs that did not converge. This means all
109         * elements will be null if the {@link #optimize(DifferentiableMultivariateRealFunction,
110         * GoalType, double[]) optimize} method did throw a {@link
111         * org.apache.commons.math.ConvergenceException ConvergenceException}).
112         * This also means that if the first element is non null, it is the best
113         * point found across all starts.</p>
114         * @return array containing the optima
115         * @exception IllegalStateException if {@link #optimize(DifferentiableMultivariateRealFunction,
116         * GoalType, double[]) optimize} has not been called
117         */
118        public RealPointValuePair[] getOptima() throws IllegalStateException {
119            if (optima == null) {
120                throw MathRuntimeException.createIllegalStateException("no optimum computed yet");
121            }
122            return optima.clone();
123        }
124    
125        /** {@inheritDoc} */
126        public void setMaxIterations(int maxIterations) {
127            this.maxIterations = maxIterations;
128        }
129    
130        /** {@inheritDoc} */
131        public int getMaxIterations() {
132            return maxIterations;
133        }
134    
135        /** {@inheritDoc} */
136        public int getIterations() {
137            return totalIterations;
138        }
139    
140        /** {@inheritDoc} */
141        public void setMaxEvaluations(int maxEvaluations) {
142            this.maxEvaluations = maxEvaluations;
143        }
144    
145        /** {@inheritDoc} */
146        public int getMaxEvaluations() {
147            return maxEvaluations;
148        }
149    
150        /** {@inheritDoc} */
151        public int getEvaluations() {
152            return totalEvaluations;
153        }
154    
155        /** {@inheritDoc} */
156        public int getGradientEvaluations() {
157            return totalGradientEvaluations;
158        }
159    
160        /** {@inheritDoc} */
161        public void setConvergenceChecker(RealConvergenceChecker checker) {
162            optimizer.setConvergenceChecker(checker);
163        }
164    
165        /** {@inheritDoc} */
166        public RealConvergenceChecker getConvergenceChecker() {
167            return optimizer.getConvergenceChecker();
168        }
169    
170        /** {@inheritDoc} */
171        public RealPointValuePair optimize(final DifferentiableMultivariateRealFunction f,
172                                             final GoalType goalType,
173                                             double[] startPoint)
174            throws FunctionEvaluationException, OptimizationException {
175    
176            optima                   = new RealPointValuePair[starts];
177            totalIterations          = 0;
178            totalEvaluations         = 0;
179            totalGradientEvaluations = 0;
180    
181            // multi-start loop
182            for (int i = 0; i < starts; ++i) {
183    
184                try {
185                    optimizer.setMaxIterations(maxIterations - totalIterations);
186                    optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations);
187                    optima[i] = optimizer.optimize(f, goalType,
188                                                   (i == 0) ? startPoint : generator.nextVector());
189                } catch (FunctionEvaluationException fee) {
190                    optima[i] = null;
191                } catch (OptimizationException oe) {
192                    optima[i] = null;
193                }
194    
195                totalIterations          += optimizer.getIterations();
196                totalEvaluations         += optimizer.getEvaluations();
197                totalGradientEvaluations += optimizer.getGradientEvaluations();
198    
199            }
200    
201            // sort the optima from best to worst, followed by null elements
202            Arrays.sort(optima, new Comparator<RealPointValuePair>() {
203                public int compare(final RealPointValuePair o1, final RealPointValuePair o2) {
204                    if (o1 == null) {
205                        return (o2 == null) ? 0 : +1;
206                    } else if (o2 == null) {
207                        return -1;
208                    }
209                    final double v1 = o1.getValue();
210                    final double v2 = o2.getValue();
211                    return (goalType == GoalType.MINIMIZE) ?
212                            Double.compare(v1, v2) : Double.compare(v2, v1);
213                }
214            });
215    
216            if (optima[0] == null) {
217                throw new OptimizationException(
218                        "none of the {0} start points lead to convergence",
219                        starts);
220            }
221    
222            // return the found point given the best objective function value
223            return optima[0];
224    
225        }
226    
227    }