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