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 */
017package org.apache.commons.math4.legacy.optim;
018
019import java.util.function.Supplier;
020import org.apache.commons.math4.legacy.exception.MathIllegalStateException;
021import org.apache.commons.math4.legacy.exception.NotStrictlyPositiveException;
022import org.apache.commons.math4.legacy.exception.TooManyEvaluationsException;
023
024/**
025 * Base class multi-start optimizer for a multivariate function.
026 * <br>
027 * This class wraps an optimizer in order to use it several times in
028 * turn with different starting points (trying to avoid being trapped
029 * in a local extremum when looking for a global one).
030 * <em>It is not a "user" class.</em>
031 *
032 * @param <PAIR> Type of the point/value pair returned by the optimization
033 * algorithm.
034 *
035 * @since 3.0
036 */
037public abstract class BaseMultiStartMultivariateOptimizer<PAIR>
038    extends BaseMultivariateOptimizer<PAIR> {
039    /** Underlying classical optimizer. */
040    private final BaseMultivariateOptimizer<PAIR> optimizer;
041    /** Number of evaluations already performed for all starts. */
042    private int totalEvaluations;
043    /** Number of starts to go. */
044    private final int starts;
045    /** Generator of start points ("multi-start"). */
046    private final Supplier<double[]> generator;
047    /** Optimization data. */
048    private OptimizationData[] optimData;
049    /**
050     * Location in {@link #optimData} where the updated maximum
051     * number of evaluations will be stored.
052     */
053    private int maxEvalIndex = -1;
054    /**
055     * Location in {@link #optimData} where the updated start value
056     * will be stored.
057     */
058    private int initialGuessIndex = -1;
059
060    /**
061     * Create a multi-start optimizer from a single-start optimizer.
062     * <p>
063     * Note that if there are bounds constraints (see {@link #getLowerBound()}
064     * and {@link #getUpperBound()}), then a simple rejection algorithm is used
065     * at each restart. This implies that the random vector generator should have
066     * a good probability to generate vectors in the bounded domain, otherwise the
067     * rejection algorithm will hit the {@link #getMaxEvaluations()} count without
068     * generating a proper restart point. Users must be take great care of the <a
069     * href="http://en.wikipedia.org/wiki/Curse_of_dimensionality">curse of dimensionality</a>.
070     * </p>
071     * @param optimizer Single-start optimizer to wrap.
072     * @param starts Number of starts to perform. If {@code starts == 1},
073     * the {@link #optimize(OptimizationData[]) optimize} will return the
074     * same solution as the given {@code optimizer} would return.
075     * @param generator Generator to use for restarts.
076     * @throws NotStrictlyPositiveException if {@code starts < 1}.
077     */
078    public BaseMultiStartMultivariateOptimizer(final BaseMultivariateOptimizer<PAIR> optimizer,
079                                               final int starts,
080                                               final Supplier<double[]> generator) {
081        super(optimizer.getConvergenceChecker());
082
083        if (starts < 1) {
084            throw new NotStrictlyPositiveException(starts);
085        }
086
087        this.optimizer = optimizer;
088        this.starts = starts;
089        this.generator = generator;
090    }
091
092    /** {@inheritDoc} */
093    @Override
094    public int getEvaluations() {
095        return totalEvaluations;
096    }
097
098    /**
099     * Gets all the optima found during the last call to {@code optimize}.
100     * The optimizer stores all the optima found during a set of
101     * restarts. The {@code optimize} method returns the best point only.
102     * This method returns all the points found at the end of each starts,
103     * including the best one already returned by the {@code optimize} method.
104     * <br>
105     * The returned array as one element for each start as specified
106     * in the constructor. It is ordered with the results from the
107     * runs that did converge first, sorted from best to worst
108     * objective value (i.e in ascending order if minimizing and in
109     * descending order if maximizing), followed by {@code null} elements
110     * corresponding to the runs that did not converge. This means all
111     * elements will be {@code null} if the {@code optimize} method did throw
112     * an exception.
113     * This also means that if the first element is not {@code null}, it is
114     * the best point found across all starts.
115     * <br>
116     * The behaviour is undefined if this method is called before
117     * {@code optimize}; it will likely throw {@code NullPointerException}.
118     *
119     * @return an array containing the optima sorted from best to worst.
120     */
121    public abstract PAIR[] getOptima();
122
123    /**
124     * {@inheritDoc}
125     *
126     * @throws MathIllegalStateException if {@code optData} does not contain an
127     * instance of {@link MaxEval} or {@link InitialGuess}.
128     */
129    @Override
130    public PAIR optimize(OptimizationData... optData) {
131        // Store arguments in order to pass them to the internal optimizer.
132       optimData = optData;
133        // Set up base class and perform computations.
134        return super.optimize(optData);
135    }
136
137    /** {@inheritDoc} */
138    @Override
139    protected PAIR doOptimize() {
140        // Remove all instances of "MaxEval" and "InitialGuess" from the
141        // array that will be passed to the internal optimizer.
142        // The former is to enforce smaller numbers of allowed evaluations
143        // (according to how many have been used up already), and the latter
144        // to impose a different start value for each start.
145        for (int i = 0; i < optimData.length; i++) {
146            if (optimData[i] instanceof MaxEval) {
147                optimData[i] = null;
148                maxEvalIndex = i;
149            }
150            if (optimData[i] instanceof InitialGuess) {
151                optimData[i] = null;
152                initialGuessIndex = i;
153                continue;
154            }
155        }
156        if (maxEvalIndex == -1) {
157            throw new MathIllegalStateException();
158        }
159        if (initialGuessIndex == -1) {
160            throw new MathIllegalStateException();
161        }
162
163        RuntimeException lastException = null;
164        totalEvaluations = 0;
165        clear();
166
167        final int maxEval = getMaxEvaluations();
168        final double[] min = getLowerBound();
169        final double[] max = getUpperBound();
170        final double[] startPoint = getStartPoint();
171
172        // Multi-start loop.
173        for (int i = 0; i < starts; i++) {
174            // CHECKSTYLE: stop IllegalCatch
175            try {
176                // Decrease number of allowed evaluations.
177                optimData[maxEvalIndex] = new MaxEval(maxEval - totalEvaluations);
178                // New start value.
179                double[] s = null;
180                if (i == 0) {
181                    s = startPoint;
182                } else {
183                    int attempts = 0;
184                    while (s == null) {
185                        if (attempts++ >= getMaxEvaluations()) {
186                            throw new TooManyEvaluationsException(getMaxEvaluations());
187                        }
188                        s = generator.get();
189                        for (int k = 0; s != null && k < s.length; ++k) {
190                            if ((min != null && s[k] < min[k]) || (max != null && s[k] > max[k])) {
191                                // reject the vector
192                                s = null;
193                                break;
194                            }
195                        }
196                    }
197                }
198                optimData[initialGuessIndex] = new InitialGuess(s);
199                // Optimize.
200                final PAIR result = optimizer.optimize(optimData);
201                store(result);
202            } catch (RuntimeException mue) {
203                lastException = mue;
204            }
205            // CHECKSTYLE: resume IllegalCatch
206
207            totalEvaluations += optimizer.getEvaluations();
208        }
209
210        final PAIR[] optima = getOptima();
211        if (optima.length == 0) {
212            // All runs failed.
213            throw lastException; // Cannot be null if starts >= 1.
214        }
215
216        // Return the best optimum.
217        return optima[0];
218    }
219
220    /**
221     * Method that will be called in order to store each found optimum.
222     *
223     * @param optimum Result of an optimization run.
224     */
225    protected abstract void store(PAIR optimum);
226    /**
227     * Method that will called in order to clear all stored optima.
228     */
229    protected abstract void clear();
230}