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.math3.optim.nonlinear.scalar.noderiv;
018
019import java.util.Comparator;
020import org.apache.commons.math3.analysis.MultivariateFunction;
021import org.apache.commons.math3.exception.NullArgumentException;
022import org.apache.commons.math3.exception.MathUnsupportedOperationException;
023import org.apache.commons.math3.exception.util.LocalizedFormats;
024import org.apache.commons.math3.optim.nonlinear.scalar.GoalType;
025import org.apache.commons.math3.optim.ConvergenceChecker;
026import org.apache.commons.math3.optim.PointValuePair;
027import org.apache.commons.math3.optim.SimpleValueChecker;
028import org.apache.commons.math3.optim.OptimizationData;
029import org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer;
030
031/**
032 * This class implements simplex-based direct search optimization.
033 *
034 * <p>
035 *  Direct search methods only use objective function values, they do
036 *  not need derivatives and don't either try to compute approximation
037 *  of the derivatives. According to a 1996 paper by Margaret H. Wright
038 *  (<a href="http://cm.bell-labs.com/cm/cs/doc/96/4-02.ps.gz">Direct
039 *  Search Methods: Once Scorned, Now Respectable</a>), they are used
040 *  when either the computation of the derivative is impossible (noisy
041 *  functions, unpredictable discontinuities) or difficult (complexity,
042 *  computation cost). In the first cases, rather than an optimum, a
043 *  <em>not too bad</em> point is desired. In the latter cases, an
044 *  optimum is desired but cannot be reasonably found. In all cases
045 *  direct search methods can be useful.
046 * </p>
047 * <p>
048 *  Simplex-based direct search methods are based on comparison of
049 *  the objective function values at the vertices of a simplex (which is a
050 *  set of n+1 points in dimension n) that is updated by the algorithms
051 *  steps.
052 * <p>
053 * <p>
054 *  The simplex update procedure ({@link NelderMeadSimplex} or
055 * {@link MultiDirectionalSimplex})  must be passed to the
056 * {@code optimize} method.
057 * </p>
058 * <p>
059 *  Each call to {@code optimize} will re-use the start configuration of
060 *  the current simplex and move it such that its first vertex is at the
061 *  provided start point of the optimization.
062 *  If the {@code optimize} method is called to solve a different problem
063 *  and the number of parameters change, the simplex must be re-initialized
064 *  to one with the appropriate dimensions.
065 * </p>
066 * <p>
067 *  Convergence is checked by providing the <em>worst</em> points of
068 *  previous and current simplex to the convergence checker, not the best
069 *  ones.
070 * </p>
071 * <p>
072 *  This simplex optimizer implementation does not directly support constrained
073 *  optimization with simple bounds; so, for such optimizations, either a more
074 *  dedicated algorithm must be used like
075 *  {@link CMAESOptimizer} or {@link BOBYQAOptimizer}, or the objective
076 *  function must be wrapped in an adapter like
077 *  {@link org.apache.commons.math3.optim.nonlinear.scalar.MultivariateFunctionMappingAdapter
078 *  MultivariateFunctionMappingAdapter} or
079 *  {@link org.apache.commons.math3.optim.nonlinear.scalar.MultivariateFunctionPenaltyAdapter
080 *  MultivariateFunctionPenaltyAdapter}.
081 *  <br/>
082 *  The call to {@link #optimize(OptimizationData[]) optimize} will throw
083 *  {@link MathUnsupportedOperationException} if bounds are passed to it.
084 * </p>
085 *
086 * @since 3.0
087 */
088public class SimplexOptimizer extends MultivariateOptimizer {
089    /** Simplex update rule. */
090    private AbstractSimplex simplex;
091
092    /**
093     * @param checker Convergence checker.
094     */
095    public SimplexOptimizer(ConvergenceChecker<PointValuePair> checker) {
096        super(checker);
097    }
098
099    /**
100     * @param rel Relative threshold.
101     * @param abs Absolute threshold.
102     */
103    public SimplexOptimizer(double rel, double abs) {
104        this(new SimpleValueChecker(rel, abs));
105    }
106
107    /**
108     * {@inheritDoc}
109     *
110     * @param optData Optimization data. In addition to those documented in
111     * {@link MultivariateOptimizer#parseOptimizationData(OptimizationData[])
112     * MultivariateOptimizer}, this method will register the following data:
113     * <ul>
114     *  <li>{@link AbstractSimplex}</li>
115     * </ul>
116     * @return {@inheritDoc}
117     */
118    @Override
119    public PointValuePair optimize(OptimizationData... 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        checkParameters();
128
129        // Indirect call to "computeObjectiveValue" in order to update the
130        // evaluations counter.
131        final MultivariateFunction evalFunc
132            = new MultivariateFunction() {
133                /** {@inheritDoc} */
134                public double value(double[] point) {
135                    return computeObjectiveValue(point);
136                }
137            };
138
139        final boolean isMinim = getGoalType() == GoalType.MINIMIZE;
140        final Comparator<PointValuePair> comparator
141            = new Comparator<PointValuePair>() {
142            /** {@inheritDoc} */
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 (getIterations() > 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
176            incrementIterationCount();
177        }
178    }
179
180    /**
181     * Scans the list of (required and optional) optimization data that
182     * characterize the problem.
183     *
184     * @param optData Optimization data.
185     * The following data will be looked for:
186     * <ul>
187     *  <li>{@link AbstractSimplex}</li>
188     * </ul>
189     */
190    @Override
191    protected void parseOptimizationData(OptimizationData... optData) {
192        // Allow base class to register its own data.
193        super.parseOptimizationData(optData);
194
195        // The existing values (as set by the previous call) are reused if
196        // not provided in the argument list.
197        for (OptimizationData data : optData) {
198            if (data instanceof AbstractSimplex) {
199                simplex = (AbstractSimplex) data;
200                // If more data must be parsed, this statement _must_ be
201                // changed to "continue".
202                break;
203            }
204        }
205    }
206
207    /**
208     * @throws MathUnsupportedOperationException if bounds were passed to the
209     * {@link #optimize(OptimizationData[]) optimize} method.
210     * @throws NullArgumentException if no initial simplex was passed to the
211     * {@link #optimize(OptimizationData[]) optimize} method.
212     */
213    private void checkParameters() {
214        if (simplex == null) {
215            throw new NullArgumentException();
216        }
217        if (getLowerBound() != null ||
218            getUpperBound() != null) {
219            throw new MathUnsupportedOperationException(LocalizedFormats.CONSTRAINT);
220        }
221    }
222}