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.direct;
019    
020    import java.util.Comparator;
021    
022    import org.apache.commons.math3.analysis.MultivariateFunction;
023    import org.apache.commons.math3.exception.NullArgumentException;
024    import org.apache.commons.math3.optimization.GoalType;
025    import org.apache.commons.math3.optimization.ConvergenceChecker;
026    import org.apache.commons.math3.optimization.PointValuePair;
027    import org.apache.commons.math3.optimization.SimpleValueChecker;
028    import org.apache.commons.math3.optimization.MultivariateOptimizer;
029    import org.apache.commons.math3.optimization.OptimizationData;
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 {@link #setSimplex(AbstractSimplex) setSimplex} method <em>must</em>
055     *  be called prior to calling the {@code optimize} method.
056     * </p>
057     * <p>
058     *  Each call to {@link #optimize(int,MultivariateFunction,GoalType,double[])
059     *  optimize} will re-use the start configuration of the current simplex and
060     *  move it such that its first vertex is at the provided start point of the
061     *  optimization. If the {@code optimize} method is called to solve a different
062     *  problem and the number of parameters change, the simplex must be
063     *  re-initialized to one with the appropriate dimensions.
064     * </p>
065     * <p>
066     *  Convergence is checked by providing the <em>worst</em> points of
067     *  previous and current simplex to the convergence checker, not the best
068     *  ones.
069     * </p>
070     * <p>
071     * This simplex optimizer implementation does not directly support constrained
072     * optimization with simple bounds, so for such optimizations, either a more
073     * dedicated method must be used like {@link CMAESOptimizer} or {@link
074     * BOBYQAOptimizer}, or the optimized method must be wrapped in an adapter like
075     * {@link MultivariateFunctionMappingAdapter} or {@link
076     * MultivariateFunctionPenaltyAdapter}.
077     * </p>
078     *
079     * @see AbstractSimplex
080     * @see MultivariateFunctionMappingAdapter
081     * @see MultivariateFunctionPenaltyAdapter
082     * @see CMAESOptimizer
083     * @see BOBYQAOptimizer
084     * @version $Id: SimplexOptimizer.java 1422230 2012-12-15 12:11:13Z erans $
085     * @deprecated As of 3.1 (to be removed in 4.0).
086     * @since 3.0
087     */
088    @Deprecated
089    public class SimplexOptimizer
090        extends BaseAbstractMultivariateOptimizer<MultivariateFunction>
091        implements MultivariateOptimizer {
092        /** Simplex. */
093        private AbstractSimplex simplex;
094    
095        /**
096         * Constructor using a default {@link SimpleValueChecker convergence
097         * checker}.
098         * @deprecated See {@link SimpleValueChecker#SimpleValueChecker()}
099         */
100        @Deprecated
101        public SimplexOptimizer() {
102            this(new SimpleValueChecker());
103        }
104    
105        /**
106         * @param checker Convergence checker.
107         */
108        public SimplexOptimizer(ConvergenceChecker<PointValuePair> checker) {
109            super(checker);
110        }
111    
112        /**
113         * @param rel Relative threshold.
114         * @param abs Absolute threshold.
115         */
116        public SimplexOptimizer(double rel, double abs) {
117            this(new SimpleValueChecker(rel, abs));
118        }
119    
120        /**
121         * Set the simplex algorithm.
122         *
123         * @param simplex Simplex.
124         * @deprecated As of 3.1. The initial simplex can now be passed as an
125         * argument of the {@link #optimize(int,MultivariateFunction,GoalType,OptimizationData[])}
126         * method.
127         */
128        @Deprecated
129        public void setSimplex(AbstractSimplex simplex) {
130            parseOptimizationData(simplex);
131        }
132    
133        /**
134         * Optimize an objective function.
135         *
136         * @param maxEval Allowed number of evaluations of the objective function.
137         * @param f Objective function.
138         * @param goalType Optimization type.
139         * @param optData Optimization data. The following data will be looked for:
140         * <ul>
141         *  <li>{@link org.apache.commons.math3.optimization.InitialGuess InitialGuess}</li>
142         *  <li>{@link AbstractSimplex}</li>
143         * </ul>
144         * @return the point/value pair giving the optimal value for objective
145         * function.
146         */
147        @Override
148        protected PointValuePair optimizeInternal(int maxEval, MultivariateFunction f,
149                                                  GoalType goalType,
150                                                  OptimizationData... optData) {
151            // Scan "optData" for the input specific to this optimizer.
152            parseOptimizationData(optData);
153    
154            // The parent's method will retrieve the common parameters from
155            // "optData" and call "doOptimize".
156            return super.optimizeInternal(maxEval, f, goalType, optData);
157        }
158    
159        /**
160         * Scans the list of (required and optional) optimization data that
161         * characterize the problem.
162         *
163         * @param optData Optimization data. The following data will be looked for:
164         * <ul>
165         *  <li>{@link AbstractSimplex}</li>
166         * </ul>
167         */
168        private void parseOptimizationData(OptimizationData... optData) {
169            // The existing values (as set by the previous call) are reused if
170            // not provided in the argument list.
171            for (OptimizationData data : optData) {
172                if (data instanceof AbstractSimplex) {
173                    simplex = (AbstractSimplex) data;
174                    continue;
175                }
176            }
177        }
178    
179        /** {@inheritDoc} */
180        @Override
181        protected PointValuePair doOptimize() {
182            if (simplex == null) {
183                throw new NullArgumentException();
184            }
185    
186            // Indirect call to "computeObjectiveValue" in order to update the
187            // evaluations counter.
188            final MultivariateFunction evalFunc
189                = new MultivariateFunction() {
190                    public double value(double[] point) {
191                        return computeObjectiveValue(point);
192                    }
193                };
194    
195            final boolean isMinim = getGoalType() == GoalType.MINIMIZE;
196            final Comparator<PointValuePair> comparator
197                = new Comparator<PointValuePair>() {
198                public int compare(final PointValuePair o1,
199                                   final PointValuePair o2) {
200                    final double v1 = o1.getValue();
201                    final double v2 = o2.getValue();
202                    return isMinim ? Double.compare(v1, v2) : Double.compare(v2, v1);
203                }
204            };
205    
206            // Initialize search.
207            simplex.build(getStartPoint());
208            simplex.evaluate(evalFunc, comparator);
209    
210            PointValuePair[] previous = null;
211            int iteration = 0;
212            final ConvergenceChecker<PointValuePair> checker = getConvergenceChecker();
213            while (true) {
214                if (iteration > 0) {
215                    boolean converged = true;
216                    for (int i = 0; i < simplex.getSize(); i++) {
217                        PointValuePair prev = previous[i];
218                        converged = converged &&
219                            checker.converged(iteration, prev, simplex.getPoint(i));
220                    }
221                    if (converged) {
222                        // We have found an optimum.
223                        return simplex.getPoint(0);
224                    }
225                }
226    
227                // We still need to search.
228                previous = simplex.getPoints();
229                simplex.iterate(evalFunc, comparator);
230                ++iteration;
231            }
232        }
233    }