    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.math3.optimization;
    019
    020    import java.util.Arrays;
    021    import java.util.Comparator;
    022
    023    import org.apache.commons.math3.analysis.MultivariateVectorFunction;
    024    import org.apache.commons.math3.exception.ConvergenceException;
    025    import org.apache.commons.math3.exception.MathIllegalStateException;
    026    import org.apache.commons.math3.exception.NotStrictlyPositiveException;
    027    import org.apache.commons.math3.exception.NullArgumentException;
    028    import org.apache.commons.math3.exception.util.LocalizedFormats;
    029    import org.apache.commons.math3.random.RandomVectorGenerator;
    030
    031    /**
    032     * Base class for all implementations of a multi-start optimizer.
    033     *
    034     * This interface is mainly intended to enforce the internal coherence of
    035     * Commons-Math. Users of the API are advised to base their code on
    036     * {@link DifferentiableMultivariateVectorMultiStartOptimizer}.
    037     *
    038     * @param <FUNC> Type of the objective function to be optimized.
    039     *
    040     * @version $Id: BaseMultivariateVectorMultiStartOptimizer.java 1422230 2012-12-15 12:11:13Z erans $
    041     * @deprecated As of 3.1 (to be removed in 4.0).
    042     * @since 3.0
    043     */
    044    @Deprecated
    045    public class BaseMultivariateVectorMultiStartOptimizer<FUNC extends MultivariateVectorFunction>
    046        implements BaseMultivariateVectorOptimizer<FUNC> {
    047        /** Underlying classical optimizer. */
    048        private final BaseMultivariateVectorOptimizer<FUNC> optimizer;
    049        /** Maximal number of evaluations allowed. */
    050        private int maxEvaluations;
    051        /** Number of evaluations already performed for all starts. */
    052        private int totalEvaluations;
    053        /** Number of starts to go. */
    054        private int starts;
    055        /** Random generator for multi-start. */
    056        private RandomVectorGenerator generator;
    057        /** Found optima. */
    058        private PointVectorValuePair[] optima;
    059
    060        /**
    061         * Create a multi-start optimizer from a single-start optimizer.
    062         *
    063         * @param optimizer Single-start optimizer to wrap.
    064         * @param starts Number of starts to perform. If {@code starts == 1},
    065         * the {@link #optimize(int,MultivariateVectorFunction,double[],double[],double[])
    066         * optimize} will return the same solution as {@code optimizer} would.
    067         * @param generator Random vector generator to use for restarts.
    068         * @throws NullArgumentException if {@code optimizer} or {@code generator}
    069         * is {@code null}.
    070         * @throws NotStrictlyPositiveException if {@code starts < 1}.
    071         */
    072        protected BaseMultivariateVectorMultiStartOptimizer(final BaseMultivariateVectorOptimizer<FUNC> optimizer,
    073                                                               final int starts,
    074                                                               final RandomVectorGenerator generator) {
    075            if (optimizer == null ||
    076                generator == null) {
    077                throw new NullArgumentException();
    078            }
    079            if (starts < 1) {
    080                throw new NotStrictlyPositiveException(starts);
    081            }
    082
    083            this.optimizer = optimizer;
    084            this.starts = starts;
    085            this.generator = generator;
    086        }
    087
    088        /**
    089         * Get all the optima found during the last call to {@link
    090         * #optimize(int,MultivariateVectorFunction,double[],double[],double[]) optimize}.
    091         * The optimizer stores all the optima found during a set of
    092         * restarts. The {@link #optimize(int,MultivariateVectorFunction,double[],double[],double[])
    093         * optimize} method returns the best point only. This method
    094         * returns all the points found at the end of each starts, including
    095         * the best one already returned by the {@link
    096         * #optimize(int,MultivariateVectorFunction,double[],double[],double[]) optimize} method.
    097         * <br/>
    098         * The returned array as one element for each start as specified
    099         * in the constructor. It is ordered with the results from the
    100         * runs that did converge first, sorted from best to worst
    101         * objective value (i.e. in ascending order if minimizing and in
    102         * descending order if maximizing), followed by and null elements
    103         * corresponding to the runs that did not converge. This means all
    104         * elements will be null if the {@link
    105         * #optimize(int,MultivariateVectorFunction,double[],double[],double[]) optimize} method did
    106         * throw a {@link ConvergenceException}). This also means that if
    107         * the first element is not {@code null}, it is the best point found
    108         * across all starts.
    109         *
    110         * @return array containing the optima
    111         * @throws MathIllegalStateException if {@link
    112         * #optimize(int,MultivariateVectorFunction,double[],double[],double[]) optimize} has not been
    113         * called.
    114         */
    115        public PointVectorValuePair[] getOptima() {
    116            if (optima == null) {
    117                throw new MathIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET);
    118            }
    119            return optima.clone();
    120        }
    121
    122        /** {@inheritDoc} */
    123        public int getMaxEvaluations() {
    124            return maxEvaluations;
    125        }
    126
    127        /** {@inheritDoc} */
    128        public int getEvaluations() {
    129            return totalEvaluations;
    130        }
    131
    132        /** {@inheritDoc} */
    133        public ConvergenceChecker<PointVectorValuePair> getConvergenceChecker() {
    134            return optimizer.getConvergenceChecker();
    135        }
    136
    137        /**
    138         * {@inheritDoc}
    139         */
    140        public PointVectorValuePair optimize(int maxEval, final FUNC f,
    141                                                double[] target, double[] weights,
    142                                                double[] startPoint) {
    143            maxEvaluations = maxEval;
    144            RuntimeException lastException = null;
    145            optima = new PointVectorValuePair[starts];
    146            totalEvaluations = 0;
    147
    148            // Multi-start loop.
    149            for (int i = 0; i < starts; ++i) {
    150
    151                // CHECKSTYLE: stop IllegalCatch
    152                try {
    153                    optima[i] = optimizer.optimize(maxEval - totalEvaluations, f, target, weights,
    154                                                   i == 0 ? startPoint : generator.nextVector());
    155                } catch (ConvergenceException oe) {
    156                    optima[i] = null;
    157                } catch (RuntimeException mue) {
    158                    lastException = mue;
    159                    optima[i] = null;
    160                }
    161                // CHECKSTYLE: resume IllegalCatch
    162
    163                totalEvaluations += optimizer.getEvaluations();
    164            }
    165
    166            sortPairs(target, weights);
    167
    168            if (optima[0] == null) {
    169                throw lastException; // cannot be null if starts >=1
    170            }
    171
    172            // Return the found point given the best objective function value.
    173            return optima[0];
    174        }
    175
    176        /**
    177         * Sort the optima from best to worst, followed by {@code null} elements.
    178         *
    179         * @param target Target value for the objective functions at optimum.
    180         * @param weights Weights for the least-squares cost computation.
    181         */
    182        private void sortPairs(final double[] target,
    183                               final double[] weights) {
    184            Arrays.sort(optima, new Comparator<PointVectorValuePair>() {
    185                    public int compare(final PointVectorValuePair o1,
    186                                       final PointVectorValuePair o2) {
    187                        if (o1 == null) {
    188                            return (o2 == null) ? 0 : 1;
    189                        } else if (o2 == null) {
    190                            return -1;
    191                        }
    192                        return Double.compare(weightedResidual(o1), weightedResidual(o2));
    193                    }
    194                    private double weightedResidual(final PointVectorValuePair pv) {
    195                        final double[] value = pv.getValueRef();
    196                        double sum = 0;
    197                        for (int i = 0; i < value.length; ++i) {
    198                            final double ri = value[i] - target[i];
    199                            sum += weights[i] * ri * ri;
    200                        }
    201                        return sum;
    202                    }
    203                });
    204        }
    205    }