    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    package org.apache.commons.math3.optim.nonlinear.scalar.noderiv;
    018
    019    import java.util.Comparator;
    020    import org.apache.commons.math3.analysis.MultivariateFunction;
    021    import org.apache.commons.math3.exception.NullArgumentException;
    022    import org.apache.commons.math3.optim.nonlinear.scalar.GoalType;
    023    import org.apache.commons.math3.optim.ConvergenceChecker;
    024    import org.apache.commons.math3.optim.PointValuePair;
    025    import org.apache.commons.math3.optim.SimpleValueChecker;
    026    import org.apache.commons.math3.optim.OptimizationData;
    027    import org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer;
    028
    029    /**
    030     * This class implements simplex-based direct search optimization.
    031     *
    032     * <p>
    033     *  Direct search methods only use objective function values, they do
    034     *  not need derivatives and don't either try to compute approximation
    035     *  of the derivatives. According to a 1996 paper by Margaret H. Wright
    036     *  (<a href="http://cm.bell-labs.com/cm/cs/doc/96/4-02.ps.gz">Direct
    037     *  Search Methods: Once Scorned, Now Respectable</a>), they are used
    038     *  when either the computation of the derivative is impossible (noisy
    039     *  functions, unpredictable discontinuities) or difficult (complexity,
    040     *  computation cost). In the first cases, rather than an optimum, a
    041     *  <em>not too bad</em> point is desired. In the latter cases, an
    042     *  optimum is desired but cannot be reasonably found. In all cases
    043     *  direct search methods can be useful.
    044     * </p>
    045     * <p>
    046     *  Simplex-based direct search methods are based on comparison of
    047     *  the objective function values at the vertices of a simplex (which is a
    048     *  set of n+1 points in dimension n) that is updated by the algorithms
    049     *  steps.
    050     * <p>
    051     * <p>
    052     *  The simplex update procedure ({@link NelderMeadSimplex} or
    053     * {@link MultiDirectionalSimplex})  must be passed to the
    054     * {@code optimize} method.
    055     * </p>
    056     * <p>
    057     *  Each call to {@code optimize} will re-use the start configuration of
    058     *  the current simplex and move it such that its first vertex is at the
    059     *  provided start point of the optimization.
    060     *  If the {@code optimize} method is called to solve a different problem
    061     *  and the number of parameters change, the simplex must be re-initialized
    062     *  to one with the appropriate dimensions.
    063     * </p>
    064     * <p>
    065     *  Convergence is checked by providing the <em>worst</em> points of
    066     *  previous and current simplex to the convergence checker, not the best
    067     *  ones.
    068     * </p>
    069     * <p>
    070     *  This simplex optimizer implementation does not directly support constrained
    071     *  optimization with simple bounds; so, for such optimizations, either a more
    072     *  dedicated algorithm must be used like
    073     *  {@link CMAESOptimizer} or {@link BOBYQAOptimizer}, or the objective
    074     *  function must be wrapped in an adapter like
    075     *  {@link org.apache.commons.math3.optim.nonlinear.scalar.MultivariateFunctionMappingAdapter
    076     *  MultivariateFunctionMappingAdapter} or
    077     *  {@link org.apache.commons.math3.optim.nonlinear.scalar.MultivariateFunctionPenaltyAdapter
    078     *  MultivariateFunctionPenaltyAdapter}.
    079     * </p>
    080     *
    081     * @version $Id: SimplexOptimizer.java 1397759 2012-10-13 01:12:58Z erans $
    082     * @since 3.0
    083     */
    084    public class SimplexOptimizer extends MultivariateOptimizer {
    085        /** Simplex update rule. */
    086        private AbstractSimplex simplex;
    087
    088        /**
    089         * @param checker Convergence checker.
    090         */
    091        public SimplexOptimizer(ConvergenceChecker<PointValuePair> checker) {
    092            super(checker);
    093        }
    094
    095        /**
    096         * @param rel Relative threshold.
    097         * @param abs Absolute threshold.
    098         */
    099        public SimplexOptimizer(double rel, double abs) {
    100            this(new SimpleValueChecker(rel, abs));
    101        }
    102
    103        /**
    104         * {@inheritDoc}
    105         *
    106         * @param optData Optimization data.
    107         * The following data will be looked for:
    108         * <ul>
    109         *  <li>{@link org.apache.commons.math3.optim.MaxEval}</li>
    110         *  <li>{@link org.apache.commons.math3.optim.InitialGuess}</li>
    111         *  <li>{@link org.apache.commons.math3.optim.SimpleBounds}</li>
    112         *  <li>{@link AbstractSimplex}</li>
    113         * </ul>
    114         * @return {@inheritDoc}
    115         */
    116        @Override
    117        public PointValuePair optimize(OptimizationData... optData) {
    118            // Retrieve settings
    119            parseOptimizationData(optData);
    120            // Set up base class and perform computation.
    121            return super.optimize(optData);
    122        }
    123
    124        /** {@inheritDoc} */
    125        @Override
    126        protected PointValuePair doOptimize() {
    127            if (simplex == null) {
    128                throw new NullArgumentException();
    129            }
    130
    131            // Indirect call to "computeObjectiveValue" in order to update the
    132            // evaluations counter.
    133            final MultivariateFunction evalFunc
    134                = new MultivariateFunction() {
    135                    public double value(double[] point) {
    136                        return computeObjectiveValue(point);
    137                    }
    138                };
    139
    140            final boolean isMinim = getGoalType() == GoalType.MINIMIZE;
    141            final Comparator<PointValuePair> comparator
    142                = new Comparator<PointValuePair>() {
    143                public int compare(final PointValuePair o1,
    144                                   final PointValuePair o2) {
    145                    final double v1 = o1.getValue();
    146                    final double v2 = o2.getValue();
    147                    return isMinim ? Double.compare(v1, v2) : Double.compare(v2, v1);
    148                }
    149            };
    150
    151            // Initialize search.
    152            simplex.build(getStartPoint());
    153            simplex.evaluate(evalFunc, comparator);
    154
    155            PointValuePair[] previous = null;
    156            int iteration = 0;
    157            final ConvergenceChecker<PointValuePair> checker = getConvergenceChecker();
    158            while (true) {
    159                if (iteration > 0) {
    160                    boolean converged = true;
    161                    for (int i = 0; i < simplex.getSize(); i++) {
    162                        PointValuePair prev = previous[i];
    163                        converged = converged &&
    164                            checker.converged(iteration, prev, simplex.getPoint(i));
    165                    }
    166                    if (converged) {
    167                        // We have found an optimum.
    168                        return simplex.getPoint(0);
    169                    }
    170                }
    171
    172                // We still need to search.
    173                previous = simplex.getPoints();
    174                simplex.iterate(evalFunc, comparator);
    175                ++iteration;
    176            }
    177        }
    178
    179        /**
    180         * Scans the list of (required and optional) optimization data that
    181         * characterize the problem.
    182         *
    183         * @param optData Optimization data.
    184         * The following data will be looked for:
    185         * <ul>
    186         *  <li>{@link AbstractSimplex}</li>
    187         * </ul>
    188         */
    189        private void parseOptimizationData(OptimizationData... optData) {
    190            // The existing values (as set by the previous call) are reused if
    191            // not provided in the argument list.
    192            for (OptimizationData data : optData) {
    193                if (data instanceof AbstractSimplex) {
    194                    simplex = (AbstractSimplex) data;
    195                    // If more data must be parsed, this statement _must_ be
    196                    // changed to "continue".
    197                    break;
    198                }
    199            }
    200        }
    201    }