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 }