commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From er...@apache.org
Subject svn commit: r1420684 [3/15] - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math3/exception/ main/java/org/apache/commons/math3/exception/util/ main/java/org/apache/commons/math3/fitting/ main/java/org/apache/commons/math3/optim/ main...
Date Wed, 12 Dec 2012 14:11:04 GMT
Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/LinearOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/LinearOptimizer.java?rev=1420684&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/LinearOptimizer.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/LinearOptimizer.java Wed Dec 12 14:10:38 2012
@@ -0,0 +1,129 @@
+/*
+ * 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.math3.optim.linear;
+
+import java.util.Collection;
+import java.util.Collections;
+import org.apache.commons.math3.exception.TooManyIterationsException;
+import org.apache.commons.math3.optim.OptimizationData;
+import org.apache.commons.math3.optim.PointValuePair;
+import org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer;
+
+/**
+ * Base class for implementing linear optimizers.
+ *
+ * @version $Id: AbstractLinearOptimizer.java 1416643 2012-12-03 19:37:14Z tn $
+ * @since 3.1
+ */
+public abstract class LinearOptimizer
+    extends MultivariateOptimizer {
+    /**
+     * Linear objective function.
+     */
+    private LinearObjectiveFunction function;
+    /**
+     * Linear constraints.
+     */
+    private Collection<LinearConstraint> linearConstraints;
+    /**
+     * Whether to restrict the variables to non-negative values.
+     */
+    private boolean nonNegative;
+
+    /**
+     * Simple constructor with default settings.
+     *
+     */
+    protected LinearOptimizer() {
+        super(null); // No convergence checker.
+    }
+
+    /**
+     * @return {@code true} if the variables are restricted to non-negative values.
+     */
+    protected boolean isRestrictedToNonNegative() {
+        return nonNegative;
+    }
+
+    /**
+     * @return the optimization type.
+     */
+    protected LinearObjectiveFunction getFunction() {
+        return function;
+    }
+
+    /**
+     * @return the optimization type.
+     */
+    protected Collection<LinearConstraint> getConstraints() {
+        return Collections.unmodifiableCollection(linearConstraints);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @param optData Optimization data. The following data will be looked for:
+     * <ul>
+     *  <li>{@link org.apache.commons.math3.optim.MaxIter}</li>
+     *  <li>{@link LinearObjectiveFunction}</li>
+     *  <li>{@link LinearConstraintSet}</li>
+     *  <li>{@link NonNegativeConstraint}</li>
+     * </ul>
+     * @return {@inheritDoc}
+     * @throws TooManyIterationsException if the maximal number of
+     * iterations is exceeded.
+     */
+    @Override
+    public PointValuePair optimize(OptimizationData... optData)
+        throws TooManyIterationsException {
+         // Retrieve settings.
+        parseOptimizationData(optData);
+        // Set up base class and perform computation.
+        return super.optimize(optData);
+    }
+
+    /**
+     * Scans the list of (required and optional) optimization data that
+     * characterize the problem.
+     *
+     * @param optData Optimization data.
+     * The following data will be looked for:
+     * <ul>
+     *  <li>{@link LinearObjectiveFunction}</li>
+     *  <li>{@link LinearConstraintSet}</li>
+     *  <li>{@link NonNegativeConstraint}</li>
+     * </ul>
+     */
+    private void parseOptimizationData(OptimizationData... optData) {
+        // The existing values (as set by the previous call) are reused if
+        // not provided in the argument list.
+        for (OptimizationData data : optData) {
+            if (data instanceof LinearObjectiveFunction) {
+                function = (LinearObjectiveFunction) data;
+                continue;
+            }
+            if (data instanceof LinearConstraintSet) {
+                linearConstraints = ((LinearConstraintSet) data).getConstraints();
+                continue;
+            }
+            if  (data instanceof NonNegativeConstraint) {
+                nonNegative = ((NonNegativeConstraint) data).isRestrictedToNonNegative();
+                continue;
+            }
+        }
+    }
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/LinearOptimizer.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/NoFeasibleSolutionException.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/NoFeasibleSolutionException.java?rev=1420684&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/NoFeasibleSolutionException.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/NoFeasibleSolutionException.java Wed Dec 12 14:10:38 2012
@@ -0,0 +1,38 @@
+/*
+ * 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.math3.optim.linear;
+
+import org.apache.commons.math3.exception.MathIllegalStateException;
+import org.apache.commons.math3.exception.util.LocalizedFormats;
+
+/**
+ * This class represents exceptions thrown by optimizers when no solution fulfills the constraints.
+ *
+ * @version $Id: NoFeasibleSolutionException.java 1416643 2012-12-03 19:37:14Z tn $
+ * @since 2.0
+ */
+public class NoFeasibleSolutionException extends MathIllegalStateException {
+    /** Serializable version identifier. */
+    private static final long serialVersionUID = -3044253632189082760L;
+
+    /**
+     * Simple constructor using a default message.
+     */
+    public NoFeasibleSolutionException() {
+        super(LocalizedFormats.NO_FEASIBLE_SOLUTION);
+    }
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/NoFeasibleSolutionException.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/NonNegativeConstraint.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/NonNegativeConstraint.java?rev=1420684&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/NonNegativeConstraint.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/NonNegativeConstraint.java Wed Dec 12 14:10:38 2012
@@ -0,0 +1,48 @@
+/*
+ * 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.math3.optim.linear;
+
+import org.apache.commons.math3.optim.OptimizationData;
+
+/**
+ * A constraint for a linear optimization problem indicating whether all
+ * variables must be restricted to non-negative values.
+ *
+ * @version $Id$
+ * @since 3.1
+ */
+public class NonNegativeConstraint implements OptimizationData {
+    /** Whether the variables are all positive. */
+    private final boolean isRestricted;
+
+    /**
+     * @param restricted If {@code true}, all the variables must be positive.
+     */
+    public NonNegativeConstraint(boolean restricted) {
+        isRestricted = restricted;
+    }
+
+    /**
+     * Indicates whether all the variables must be restricted to non-negative
+     * values.
+     *
+     * @return {@code true} if all the variables must be positive.
+     */
+    public boolean isRestrictedToNonNegative() {
+        return isRestricted;
+    }
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/NonNegativeConstraint.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/Relationship.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/Relationship.java?rev=1420684&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/Relationship.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/Relationship.java Wed Dec 12 14:10:38 2012
@@ -0,0 +1,65 @@
+/*
+ * 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.math3.optim.linear;
+
+/**
+ * Types of relationships between two cells in a Solver {@link LinearConstraint}.
+ *
+ * @version $Id: Relationship.java 1416643 2012-12-03 19:37:14Z tn $
+ * @since 2.0
+ */
+public enum Relationship {
+    /** Equality relationship. */
+    EQ("="),
+    /** Lesser than or equal relationship. */
+    LEQ("<="),
+    /** Greater than or equal relationship. */
+    GEQ(">=");
+
+    /** Display string for the relationship. */
+    private final String stringValue;
+
+    /**
+     * Simple constructor.
+     *
+     * @param stringValue Display string for the relationship.
+     */
+    private Relationship(String stringValue) {
+        this.stringValue = stringValue;
+    }
+
+    @Override
+    public String toString() {
+        return stringValue;
+    }
+
+    /**
+     * Gets the relationship obtained when multiplying all coefficients by -1.
+     *
+     * @return the opposite relationship.
+     */
+    public Relationship oppositeRelationship() {
+        switch (this) {
+        case LEQ :
+            return GEQ;
+        case GEQ :
+            return LEQ;
+        default :
+            return EQ;
+        }
+    }
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/Relationship.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java?rev=1420684&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java Wed Dec 12 14:10:38 2012
@@ -0,0 +1,245 @@
+/*
+ * 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.math3.optim.linear;
+
+import java.util.ArrayList;
+import java.util.List;
+import org.apache.commons.math3.exception.TooManyIterationsException;
+import org.apache.commons.math3.optim.PointValuePair;
+import org.apache.commons.math3.util.Precision;
+
+/**
+ * Solves a linear problem using the "Two-Phase Simplex" method.
+ *
+ * @version $Id: SimplexSolver.java 1416643 2012-12-03 19:37:14Z tn $
+ * @since 2.0
+ */
+public class SimplexSolver extends LinearOptimizer {
+    /** Default amount of error to accept for algorithm convergence. */
+    private static final double DEFAULT_EPSILON = 1.0e-6;
+
+    /** Default amount of error to accept in floating point comparisons (as ulps). */
+    private static final int DEFAULT_ULPS = 10;
+
+    /** Amount of error to accept for algorithm convergence. */
+    private final double epsilon;
+
+    /** Amount of error to accept in floating point comparisons (as ulps). */
+    private final int maxUlps;
+
+    /**
+     * Builds a simplex solver with default settings.
+     */
+    public SimplexSolver() {
+        this(DEFAULT_EPSILON, DEFAULT_ULPS);
+    }
+
+    /**
+     * Builds a simplex solver with a specified accepted amount of error.
+     *
+     * @param epsilon Amount of error to accept for algorithm convergence.
+     * @param maxUlps Amount of error to accept in floating point comparisons.
+     */
+    public SimplexSolver(final double epsilon,
+                         final int maxUlps) {
+        this.epsilon = epsilon;
+        this.maxUlps = maxUlps;
+    }
+
+    /**
+     * Returns the column with the most negative coefficient in the objective function row.
+     *
+     * @param tableau Simple tableau for the problem.
+     * @return the column with the most negative coefficient.
+     */
+    private Integer getPivotColumn(SimplexTableau tableau) {
+        double minValue = 0;
+        Integer minPos = null;
+        for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++) {
+            final double entry = tableau.getEntry(0, i);
+            // check if the entry is strictly smaller than the current minimum
+            // do not use a ulp/epsilon check
+            if (entry < minValue) {
+                minValue = entry;
+                minPos = i;
+            }
+        }
+        return minPos;
+    }
+
+    /**
+     * Returns the row with the minimum ratio as given by the minimum ratio test (MRT).
+     *
+     * @param tableau Simple tableau for the problem.
+     * @param col Column to test the ratio of (see {@link #getPivotColumn(SimplexTableau)}).
+     * @return the row with the minimum ratio.
+     */
+    private Integer getPivotRow(SimplexTableau tableau, final int col) {
+        // create a list of all the rows that tie for the lowest score in the minimum ratio test
+        List<Integer> minRatioPositions = new ArrayList<Integer>();
+        double minRatio = Double.MAX_VALUE;
+        for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getHeight(); i++) {
+            final double rhs = tableau.getEntry(i, tableau.getWidth() - 1);
+            final double entry = tableau.getEntry(i, col);
+
+            if (Precision.compareTo(entry, 0d, maxUlps) > 0) {
+                final double ratio = rhs / entry;
+                // check if the entry is strictly equal to the current min ratio
+                // do not use a ulp/epsilon check
+                final int cmp = Double.compare(ratio, minRatio);
+                if (cmp == 0) {
+                    minRatioPositions.add(i);
+                } else if (cmp < 0) {
+                    minRatio = ratio;
+                    minRatioPositions = new ArrayList<Integer>();
+                    minRatioPositions.add(i);
+                }
+            }
+        }
+
+        if (minRatioPositions.size() == 0) {
+            return null;
+        } else if (minRatioPositions.size() > 1) {
+            // there's a degeneracy as indicated by a tie in the minimum ratio test
+
+            // 1. check if there's an artificial variable that can be forced out of the basis
+            if (tableau.getNumArtificialVariables() > 0) {
+                for (Integer row : minRatioPositions) {
+                    for (int i = 0; i < tableau.getNumArtificialVariables(); i++) {
+                        int column = i + tableau.getArtificialVariableOffset();
+                        final double entry = tableau.getEntry(row, column);
+                        if (Precision.equals(entry, 1d, maxUlps) && row.equals(tableau.getBasicRow(column))) {
+                            return row;
+                        }
+                    }
+                }
+            }
+
+            // 2. apply Bland's rule to prevent cycling:
+            //    take the row for which the corresponding basic variable has the smallest index
+            //
+            // see http://www.stanford.edu/class/msande310/blandrule.pdf
+            // see http://en.wikipedia.org/wiki/Bland%27s_rule (not equivalent to the above paper)
+            //
+            // Additional heuristic: if we did not get a solution after half of maxIterations
+            //                       revert to the simple case of just returning the top-most row
+            // This heuristic is based on empirical data gathered while investigating MATH-828.
+            if (getEvaluations() < getMaxEvaluations() / 2) {
+                Integer minRow = null;
+                int minIndex = tableau.getWidth();
+                final int varStart = tableau.getNumObjectiveFunctions();
+                final int varEnd = tableau.getWidth() - 1;
+                for (Integer row : minRatioPositions) {
+                    for (int i = varStart; i < varEnd && !row.equals(minRow); i++) {
+                        final Integer basicRow = tableau.getBasicRow(i);
+                        if (basicRow != null && basicRow.equals(row)) {
+                            if (i < minIndex) {
+                                minIndex = i;
+                                minRow = row;
+                            }
+                        }
+                    }
+                }
+                return minRow;
+            }
+        }
+        return minRatioPositions.get(0);
+    }
+
+    /**
+     * Runs one iteration of the Simplex method on the given model.
+     *
+     * @param tableau Simple tableau for the problem.
+     * @throws TooManyIterationsException if the allowed number of iterations has been exhausted.
+     * @throws UnboundedSolutionException if the model is found not to have a bounded solution.
+     */
+    protected void doIteration(final SimplexTableau tableau)
+        throws TooManyIterationsException,
+               UnboundedSolutionException {
+
+        incrementIterationCount();
+
+        Integer pivotCol = getPivotColumn(tableau);
+        Integer pivotRow = getPivotRow(tableau, pivotCol);
+        if (pivotRow == null) {
+            throw new UnboundedSolutionException();
+        }
+
+        // set the pivot element to 1
+        double pivotVal = tableau.getEntry(pivotRow, pivotCol);
+        tableau.divideRow(pivotRow, pivotVal);
+
+        // set the rest of the pivot column to 0
+        for (int i = 0; i < tableau.getHeight(); i++) {
+            if (i != pivotRow) {
+                final double multiplier = tableau.getEntry(i, pivotCol);
+                tableau.subtractRow(i, pivotRow, multiplier);
+            }
+        }
+    }
+
+    /**
+     * Solves Phase 1 of the Simplex method.
+     *
+     * @param tableau Simple tableau for the problem.
+     * @throws TooManyIterationsException if the allowed number of iterations has been exhausted.
+     * @throws UnboundedSolutionException if the model is found not to have a bounded solution.
+     * @throws NoFeasibleSolutionException if there is no feasible solution?
+     */
+    protected void solvePhase1(final SimplexTableau tableau)
+        throws TooManyIterationsException,
+               UnboundedSolutionException,
+               NoFeasibleSolutionException {
+
+        // make sure we're in Phase 1
+        if (tableau.getNumArtificialVariables() == 0) {
+            return;
+        }
+
+        while (!tableau.isOptimal()) {
+            doIteration(tableau);
+        }
+
+        // if W is not zero then we have no feasible solution
+        if (!Precision.equals(tableau.getEntry(0, tableau.getRhsOffset()), 0d, epsilon)) {
+            throw new NoFeasibleSolutionException();
+        }
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public PointValuePair doOptimize()
+        throws TooManyIterationsException,
+               UnboundedSolutionException,
+               NoFeasibleSolutionException {
+        final SimplexTableau tableau =
+            new SimplexTableau(getFunction(),
+                               getConstraints(),
+                               getGoalType(),
+                               isRestrictedToNonNegative(),
+                               epsilon,
+                               maxUlps);
+
+        solvePhase1(tableau);
+        tableau.dropPhase1Objective();
+
+        while (!tableau.isOptimal()) {
+            doIteration(tableau);
+        }
+        return tableau.getSolution();
+    }
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java?rev=1420684&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java Wed Dec 12 14:10:38 2012
@@ -0,0 +1,637 @@
+/*
+ * 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.math3.optim.linear;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.TreeSet;
+
+import org.apache.commons.math3.linear.Array2DRowRealMatrix;
+import org.apache.commons.math3.linear.MatrixUtils;
+import org.apache.commons.math3.linear.RealMatrix;
+import org.apache.commons.math3.linear.RealVector;
+import org.apache.commons.math3.optim.GoalType;
+import org.apache.commons.math3.optim.PointValuePair;
+import org.apache.commons.math3.util.FastMath;
+import org.apache.commons.math3.util.Precision;
+
+/**
+ * A tableau for use in the Simplex method.
+ *
+ * <p>
+ * Example:
+ * <pre>
+ *   W |  Z |  x1 |  x2 |  x- | s1 |  s2 |  a1 |  RHS
+ * ---------------------------------------------------
+ *  -1    0    0     0     0     0     0     1     0   &lt;= phase 1 objective
+ *   0    1   -15   -10    0     0     0     0     0   &lt;= phase 2 objective
+ *   0    0    1     0     0     1     0     0     2   &lt;= constraint 1
+ *   0    0    0     1     0     0     1     0     3   &lt;= constraint 2
+ *   0    0    1     1     0     0     0     1     4   &lt;= constraint 3
+ * </pre>
+ * W: Phase 1 objective function</br>
+ * Z: Phase 2 objective function</br>
+ * x1 &amp; x2: Decision variables</br>
+ * x-: Extra decision variable to allow for negative values</br>
+ * s1 &amp; s2: Slack/Surplus variables</br>
+ * a1: Artificial variable</br>
+ * RHS: Right hand side</br>
+ * </p>
+ * @version $Id: SimplexTableau.java 1416643 2012-12-03 19:37:14Z tn $
+ * @since 2.0
+ */
+class SimplexTableau implements Serializable {
+
+    /** Column label for negative vars. */
+    private static final String NEGATIVE_VAR_COLUMN_LABEL = "x-";
+
+    /** Default amount of error to accept in floating point comparisons (as ulps). */
+    private static final int DEFAULT_ULPS = 10;
+
+    /** The cut-off threshold to zero-out entries. */
+    private static final double CUTOFF_THRESHOLD = 1e-12;
+
+    /** Serializable version identifier. */
+    private static final long serialVersionUID = -1369660067587938365L;
+
+    /** Linear objective function. */
+    private final LinearObjectiveFunction f;
+
+    /** Linear constraints. */
+    private final List<LinearConstraint> constraints;
+
+    /** Whether to restrict the variables to non-negative values. */
+    private final boolean restrictToNonNegative;
+
+    /** The variables each column represents */
+    private final List<String> columnLabels = new ArrayList<String>();
+
+    /** Simple tableau. */
+    private transient RealMatrix tableau;
+
+    /** Number of decision variables. */
+    private final int numDecisionVariables;
+
+    /** Number of slack variables. */
+    private final int numSlackVariables;
+
+    /** Number of artificial variables. */
+    private int numArtificialVariables;
+
+    /** Amount of error to accept when checking for optimality. */
+    private final double epsilon;
+
+    /** Amount of error to accept in floating point comparisons. */
+    private final int maxUlps;
+
+    /**
+     * Builds a tableau for a linear problem.
+     *
+     * @param f Linear objective function.
+     * @param constraints Linear constraints.
+     * @param goalType Optimization goal: either {@link GoalType#MAXIMIZE}
+     * or {@link GoalType#MINIMIZE}.
+     * @param restrictToNonNegative Whether to restrict the variables to non-negative values.
+     * @param epsilon Amount of error to accept when checking for optimality.
+     */
+    SimplexTableau(final LinearObjectiveFunction f,
+                   final Collection<LinearConstraint> constraints,
+                   final GoalType goalType,
+                   final boolean restrictToNonNegative,
+                   final double epsilon) {
+        this(f, constraints, goalType, restrictToNonNegative, epsilon, DEFAULT_ULPS);
+    }
+
+    /**
+     * Build a tableau for a linear problem.
+     * @param f linear objective function
+     * @param constraints linear constraints
+     * @param goalType type of optimization goal: either {@link GoalType#MAXIMIZE} or {@link GoalType#MINIMIZE}
+     * @param restrictToNonNegative whether to restrict the variables to non-negative values
+     * @param epsilon amount of error to accept when checking for optimality
+     * @param maxUlps amount of error to accept in floating point comparisons
+     */
+    SimplexTableau(final LinearObjectiveFunction f,
+                   final Collection<LinearConstraint> constraints,
+                   final GoalType goalType,
+                   final boolean restrictToNonNegative,
+                   final double epsilon,
+                   final int maxUlps) {
+        this.f                      = f;
+        this.constraints            = normalizeConstraints(constraints);
+        this.restrictToNonNegative  = restrictToNonNegative;
+        this.epsilon                = epsilon;
+        this.maxUlps                = maxUlps;
+        this.numDecisionVariables   = f.getCoefficients().getDimension() +
+                                      (restrictToNonNegative ? 0 : 1);
+        this.numSlackVariables      = getConstraintTypeCounts(Relationship.LEQ) +
+                                      getConstraintTypeCounts(Relationship.GEQ);
+        this.numArtificialVariables = getConstraintTypeCounts(Relationship.EQ) +
+                                      getConstraintTypeCounts(Relationship.GEQ);
+        this.tableau = createTableau(goalType == GoalType.MAXIMIZE);
+        initializeColumnLabels();
+    }
+
+    /**
+     * Initialize the labels for the columns.
+     */
+    protected void initializeColumnLabels() {
+      if (getNumObjectiveFunctions() == 2) {
+        columnLabels.add("W");
+      }
+      columnLabels.add("Z");
+      for (int i = 0; i < getOriginalNumDecisionVariables(); i++) {
+        columnLabels.add("x" + i);
+      }
+      if (!restrictToNonNegative) {
+        columnLabels.add(NEGATIVE_VAR_COLUMN_LABEL);
+      }
+      for (int i = 0; i < getNumSlackVariables(); i++) {
+        columnLabels.add("s" + i);
+      }
+      for (int i = 0; i < getNumArtificialVariables(); i++) {
+        columnLabels.add("a" + i);
+      }
+      columnLabels.add("RHS");
+    }
+
+    /**
+     * Create the tableau by itself.
+     * @param maximize if true, goal is to maximize the objective function
+     * @return created tableau
+     */
+    protected RealMatrix createTableau(final boolean maximize) {
+
+        // create a matrix of the correct size
+        int width = numDecisionVariables + numSlackVariables +
+        numArtificialVariables + getNumObjectiveFunctions() + 1; // + 1 is for RHS
+        int height = constraints.size() + getNumObjectiveFunctions();
+        Array2DRowRealMatrix matrix = new Array2DRowRealMatrix(height, width);
+
+        // initialize the objective function rows
+        if (getNumObjectiveFunctions() == 2) {
+            matrix.setEntry(0, 0, -1);
+        }
+        int zIndex = (getNumObjectiveFunctions() == 1) ? 0 : 1;
+        matrix.setEntry(zIndex, zIndex, maximize ? 1 : -1);
+        RealVector objectiveCoefficients =
+            maximize ? f.getCoefficients().mapMultiply(-1) : f.getCoefficients();
+        copyArray(objectiveCoefficients.toArray(), matrix.getDataRef()[zIndex]);
+        matrix.setEntry(zIndex, width - 1,
+            maximize ? f.getConstantTerm() : -1 * f.getConstantTerm());
+
+        if (!restrictToNonNegative) {
+            matrix.setEntry(zIndex, getSlackVariableOffset() - 1,
+                getInvertedCoefficientSum(objectiveCoefficients));
+        }
+
+        // initialize the constraint rows
+        int slackVar = 0;
+        int artificialVar = 0;
+        for (int i = 0; i < constraints.size(); i++) {
+            LinearConstraint constraint = constraints.get(i);
+            int row = getNumObjectiveFunctions() + i;
+
+            // decision variable coefficients
+            copyArray(constraint.getCoefficients().toArray(), matrix.getDataRef()[row]);
+
+            // x-
+            if (!restrictToNonNegative) {
+                matrix.setEntry(row, getSlackVariableOffset() - 1,
+                    getInvertedCoefficientSum(constraint.getCoefficients()));
+            }
+
+            // RHS
+            matrix.setEntry(row, width - 1, constraint.getValue());
+
+            // slack variables
+            if (constraint.getRelationship() == Relationship.LEQ) {
+                matrix.setEntry(row, getSlackVariableOffset() + slackVar++, 1);  // slack
+            } else if (constraint.getRelationship() == Relationship.GEQ) {
+                matrix.setEntry(row, getSlackVariableOffset() + slackVar++, -1); // excess
+            }
+
+            // artificial variables
+            if ((constraint.getRelationship() == Relationship.EQ) ||
+                    (constraint.getRelationship() == Relationship.GEQ)) {
+                matrix.setEntry(0, getArtificialVariableOffset() + artificialVar, 1);
+                matrix.setEntry(row, getArtificialVariableOffset() + artificialVar++, 1);
+                matrix.setRowVector(0, matrix.getRowVector(0).subtract(matrix.getRowVector(row)));
+            }
+        }
+
+        return matrix;
+    }
+
+    /**
+     * Get new versions of the constraints which have positive right hand sides.
+     * @param originalConstraints original (not normalized) constraints
+     * @return new versions of the constraints
+     */
+    public List<LinearConstraint> normalizeConstraints(Collection<LinearConstraint> originalConstraints) {
+        List<LinearConstraint> normalized = new ArrayList<LinearConstraint>();
+        for (LinearConstraint constraint : originalConstraints) {
+            normalized.add(normalize(constraint));
+        }
+        return normalized;
+    }
+
+    /**
+     * Get a new equation equivalent to this one with a positive right hand side.
+     * @param constraint reference constraint
+     * @return new equation
+     */
+    private LinearConstraint normalize(final LinearConstraint constraint) {
+        if (constraint.getValue() < 0) {
+            return new LinearConstraint(constraint.getCoefficients().mapMultiply(-1),
+                                        constraint.getRelationship().oppositeRelationship(),
+                                        -1 * constraint.getValue());
+        }
+        return new LinearConstraint(constraint.getCoefficients(),
+                                    constraint.getRelationship(), constraint.getValue());
+    }
+
+    /**
+     * Get the number of objective functions in this tableau.
+     * @return 2 for Phase 1.  1 for Phase 2.
+     */
+    protected final int getNumObjectiveFunctions() {
+        return this.numArtificialVariables > 0 ? 2 : 1;
+    }
+
+    /**
+     * Get a count of constraints corresponding to a specified relationship.
+     * @param relationship relationship to count
+     * @return number of constraint with the specified relationship
+     */
+    private int getConstraintTypeCounts(final Relationship relationship) {
+        int count = 0;
+        for (final LinearConstraint constraint : constraints) {
+            if (constraint.getRelationship() == relationship) {
+                ++count;
+            }
+        }
+        return count;
+    }
+
+    /**
+     * Get the -1 times the sum of all coefficients in the given array.
+     * @param coefficients coefficients to sum
+     * @return the -1 times the sum of all coefficients in the given array.
+     */
+    protected static double getInvertedCoefficientSum(final RealVector coefficients) {
+        double sum = 0;
+        for (double coefficient : coefficients.toArray()) {
+            sum -= coefficient;
+        }
+        return sum;
+    }
+
+    /**
+     * Checks whether the given column is basic.
+     * @param col index of the column to check
+     * @return the row that the variable is basic in.  null if the column is not basic
+     */
+    protected Integer getBasicRow(final int col) {
+        Integer row = null;
+        for (int i = 0; i < getHeight(); i++) {
+            final double entry = getEntry(i, col);
+            if (Precision.equals(entry, 1d, maxUlps) && (row == null)) {
+                row = i;
+            } else if (!Precision.equals(entry, 0d, maxUlps)) {
+                return null;
+            }
+        }
+        return row;
+    }
+
+    /**
+     * Removes the phase 1 objective function, positive cost non-artificial variables,
+     * and the non-basic artificial variables from this tableau.
+     */
+    protected void dropPhase1Objective() {
+        if (getNumObjectiveFunctions() == 1) {
+            return;
+        }
+
+        Set<Integer> columnsToDrop = new TreeSet<Integer>();
+        columnsToDrop.add(0);
+
+        // positive cost non-artificial variables
+        for (int i = getNumObjectiveFunctions(); i < getArtificialVariableOffset(); i++) {
+            final double entry = tableau.getEntry(0, i);
+            if (Precision.compareTo(entry, 0d, epsilon) > 0) {
+                columnsToDrop.add(i);
+            }
+        }
+
+        // non-basic artificial variables
+        for (int i = 0; i < getNumArtificialVariables(); i++) {
+            int col = i + getArtificialVariableOffset();
+            if (getBasicRow(col) == null) {
+                columnsToDrop.add(col);
+            }
+        }
+
+        double[][] matrix = new double[getHeight() - 1][getWidth() - columnsToDrop.size()];
+        for (int i = 1; i < getHeight(); i++) {
+            int col = 0;
+            for (int j = 0; j < getWidth(); j++) {
+                if (!columnsToDrop.contains(j)) {
+                    matrix[i - 1][col++] = tableau.getEntry(i, j);
+                }
+            }
+        }
+
+        // remove the columns in reverse order so the indices are correct
+        Integer[] drop = columnsToDrop.toArray(new Integer[columnsToDrop.size()]);
+        for (int i = drop.length - 1; i >= 0; i--) {
+            columnLabels.remove((int) drop[i]);
+        }
+
+        this.tableau = new Array2DRowRealMatrix(matrix);
+        this.numArtificialVariables = 0;
+    }
+
+    /**
+     * @param src the source array
+     * @param dest the destination array
+     */
+    private void copyArray(final double[] src, final double[] dest) {
+        System.arraycopy(src, 0, dest, getNumObjectiveFunctions(), src.length);
+    }
+
+    /**
+     * Returns whether the problem is at an optimal state.
+     * @return whether the model has been solved
+     */
+    boolean isOptimal() {
+        for (int i = getNumObjectiveFunctions(); i < getWidth() - 1; i++) {
+            final double entry = tableau.getEntry(0, i);
+            if (Precision.compareTo(entry, 0d, epsilon) < 0) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * Get the current solution.
+     * @return current solution
+     */
+    protected PointValuePair getSolution() {
+        int negativeVarColumn = columnLabels.indexOf(NEGATIVE_VAR_COLUMN_LABEL);
+        Integer negativeVarBasicRow = negativeVarColumn > 0 ? getBasicRow(negativeVarColumn) : null;
+        double mostNegative = negativeVarBasicRow == null ? 0 : getEntry(negativeVarBasicRow, getRhsOffset());
+
+        Set<Integer> basicRows = new HashSet<Integer>();
+        double[] coefficients = new double[getOriginalNumDecisionVariables()];
+        for (int i = 0; i < coefficients.length; i++) {
+            int colIndex = columnLabels.indexOf("x" + i);
+            if (colIndex < 0) {
+                coefficients[i] = 0;
+                continue;
+            }
+            Integer basicRow = getBasicRow(colIndex);
+            if (basicRow != null && basicRow == 0) {
+                // if the basic row is found to be the objective function row
+                // set the coefficient to 0 -> this case handles unconstrained
+                // variables that are still part of the objective function
+                coefficients[i] = 0;
+            } else if (basicRows.contains(basicRow)) {
+                // if multiple variables can take a given value
+                // then we choose the first and set the rest equal to 0
+                coefficients[i] = 0 - (restrictToNonNegative ? 0 : mostNegative);
+            } else {
+                basicRows.add(basicRow);
+                coefficients[i] =
+                    (basicRow == null ? 0 : getEntry(basicRow, getRhsOffset())) -
+                    (restrictToNonNegative ? 0 : mostNegative);
+            }
+        }
+        return new PointValuePair(coefficients, f.value(coefficients));
+    }
+
+    /**
+     * Subtracts a multiple of one row from another.
+     * <p>
+     * After application of this operation, the following will hold:
+     * <pre>minuendRow = minuendRow - multiple * subtrahendRow</pre>
+     *
+     * @param dividendRow index of the row
+     * @param divisor value of the divisor
+     */
+    protected void divideRow(final int dividendRow, final double divisor) {
+        for (int j = 0; j < getWidth(); j++) {
+            tableau.setEntry(dividendRow, j, tableau.getEntry(dividendRow, j) / divisor);
+        }
+    }
+
+    /**
+     * Subtracts a multiple of one row from another.
+     * <p>
+     * After application of this operation, the following will hold:
+     * <pre>minuendRow = minuendRow - multiple * subtrahendRow</pre>
+     *
+     * @param minuendRow row index
+     * @param subtrahendRow row index
+     * @param multiple multiplication factor
+     */
+    protected void subtractRow(final int minuendRow, final int subtrahendRow,
+                               final double multiple) {
+        for (int i = 0; i < getWidth(); i++) {
+            double result = tableau.getEntry(minuendRow, i) - tableau.getEntry(subtrahendRow, i) * multiple;
+            // cut-off values smaller than the CUTOFF_THRESHOLD, otherwise may lead to numerical instabilities
+            if (FastMath.abs(result) < CUTOFF_THRESHOLD) {
+                result = 0.0;
+            }
+            tableau.setEntry(minuendRow, i, result);
+        }
+    }
+
+    /**
+     * Get the width of the tableau.
+     * @return width of the tableau
+     */
+    protected final int getWidth() {
+        return tableau.getColumnDimension();
+    }
+
+    /**
+     * Get the height of the tableau.
+     * @return height of the tableau
+     */
+    protected final int getHeight() {
+        return tableau.getRowDimension();
+    }
+
+    /**
+     * Get an entry of the tableau.
+     * @param row row index
+     * @param column column index
+     * @return entry at (row, column)
+     */
+    protected final double getEntry(final int row, final int column) {
+        return tableau.getEntry(row, column);
+    }
+
+    /**
+     * Set an entry of the tableau.
+     * @param row row index
+     * @param column column index
+     * @param value for the entry
+     */
+    protected final void setEntry(final int row, final int column,
+                                  final double value) {
+        tableau.setEntry(row, column, value);
+    }
+
+    /**
+     * Get the offset of the first slack variable.
+     * @return offset of the first slack variable
+     */
+    protected final int getSlackVariableOffset() {
+        return getNumObjectiveFunctions() + numDecisionVariables;
+    }
+
+    /**
+     * Get the offset of the first artificial variable.
+     * @return offset of the first artificial variable
+     */
+    protected final int getArtificialVariableOffset() {
+        return getNumObjectiveFunctions() + numDecisionVariables + numSlackVariables;
+    }
+
+    /**
+     * Get the offset of the right hand side.
+     * @return offset of the right hand side
+     */
+    protected final int getRhsOffset() {
+        return getWidth() - 1;
+    }
+
+    /**
+     * Get the number of decision variables.
+     * <p>
+     * If variables are not restricted to positive values, this will include 1 extra decision variable to represent
+     * the absolute value of the most negative variable.
+     *
+     * @return number of decision variables
+     * @see #getOriginalNumDecisionVariables()
+     */
+    protected final int getNumDecisionVariables() {
+        return numDecisionVariables;
+    }
+
+    /**
+     * Get the original number of decision variables.
+     * @return original number of decision variables
+     * @see #getNumDecisionVariables()
+     */
+    protected final int getOriginalNumDecisionVariables() {
+        return f.getCoefficients().getDimension();
+    }
+
+    /**
+     * Get the number of slack variables.
+     * @return number of slack variables
+     */
+    protected final int getNumSlackVariables() {
+        return numSlackVariables;
+    }
+
+    /**
+     * Get the number of artificial variables.
+     * @return number of artificial variables
+     */
+    protected final int getNumArtificialVariables() {
+        return numArtificialVariables;
+    }
+
+    /**
+     * Get the tableau data.
+     * @return tableau data
+     */
+    protected final double[][] getData() {
+        return tableau.getData();
+    }
+
+    @Override
+    public boolean equals(Object other) {
+
+      if (this == other) {
+        return true;
+      }
+
+      if (other instanceof SimplexTableau) {
+          SimplexTableau rhs = (SimplexTableau) other;
+          return (restrictToNonNegative  == rhs.restrictToNonNegative) &&
+                 (numDecisionVariables   == rhs.numDecisionVariables) &&
+                 (numSlackVariables      == rhs.numSlackVariables) &&
+                 (numArtificialVariables == rhs.numArtificialVariables) &&
+                 (epsilon                == rhs.epsilon) &&
+                 (maxUlps                == rhs.maxUlps) &&
+                 f.equals(rhs.f) &&
+                 constraints.equals(rhs.constraints) &&
+                 tableau.equals(rhs.tableau);
+      }
+      return false;
+    }
+
+    @Override
+    public int hashCode() {
+        return Boolean.valueOf(restrictToNonNegative).hashCode() ^
+               numDecisionVariables ^
+               numSlackVariables ^
+               numArtificialVariables ^
+               Double.valueOf(epsilon).hashCode() ^
+               maxUlps ^
+               f.hashCode() ^
+               constraints.hashCode() ^
+               tableau.hashCode();
+    }
+
+    /**
+     * Serialize the instance.
+     * @param oos stream where object should be written
+     * @throws IOException if object cannot be written to stream
+     */
+    private void writeObject(ObjectOutputStream oos)
+        throws IOException {
+        oos.defaultWriteObject();
+        MatrixUtils.serializeRealMatrix(tableau, oos);
+    }
+
+    /**
+     * Deserialize the instance.
+     * @param ois stream from which the object should be read
+     * @throws ClassNotFoundException if a class in the stream cannot be found
+     * @throws IOException if object cannot be read from the stream
+     */
+    private void readObject(ObjectInputStream ois)
+      throws ClassNotFoundException, IOException {
+        ois.defaultReadObject();
+        MatrixUtils.deserializeRealMatrix(this, "tableau", ois);
+    }
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/UnboundedSolutionException.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/UnboundedSolutionException.java?rev=1420684&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/UnboundedSolutionException.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/UnboundedSolutionException.java Wed Dec 12 14:10:38 2012
@@ -0,0 +1,38 @@
+/*
+ * 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.math3.optim.linear;
+
+import org.apache.commons.math3.exception.MathIllegalStateException;
+import org.apache.commons.math3.exception.util.LocalizedFormats;
+
+/**
+ * This class represents exceptions thrown by optimizers when a solution escapes to infinity.
+ *
+ * @version $Id: UnboundedSolutionException.java 1416643 2012-12-03 19:37:14Z tn $
+ * @since 2.0
+ */
+public class UnboundedSolutionException extends MathIllegalStateException {
+    /** Serializable version identifier. */
+    private static final long serialVersionUID = 940539497277290619L;
+
+    /**
+     * Simple constructor using a default message.
+     */
+    public UnboundedSolutionException() {
+        super(LocalizedFormats.UNBOUNDED_SOLUTION);
+    }
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/UnboundedSolutionException.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/package-info.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/package-info.java?rev=1420684&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/package-info.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/package-info.java Wed Dec 12 14:10:38 2012
@@ -0,0 +1,21 @@
+/*
+ * 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.math3.optim.linear;
+
+/**
+ * Optimization algorithms for linear constrained problems.
+ */

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/package-info.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/GradientMultivariateOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/GradientMultivariateOptimizer.java?rev=1420684&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/GradientMultivariateOptimizer.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/GradientMultivariateOptimizer.java Wed Dec 12 14:10:38 2012
@@ -0,0 +1,105 @@
+/*
+ * 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.math3.optim.nonlinear.scalar;
+
+import org.apache.commons.math3.analysis.MultivariateVectorFunction;
+import org.apache.commons.math3.optim.ConvergenceChecker;
+import org.apache.commons.math3.optim.OptimizationData;
+import org.apache.commons.math3.optim.PointValuePair;
+import org.apache.commons.math3.exception.TooManyEvaluationsException;
+
+/**
+ * Base class for implementing optimizers for multivariate scalar
+ * differentiable functions.
+ * It contains boiler-plate code for dealing with gradient evaluation.
+ *
+ * @version $Id$
+ * @since 3.1
+ */
+public abstract class GradientMultivariateOptimizer
+    extends MultivariateOptimizer {
+    /**
+     * Gradient of the objective function.
+     */
+    private MultivariateVectorFunction gradient;
+
+    /**
+     * @param checker Convergence checker.
+     */
+    protected GradientMultivariateOptimizer(ConvergenceChecker<PointValuePair> checker) {
+        super(checker);
+    }
+
+    /**
+     * Compute the gradient vector.
+     *
+     * @param params Point at which the gradient must be evaluated.
+     * @return the gradient at the specified point.
+     */
+    protected double[] computeObjectiveGradient(final double[] params) {
+        return gradient.value(params);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * @param optData Optimization data.
+     * The following data will be looked for:
+     * <ul>
+     *  <li>{@link org.apache.commons.math3.optim.MaxEval}</li>
+     *  <li>{@link org.apache.commons.math3.optim.InitialGuess}</li>
+     *  <li>{@link org.apache.commons.math3.optim.SimpleBounds}</li>
+     *  <li>{@link org.apache.commons.math3.optim.GoalType}</li>
+     *  <li>{@link org.apache.commons.math3.optim.ObjectiveFunction}</li>
+     *  <li>{@link ObjectiveFunctionGradient}</li>
+     * </ul>
+     * @return {@inheritDoc}
+     * @throws TooManyEvaluationsException if the maximal number of
+     * evaluations (of the objective function) is exceeded.
+     */
+    @Override
+    public PointValuePair optimize(OptimizationData... optData)
+        throws TooManyEvaluationsException {
+         // Retrieve settings.
+        parseOptimizationData(optData);
+        // Set up base class and perform computation.
+        return super.optimize(optData);
+    }
+
+    /**
+     * Scans the list of (required and optional) optimization data that
+     * characterize the problem.
+     *
+     * @param optData Optimization data.
+     * The following data will be looked for:
+     * <ul>
+     *  <li>{@link ObjectiveFunction}</li>
+     * </ul>
+     */
+    private void parseOptimizationData(OptimizationData... optData) {
+        // The existing values (as set by the previous call) are reused if
+        // not provided in the argument list.
+        for (OptimizationData data : optData) {
+            if  (data instanceof ObjectiveFunctionGradient) {
+                gradient = ((ObjectiveFunctionGradient) data).getObjectiveFunctionGradient();
+                // If more data must be parsed, this statement _must_ be
+                // changed to "continue".
+                break;
+            }
+        }
+    }
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/GradientMultivariateOptimizer.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/LeastSquaresConverter.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/LeastSquaresConverter.java?rev=1420684&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/LeastSquaresConverter.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/LeastSquaresConverter.java Wed Dec 12 14:10:38 2012
@@ -0,0 +1,187 @@
+/*
+ * 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.math3.optim.nonlinear.scalar;
+
+import org.apache.commons.math3.analysis.MultivariateFunction;
+import org.apache.commons.math3.analysis.MultivariateVectorFunction;
+import org.apache.commons.math3.exception.DimensionMismatchException;
+import org.apache.commons.math3.linear.RealMatrix;
+
+/**
+ * This class converts
+ * {@link MultivariateVectorFunction vectorial objective functions} to
+ * {@link MultivariateFunction scalar objective functions}
+ * when the goal is to minimize them.
+ * <br/>
+ * This class is mostly used when the vectorial objective function represents
+ * a theoretical result computed from a point set applied to a model and
+ * the models point 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.
+ * <br/>
+ * This class computes a possibly weighted squared sum of the residuals, which is
+ * 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 MultivariateFunction} 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.
+ * <br/>
+ * This class support combination of residuals with or without weights and correlations.
+  *
+ * @see MultivariateFunction
+ * @see MultivariateVectorFunction
+ * @version $Id: LeastSquaresConverter.java 1416643 2012-12-03 19:37:14Z tn $
+ * @since 2.0
+ */
+
+public class LeastSquaresConverter implements MultivariateFunction {
+    /** Underlying vectorial function. */
+    private final MultivariateVectorFunction function;
+    /** Observations to be compared to objective function to compute residuals. */
+    private final double[] observations;
+    /** Optional weights for the residuals. */
+    private final double[] weights;
+    /** Optional scaling matrix (weight and correlations) for the residuals. */
+    private final RealMatrix scale;
+
+    /**
+     * Builds a simple converter for uncorrelated residuals with identical
+     * weights.
+     *
+     * @param function vectorial residuals function to wrap
+     * @param observations observations to be compared to objective function to compute residuals
+     */
+    public LeastSquaresConverter(final MultivariateVectorFunction function,
+                                 final double[] observations) {
+        this.function     = function;
+        this.observations = observations.clone();
+        this.weights      = null;
+        this.scale        = null;
+    }
+
+    /**
+     * Builds a simple converter for uncorrelated residuals with the
+     * specified weights.
+     * <p>
+     * The scalar objective function value is computed as:
+     * <pre>
+     * objective = &sum;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 residuals array in which even elements
+     * are angular measurements in degrees with a 0.01&deg; 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 array computed by the objective function, the observations array and the
+     * weights array must have consistent sizes or a {@link DimensionMismatchException}
+     * 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
+     * @throws DimensionMismatchException if the observations vector and the weights
+     * vector dimensions do not match (objective function dimension is checked only when
+     * the {@link #value(double[])} method is called)
+     */
+    public LeastSquaresConverter(final MultivariateVectorFunction function,
+                                 final double[] observations,
+                                 final double[] weights) {
+        if (observations.length != weights.length) {
+            throw new DimensionMismatchException(observations.length, weights.length);
+        }
+        this.function     = function;
+        this.observations = observations.clone();
+        this.weights      = weights.clone();
+        this.scale        = null;
+    }
+
+    /**
+     * Builds a simple converter for correlated residuals with the
+     * specified weights.
+     * <p>
+     * The scalar objective function value is computed as:
+     * <pre>
+     * objective = y<sup>T</sup>y with y = scale&times;(observation-objective)
+     * </pre>
+     * </p>
+     * <p>
+     * The array computed by the objective function, the observations array and the
+     * the scaling matrix must have consistent sizes or a {@link DimensionMismatchException}
+     * 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 scale scaling matrix
+     * @throws DimensionMismatchException if the observations vector and the scale
+     * matrix dimensions do not match (objective function dimension is checked only when
+     * the {@link #value(double[])} method is called)
+     */
+    public LeastSquaresConverter(final MultivariateVectorFunction function,
+                                 final double[] observations,
+                                 final RealMatrix scale) {
+        if (observations.length != scale.getColumnDimension()) {
+            throw new DimensionMismatchException(observations.length, scale.getColumnDimension());
+        }
+        this.function     = function;
+        this.observations = observations.clone();
+        this.weights      = null;
+        this.scale        = scale.copy();
+    }
+
+    /** {@inheritDoc} */
+    public double value(final double[] point) {
+        // compute residuals
+        final double[] residuals = function.value(point);
+        if (residuals.length != observations.length) {
+            throw new DimensionMismatchException(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) {
+            for (int i = 0; i < residuals.length; ++i) {
+                final double ri = residuals[i];
+                sumSquares +=  weights[i] * ri * ri;
+            }
+        } else if (scale != null) {
+            for (final double yi : scale.operate(residuals)) {
+                sumSquares += yi * yi;
+            }
+        } else {
+            for (final double ri : residuals) {
+                sumSquares += ri * ri;
+            }
+        }
+
+        return sumSquares;
+    }
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/LeastSquaresConverter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/MultiStartMultivariateOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/MultiStartMultivariateOptimizer.java?rev=1420684&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/MultiStartMultivariateOptimizer.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/MultiStartMultivariateOptimizer.java Wed Dec 12 14:10:38 2012
@@ -0,0 +1,112 @@
+/*
+ * 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.math3.optim.nonlinear.scalar;
+
+import java.util.Collections;
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Comparator;
+import org.apache.commons.math3.exception.NotStrictlyPositiveException;
+import org.apache.commons.math3.exception.NullArgumentException;
+import org.apache.commons.math3.random.RandomVectorGenerator;
+import org.apache.commons.math3.optim.BaseMultiStartMultivariateOptimizer;
+import org.apache.commons.math3.optim.PointValuePair;
+import org.apache.commons.math3.optim.GoalType;
+
+/**
+ * Multi-start optimizer.
+ *
+ * This class wraps an optimizer in order to use it several times in
+ * turn with different starting points (trying to avoid being trapped
+ * in a local extremum when looking for a global one).
+ *
+ * @version $Id$
+ * @since 3.0
+ */
+public class MultiStartMultivariateOptimizer
+    extends BaseMultiStartMultivariateOptimizer<PointValuePair> {
+    /** Underlying optimizer. */
+    private final MultivariateOptimizer optimizer;
+    /** Found optima. */
+    private final List<PointValuePair> optima = new ArrayList<PointValuePair>();
+
+    /**
+     * Create a multi-start optimizer from a single-start optimizer.
+     *
+     * @param optimizer Single-start optimizer to wrap.
+     * @param starts Number of starts to perform.
+     * If {@code starts == 1}, the result will be same as if {@code optimizer}
+     * is called directly.
+     * @param generator Random vector generator to use for restarts.
+     * @throws NullArgumentException if {@code optimizer} or {@code generator}
+     * is {@code null}.
+     * @throws NotStrictlyPositiveException if {@code starts < 1}.
+     */
+    public MultiStartMultivariateOptimizer(final MultivariateOptimizer optimizer,
+                                           final int starts,
+                                           final RandomVectorGenerator generator)
+        throws NullArgumentException,
+        NotStrictlyPositiveException {
+        super(optimizer, starts, generator);
+        this.optimizer = optimizer;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public PointValuePair[] getOptima() {
+        Collections.sort(optima, getPairComparator());
+        return optima.toArray(new PointValuePair[0]);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    protected void store(PointValuePair optimum) {
+        optima.add(optimum);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    protected void clear() {
+        optima.clear();
+    }
+
+    /**
+     * @return a comparator for sorting the optima.
+     */
+    private Comparator<PointValuePair> getPairComparator() {
+        return 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 (optimizer.getGoalType() == GoalType.MINIMIZE) ?
+                    Double.compare(v1, v2) : Double.compare(v2, v1);
+            }
+        };
+    }
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/MultiStartMultivariateOptimizer.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/MultivariateFunctionMappingAdapter.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/MultivariateFunctionMappingAdapter.java?rev=1420684&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/MultivariateFunctionMappingAdapter.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/MultivariateFunctionMappingAdapter.java Wed Dec 12 14:10:38 2012
@@ -0,0 +1,295 @@
+/*
+ * 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.math3.optim.nonlinear.scalar;
+
+import org.apache.commons.math3.analysis.MultivariateFunction;
+import org.apache.commons.math3.analysis.UnivariateFunction;
+import org.apache.commons.math3.analysis.function.Logit;
+import org.apache.commons.math3.analysis.function.Sigmoid;
+import org.apache.commons.math3.exception.DimensionMismatchException;
+import org.apache.commons.math3.exception.NumberIsTooSmallException;
+import org.apache.commons.math3.util.FastMath;
+import org.apache.commons.math3.util.MathUtils;
+
+/**
+ * <p>Adapter for mapping bounded {@link MultivariateFunction} to unbounded ones.</p>
+ *
+ * <p>
+ * This adapter can be used to wrap functions subject to simple bounds on
+ * parameters so they can be used by optimizers that do <em>not</em> directly
+ * support simple bounds.
+ * </p>
+ * <p>
+ * The principle is that the user function that will be wrapped will see its
+ * parameters bounded as required, i.e when its {@code value} method is called
+ * with argument array {@code point}, the elements array will fulfill requirement
+ * {@code lower[i] <= point[i] <= upper[i]} for all i. Some of the components
+ * may be unbounded or bounded only on one side if the corresponding bound is
+ * set to an infinite value. The optimizer will not manage the user function by
+ * itself, but it will handle this adapter and it is this adapter that will take
+ * care the bounds are fulfilled. The adapter {@link #value(double[])} method will
+ * be called by the optimizer with unbound parameters, and the adapter will map
+ * the unbounded value to the bounded range using appropriate functions like
+ * {@link Sigmoid} for double bounded elements for example.
+ * </p>
+ * <p>
+ * As the optimizer sees only unbounded parameters, it should be noted that the
+ * start point or simplex expected by the optimizer should be unbounded, so the
+ * user is responsible for converting his bounded point to unbounded by calling
+ * {@link #boundedToUnbounded(double[])} before providing them to the optimizer.
+ * For the same reason, the point returned by the {@link
+ * org.apache.commons.math3.optimization.BaseMultivariateOptimizer#optimize(int,
+ * MultivariateFunction, org.apache.commons.math3.optimization.GoalType, double[])}
+ * method is unbounded. So to convert this point to bounded, users must call
+ * {@link #unboundedToBounded(double[])} by themselves!</p>
+ * <p>
+ * This adapter is only a poor man solution to simple bounds optimization constraints
+ * that can be used with simple optimizers like
+ * {@link org.apache.commons.math3.optim.nonlinear.scalar.noderiv.SimplexOptimizer
+ * SimplexOptimizer}.
+ * A better solution is to use an optimizer that directly supports simple bounds like
+ * {@link org.apache.commons.math3.optim.nonlinear.scalar.noderiv.CMAESOptimizer
+ * CMAESOptimizer} or
+ * {@link org.apache.commons.math3.optim.nonlinear.scalar.noderiv.BOBYQAOptimizer
+ * BOBYQAOptimizer}.
+ * One caveat of this poor-man's solution is that behavior near the bounds may be
+ * numerically unstable as bounds are mapped from infinite values.
+ * Another caveat is that convergence values are evaluated by the optimizer with
+ * respect to unbounded variables, so there will be scales differences when
+ * converted to bounded variables.
+ * </p>
+ *
+ * @see MultivariateFunctionPenaltyAdapter
+ *
+ * @version $Id: MultivariateFunctionMappingAdapter.java 1416643 2012-12-03 19:37:14Z tn $
+ * @since 3.0
+ */
+public class MultivariateFunctionMappingAdapter
+    implements MultivariateFunction {
+    /** Underlying bounded function. */
+    private final MultivariateFunction bounded;
+    /** Mapping functions. */
+    private final Mapper[] mappers;
+
+    /** Simple constructor.
+     * @param bounded bounded function
+     * @param lower lower bounds for each element of the input parameters array
+     * (some elements may be set to {@code Double.NEGATIVE_INFINITY} for
+     * unbounded values)
+     * @param upper upper bounds for each element of the input parameters array
+     * (some elements may be set to {@code Double.POSITIVE_INFINITY} for
+     * unbounded values)
+     * @exception DimensionMismatchException if lower and upper bounds are not
+     * consistent, either according to dimension or to values
+     */
+    public MultivariateFunctionMappingAdapter(final MultivariateFunction bounded,
+                                              final double[] lower, final double[] upper) {
+        // safety checks
+        MathUtils.checkNotNull(lower);
+        MathUtils.checkNotNull(upper);
+        if (lower.length != upper.length) {
+            throw new DimensionMismatchException(lower.length, upper.length);
+        }
+        for (int i = 0; i < lower.length; ++i) {
+            // note the following test is written in such a way it also fails for NaN
+            if (!(upper[i] >= lower[i])) {
+                throw new NumberIsTooSmallException(upper[i], lower[i], true);
+            }
+        }
+
+        this.bounded = bounded;
+        this.mappers = new Mapper[lower.length];
+        for (int i = 0; i < mappers.length; ++i) {
+            if (Double.isInfinite(lower[i])) {
+                if (Double.isInfinite(upper[i])) {
+                    // element is unbounded, no transformation is needed
+                    mappers[i] = new NoBoundsMapper();
+                } else {
+                    // element is simple-bounded on the upper side
+                    mappers[i] = new UpperBoundMapper(upper[i]);
+                }
+            } else {
+                if (Double.isInfinite(upper[i])) {
+                    // element is simple-bounded on the lower side
+                    mappers[i] = new LowerBoundMapper(lower[i]);
+                } else {
+                    // element is double-bounded
+                    mappers[i] = new LowerUpperBoundMapper(lower[i], upper[i]);
+                }
+            }
+        }
+    }
+
+    /**
+     * Maps an array from unbounded to bounded.
+     *
+     * @param point Unbounded values.
+     * @return the bounded values.
+     */
+    public double[] unboundedToBounded(double[] point) {
+        // Map unbounded input point to bounded point.
+        final double[] mapped = new double[mappers.length];
+        for (int i = 0; i < mappers.length; ++i) {
+            mapped[i] = mappers[i].unboundedToBounded(point[i]);
+        }
+
+        return mapped;
+    }
+
+    /**
+     * Maps an array from bounded to unbounded.
+     *
+     * @param point Bounded values.
+     * @return the unbounded values.
+     */
+    public double[] boundedToUnbounded(double[] point) {
+        // Map bounded input point to unbounded point.
+        final double[] mapped = new double[mappers.length];
+        for (int i = 0; i < mappers.length; ++i) {
+            mapped[i] = mappers[i].boundedToUnbounded(point[i]);
+        }
+
+        return mapped;
+    }
+
+    /**
+     * Compute the underlying function value from an unbounded point.
+     * <p>
+     * This method simply bounds the unbounded point using the mappings
+     * set up at construction and calls the underlying function using
+     * the bounded point.
+     * </p>
+     * @param point unbounded value
+     * @return underlying function value
+     * @see #unboundedToBounded(double[])
+     */
+    public double value(double[] point) {
+        return bounded.value(unboundedToBounded(point));
+    }
+
+    /** Mapping interface. */
+    private interface Mapper {
+        /**
+         * Maps a value from unbounded to bounded.
+         *
+         * @param y Unbounded value.
+         * @return the bounded value.
+         */
+        double unboundedToBounded(double y);
+
+        /**
+         * Maps a value from bounded to unbounded.
+         *
+         * @param x Bounded value.
+         * @return the unbounded value.
+         */
+        double boundedToUnbounded(double x);
+    }
+
+    /** Local class for no bounds mapping. */
+    private static class NoBoundsMapper implements Mapper {
+        /** {@inheritDoc} */
+        public double unboundedToBounded(final double y) {
+            return y;
+        }
+
+        /** {@inheritDoc} */
+        public double boundedToUnbounded(final double x) {
+            return x;
+        }
+    }
+
+    /** Local class for lower bounds mapping. */
+    private static class LowerBoundMapper implements Mapper {
+        /** Low bound. */
+        private final double lower;
+
+        /**
+         * Simple constructor.
+         *
+         * @param lower lower bound
+         */
+        public LowerBoundMapper(final double lower) {
+            this.lower = lower;
+        }
+
+        /** {@inheritDoc} */
+        public double unboundedToBounded(final double y) {
+            return lower + FastMath.exp(y);
+        }
+
+        /** {@inheritDoc} */
+        public double boundedToUnbounded(final double x) {
+            return FastMath.log(x - lower);
+        }
+
+    }
+
+    /** Local class for upper bounds mapping. */
+    private static class UpperBoundMapper implements Mapper {
+
+        /** Upper bound. */
+        private final double upper;
+
+        /** Simple constructor.
+         * @param upper upper bound
+         */
+        public UpperBoundMapper(final double upper) {
+            this.upper = upper;
+        }
+
+        /** {@inheritDoc} */
+        public double unboundedToBounded(final double y) {
+            return upper - FastMath.exp(-y);
+        }
+
+        /** {@inheritDoc} */
+        public double boundedToUnbounded(final double x) {
+            return -FastMath.log(upper - x);
+        }
+
+    }
+
+    /** Local class for lower and bounds mapping. */
+    private static class LowerUpperBoundMapper implements Mapper {
+        /** Function from unbounded to bounded. */
+        private final UnivariateFunction boundingFunction;
+        /** Function from bounded to unbounded. */
+        private final UnivariateFunction unboundingFunction;
+
+        /**
+         * Simple constructor.
+         *
+         * @param lower lower bound
+         * @param upper upper bound
+         */
+        public LowerUpperBoundMapper(final double lower, final double upper) {
+            boundingFunction   = new Sigmoid(lower, upper);
+            unboundingFunction = new Logit(lower, upper);
+        }
+
+        /** {@inheritDoc} */
+        public double unboundedToBounded(final double y) {
+            return boundingFunction.value(y);
+        }
+
+        /** {@inheritDoc} */
+        public double boundedToUnbounded(final double x) {
+            return unboundingFunction.value(x);
+        }
+    }
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/nonlinear/scalar/MultivariateFunctionMappingAdapter.java
------------------------------------------------------------------------------
    svn:eol-style = native



Mime
View raw message