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
018package org.apache.commons.math3.optimization.direct;
019
020import java.util.Arrays;
021import java.util.Comparator;
022
023import org.apache.commons.math3.analysis.MultivariateFunction;
024import org.apache.commons.math3.exception.NotStrictlyPositiveException;
025import org.apache.commons.math3.exception.DimensionMismatchException;
026import org.apache.commons.math3.exception.ZeroException;
027import org.apache.commons.math3.exception.OutOfRangeException;
028import org.apache.commons.math3.exception.NullArgumentException;
029import org.apache.commons.math3.exception.MathIllegalArgumentException;
030import org.apache.commons.math3.exception.util.LocalizedFormats;
031import org.apache.commons.math3.optimization.PointValuePair;
032import org.apache.commons.math3.optimization.OptimizationData;
033
034/**
035 * This class implements the simplex concept.
036 * It is intended to be used in conjunction with {@link SimplexOptimizer}.
037 * <br/>
038 * The initial configuration of the simplex is set by the constructors
039 * {@link #AbstractSimplex(double[])} or {@link #AbstractSimplex(double[][])}.
040 * The other {@link #AbstractSimplex(int) constructor} will set all steps
041 * to 1, thus building a default configuration from a unit hypercube.
042 * <br/>
043 * Users <em>must</em> call the {@link #build(double[]) build} method in order
044 * to create the data structure that will be acted on by the other methods of
045 * this class.
046 *
047 * @see SimplexOptimizer
048 * @version $Id: AbstractSimplex.java 1422230 2012-12-15 12:11:13Z erans $
049 * @deprecated As of 3.1 (to be removed in 4.0).
050 * @since 3.0
051 */
052@Deprecated
053public abstract class AbstractSimplex implements OptimizationData {
054    /** Simplex. */
055    private PointValuePair[] simplex;
056    /** Start simplex configuration. */
057    private double[][] startConfiguration;
058    /** Simplex dimension (must be equal to {@code simplex.length - 1}). */
059    private final int dimension;
060
061    /**
062     * Build a unit hypercube simplex.
063     *
064     * @param n Dimension of the simplex.
065     */
066    protected AbstractSimplex(int n) {
067        this(n, 1d);
068    }
069
070    /**
071     * Build a hypercube simplex with the given side length.
072     *
073     * @param n Dimension of the simplex.
074     * @param sideLength Length of the sides of the hypercube.
075     */
076    protected AbstractSimplex(int n,
077                              double sideLength) {
078        this(createHypercubeSteps(n, sideLength));
079    }
080
081    /**
082     * The start configuration for simplex is built from a box parallel to
083     * the canonical axes of the space. The simplex is the subset of vertices
084     * of a box parallel to the canonical axes. It is built as the path followed
085     * while traveling from one vertex of the box to the diagonally opposite
086     * vertex moving only along the box edges. The first vertex of the box will
087     * be located at the start point of the optimization.
088     * As an example, in dimension 3 a simplex has 4 vertices. Setting the
089     * steps to (1, 10, 2) and the start point to (1, 1, 1) would imply the
090     * start simplex would be: { (1, 1, 1), (2, 1, 1), (2, 11, 1), (2, 11, 3) }.
091     * The first vertex would be set to the start point at (1, 1, 1) and the
092     * last vertex would be set to the diagonally opposite vertex at (2, 11, 3).
093     *
094     * @param steps Steps along the canonical axes representing box edges. They
095     * may be negative but not zero.
096     * @throws NullArgumentException if {@code steps} is {@code null}.
097     * @throws ZeroException if one of the steps is zero.
098     */
099    protected AbstractSimplex(final double[] steps) {
100        if (steps == null) {
101            throw new NullArgumentException();
102        }
103        if (steps.length == 0) {
104            throw new ZeroException();
105        }
106        dimension = steps.length;
107
108        // Only the relative position of the n final vertices with respect
109        // to the first one are stored.
110        startConfiguration = new double[dimension][dimension];
111        for (int i = 0; i < dimension; i++) {
112            final double[] vertexI = startConfiguration[i];
113            for (int j = 0; j < i + 1; j++) {
114                if (steps[j] == 0) {
115                    throw new ZeroException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX);
116                }
117                System.arraycopy(steps, 0, vertexI, 0, j + 1);
118            }
119        }
120    }
121
122    /**
123     * The real initial simplex will be set up by moving the reference
124     * simplex such that its first point is located at the start point of the
125     * optimization.
126     *
127     * @param referenceSimplex Reference simplex.
128     * @throws NotStrictlyPositiveException if the reference simplex does not
129     * contain at least one point.
130     * @throws DimensionMismatchException if there is a dimension mismatch
131     * in the reference simplex.
132     * @throws IllegalArgumentException if one of its vertices is duplicated.
133     */
134    protected AbstractSimplex(final double[][] referenceSimplex) {
135        if (referenceSimplex.length <= 0) {
136            throw new NotStrictlyPositiveException(LocalizedFormats.SIMPLEX_NEED_ONE_POINT,
137                                                   referenceSimplex.length);
138        }
139        dimension = referenceSimplex.length - 1;
140
141        // Only the relative position of the n final vertices with respect
142        // to the first one are stored.
143        startConfiguration = new double[dimension][dimension];
144        final double[] ref0 = referenceSimplex[0];
145
146        // Loop over vertices.
147        for (int i = 0; i < referenceSimplex.length; i++) {
148            final double[] refI = referenceSimplex[i];
149
150            // Safety checks.
151            if (refI.length != dimension) {
152                throw new DimensionMismatchException(refI.length, dimension);
153            }
154            for (int j = 0; j < i; j++) {
155                final double[] refJ = referenceSimplex[j];
156                boolean allEquals = true;
157                for (int k = 0; k < dimension; k++) {
158                    if (refI[k] != refJ[k]) {
159                        allEquals = false;
160                        break;
161                    }
162                }
163                if (allEquals) {
164                    throw new MathIllegalArgumentException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX,
165                                                           i, j);
166                }
167            }
168
169            // Store vertex i position relative to vertex 0 position.
170            if (i > 0) {
171                final double[] confI = startConfiguration[i - 1];
172                for (int k = 0; k < dimension; k++) {
173                    confI[k] = refI[k] - ref0[k];
174                }
175            }
176        }
177    }
178
179    /**
180     * Get simplex dimension.
181     *
182     * @return the dimension of the simplex.
183     */
184    public int getDimension() {
185        return dimension;
186    }
187
188    /**
189     * Get simplex size.
190     * After calling the {@link #build(double[]) build} method, this method will
191     * will be equivalent to {@code getDimension() + 1}.
192     *
193     * @return the size of the simplex.
194     */
195    public int getSize() {
196        return simplex.length;
197    }
198
199    /**
200     * Compute the next simplex of the algorithm.
201     *
202     * @param evaluationFunction Evaluation function.
203     * @param comparator Comparator to use to sort simplex vertices from best
204     * to worst.
205     * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
206     * if the algorithm fails to converge.
207     */
208    public abstract void iterate(final MultivariateFunction evaluationFunction,
209                                 final Comparator<PointValuePair> comparator);
210
211    /**
212     * Build an initial simplex.
213     *
214     * @param startPoint First point of the simplex.
215     * @throws DimensionMismatchException if the start point does not match
216     * simplex dimension.
217     */
218    public void build(final double[] startPoint) {
219        if (dimension != startPoint.length) {
220            throw new DimensionMismatchException(dimension, startPoint.length);
221        }
222
223        // Set first vertex.
224        simplex = new PointValuePair[dimension + 1];
225        simplex[0] = new PointValuePair(startPoint, Double.NaN);
226
227        // Set remaining vertices.
228        for (int i = 0; i < dimension; i++) {
229            final double[] confI = startConfiguration[i];
230            final double[] vertexI = new double[dimension];
231            for (int k = 0; k < dimension; k++) {
232                vertexI[k] = startPoint[k] + confI[k];
233            }
234            simplex[i + 1] = new PointValuePair(vertexI, Double.NaN);
235        }
236    }
237
238    /**
239     * Evaluate all the non-evaluated points of the simplex.
240     *
241     * @param evaluationFunction Evaluation function.
242     * @param comparator Comparator to use to sort simplex vertices from best to worst.
243     * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
244     * if the maximal number of evaluations is exceeded.
245     */
246    public void evaluate(final MultivariateFunction evaluationFunction,
247                         final Comparator<PointValuePair> comparator) {
248        // Evaluate the objective function at all non-evaluated simplex points.
249        for (int i = 0; i < simplex.length; i++) {
250            final PointValuePair vertex = simplex[i];
251            final double[] point = vertex.getPointRef();
252            if (Double.isNaN(vertex.getValue())) {
253                simplex[i] = new PointValuePair(point, evaluationFunction.value(point), false);
254            }
255        }
256
257        // Sort the simplex from best to worst.
258        Arrays.sort(simplex, comparator);
259    }
260
261    /**
262     * Replace the worst point of the simplex by a new point.
263     *
264     * @param pointValuePair Point to insert.
265     * @param comparator Comparator to use for sorting the simplex vertices
266     * from best to worst.
267     */
268    protected void replaceWorstPoint(PointValuePair pointValuePair,
269                                     final Comparator<PointValuePair> comparator) {
270        for (int i = 0; i < dimension; i++) {
271            if (comparator.compare(simplex[i], pointValuePair) > 0) {
272                PointValuePair tmp = simplex[i];
273                simplex[i] = pointValuePair;
274                pointValuePair = tmp;
275            }
276        }
277        simplex[dimension] = pointValuePair;
278    }
279
280    /**
281     * Get the points of the simplex.
282     *
283     * @return all the simplex points.
284     */
285    public PointValuePair[] getPoints() {
286        final PointValuePair[] copy = new PointValuePair[simplex.length];
287        System.arraycopy(simplex, 0, copy, 0, simplex.length);
288        return copy;
289    }
290
291    /**
292     * Get the simplex point stored at the requested {@code index}.
293     *
294     * @param index Location.
295     * @return the point at location {@code index}.
296     */
297    public PointValuePair getPoint(int index) {
298        if (index < 0 ||
299            index >= simplex.length) {
300            throw new OutOfRangeException(index, 0, simplex.length - 1);
301        }
302        return simplex[index];
303    }
304
305    /**
306     * Store a new point at location {@code index}.
307     * Note that no deep-copy of {@code point} is performed.
308     *
309     * @param index Location.
310     * @param point New value.
311     */
312    protected void setPoint(int index, PointValuePair point) {
313        if (index < 0 ||
314            index >= simplex.length) {
315            throw new OutOfRangeException(index, 0, simplex.length - 1);
316        }
317        simplex[index] = point;
318    }
319
320    /**
321     * Replace all points.
322     * Note that no deep-copy of {@code points} is performed.
323     *
324     * @param points New Points.
325     */
326    protected void setPoints(PointValuePair[] points) {
327        if (points.length != simplex.length) {
328            throw new DimensionMismatchException(points.length, simplex.length);
329        }
330        simplex = points;
331    }
332
333    /**
334     * Create steps for a unit hypercube.
335     *
336     * @param n Dimension of the hypercube.
337     * @param sideLength Length of the sides of the hypercube.
338     * @return the steps.
339     */
340    private static double[] createHypercubeSteps(int n,
341                                                 double sideLength) {
342        final double[] steps = new double[n];
343        for (int i = 0; i < n; i++) {
344            steps[i] = sideLength;
345        }
346        return steps;
347    }
348}