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;
018
019import org.apache.commons.math3.util.FastMath;
020import org.apache.commons.math3.util.Pair;
021import org.apache.commons.math3.exception.NotStrictlyPositiveException;
022
023/**
024 * Simple implementation of the {@link ConvergenceChecker} interface using
025 * only point coordinates.
026 *
027 * Convergence is considered to have been reached if either the relative
028 * difference between each point coordinate are smaller than a threshold
029 * or if either the absolute difference between the point coordinates are
030 * smaller than another threshold.
031 * <br/>
032 * The {@link #converged(int,Pair,Pair) converged} method will also return
033 * {@code true} if the number of iterations has been set (see
034 * {@link #SimplePointChecker(double,double,int) this constructor}).
035 *
036 * @param <PAIR> Type of the (point, value) pair.
037 * The type of the "value" part of the pair (not used by this class).
038 *
039 * @since 3.0
040 */
041public class SimplePointChecker<PAIR extends Pair<double[], ? extends Object>>
042    extends AbstractConvergenceChecker<PAIR> {
043    /**
044     * If {@link #maxIterationCount} is set to this value, the number of
045     * iterations will never cause {@link #converged(int, Pair, Pair)}
046     * to return {@code true}.
047     */
048    private static final int ITERATION_CHECK_DISABLED = -1;
049    /**
050     * Number of iterations after which the
051     * {@link #converged(int, Pair, Pair)} method
052     * will return true (unless the check is disabled).
053     */
054    private final int maxIterationCount;
055
056    /**
057     * Build an instance with specified thresholds.
058     * In order to perform only relative checks, the absolute tolerance
059     * must be set to a negative value. In order to perform only absolute
060     * checks, the relative tolerance must be set to a negative value.
061     *
062     * @param relativeThreshold relative tolerance threshold
063     * @param absoluteThreshold absolute tolerance threshold
064     */
065    public SimplePointChecker(final double relativeThreshold,
066                              final double absoluteThreshold) {
067        super(relativeThreshold, absoluteThreshold);
068        maxIterationCount = ITERATION_CHECK_DISABLED;
069    }
070
071    /**
072     * Builds an instance with specified thresholds.
073     * In order to perform only relative checks, the absolute tolerance
074     * must be set to a negative value. In order to perform only absolute
075     * checks, the relative tolerance must be set to a negative value.
076     *
077     * @param relativeThreshold Relative tolerance threshold.
078     * @param absoluteThreshold Absolute tolerance threshold.
079     * @param maxIter Maximum iteration count.
080     * @throws NotStrictlyPositiveException if {@code maxIter <= 0}.
081     *
082     * @since 3.1
083     */
084    public SimplePointChecker(final double relativeThreshold,
085                              final double absoluteThreshold,
086                              final int maxIter) {
087        super(relativeThreshold, absoluteThreshold);
088
089        if (maxIter <= 0) {
090            throw new NotStrictlyPositiveException(maxIter);
091        }
092        maxIterationCount = maxIter;
093    }
094
095    /**
096     * Check if the optimization algorithm has converged considering the
097     * last two points.
098     * This method may be called several times from the same algorithm
099     * iteration with different points. This can be detected by checking the
100     * iteration number at each call if needed. Each time this method is
101     * called, the previous and current point correspond to points with the
102     * same role at each iteration, so they can be compared. As an example,
103     * simplex-based algorithms call this method for all points of the simplex,
104     * not only for the best or worst ones.
105     *
106     * @param iteration Index of current iteration
107     * @param previous Best point in the previous iteration.
108     * @param current Best point in the current iteration.
109     * @return {@code true} if the arguments satify the convergence criterion.
110     */
111    @Override
112    public boolean converged(final int iteration,
113                             final PAIR previous,
114                             final PAIR current) {
115        if (maxIterationCount != ITERATION_CHECK_DISABLED && iteration >= maxIterationCount) {
116            return true;
117        }
118
119        final double[] p = previous.getKey();
120        final double[] c = current.getKey();
121        for (int i = 0; i < p.length; ++i) {
122            final double pi = p[i];
123            final double ci = c[i];
124            final double difference = FastMath.abs(pi - ci);
125            final double size = FastMath.max(FastMath.abs(pi), FastMath.abs(ci));
126            if (difference > size * getRelativeThreshold() &&
127                difference > getAbsoluteThreshold()) {
128                return false;
129            }
130        }
131        return true;
132    }
133}