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.DifferentiableMultivariateVectorialFunction;
026    import org.apache.commons.math.random.RandomVectorGenerator;
027    
028    /**
029     * Special implementation of the {@link DifferentiableMultivariateVectorialOptimizer} 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 MultiStartDifferentiableMultivariateVectorialOptimizer
040        implements DifferentiableMultivariateVectorialOptimizer {
041    
042        /** Serializable version identifier. */
043        private static final long serialVersionUID = 9206382258980561530L;
044    
045        /** Underlying classical optimizer. */
046        private final DifferentiableMultivariateVectorialOptimizer optimizer;
047    
048        /** Maximal number of iterations allowed. */
049        private int maxIterations;
050    
051        /** Number of iterations already performed for all starts. */
052        private int totalIterations;
053    
054        /** Maximal number of evaluations allowed. */
055        private int maxEvaluations;
056    
057        /** Number of evaluations already performed for all starts. */
058        private int totalEvaluations;
059    
060        /** Number of jacobian evaluations already performed for all starts. */
061        private int totalJacobianEvaluations;
062    
063        /** Number of starts to go. */
064        private int starts;
065    
066        /** Random generator for multi-start. */
067        private RandomVectorGenerator generator;
068    
069        /** Found optima. */
070        private VectorialPointValuePair[] optima;
071    
072        /**
073         * Create a multi-start optimizer from a single-start optimizer
074         * @param optimizer single-start optimizer to wrap
075         * @param starts number of starts to perform (including the
076         * first one), multi-start is disabled if value is less than or
077         * equal to 1
078         * @param generator random vector generator to use for restarts
079         */
080        public MultiStartDifferentiableMultivariateVectorialOptimizer(
081                    final DifferentiableMultivariateVectorialOptimizer optimizer,
082                    final int starts,
083                    final RandomVectorGenerator generator) {
084            this.optimizer                = optimizer;
085            this.totalIterations          = 0;
086            this.totalEvaluations         = 0;
087            this.totalJacobianEvaluations = 0;
088            this.starts                   = starts;
089            this.generator                = generator;
090            this.optima                   = null;
091            setMaxIterations(Integer.MAX_VALUE);
092            setMaxEvaluations(Integer.MAX_VALUE);
093        }
094    
095        /** Get all the optima found during the last call to {@link
096         * #optimize(DifferentiableMultivariateVectorialFunction,
097         * double[], double[], double[]) optimize}.
098         * <p>The optimizer stores all the optima found during a set of
099         * restarts. The {@link #optimize(DifferentiableMultivariateVectorialFunction,
100         * double[], double[], double[]) optimize} method returns the
101         * best point only. This method returns all the points found at the
102         * end of each starts, including the best one already returned by the {@link
103         * #optimize(DifferentiableMultivariateVectorialFunction, double[],
104         * double[], double[]) optimize} method.
105         * </p>
106         * <p>
107         * The returned array as one element for each start as specified
108         * in the constructor. It is ordered with the results from the
109         * runs that did converge first, sorted from best to worst
110         * objective value (i.e in ascending order if minimizing and in
111         * descending order if maximizing), followed by and null elements
112         * corresponding to the runs that did not converge. This means all
113         * elements will be null if the {@link #optimize(DifferentiableMultivariateVectorialFunction,
114         * double[], double[], double[]) optimize} method did throw a {@link
115         * org.apache.commons.math.ConvergenceException ConvergenceException}).
116         * This also means that if the first element is non null, it is the best
117         * point found across all starts.</p>
118         * @return array containing the optima
119         * @exception IllegalStateException if {@link #optimize(DifferentiableMultivariateVectorialFunction,
120         * double[], double[], double[]) optimize} has not been called
121         */
122        public VectorialPointValuePair[] getOptima() throws IllegalStateException {
123            if (optima == null) {
124                throw MathRuntimeException.createIllegalStateException("no optimum computed yet");
125            }
126            return optima.clone();
127        }
128    
129        /** {@inheritDoc} */
130        public void setMaxIterations(int maxIterations) {
131            this.maxIterations = maxIterations;
132        }
133    
134        /** {@inheritDoc} */
135        public int getMaxIterations() {
136            return maxIterations;
137        }
138    
139        /** {@inheritDoc} */
140        public int getIterations() {
141            return totalIterations;
142        }
143    
144        /** {@inheritDoc} */
145        public void setMaxEvaluations(int maxEvaluations) {
146            this.maxEvaluations = maxEvaluations;
147        }
148    
149        /** {@inheritDoc} */
150        public int getMaxEvaluations() {
151            return maxEvaluations;
152        }
153    
154        /** {@inheritDoc} */
155        public int getEvaluations() {
156            return totalEvaluations;
157        }
158    
159        /** {@inheritDoc} */
160        public int getJacobianEvaluations() {
161            return totalJacobianEvaluations;
162        }
163    
164        /** {@inheritDoc} */
165        public void setConvergenceChecker(VectorialConvergenceChecker checker) {
166            optimizer.setConvergenceChecker(checker);
167        }
168    
169        /** {@inheritDoc} */
170        public VectorialConvergenceChecker getConvergenceChecker() {
171            return optimizer.getConvergenceChecker();
172        }
173    
174        /** {@inheritDoc} */
175        public VectorialPointValuePair optimize(final DifferentiableMultivariateVectorialFunction f,
176                                                final double[] target, final double[] weights,
177                                                final double[] startPoint)
178            throws FunctionEvaluationException, OptimizationException, IllegalArgumentException {
179    
180            optima                   = new VectorialPointValuePair[starts];
181            totalIterations          = 0;
182            totalEvaluations         = 0;
183            totalJacobianEvaluations = 0;
184    
185            // multi-start loop
186            for (int i = 0; i < starts; ++i) {
187    
188                try {
189                    optimizer.setMaxIterations(maxIterations - totalIterations);
190                    optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations);
191                    optima[i] = optimizer.optimize(f, target, weights,
192                                                   (i == 0) ? startPoint : generator.nextVector());
193                } catch (FunctionEvaluationException fee) {
194                    optima[i] = null;
195                } catch (OptimizationException oe) {
196                    optima[i] = null;
197                }
198    
199                totalIterations          += optimizer.getIterations();
200                totalEvaluations         += optimizer.getEvaluations();
201                totalJacobianEvaluations += optimizer.getJacobianEvaluations();
202    
203            }
204    
205            // sort the optima from best to worst, followed by null elements
206            Arrays.sort(optima, new Comparator<VectorialPointValuePair>() {
207                public int compare(final VectorialPointValuePair o1, final VectorialPointValuePair o2) {
208                    if (o1 == null) {
209                        return (o2 == null) ? 0 : +1;
210                    } else if (o2 == null) {
211                        return -1;
212                    }
213                    return Double.compare(weightedResidual(o1), weightedResidual(o2));
214                }
215                private double weightedResidual(final VectorialPointValuePair pv) {
216                    final double[] value = pv.getValueRef();
217                    double sum = 0;
218                    for (int i = 0; i < value.length; ++i) {
219                        final double ri = value[i] - target[i];
220                        sum += weights[i] * ri * ri;
221                    }
222                    return sum;
223                }
224            });
225    
226            if (optima[0] == null) {
227                throw new OptimizationException(
228                        "none of the {0} start points lead to convergence",
229                        starts);
230            }
231    
232            // return the found point given the best objective function value
233            return optima[0];
234    
235        }
236    
237    }