001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 018 package org.apache.commons.math.optimization; 019 020 import java.util.Arrays; 021 import java.util.Comparator; 022 023 import org.apache.commons.math.FunctionEvaluationException; 024 import org.apache.commons.math.MathRuntimeException; 025 import org.apache.commons.math.analysis.DifferentiableMultivariateVectorialFunction; 026 import org.apache.commons.math.random.RandomVectorGenerator; 027 028 /** 029 * Special implementation of the {@link DifferentiableMultivariateVectorialOptimizer} interface adding 030 * multi-start features to an existing optimizer. 031 * <p> 032 * This class wraps a classical optimizer to use it several times in 033 * turn with different starting points in order to avoid being trapped 034 * into a local extremum when looking for a global one. 035 * </p> 036 * @version $Revision: 811685 $ $Date: 2009-09-05 13:36:48 -0400 (Sat, 05 Sep 2009) $ 037 * @since 2.0 038 */ 039 public class MultiStartDifferentiableMultivariateVectorialOptimizer 040 implements DifferentiableMultivariateVectorialOptimizer { 041 042 /** Serializable version identifier. */ 043 private static final long serialVersionUID = 9206382258980561530L; 044 045 /** Underlying classical optimizer. */ 046 private final DifferentiableMultivariateVectorialOptimizer optimizer; 047 048 /** Maximal number of iterations allowed. */ 049 private int maxIterations; 050 051 /** Number of iterations already performed for all starts. */ 052 private int totalIterations; 053 054 /** Maximal number of evaluations allowed. */ 055 private int maxEvaluations; 056 057 /** Number of evaluations already performed for all starts. */ 058 private int totalEvaluations; 059 060 /** Number of jacobian evaluations already performed for all starts. */ 061 private int totalJacobianEvaluations; 062 063 /** Number of starts to go. */ 064 private int starts; 065 066 /** Random generator for multi-start. */ 067 private RandomVectorGenerator generator; 068 069 /** Found optima. */ 070 private VectorialPointValuePair[] optima; 071 072 /** 073 * Create a multi-start optimizer from a single-start optimizer 074 * @param optimizer single-start optimizer to wrap 075 * @param starts number of starts to perform (including the 076 * first one), multi-start is disabled if value is less than or 077 * equal to 1 078 * @param generator random vector generator to use for restarts 079 */ 080 public MultiStartDifferentiableMultivariateVectorialOptimizer( 081 final DifferentiableMultivariateVectorialOptimizer optimizer, 082 final int starts, 083 final RandomVectorGenerator generator) { 084 this.optimizer = optimizer; 085 this.totalIterations = 0; 086 this.totalEvaluations = 0; 087 this.totalJacobianEvaluations = 0; 088 this.starts = starts; 089 this.generator = generator; 090 this.optima = null; 091 setMaxIterations(Integer.MAX_VALUE); 092 setMaxEvaluations(Integer.MAX_VALUE); 093 } 094 095 /** Get all the optima found during the last call to {@link 096 * #optimize(DifferentiableMultivariateVectorialFunction, 097 * double[], double[], double[]) optimize}. 098 * <p>The optimizer stores all the optima found during a set of 099 * restarts. The {@link #optimize(DifferentiableMultivariateVectorialFunction, 100 * double[], double[], double[]) optimize} method returns the 101 * best point only. This method returns all the points found at the 102 * end of each starts, including the best one already returned by the {@link 103 * #optimize(DifferentiableMultivariateVectorialFunction, double[], 104 * double[], double[]) optimize} method. 105 * </p> 106 * <p> 107 * The returned array as one element for each start as specified 108 * in the constructor. It is ordered with the results from the 109 * runs that did converge first, sorted from best to worst 110 * objective value (i.e in ascending order if minimizing and in 111 * descending order if maximizing), followed by and null elements 112 * corresponding to the runs that did not converge. This means all 113 * elements will be null if the {@link #optimize(DifferentiableMultivariateVectorialFunction, 114 * double[], double[], double[]) optimize} method did throw a {@link 115 * org.apache.commons.math.ConvergenceException ConvergenceException}). 116 * This also means that if the first element is non null, it is the best 117 * point found across all starts.</p> 118 * @return array containing the optima 119 * @exception IllegalStateException if {@link #optimize(DifferentiableMultivariateVectorialFunction, 120 * double[], double[], double[]) optimize} has not been called 121 */ 122 public VectorialPointValuePair[] getOptima() throws IllegalStateException { 123 if (optima == null) { 124 throw MathRuntimeException.createIllegalStateException("no optimum computed yet"); 125 } 126 return optima.clone(); 127 } 128 129 /** {@inheritDoc} */ 130 public void setMaxIterations(int maxIterations) { 131 this.maxIterations = maxIterations; 132 } 133 134 /** {@inheritDoc} */ 135 public int getMaxIterations() { 136 return maxIterations; 137 } 138 139 /** {@inheritDoc} */ 140 public int getIterations() { 141 return totalIterations; 142 } 143 144 /** {@inheritDoc} */ 145 public void setMaxEvaluations(int maxEvaluations) { 146 this.maxEvaluations = maxEvaluations; 147 } 148 149 /** {@inheritDoc} */ 150 public int getMaxEvaluations() { 151 return maxEvaluations; 152 } 153 154 /** {@inheritDoc} */ 155 public int getEvaluations() { 156 return totalEvaluations; 157 } 158 159 /** {@inheritDoc} */ 160 public int getJacobianEvaluations() { 161 return totalJacobianEvaluations; 162 } 163 164 /** {@inheritDoc} */ 165 public void setConvergenceChecker(VectorialConvergenceChecker checker) { 166 optimizer.setConvergenceChecker(checker); 167 } 168 169 /** {@inheritDoc} */ 170 public VectorialConvergenceChecker getConvergenceChecker() { 171 return optimizer.getConvergenceChecker(); 172 } 173 174 /** {@inheritDoc} */ 175 public VectorialPointValuePair optimize(final DifferentiableMultivariateVectorialFunction f, 176 final double[] target, final double[] weights, 177 final double[] startPoint) 178 throws FunctionEvaluationException, OptimizationException, IllegalArgumentException { 179 180 optima = new VectorialPointValuePair[starts]; 181 totalIterations = 0; 182 totalEvaluations = 0; 183 totalJacobianEvaluations = 0; 184 185 // multi-start loop 186 for (int i = 0; i < starts; ++i) { 187 188 try { 189 optimizer.setMaxIterations(maxIterations - totalIterations); 190 optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations); 191 optima[i] = optimizer.optimize(f, target, weights, 192 (i == 0) ? startPoint : generator.nextVector()); 193 } catch (FunctionEvaluationException fee) { 194 optima[i] = null; 195 } catch (OptimizationException oe) { 196 optima[i] = null; 197 } 198 199 totalIterations += optimizer.getIterations(); 200 totalEvaluations += optimizer.getEvaluations(); 201 totalJacobianEvaluations += optimizer.getJacobianEvaluations(); 202 203 } 204 205 // sort the optima from best to worst, followed by null elements 206 Arrays.sort(optima, new Comparator<VectorialPointValuePair>() { 207 public int compare(final VectorialPointValuePair o1, final VectorialPointValuePair o2) { 208 if (o1 == null) { 209 return (o2 == null) ? 0 : +1; 210 } else if (o2 == null) { 211 return -1; 212 } 213 return Double.compare(weightedResidual(o1), weightedResidual(o2)); 214 } 215 private double weightedResidual(final VectorialPointValuePair pv) { 216 final double[] value = pv.getValueRef(); 217 double sum = 0; 218 for (int i = 0; i < value.length; ++i) { 219 final double ri = value[i] - target[i]; 220 sum += weights[i] * ri * ri; 221 } 222 return sum; 223 } 224 }); 225 226 if (optima[0] == null) { 227 throw new OptimizationException( 228 "none of the {0} start points lead to convergence", 229 starts); 230 } 231 232 // return the found point given the best objective function value 233 return optima[0]; 234 235 } 236 237 }