You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by lu...@apache.org on 2009/03/04 01:07:51 UTC
svn commit: r749850 [1/2] - in /commons/proper/math/trunk/src:
java/org/apache/commons/math/ java/org/apache/commons/math/optimization/
java/org/apache/commons/math/optimization/direct/
test/org/apache/commons/math/optimization/direct/
Author: luc
Date: Wed Mar 4 00:07:51 2009
New Revision: 749850
URL: http://svn.apache.org/viewvc?rev=749850&view=rev
Log:
continued refactoring of optimization framework:
- improved general interfaces at top optimization level
- added a simple implementation of ConvergenceChecker (ObjectiveValueChecker)
- added a general multi-start wrapper
- changed the direct search optimizers to the new interfaces
This work is still not complete yet. The general package classes
are very close to the former design, they have almost not been changed
structurally.
Added:
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/MultiStartOptimizer.java (with props)
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ObjectiveValueChecker.java (with props)
Modified:
commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ConvergenceChecker.java
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/LeastSquaresConverter.java
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/MultiObjectiveFunction.java
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ObjectiveFunction.java
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/Optimizer.java
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/PointValuePair.java
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/DirectSearchOptimizer.java
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/MultiDirectional.java
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/NelderMead.java
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/package.html
commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/direct/MultiDirectionalTest.java
commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/direct/NelderMeadTest.java
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java?rev=749850&r1=749849&r2=749850&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java Wed Mar 4 00:07:51 2009
@@ -70,6 +70,7 @@
// org.apache.commons.math.DimensionMismatchException
// org.apache.commons.math.optimization.LeastSquaresConverter
+ // org.apache.commons.math.optimization.direct.DirectSearchOptimizer
{ "dimension mismatch {0} != {1}",
"dimensions incompatibles {0} != {1}" },
@@ -106,9 +107,19 @@
{ "Conversion Exception in Transformation: {0}",
"Exception de conversion dans une transformation : {0}" },
- // org.apache.commons.math.optimization.general.AbstractEstimator
+ // org.apache.commons.math.optimization.MultiStartOptimizer
+ { "no optimum computed yet",
+ "aucun optimum n''a encore \u00e9t\u00e9 calcul\u00e9" },
+
+ // org.apache.commons.math.optimization.direct.DirectSearchOptimizer
+ { "simplex must contain at least one point",
+ "le simplex doit contenir au moins un point" },
+ { "equals vertices {0} and {1} in simplex configuration",
+ "sommets {0} et {1} \u00e9gaux dans la configuration du simplex" },
{ "maximal number of evaluations exceeded ({0})",
"nombre maximal d''\u00e9valuations d\u00e9pass\u00e9 ({0})" },
+
+ // org.apache.commons.math.optimization.general.AbstractEstimator
{ "unable to compute covariances: singular problem",
"impossible de calculer les covariances : probl\u00e8me singulier"},
{ "no degrees of freedom ({0} measurements, {1} parameters)",
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ConvergenceChecker.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ConvergenceChecker.java?rev=749850&r1=749849&r2=749850&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ConvergenceChecker.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ConvergenceChecker.java Wed Mar 4 00:07:51 2009
@@ -17,11 +17,10 @@
package org.apache.commons.math.optimization;
-import org.apache.commons.math.optimization.direct.DirectSearchOptimizer;
+import java.io.Serializable;
-
-/** This interface specifies how to check if a {@link
- * DirectSearchOptimizer direct search method} has converged.
+/** This interface specifies how to check if an {@link Optimizer optimization
+ * algorithm} has converged.
*
* <p>Deciding if convergence has been reached is a problem-dependent
* issue. The user should provide a class implementing this interface
@@ -29,22 +28,25 @@
* the problem at hand.</p>
*
* @version $Revision$ $Date$
- * @since 1.2
+ * @since 2.0
*/
-public interface ConvergenceChecker {
+public interface ConvergenceChecker extends Serializable {
- /** Check if the optimization algorithm has converged on the simplex.
+ /** Check if the optimization algorithm has converged considering the last points.
* <p>
- * When this method is called, all points in the simplex have been evaluated
- * and are sorted from lowest to largest value. The values are either the
- * original objective function values if the optimizer was configured for
- * minimization, or the opposites of the original objective function values
- * if the optimizer was configured for maximization.
+ * This method may be called several time from the same algorithm iteration with
+ * different points. This can be detected by checking the iteration number at each
+ * call if needed. Each time this method is called, the previous and current point
+ * correspond to points with the same role at each iteration, so they can be
+ * compared. As an example, simplex-based algorithms call this method for all
+ * points of the simplex, not only for the best or worst ones.
* </p>
- * @param simplex ordered simplex
+ * @param iteration index of current iteration
+ * @param previous point from previous iteration
+ * @param current point from current iteration
* @return true if the algorithm is considered to have converged
*/
- boolean converged(PointValuePair[] simplex);
+ boolean converged(int iteration, PointValuePair previous, PointValuePair current);
}
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/LeastSquaresConverter.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/LeastSquaresConverter.java?rev=749850&r1=749849&r2=749850&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/LeastSquaresConverter.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/LeastSquaresConverter.java Wed Mar 4 00:07:51 2009
@@ -17,6 +17,7 @@
package org.apache.commons.math.optimization;
+import org.apache.commons.math.MathRuntimeException;
import org.apache.commons.math.linear.RealMatrix;
/** This class converts {@link MultiObjectiveFunction vectorial
@@ -24,17 +25,21 @@
* when the goal is to minimize them.
* <p>
* This class is mostly used when the vectorial objective function represents
- * residuals, i.e. differences between a theoretical result computed from a
- * variables set applied to a model and a reference. Residuals are intended to be
- * minimized in order to get the variables set that best fit the model to the
- * reference. The reference may be obtained for example from physical measurements
- * whether the model is built from theoretical considerations.
+ * a theoretical result computed from a variables set applied to a model and
+ * the models variables must be adjusted to fit the theoretical result to some
+ * reference observations. The observations may be obtained for example from
+ * physical measurements whether the model is built from theoretical
+ * considerations.
* </p>
* <p>
* This class computes a possibly weighted squared sum of the residuals, which is
- * a scalar value. It implements the {@link ObjectiveFunction} interface and can
- * therefore be minimized by any optimizer supporting scalar objectives functions.
- * This correspond to a least square estimation.
+ * a scalar value. The residuals are the difference between the theoretical model
+ * (i.e. the output of the vectorial objective function) and the observations. The
+ * class implements the {@link ObjectiveFunction} interface and can therefore be
+ * minimized by any optimizer supporting scalar objectives functions.This is one way
+ * to perform a least square estimation. There are other ways to do this without using
+ * this converter, as some optimization algorithms directly support vectorial objective
+ * functions.
* </p>
* <p>
* This class support combination of residuals with or without weights and correlations.
@@ -49,11 +54,14 @@
public class LeastSquaresConverter implements ObjectiveFunction {
/** Serializable version identifier. */
- private static final long serialVersionUID = -5174886571116126798L;
+ private static final long serialVersionUID = 2424320989874772110L;
/** Underlying vectorial function. */
private final MultiObjectiveFunction function;
+ /** Observations to be compared to objective function to compute residuals. */
+ private final double[] observations;
+
/** Optional weights for the residuals. */
private final double[] weights;
@@ -62,85 +70,112 @@
/** Build a simple converter for uncorrelated residuals with the same weight.
* @param function vectorial residuals function to wrap
+ * @param observations observations to be compared to objective function to compute residuals
*/
- public LeastSquaresConverter (final MultiObjectiveFunction function) {
- this.function = function;
- this.weights = null;
- this.scale = null;
+ public LeastSquaresConverter (final MultiObjectiveFunction function,
+ final double[] observations) {
+ this.function = function;
+ this.observations = observations.clone();
+ this.weights = null;
+ this.scale = null;
}
/** Build a simple converter for uncorrelated residuals with the specific weights.
* <p>
* The scalar objective function value is computed as:
* <pre>
- * objective = ∑(weight<sub>i</sub>residual<sub>i</sub>)<sup>2</sup>
+ * objective = ∑weight<sub>i</sub>(observation<sub>i</sub>-objective<sub>i</sub>)<sup>2</sup>
* </pre>
* </p>
* <p>
* Weights can be used for example to combine residuals with different standard
- * deviations. As an example, consider a 2000 elements residuals array in which
- * even elements are angular measurements in degrees with a 0.01° standard
- * deviation and off elements are distance measurements in meters with a 15m
- * standard deviation. In this case, the weights array should be initialized with
- * value 1.0/0.01 in the even elements and 1.0/15.0 in the odd elements.
+ * deviations. As an example, consider a residuals array in which even elements
+ * are angular measurements in degrees with a 0.01° standard deviation and
+ * odd elements are distance measurements in meters with a 15m standard deviation.
+ * In this case, the weights array should be initialized with value
+ * 1.0/(0.01<sup>2</sup>) in the even elements and 1.0/(15.0<sup>2</sup>) in the
+ * odd elements (i.e. reciprocals of variances).
* </p>
* <p>
- * The residuals array computed by the function and the weights array must
- * have consistent sizes or a {@link ObjectiveException} will be triggered while
- * computing the scalar objective.
+ * The array computed by the objective function, the observations array and the
+ * weights array must have consistent sizes or a {@link ObjectiveException} will be
+ * triggered while computing the scalar objective.
* </p>
* @param function vectorial residuals function to wrap
+ * @param observations observations to be compared to objective function to compute residuals
* @param weights weights to apply to the residuals
+ * @exception IllegalArgumentException if the observations vector and the weights
+ * vector dimensions don't match (objective function dimension is checked only when
+ * the {@link #objective} method is called)
*/
public LeastSquaresConverter (final MultiObjectiveFunction function,
- final double[] weights) {
- this.function = function;
- this.weights = weights.clone();
- this.scale = null;
+ final double[] observations, final double[] weights)
+ throws IllegalArgumentException {
+ if (observations.length != weights.length) {
+ throw MathRuntimeException.createIllegalArgumentException(
+ "dimension mismatch {0} != {1}",
+ observations.length, weights.length);
+ }
+ this.function = function;
+ this.observations = observations.clone();
+ this.weights = weights.clone();
+ this.scale = null;
}
- /** Build a simple convertor for correlated residuals with the specific weights.
+ /** Build a simple converter for correlated residuals with the specific weights.
* <p>
* The scalar objective function value is computed as:
* <pre>
- * objective = ∑(y<sub>i</sub>)<sup>2</sup> with y = scale×residual
+ * objective = y<sup>T</sup>y with y = scale×(observation-objective)
* </pre>
* </p>
* <p>
- * The residuals array computed by the function and the scaling matrix must
- * have consistent sizes or a {@link ObjectiveException} will be triggered while
- * computing the scalar objective.
+ * The array computed by the objective function, the observations array and the
+ * the scaling matrix must have consistent sizes or a {@link ObjectiveException}
+ * will be triggered while computing the scalar objective.
* </p>
* @param function vectorial residuals function to wrap
- * @param scale scaling matrix (
+ * @param observations observations to be compared to objective function to compute residuals
+ * @param scale scaling matrix
+ * @exception IllegalArgumentException if the observations vector and the scale
+ * matrix dimensions don't match (objective function dimension is checked only when
+ * the {@link #objective} method is called)
*/
public LeastSquaresConverter (final MultiObjectiveFunction function,
- final RealMatrix scale) {
- this.function = function;
- this.weights = null;
- this.scale = scale.copy();
+ final double[] observations, final RealMatrix scale)
+ throws IllegalArgumentException {
+ if (observations.length != scale.getColumnDimension()) {
+ throw MathRuntimeException.createIllegalArgumentException(
+ "dimension mismatch {0} != {1}",
+ observations.length, scale.getColumnDimension());
+ }
+ this.function = function;
+ this.observations = observations.clone();
+ this.weights = null;
+ this.scale = scale.copy();
}
/** {@inheritDoc} */
public double objective(final double[] variables) throws ObjectiveException {
+ // compute residuals
final double[] residuals = function.objective(variables);
- double sumSquares = 0;
+ if (residuals.length != observations.length) {
+ throw new ObjectiveException("dimension mismatch {0} != {1}",
+ residuals.length, observations.length);
+ }
+ for (int i = 0; i < residuals.length; ++i) {
+ residuals[i] -= observations[i];
+ }
+ // compute sum of squares
+ double sumSquares = 0;
if (weights != null) {
- if (weights.length != residuals.length) {
- throw new ObjectiveException("dimension mismatch {0} != {1}",
- weights.length, residuals.length);
- }
- for (int i = 0; i < weights.length; ++i) {
- final double ai = residuals[i] * weights[i];
- sumSquares += ai * ai;
+ for (int i = 0; i < residuals.length; ++i) {
+ final double ri = residuals[i];
+ sumSquares += weights[i] * ri * ri;
}
} else if (scale != null) {
- if (scale.getColumnDimension() != residuals.length) {
- throw new ObjectiveException("dimension mismatch {0} != {1}",
- scale.getColumnDimension(), residuals.length);
- }
for (final double yi : scale.operate(residuals)) {
sumSquares += yi * yi;
}
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/MultiObjectiveFunction.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/MultiObjectiveFunction.java?rev=749850&r1=749849&r2=749850&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/MultiObjectiveFunction.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/MultiObjectiveFunction.java Wed Mar 4 00:07:51 2009
@@ -32,7 +32,9 @@
* @param variables variables set
* @return function value for the given variables set
* @exception ObjectiveException if no cost can be computed for the parameters
+ * @exception IllegalArgumentException if variables dimension is wrong
*/
- double[] objective(double[] variables) throws ObjectiveException;
+ double[] objective(double[] variables)
+ throws ObjectiveException, IllegalArgumentException;
}
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/MultiStartOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/MultiStartOptimizer.java?rev=749850&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/MultiStartOptimizer.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/MultiStartOptimizer.java Wed Mar 4 00:07:51 2009
@@ -0,0 +1,189 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.commons.math.optimization;
+
+import java.util.Arrays;
+import java.util.Comparator;
+
+import org.apache.commons.math.ConvergenceException;
+import org.apache.commons.math.MathRuntimeException;
+import org.apache.commons.math.random.RandomVectorGenerator;
+
+/**
+ * Special implementation of the {@link Optimizer} interface adding
+ * multi-start features to an existing optimizer.
+ * <p>
+ * This class wraps a classical optimizer to use it several times in
+ * turn with different starting points in order to avoid being trapped
+ * into a local extremum when looking for a global one.
+ * </p>
+ * @version $Revision$ $Date$
+ * @since 2.0
+ */
+public class MultiStartOptimizer implements Optimizer {
+
+ /** Serializable version identifier. */
+ private static final long serialVersionUID = 6648351778723282863L;
+
+ /** Underlying classical optimizer. */
+ private final Optimizer optimizer;
+
+ /** Number of evaluations already performed for all starts. */
+ private int totalEvaluations;
+
+ /** Maximal number of evaluations allowed. */
+ private int maxEvaluations;
+
+ /** Number of starts to go. */
+ private int starts;
+
+ /** Random generator for multi-start. */
+ private RandomVectorGenerator generator;
+
+ /** Found optima. */
+ private PointValuePair[] optima;
+
+ /**
+ * Create a multi-start optimizer from a single-start optimizer
+ * @param optimizer single-start optimizer to wrap
+ * @param starts number of starts to perform (including the
+ * first one), multi-start is disabled if value is less than or
+ * equal to 1
+ * @param generator random vector generator to use for restarts
+ */
+ public MultiStartOptimizer(final Optimizer optimizer, final int starts,
+ final RandomVectorGenerator generator) {
+ this.optimizer = optimizer;
+ this.totalEvaluations = 0;
+ this.maxEvaluations = Integer.MAX_VALUE;
+ this.starts = starts;
+ this.generator = generator;
+ this.optima = null;
+ }
+
+ /** Get all the optima found during the last call to {@link
+ * #optimize(ObjectiveFunction, GoalType, double[]) optimize}.
+ * <p>The optimizer stores all the optima found during a set of
+ * restarts. The {@link #optimize(ObjectiveFunction, GoalType,
+ * double[]) optimize} method returns the best point only. This
+ * method returns all the points found at the end of each starts,
+ * including the best one already returned by the {@link
+ * #optimize(ObjectiveFunction, GoalType, double[]) optimize}
+ * method.
+ * </p>
+ * <p>
+ * The returned array as one element for each start as specified
+ * in the constructor. It is ordered with the results from the
+ * runs that did converge first, sorted from best to worst
+ * objective value (i.e in ascending order if minimizing and in
+ * descending order if maximizing), followed by and null elements
+ * corresponding to the runs that did not converge. This means all
+ * elements will be null if the {@link #optimize(ObjectiveFunction,
+ * GoalType, double[]) optimize} method did throw a {@link
+ * ConvergenceException ConvergenceException}). This also means that
+ * if the first element is non null, it is the best point found across
+ * all starts.</p>
+ * @return array containing the optima
+ * @exception IllegalStateException if {@link #optimize(ObjectiveFunction,
+ * GoalType, double[]) optimize} has not been called
+ */
+ public PointValuePair[] getOptima() throws IllegalStateException {
+ if (optima == null) {
+ throw MathRuntimeException.createIllegalStateException("no optimum computed yet");
+ }
+ return (PointValuePair[]) optima.clone();
+ }
+
+ /** {@inheritDoc} */
+ public int getEvaluations() {
+ return totalEvaluations;
+ }
+
+ /** {@inheritDoc} */
+ public void setMaxEvaluations(int maxEvaluations) {
+ this.maxEvaluations = maxEvaluations;
+ }
+
+ /** {@inheritDoc} */
+ public int getMaxEvaluations() {
+ return maxEvaluations;
+ }
+
+ /** {@inheritDoc} */
+ public void setConvergenceChecker(ConvergenceChecker checker) {
+ optimizer.setConvergenceChecker(checker);
+ }
+
+ /** {@inheritDoc} */
+ public ConvergenceChecker getConvergenceChecker() {
+ return optimizer.getConvergenceChecker();
+ }
+
+ /** {@inheritDoc} */
+ public PointValuePair optimize(final ObjectiveFunction f,
+ final GoalType goalType,
+ double[] startPoint)
+ throws ObjectiveException, OptimizationException {
+
+ optima = new PointValuePair[starts];
+ totalEvaluations = 0;
+
+ // multi-start loop
+ for (int i = 0; i < starts; ++i) {
+
+ try {
+ optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations);
+ optima[i] = optimizer.optimize(f, goalType,
+ (i == 0) ? startPoint : generator.nextVector());
+ } catch (ObjectiveException obe) {
+ optima[i] = null;
+ } catch (OptimizationException ope) {
+ optima[i] = null;
+ }
+
+ totalEvaluations += optimizer.getEvaluations();
+
+ }
+
+ // sort the optima from best to worst, followed by null elements
+ Arrays.sort(optima, new Comparator<PointValuePair>() {
+ public int compare(final PointValuePair o1, final PointValuePair o2) {
+ if (o1 == null) {
+ return (o2 == null) ? 0 : +1;
+ } else if (o2 == null) {
+ return -1;
+ }
+ final double v1 = o1.getValue();
+ final double v2 = o2.getValue();
+ return (goalType == GoalType.MINIMIZE) ?
+ Double.compare(v1, v2) : Double.compare(v2, v1);
+ }
+ });
+
+ if (optima[0] == null) {
+ throw new OptimizationException(
+ "none of the {0} start points lead to convergence",
+ starts);
+ }
+
+ // return the found point given the best objective function value
+ return optima[0];
+
+ }
+
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/MultiStartOptimizer.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/MultiStartOptimizer.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ObjectiveFunction.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ObjectiveFunction.java?rev=749850&r1=749849&r2=749850&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ObjectiveFunction.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ObjectiveFunction.java Wed Mar 4 00:07:51 2009
@@ -31,7 +31,9 @@
* @param variables variables set
* @return function value for the given variables set
* @exception ObjectiveException if no value can be computed for the parameters
+ * @exception IllegalArgumentException if variables dimension is wrong
*/
- double objective(double[] variables) throws ObjectiveException;
+ double objective(double[] variables)
+ throws ObjectiveException, IllegalArgumentException;
}
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ObjectiveValueChecker.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ObjectiveValueChecker.java?rev=749850&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ObjectiveValueChecker.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ObjectiveValueChecker.java Wed Mar 4 00:07:51 2009
@@ -0,0 +1,84 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.commons.math.optimization;
+
+import org.apache.commons.math.util.MathUtils;
+
+/**
+ * Special implementation of the {@link ConvergenceChecker} interface using
+ * only objective function values.
+ * <p>
+ * Convergence is considered to have been reached if either the relative
+ * difference between the objective function values is smaller than a
+ * threshold or if either the absolute difference between the objective
+ * function values is smaller than another threshold.
+ * </p>
+ * @version $Revision$ $Date$
+ * @since 2.0
+ */
+public class ObjectiveValueChecker implements ConvergenceChecker {
+
+ /** Serializable version identifier. */
+ private static final long serialVersionUID = 2490271385513842607L;
+
+ /** Default relative threshold. */
+ private static final double DEFAULT_RELATIVE_THRESHOLD = 100 * MathUtils.EPSILON;
+
+ /** Default absolute threshold. */
+ private static final double DEFAULT_ABSOLUTE_THRESHOLD = 100 * MathUtils.SAFE_MIN;
+
+ /** Relative tolerance threshold. */
+ private final double relativeThreshold;
+
+ /** Absolute tolerance threshold. */
+ private final double absoluteThreshold;
+
+ /** Build an instance with default threshold.
+ */
+ public ObjectiveValueChecker() {
+ this.relativeThreshold = DEFAULT_RELATIVE_THRESHOLD;
+ this.absoluteThreshold = DEFAULT_ABSOLUTE_THRESHOLD;
+ }
+
+ /** Build an instance with a specified threshold.
+ * <p>
+ * In order to perform only relative checks, the absolute tolerance
+ * must be set to a negative value. In order to perform only absolute
+ * checks, the relative tolerance must be set to a negative value.
+ * </p>
+ * @param relativeThreshold relative tolerance threshold
+ * @param absoluteThreshold absolute tolerance threshold
+ */
+ public ObjectiveValueChecker(final double relativeThreshold,
+ final double absoluteThreshold) {
+ this.relativeThreshold = relativeThreshold;
+ this.absoluteThreshold = absoluteThreshold;
+ }
+
+ /** {@inheritDoc} */
+ public boolean converged(final int iteration,
+ final PointValuePair previous,
+ final PointValuePair current) {
+ final double p = previous.getValue();
+ final double c = current.getValue();
+ final double difference = Math.abs(p - c);
+ final double size = Math.max(Math.abs(p), Math.abs(c));
+ return (difference <= (size * relativeThreshold)) || (difference <= absoluteThreshold);
+ }
+
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ObjectiveValueChecker.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/ObjectiveValueChecker.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/Optimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/Optimizer.java?rev=749850&r1=749849&r2=749850&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/Optimizer.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/Optimizer.java Wed Mar 4 00:07:51 2009
@@ -27,29 +27,61 @@
public interface Optimizer extends Serializable {
/** Set the maximal number of objective function calls.
- * @param maxEvaluations maximal number of function calls for each
- * start (note that the number may be checked <em>after</em>
- * a few related calls have been made, this means that in some
- * cases this number will be exceeded by a few units, depending on
- * the dimension of the problem and kind of optimizer).
+ * <p>
+ * The number of objective function calls may be checked <em>after</em> a few
+ * related calls have been made. This implies that in some cases this number may
+ * be exceeded by a few units, depending on the dimension of the problem and kind
+ * of optimizer.
+ * </p>
+ * @param maxEvaluations maximal number of function calls
+ * .
*/
void setMaxEvaluations(int maxEvaluations);
+ /** Get the maximal number of objective function calls.
+ * <p>
+ * The number of objective function calls may be checked <em>after</em> a few
+ * related calls have been made. This implies that in some cases this number may
+ * be exceeded by a few units, depending on the dimension of the problem and kind
+ * of optimizer.
+ * </p>
+ * @return maximal number of function calls
+ */
+ int getMaxEvaluations();
+
/** Set the convergence checker.
* @param checker object to use to check for convergence
*/
void setConvergenceChecker(ConvergenceChecker checker);
+ /** Get the convergence checker.
+ * @param checker object to use to check for convergence
+ */
+ ConvergenceChecker getConvergenceChecker();
+
/** Optimizes an objective function.
* @param f objective function
* @param goalType type of optimization goal: either {@link GoalType#MAXIMIZE}
* or {@link GoalType#MINIMIZE}
+ * @param startPoint the start point for optimization
* @return the point/value pair giving the optimal value for objective function
* @exception ObjectiveException if the objective function throws one during
* the search
* @exception OptimizationException if the algorithm failed to converge
+ * @exception IllegalArgumentException if the start point dimension is wrong
+ */
+ PointValuePair optimize(ObjectiveFunction f, GoalType goalType,
+ double[] startPoint)
+ throws ObjectiveException, OptimizationException, IllegalArgumentException;
+
+ /** Get the number of evaluations of the objective function.
+ * <p>
+ * The number of evaluation correspond to the last call to the
+ * {@link #optimize(ObjectiveFunction, GoalType, double[]) optimize}
+ * method. It is 0 if the method has not been called yet.
+ * </p>
+ * @return number of evaluations of the objective function
*/
- PointValuePair optimize(final ObjectiveFunction f, final GoalType goalType)
- throws ObjectiveException, OptimizationException;
+ int getEvaluations();
}
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/PointValuePair.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/PointValuePair.java?rev=749850&r1=749849&r2=749850&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/PointValuePair.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/PointValuePair.java Wed Mar 4 00:07:51 2009
@@ -19,7 +19,6 @@
import java.io.Serializable;
-
/**
* This class holds a point and the value of an objective function at this point.
* <p>This is a simple immutable container.</p>
@@ -30,7 +29,7 @@
public class PointValuePair implements Serializable {
/** Serializable version identifier. */
- private static final long serialVersionUID = 2254035971797977063L;
+ private static final long serialVersionUID = 1003888396256744753L;
/** Point coordinates. */
private final double[] point;
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/DirectSearchOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/DirectSearchOptimizer.java?rev=749850&r1=749849&r2=749850&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/DirectSearchOptimizer.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/DirectSearchOptimizer.java Wed Mar 4 00:07:51 2009
@@ -17,27 +17,18 @@
package org.apache.commons.math.optimization.direct;
-import java.io.Serializable;
import java.util.Arrays;
import java.util.Comparator;
-import org.apache.commons.math.ConvergenceException;
-import org.apache.commons.math.DimensionMismatchException;
import org.apache.commons.math.MathRuntimeException;
-import org.apache.commons.math.linear.RealMatrix;
-import org.apache.commons.math.linear.decomposition.NotPositiveDefiniteMatrixException;
import org.apache.commons.math.optimization.ConvergenceChecker;
+import org.apache.commons.math.optimization.GoalType;
import org.apache.commons.math.optimization.ObjectiveException;
import org.apache.commons.math.optimization.ObjectiveFunction;
+import org.apache.commons.math.optimization.OptimizationException;
+import org.apache.commons.math.optimization.Optimizer;
import org.apache.commons.math.optimization.PointValuePair;
-import org.apache.commons.math.random.CorrelatedRandomVectorGenerator;
-import org.apache.commons.math.random.JDKRandomGenerator;
-import org.apache.commons.math.random.RandomGenerator;
-import org.apache.commons.math.random.RandomVectorGenerator;
-import org.apache.commons.math.random.UncorrelatedRandomVectorGenerator;
-import org.apache.commons.math.random.UniformRandomGenerator;
-import org.apache.commons.math.stat.descriptive.moment.VectorialCovariance;
-import org.apache.commons.math.stat.descriptive.moment.VectorialMean;
+import org.apache.commons.math.optimization.ObjectiveValueChecker;
/**
* This class implements simplex-based direct search optimization
@@ -49,7 +40,7 @@
* (<a href="http://cm.bell-labs.com/cm/cs/doc/96/4-02.ps.gz">Direct
* Search Methods: Once Scorned, Now Respectable</a>), they are used
* when either the computation of the derivative is impossible (noisy
- * functions, unpredictable dicontinuities) or difficult (complexity,
+ * functions, unpredictable discontinuities) or difficult (complexity,
* computation cost). In the first cases, rather than an optimum, a
* <em>not too bad</em> point is desired. In the latter cases, an
* optimum is desired but cannot be reasonably found. In all cases
@@ -58,18 +49,26 @@
* <p>Simplex-based direct search methods are based on comparison of
* the objective function values at the vertices of a simplex (which is a
* set of n+1 points in dimension n) that is updated by the algorithms
- * steps.</p>
+ * steps.<p>
*
- * <p>Optimization can be attempted either in single-start or in
- * multi-start mode. Multi-start is a traditional way to try to avoid
- * being trapped in a local optimum and miss the global optimum of a
- * function. It can also be used to verify the convergence of an
- * algorithm. The various multi-start-enabled <code>optimize</code>
- * methods return the best optimum found after all starts, and the
- * {@link #getOptimum getOptimum} method can be used to retrieve all
- * optima from all starts (including the one already provided by the
- * {@link #optimize(ObjectiveFunction, int, ConvergenceChecker, double[],
- * double[]) optimize} method).</p>
+ * <p>The initial configuration of the simplex can be set using either
+ * {@link #setStartConfiguration(double[])} or {@link
+ * #setStartConfiguration(double[][])}. If neither method has been called
+ * before optimization is attempted, an explicit call to the first method
+ * with all steps set to +1 is triggered, thus building a default
+ * configuration from a unit hypercube. Each call to {@link
+ * #optimize(ObjectiveFunction, GoalType, double[]) optimize} will reuse
+ * the current start configuration and move it such that its first vertex
+ * is at the provided start point of the optimization. If the same optimizer
+ * is used to solve different problems and the number of parameters change,
+ * the start configuration <em>must</em> be reset or a dimension mismatch
+ * will occur.</p>
+ *
+ * <p>If {@link #setConvergenceChecker(ConvergenceChecker)} is not called,
+ * a default {@link ObjectiveValueChecker} is used.</p>
+ *
+ * <p>Convergence is checked by providing the <em>worst</em> points of
+ * previous and current simplex to the convergence checker, not the best ones.</p>
*
* <p>This class is the base class performing the boilerplate simplex
* initialization and handling. The simplex update by itself is
@@ -82,23 +81,10 @@
* @version $Revision$ $Date$
* @since 1.2
*/
-public abstract class DirectSearchOptimizer implements Serializable {
+public abstract class DirectSearchOptimizer implements Optimizer {
/** Serializable version identifier. */
- private static final long serialVersionUID = -3913013760494455466L;
-
- /** Comparator for {@link PointValuePair} objects. */
- private static final Comparator<PointValuePair> PAIR_COMPARATOR =
- new Comparator<PointValuePair>() {
- public int compare(PointValuePair o1, PointValuePair o2) {
- if (o1 == null) {
- return (o2 == null) ? 0 : +1;
- } else if (o2 == null) {
- return -1;
- }
- return (o1.getValue() < o2.getValue()) ? -1 : ((o1 == o2) ? 0 : +1);
- }
- };
+ private static final long serialVersionUID = 4299910390345933369L;
/** Simplex. */
protected PointValuePair[] simplex;
@@ -106,497 +92,209 @@
/** Objective function. */
private ObjectiveFunction f;
- /** Indicator for minimization. */
- private boolean minimizing;
+ /** Convergence checker. */
+ private ConvergenceChecker checker;
/** Number of evaluations already performed for the current start. */
private int evaluations;
- /** Number of evaluations already performed for all starts. */
- private int totalEvaluations;
+ /** Maximal number of evaluations allowed. */
+ private int maxEvaluations;
- /** Number of starts to go. */
- private int starts;
-
- /** Random generator for multi-start. */
- private RandomVectorGenerator generator;
-
- /** Found optima. */
- private PointValuePair[] optima;
+ /** Start simplex configuration. */
+ private double[][] startConfiguration;
/** Simple constructor.
*/
protected DirectSearchOptimizer() {
+ setConvergenceChecker(new ObjectiveValueChecker());
}
- /** Optimizes an objective function.
- * <p>The initial simplex is built from two vertices that are
- * considered to represent two opposite vertices of a box parallel
- * to the canonical axes of the space. The simplex is the subset of
- * vertices encountered while going from vertexA to vertexB
- * traveling along the box edges only. This can be seen as a scaled
- * regular simplex using the projected separation between the given
- * points as the scaling factor along each coordinate axis.</p>
- * <p>The optimization is performed in single-start mode.</p>
- * @param f objective function
- * @param maxEvaluations maximal number of function calls for each
- * start (note that the number will be checked <em>after</em>
- * complete simplices have been evaluated, this means that in some
- * cases this number will be exceeded by a few units, depending on
- * the dimension of the problem)
- * @param checker object to use to check for convergence
- * @param minimizing if true, function must be minimize otherwise it must be maximized
- * @param vertexA first vertex
- * @param vertexB last vertex
- * @return the point/value pairs giving the optimal value for objective function
- * @exception ObjectiveException if the objective function throws one during
- * the search
- * @exception ConvergenceException if none of the starts did
- * converge (it is not thrown if at least one start did converge)
- */
- public PointValuePair optimize(final ObjectiveFunction f, final int maxEvaluations,
- final ConvergenceChecker checker, final boolean minimizing,
- final double[] vertexA, final double[] vertexB)
- throws ObjectiveException, ConvergenceException {
-
- // set up optimizer
- buildSimplex(vertexA, vertexB);
- setSingleStart();
-
- // compute optimum
- return optimize(f, maxEvaluations, checker, minimizing);
-
- }
-
- /** Optimizes an objective function.
- * <p>The initial simplex is built from two vertices that are
- * considered to represent two opposite vertices of a box parallel
- * to the canonical axes of the space. The simplex is the subset of
- * vertices encountered while going from vertexA to vertexB
- * traveling along the box edges only. This can be seen as a scaled
- * regular simplex using the projected separation between the given
- * points as the scaling factor along each coordinate axis.</p>
- * <p>The optimization is performed in multi-start mode.</p>
- * @param f objective function
- * @param maxEvaluations maximal number of function calls for each
- * start (note that the number will be checked <em>after</em>
- * complete simplices have been evaluated, this means that in some
- * cases this number will be exceeded by a few units, depending on
- * the dimension of the problem)
- * @param checker object to use to check for convergence
- * @param minimizing if true, function must be minimize otherwise it must be maximized
- * @param vertexA first vertex
- * @param vertexB last vertex
- * @param starts number of starts to perform (including the
- * first one), multi-start is disabled if value is less than or
- * equal to 1
- * @param seed seed for the random vector generator
- * @return the point/value pairs giving the optimal value for objective function
- * @exception ObjectiveException if the obective function throws one during
- * the search
- * @exception ConvergenceException if none of the starts did
- * converge (it is not thrown if at least one start did converge)
- */
- public PointValuePair optimize(final ObjectiveFunction f, final int maxEvaluations,
- final ConvergenceChecker checker, final boolean minimizing,
- final double[] vertexA, final double[] vertexB,
- final int starts, final long seed)
- throws ObjectiveException, ConvergenceException {
-
- // set up the simplex traveling around the box
- buildSimplex(vertexA, vertexB);
-
- // we consider the simplex could have been produced by a generator
- // having its mean value at the center of the box, the standard
- // deviation along each axe being the corresponding half size
- final double[] mean = new double[vertexA.length];
- final double[] standardDeviation = new double[vertexA.length];
- for (int i = 0; i < vertexA.length; ++i) {
- mean[i] = 0.5 * (vertexA[i] + vertexB[i]);
- standardDeviation[i] = 0.5 * Math.abs(vertexA[i] - vertexB[i]);
- }
-
- final RandomGenerator rg = new JDKRandomGenerator();
- rg.setSeed(seed);
- final UniformRandomGenerator urg = new UniformRandomGenerator(rg);
- final RandomVectorGenerator rvg =
- new UncorrelatedRandomVectorGenerator(mean, standardDeviation, urg);
- setMultiStart(starts, rvg);
-
- // compute optimum
- return optimize(f, maxEvaluations, checker, minimizing);
-
- }
-
- /** Optimizes an objective function.
- * <p>The simplex is built from all its vertices.</p>
- * <p>The optimization is performed in single-start mode.</p>
- * @param f objective function
- * @param maxEvaluations maximal number of function calls for each
- * start (note that the number will be checked <em>after</em>
- * complete simplices have been evaluated, this means that in some
- * cases this number will be exceeded by a few units, depending on
- * the dimension of the problem)
- * @param checker object to use to check for convergence
- * @param minimizing if true, function must be minimize otherwise it must be maximized
- * @param vertices array containing all vertices of the simplex
- * @return the point/value pairs giving the optimal value for objective function
- * @exception ObjectiveException if the objective function throws one during
- * the search
- * @exception ConvergenceException if none of the starts did
- * converge (it is not thrown if at least one start did converge)
- */
- public PointValuePair optimize(final ObjectiveFunction f, final int maxEvaluations,
- final ConvergenceChecker checker, final boolean minimizing,
- final double[][] vertices)
- throws ObjectiveException, ConvergenceException {
-
- // set up optimizer
- buildSimplex(vertices);
- setSingleStart();
-
- // compute optimum
- return optimize(f, maxEvaluations, checker, minimizing);
-
- }
-
- /** Optimizes an objective function.
- * <p>The simplex is built from all its vertices.</p>
- * <p>The optimization is performed in multi-start mode.</p>
- * @param f objective function
- * @param maxEvaluations maximal number of function calls for each
- * start (note that the number will be checked <em>after</em>
- * complete simplices have been evaluated, this means that in some
- * cases this number will be exceeded by a few units, depending on
- * the dimension of the problem)
- * @param checker object to use to check for convergence
- * @param minimizing if true, function must be minimize otherwise it must be maximized
- * @param vertices array containing all vertices of the simplex
- * @param starts number of starts to perform (including the
- * first one), multi-start is disabled if value is less than or
- * equal to 1
- * @param seed seed for the random vector generator
- * @return the point/value pairs giving the optimal value for objective function
- * @exception NotPositiveDefiniteMatrixException if the vertices
- * array is degenerated
- * @exception ObjectiveException if the objective function throws one during
- * the search
- * @exception ConvergenceException if none of the starts did
- * converge (it is not thrown if at least one start did converge)
- */
- public PointValuePair optimize(final ObjectiveFunction f, final int maxEvaluations,
- final ConvergenceChecker checker, final boolean minimizing,
- final double[][] vertices,
- final int starts, final long seed)
- throws NotPositiveDefiniteMatrixException, ObjectiveException, ConvergenceException {
-
- try {
- // store the points into the simplex
- buildSimplex(vertices);
-
- // compute the statistical properties of the simplex points
- final VectorialMean meanStat = new VectorialMean(vertices[0].length);
- final VectorialCovariance covStat = new VectorialCovariance(vertices[0].length, true);
- for (int i = 0; i < vertices.length; ++i) {
- meanStat.increment(vertices[i]);
- covStat.increment(vertices[i]);
+ /** Set start configuration for simplex.
+ * <p>The start configuration for simplex is built from a box parallel to
+ * the canonical axes of the space. The simplex is the subset of vertices
+ * of a box parallel to the canonical axes. It is built as the path followed
+ * while traveling from one vertex of the box to the diagonally opposite
+ * vertex moving only along the box edges. The first vertex of the box will
+ * be located at the start point of the optimization.</p>
+ * <p>As an example, in dimension 3 a simplex has 4 vertices. Setting the
+ * steps to (1, 10, 2) and the start point to (1, 1, 1) would imply the
+ * start simplex would be: { (1, 1, 1), (2, 1, 1), (2, 11, 1), (2, 11, 3) }.
+ * The first vertex would be set to the start point at (1, 1, 1) and the
+ * last vertex would be set to the diagonally opposite vertex at (2, 11, 3).</p>
+ * @param steps steps along the canonical axes representing box edges,
+ * they may be negative but not null
+ * @exception IllegalArgumentException if one step is null
+ */
+ public void setStartConfiguration(final double[] steps)
+ throws IllegalArgumentException {
+ // only the relative position of the n final vertices with respect
+ // to the first one are stored
+ final int n = steps.length;
+ startConfiguration = new double[n][n];
+ for (int i = 0; i < n; ++i) {
+ final double[] vertexI = startConfiguration[i];
+ for (int j = 0; j < i + 1; ++j) {
+ if (steps[j] == 0.0) {
+ throw MathRuntimeException.createIllegalArgumentException(
+ "equals vertices {0} and {1} in simplex configuration",
+ j, j + 1);
+ }
+ System.arraycopy(steps, 0, vertexI, 0, j + 1);
}
- final double[] mean = meanStat.getResult();
- final RealMatrix covariance = covStat.getResult();
-
-
- final RandomGenerator rg = new JDKRandomGenerator();
- rg.setSeed(seed);
- final RandomVectorGenerator rvg =
- new CorrelatedRandomVectorGenerator(mean,
- covariance, 1.0e-12 * covariance.getNorm(),
- new UniformRandomGenerator(rg));
- setMultiStart(starts, rvg);
-
- // compute optimum
- return optimize(f, maxEvaluations, checker, minimizing);
-
- } catch (DimensionMismatchException dme) {
- // this should not happen
- throw new MathRuntimeException(dme, "unexpected exception caught");
}
-
}
- /** Optimizes an objective function.
- * <p>The simplex is built randomly.</p>
- * <p>The optimization is performed in single-start mode.</p>
- * @param f objective function
- * @param maxEvaluations maximal number of function calls for each
- * start (note that the number will be checked <em>after</em>
- * complete simplices have been evaluated, this means that in some
- * cases this number will be exceeded by a few units, depending on
- * the dimension of the problem)
- * @param checker object to use to check for convergence
- * @param minimizing if true, function must be minimize otherwise it must be maximized
- * @param generator random vector generator
- * @return the point/value pairs giving the optimal value for objective function
- * @exception ObjectiveException if the objective function throws one during
- * the search
- * @exception ConvergenceException if none of the starts did
- * converge (it is not thrown if at least one start did converge)
- */
- public PointValuePair optimize(final ObjectiveFunction f, final int maxEvaluations,
- final ConvergenceChecker checker, final boolean minimizing,
- final RandomVectorGenerator generator)
- throws ObjectiveException, ConvergenceException {
-
- // set up optimizer
- buildSimplex(generator);
- setSingleStart();
-
- // compute optimum
- return optimize(f, maxEvaluations, checker, minimizing);
-
- }
-
- /** Optimizes an objective function.
- * <p>The simplex is built randomly.</p>
- * <p>The optimization is performed in multi-start mode.</p>
- * @param f objective function
- * @param maxEvaluations maximal number of function calls for each
- * start (note that the number will be checked <em>after</em>
- * complete simplices have been evaluated, this means that in some
- * cases this number will be exceeded by a few units, depending on
- * the dimension of the problem)
- * @param checker object to use to check for convergence
- * @param minimizing if true, function must be minimize otherwise it must be maximized
- * @param generator random vector generator
- * @param starts number of starts to perform (including the
- * first one), multi-start is disabled if value is less than or
- * equal to 1
- * @return the point/value pairs giving the optimal value for objective function
- * @exception ObjectiveException if the objective function throws one during
- * the search
- * @exception ConvergenceException if none of the starts did
- * converge (it is not thrown if at least one start did converge)
- */
- public PointValuePair optimize(final ObjectiveFunction f, final int maxEvaluations,
- final ConvergenceChecker checker, final boolean minimizing,
- final RandomVectorGenerator generator,
- final int starts)
- throws ObjectiveException, ConvergenceException {
-
- // set up optimizer
- buildSimplex(generator);
- setMultiStart(starts, generator);
-
- // compute optimum
- return optimize(f, maxEvaluations, checker, minimizing);
-
- }
-
- /** Build a simplex from two extreme vertices.
- * <p>The two vertices are considered to represent two opposite
- * vertices of a box parallel to the canonical axes of the
- * space. The simplex is the subset of vertices encountered while
- * going from vertexA to vertexB traveling along the box edges
- * only. This can be seen as a scaled regular simplex using the
- * projected separation between the given points as the scaling
- * factor along each coordinate axis.</p>
- * @param vertexA first vertex
- * @param vertexB last vertex
- */
- private void buildSimplex(final double[] vertexA, final double[] vertexB) {
-
- final int n = vertexA.length;
- simplex = new PointValuePair[n + 1];
-
- // set up the simplex traveling around the box
- for (int i = 0; i <= n; ++i) {
- final double[] vertex = new double[n];
- if (i > 0) {
- System.arraycopy(vertexB, 0, vertex, 0, i);
+ /** Set start configuration for simplex.
+ * <p>The real initial simplex will be set up by moving the reference
+ * simplex such that its first point is located at the start point of the
+ * optimization.</p>
+ * @param referenceSimplex reference simplex
+ * @exception IllegalArgumentException if the reference simplex does not
+ * contain at least one point, or if there is a dimension mismatch
+ * in the reference simplex or if one of its vertices is duplicated
+ */
+ public void setStartConfiguration(final double[][] referenceSimplex)
+ throws IllegalArgumentException {
+
+ // only the relative position of the n final vertices with respect
+ // to the first one are stored
+ final int n = referenceSimplex.length - 1;
+ if (n < 0) {
+ throw MathRuntimeException.createIllegalArgumentException(
+ "simplex must contain at least one point");
+ }
+ startConfiguration = new double[n][n];
+ final double[] ref0 = referenceSimplex[0];
+
+ // vertices loop
+ for (int i = 0; i < n + 1; ++i) {
+
+ final double[] refI = referenceSimplex[i];
+
+ // safety checks
+ if (refI.length != n) {
+ throw MathRuntimeException.createIllegalArgumentException(
+ "dimension mismatch {0} != {1}",
+ refI.length, n);
}
- if (i < n) {
- System.arraycopy(vertexA, i, vertex, i, n - i);
+ for (int j = 0; j < i; ++j) {
+ final double[] refJ = referenceSimplex[j];
+ boolean allEquals = true;
+ for (int k = 0; k < n; ++k) {
+ if (refI[k] != refJ[k]) {
+ allEquals = false;
+ break;
+ }
+ }
+ if (allEquals) {
+ throw MathRuntimeException.createIllegalArgumentException(
+ "equals vertices {0} and {1} in simplex configuration",
+ i, j);
+ }
}
- simplex[i] = new PointValuePair(vertex, Double.NaN);
- }
- }
+ // store vertex i position relative to vertex 0 position
+ if (i > 0) {
+ final double[] confI = startConfiguration[i - 1];
+ for (int k = 0; k < n; ++k) {
+ confI[k] = refI[k] - ref0[k];
+ }
+ }
- /** Build a simplex from all its points.
- * @param vertices array containing all vertices of the simplex
- */
- private void buildSimplex(final double[][] vertices) {
- final int n = vertices.length - 1;
- simplex = new PointValuePair[n + 1];
- for (int i = 0; i <= n; ++i) {
- simplex[i] = new PointValuePair(vertices[i], Double.NaN);
}
- }
-
- /** Build a simplex randomly.
- * @param generator random vector generator
- */
- private void buildSimplex(final RandomVectorGenerator generator) {
-
- // use first vector size to compute the number of points
- final double[] vertex = generator.nextVector();
- final int n = vertex.length;
- simplex = new PointValuePair[n + 1];
- simplex[0] = new PointValuePair(vertex, Double.NaN);
- // fill up the vertex
- for (int i = 1; i <= n; ++i) {
- simplex[i] = new PointValuePair(generator.nextVector(), Double.NaN);
- }
+ }
+ /** {@inheritDoc} */
+ public void setMaxEvaluations(int maxEvaluations) {
+ this.maxEvaluations = maxEvaluations;
}
- /** Set up single-start mode.
- */
- private void setSingleStart() {
- starts = 1;
- generator = null;
- optima = null;
+ /** {@inheritDoc} */
+ public int getMaxEvaluations() {
+ return maxEvaluations;
}
- /** Set up multi-start mode.
- * @param starts number of starts to perform (including the
- * first one), multi-start is disabled if value is less than or
- * equal to 1
- * @param generator random vector generator to use for restarts
- */
- private void setMultiStart(final int starts, final RandomVectorGenerator generator) {
- if (starts < 2) {
- this.starts = 1;
- this.generator = null;
- optima = null;
- } else {
- this.starts = starts;
- this.generator = generator;
- optima = null;
- }
+ /** {@inheritDoc} */
+ public void setConvergenceChecker(ConvergenceChecker checker) {
+ this.checker = checker;
}
- /** Get all the optima found during the last call to {@link
- * #optimize(ObjectiveFunction, int, ConvergenceChecker, double[], double[])
- * minimize}.
- * <p>The optimizer stores all the optima found during a set of
- * restarts when multi-start mode is enabled. The {@link
- * #optimize(ObjectiveFunction, int, ConvergenceChecker, double[], double[])
- * optimize} method returns the best point only. This method
- * returns all the points found at the end of each starts, including
- * the best one already returned by the {@link #optimize(ObjectiveFunction,
- * int, ConvergenceChecker, double[], double[]) optimize} method.
- * The array as one element for each start as specified in the constructor
- * (it has one element only if optimizer has been set up for single-start).</p>
- * <p>The array containing the optimum is ordered with the results
- * from the runs that did converge first, sorted from lowest to
- * highest objective value if minimizing (from highest to lowest if maximizing),
- * and null elements corresponding to the runs that did not converge. This means
- * all elements will be null if the {@link #optimize(ObjectiveFunction, int,
- * ConvergenceChecker, double[], double[]) optimize} method did throw a {@link
- * ConvergenceException ConvergenceException}). This also means that if the first
- * element is non null, it is the best point found accross all starts.</p>
- * @return array containing the optima, or null if {@link
- * #optimize(ObjectiveFunction, int, ConvergenceChecker, double[], double[])
- * optimize} has not been called
- */
- public PointValuePair[] getOptima() {
- return (PointValuePair[]) optima.clone();
+ /** {@inheritDoc} */
+ public ConvergenceChecker getConvergenceChecker() {
+ return checker;
}
- /** Optimizes an objective function.
- * @param f objective function
- * @param maxEvaluations maximal number of function calls for each
- * start (note that the number will be checked <em>after</em>
- * complete simplices have been evaluated, this means that in some
- * cases this number will be exceeded by a few units, depending on
- * the dimension of the problem)
- * @param checker object to use to check for convergence
- * @param minimizing if true, function must be minimize otherwise it must be maximized
- * @return the point/value pairs giving the optimal value for objective function
- * @exception ObjectiveException if the objective function throws one during
- * the search
- * @exception ConvergenceException if none of the starts did
- * converge (it is not thrown if at least one start did converge)
- */
- private PointValuePair optimize(final ObjectiveFunction f, final int maxEvaluations,
- final ConvergenceChecker checker, final boolean minimizing)
- throws ObjectiveException, ConvergenceException {
-
- this.f = f;
- this.minimizing = minimizing;
- optima = new PointValuePair[starts];
- totalEvaluations = 0;
+ /** {@inheritDoc} */
+ public PointValuePair optimize(final ObjectiveFunction f, final GoalType goalType,
+ final double[] startPoint)
+ throws ObjectiveException, OptimizationException, IllegalArgumentException {
- // multi-start loop
- for (int i = 0; i < starts; ++i) {
+ if (startConfiguration == null) {
+ // no initial configuration has been set up for simplex
+ // build a default one from a unit hypercube
+ final double[] unit = new double[startPoint.length];
+ Arrays.fill(unit, 1.0);
+ setStartConfiguration(unit);
+ }
- evaluations = 0;
- evaluateSimplex();
+ this.f = f;
+ final Comparator<PointValuePair> comparator = new Comparator<PointValuePair>() {
+ public int compare(final PointValuePair o1, final PointValuePair o2) {
+ final double v1 = o1.getValue();
+ final double v2 = o2.getValue();
+ return (goalType == GoalType.MINIMIZE) ?
+ Double.compare(v1, v2) : Double.compare(v2, v1);
+ }
+ };
- for (boolean loop = true; loop;) {
- if (checker.converged(simplex)) {
+ // initialize search
+ evaluations = 0;
+ buildSimplex(startPoint);
+ evaluateSimplex(comparator);
+
+ PointValuePair[] previous = new PointValuePair[simplex.length];
+ int iterations = 0;
+ while (evaluations <= maxEvaluations) {
+
+ if (++iterations > 1) {
+ boolean converged = true;
+ for (int i = 0; i < simplex.length; ++i) {
+ converged &= checker.converged(iterations, previous[i], simplex[i]);
+ }
+ if (converged) {
// we have found an optimum
- optima[i] = simplex[0];
- loop = false;
- } else if (evaluations >= maxEvaluations) {
- // this start did not converge, try a new one
- optima[i] = null;
- loop = false;
- } else {
- iterateSimplex();
+ return simplex[0];
}
}
- totalEvaluations += evaluations;
-
- if (i < (starts - 1)) {
- // restart
- buildSimplex(generator);
- }
+ // we still need to search
+ System.arraycopy(simplex, 0, previous, 0, simplex.length);
+ iterateSimplex(comparator);
}
- // sort the optima from best to poorest, followed by
- // null elements
- Arrays.sort(optima, PAIR_COMPARATOR);
-
- if (!minimizing) {
- // revert objective function sign to match user original definition
- for (int i = 0; i < optima.length; ++i) {
- final PointValuePair current = optima[i];
- if (current != null) {
- optima[i] = new PointValuePair(current.getPoint(), -current.getValue());
- }
- }
- }
-
- // return the found point given the best objective function value
- if (optima[0] == null) {
- throw new ConvergenceException(
- "none of the {0} start points lead to convergence",
- starts);
- }
- return optima[0];
+ throw new OptimizationException(
+ "maximal number of evaluations exceeded ({0})",
+ evaluations);
}
- /** Get the total number of evaluations of the objective function.
- * <p>
- * The total number of evaluations includes all evaluations for all
- * starts if in optimization was done in multi-start mode.
- * </p>
- * @return total number of evaluations of the objective function
- */
- public int getTotalEvaluations() {
- return totalEvaluations;
+ /** {@inheritDoc} */
+ public int getEvaluations() {
+ return evaluations;
}
/** Compute the next simplex of the algorithm.
+ * @param comparator comparator to use to sort simplex vertices from best to worst
* @exception ObjectiveException if the function cannot be evaluated at
* some point
+ * @exception OptimizationException if the algorithm failed to converge
+ * @exception IllegalArgumentException if the start point dimension is wrong
*/
- protected abstract void iterateSimplex() throws ObjectiveException;
+ protected abstract void iterateSimplex(final Comparator<PointValuePair> comparator)
+ throws ObjectiveException, OptimizationException, IllegalArgumentException;
/** Evaluate the objective function on one point.
* <p>A side effect of this method is to count the number of
@@ -604,39 +302,76 @@
* @param x point on which the objective function should be evaluated
* @return objective function value at the given point
* @exception ObjectiveException if no value can be computed for the parameters
+ * @exception IllegalArgumentException if the start point dimension is wrong
*/
- protected double evaluate(final double[] x) throws ObjectiveException {
+ protected double evaluate(final double[] x)
+ throws ObjectiveException, IllegalArgumentException {
evaluations++;
- return minimizing ? f.objective(x) : -f.objective(x);
+ return f.objective(x);
+ }
+
+ /** Build an initial simplex.
+ * @param startPoint the start point for optimization
+ * @exception IllegalArgumentException
+ */
+ private void buildSimplex(final double[] startPoint)
+ throws IllegalArgumentException {
+
+ final int n = startPoint.length;
+ if (n != startConfiguration.length) {
+ throw MathRuntimeException.createIllegalArgumentException(
+ "dimension mismatch {0} != {1}",
+ n, simplex.length);
+ }
+
+ // set first vertex
+ simplex = new PointValuePair[n + 1];
+ simplex[0] = new PointValuePair(startPoint, Double.NaN);
+
+ // set remaining vertices
+ for (int i = 0; i < n; ++i) {
+ final double[] confI = startConfiguration[i];
+ final double[] vertexI = new double[n];
+ for (int k = 0; k < n; ++k) {
+ vertexI[k] = startPoint[k] + confI[k];
+ }
+ simplex[i + 1] = new PointValuePair(vertexI, Double.NaN);
+ }
+
}
/** Evaluate all the non-evaluated points of the simplex.
+ * @param comparator comparator to use to sort simplex vertices from best to worst
* @exception ObjectiveException if no value can be computed for the parameters
*/
- protected void evaluateSimplex() throws ObjectiveException {
+ protected void evaluateSimplex(final Comparator<PointValuePair> comparator)
+ throws ObjectiveException {
// evaluate the objective function at all non-evaluated simplex points
for (int i = 0; i < simplex.length; ++i) {
- PointValuePair pair = simplex[i];
- if (Double.isNaN(pair.getValue())) {
- simplex[i] = new PointValuePair(pair.getPoint(), evaluate(pair.getPoint()));
+ final PointValuePair vertex = simplex[i];
+ final double[] point = vertex.getPoint();
+ if (Double.isNaN(vertex.getValue())) {
+ simplex[i] = new PointValuePair(point, evaluate(point));
}
}
- // sort the simplex from best to poorest
- Arrays.sort(simplex, PAIR_COMPARATOR);
+ // sort the simplex from best to worst
+ Arrays.sort(simplex, comparator);
}
/** Replace the worst point of the simplex by a new point.
* @param pointValuePair point to insert
+ * @param comparator comparator to use to sort simplex vertices from best to worst
*/
- protected void replaceWorstPoint(PointValuePair pointValuePair) {
+ protected void replaceWorstPoint(PointValuePair pointValuePair,
+ final Comparator<PointValuePair> comparator) {
int n = simplex.length - 1;
for (int i = 0; i < n; ++i) {
- if (simplex[i].getValue() > pointValuePair.getValue()) {
+ if (comparator.compare(simplex[i], pointValuePair) > 0) {
PointValuePair tmp = simplex[i];
- simplex[i] = pointValuePair;
+ simplex[i] = pointValuePair;
pointValuePair = tmp;
}
}
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/MultiDirectional.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/MultiDirectional.java?rev=749850&r1=749849&r2=749850&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/MultiDirectional.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/MultiDirectional.java Wed Mar 4 00:07:51 2009
@@ -17,7 +17,10 @@
package org.apache.commons.math.optimization.direct;
+import java.util.Comparator;
+
import org.apache.commons.math.optimization.ObjectiveException;
+import org.apache.commons.math.optimization.OptimizationException;
import org.apache.commons.math.optimization.PointValuePair;
/**
@@ -55,28 +58,27 @@
this.gamma = gamma;
}
- /** Compute the next simplex of the algorithm.
- * @exception ObjectiveException if the function cannot be evaluated at
- * some point
- */
- protected void iterateSimplex() throws ObjectiveException {
+ /** {@inheritDoc} */
+ protected void iterateSimplex(final Comparator<PointValuePair> comparator)
+ throws ObjectiveException, OptimizationException, IllegalArgumentException {
- while (true) {
+ final int max = getMaxEvaluations();
+ while (getEvaluations() < max) {
// save the original vertex
final PointValuePair[] original = simplex;
- final double originalValue = original[0].getValue();
+ final PointValuePair best = original[0];
// perform a reflection step
- final double reflectedValue = evaluateNewSimplex(original, 1.0);
- if (reflectedValue < originalValue) {
+ final PointValuePair reflected = evaluateNewSimplex(original, 1.0, comparator);
+ if (comparator.compare(reflected, best) < 0) {
// compute the expanded simplex
- final PointValuePair[] reflected = simplex;
- final double expandedValue = evaluateNewSimplex(original, khi);
- if (reflectedValue <= expandedValue) {
+ final PointValuePair[] reflectedSimplex = simplex;
+ final PointValuePair expanded = evaluateNewSimplex(original, khi, comparator);
+ if (comparator.compare(reflected, expanded) <= 0) {
// accept the reflected simplex
- simplex = reflected;
+ simplex = reflectedSimplex;
}
return;
@@ -84,25 +86,31 @@
}
// compute the contracted simplex
- final double contractedValue = evaluateNewSimplex(original, gamma);
- if (contractedValue < originalValue) {
+ final PointValuePair contracted = evaluateNewSimplex(original, gamma, comparator);
+ if (comparator.compare(contracted, best) < 0) {
// accept the contracted simplex
return;
}
}
+ throw new OptimizationException(
+ "maximal number of evaluations exceeded ({0})",
+ getEvaluations());
+
}
/** Compute and evaluate a new simplex.
* @param original original simplex (to be preserved)
* @param coeff linear coefficient
- * @return smallest value in the transformed simplex
+ * @param comparator comparator to use to sort simplex vertices from best to poorest
+ * @return best point in the transformed simplex
* @exception ObjectiveException if the function cannot be evaluated at
* some point
*/
- private double evaluateNewSimplex(final PointValuePair[] original,
- final double coeff)
+ private PointValuePair evaluateNewSimplex(final PointValuePair[] original,
+ final double coeff,
+ final Comparator<PointValuePair> comparator)
throws ObjectiveException {
final double[] xSmallest = original[0].getPoint();
@@ -121,8 +129,8 @@
}
// evaluate it
- evaluateSimplex();
- return simplex[0].getValue();
+ evaluateSimplex(comparator);
+ return simplex[0];
}
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/NelderMead.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/NelderMead.java?rev=749850&r1=749849&r2=749850&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/NelderMead.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/direct/NelderMead.java Wed Mar 4 00:07:51 2009
@@ -17,6 +17,8 @@
package org.apache.commons.math.optimization.direct;
+import java.util.Comparator;
+
import org.apache.commons.math.optimization.ObjectiveException;
import org.apache.commons.math.optimization.PointValuePair;
@@ -70,16 +72,17 @@
}
/** {@inheritDoc} */
- protected void iterateSimplex() throws ObjectiveException {
+ protected void iterateSimplex(final Comparator<PointValuePair> comparator)
+ throws ObjectiveException {
// the simplex has n+1 point if dimension is n
final int n = simplex.length - 1;
// interesting values
- final double smallest = simplex[0].getValue();
- final double secondLargest = simplex[n-1].getValue();
- final double largest = simplex[n].getValue();
- final double[] xLargest = simplex[n].getPoint();
+ final PointValuePair best = simplex[0];
+ final PointValuePair secondBest = simplex[n-1];
+ final PointValuePair worst = simplex[n];
+ final double[] xWorst = worst.getPoint();
// compute the centroid of the best vertices
// (dismissing the worst point at index n)
@@ -98,46 +101,47 @@
// compute the reflection point
final double[] xR = new double[n];
for (int j = 0; j < n; ++j) {
- xR[j] = centroid[j] + rho * (centroid[j] - xLargest[j]);
+ xR[j] = centroid[j] + rho * (centroid[j] - xWorst[j]);
}
- final double valueR = evaluate(xR);
+ final PointValuePair reflected = new PointValuePair(xR, evaluate(xR));
- if ((smallest <= valueR) && (valueR < secondLargest)) {
+ if ((comparator.compare(best, reflected) <= 0) &&
+ (comparator.compare(reflected, secondBest) < 0)) {
// accept the reflected point
- replaceWorstPoint(new PointValuePair(xR, valueR));
+ replaceWorstPoint(reflected, comparator);
- } else if (valueR < smallest) {
+ } else if (comparator.compare(reflected, best) < 0) {
// compute the expansion point
final double[] xE = new double[n];
for (int j = 0; j < n; ++j) {
xE[j] = centroid[j] + khi * (xR[j] - centroid[j]);
}
- final double valueE = evaluate(xE);
+ final PointValuePair expanded = new PointValuePair(xE, evaluate(xE));
- if (valueE < valueR) {
+ if (comparator.compare(expanded, reflected) < 0) {
// accept the expansion point
- replaceWorstPoint(new PointValuePair(xE, valueE));
+ replaceWorstPoint(expanded, comparator);
} else {
// accept the reflected point
- replaceWorstPoint(new PointValuePair(xR, valueR));
+ replaceWorstPoint(reflected, comparator);
}
} else {
- if (valueR < largest) {
+ if (comparator.compare(reflected, worst) < 0) {
// perform an outside contraction
final double[] xC = new double[n];
for (int j = 0; j < n; ++j) {
xC[j] = centroid[j] + gamma * (xR[j] - centroid[j]);
}
- final double valueC = evaluate(xC);
+ final PointValuePair outContracted = new PointValuePair(xC, evaluate(xC));
- if (valueC <= valueR) {
+ if (comparator.compare(outContracted, reflected) <= 0) {
// accept the contraction point
- replaceWorstPoint(new PointValuePair(xC, valueC));
+ replaceWorstPoint(outContracted, comparator);
return;
}
@@ -146,13 +150,13 @@
// perform an inside contraction
final double[] xC = new double[n];
for (int j = 0; j < n; ++j) {
- xC[j] = centroid[j] - gamma * (centroid[j] - xLargest[j]);
+ xC[j] = centroid[j] - gamma * (centroid[j] - xWorst[j]);
}
- final double valueC = evaluate(xC);
+ final PointValuePair inContracted = new PointValuePair(xC, evaluate(xC));
- if (valueC < largest) {
+ if (comparator.compare(inContracted, worst) < 0) {
// accept the contraction point
- replaceWorstPoint(new PointValuePair(xC, valueC));
+ replaceWorstPoint(inContracted, comparator);
return;
}
@@ -167,7 +171,7 @@
}
simplex[i] = new PointValuePair(x, Double.NaN);
}
- evaluateSimplex();
+ evaluateSimplex(comparator);
}
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/package.html
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/package.html?rev=749850&r1=749849&r2=749850&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/package.html (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/package.html Wed Mar 4 00:07:51 2009
@@ -43,11 +43,21 @@
The {@link org.apache.commons.math.optimization.LeastSquaresConverter
LeastSquaresConverter} class can be used to convert vectorial objective functions to
scalar objective functions when the goal is to minimize them. This class is mostly used
-when the vectorial objective function represents residuals, i.e. differences between a
-theoretical result computed from a variables set applied to a model and a reference.
-Residuals are intended to be minimized in order to get the variables set that best fit
-the model to the reference. The reference may be obtained for example from physical
-measurements whether the model is built from theoretical considerations.
+when the vectorial objective function represents theoretical results computed from a
+variables set applied to a model that should be fit against observations. Subtracting the
+observations from the theoretical results give residuals. Residuals are intended to be
+minimized in order to get the variables set that best fit the model to the observations.
+The observations may be obtained for example from physical measurements whether the model
+is built from theoretical considerations.
+</p>
+
+<p>
+The {@link org.apache.commons.math.optimization.Optimizer Optimizer} interface represents
+the optimization algorithm by itself. Several implementations of this interface are
+available for different kind of problems. There is also one special implementations, the
+{@link org.apache.commons.math.optimization.MultiStartOptimizer MultiStartOptimizer} which
+wraps a classical optimizer to use it several times in row with different starting points
+in order to avoid being trapped into a local extremum when looking for a global one.
</p>
</body>
</html>