You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2012/12/12 15:11:04 UTC
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...
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 <= phase 1 objective
+ * 0 1 -15 -10 0 0 0 0 0 <= phase 2 objective
+ * 0 0 1 0 0 1 0 0 2 <= constraint 1
+ * 0 0 0 1 0 0 1 0 3 <= constraint 2
+ * 0 0 1 1 0 0 0 1 4 <= constraint 3
+ * </pre>
+ * W: Phase 1 objective function</br>
+ * Z: Phase 2 objective function</br>
+ * x1 & x2: Decision variables</br>
+ * x-: Extra decision variable to allow for negative values</br>
+ * s1 & 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 = ∑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° 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×(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