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 */ 017package org.apache.commons.math4.legacy.optim.nonlinear.scalar; 018 019import org.apache.commons.math4.legacy.analysis.MultivariateFunction; 020import org.apache.commons.math4.legacy.analysis.UnivariateFunction; 021import org.apache.commons.math4.legacy.optim.BaseMultivariateOptimizer; 022import org.apache.commons.math4.legacy.optim.ConvergenceChecker; 023import org.apache.commons.math4.legacy.optim.OptimizationData; 024import org.apache.commons.math4.legacy.optim.PointValuePair; 025import org.apache.commons.math4.legacy.optim.MaxEval; 026import org.apache.commons.math4.legacy.optim.univariate.BracketFinder; 027import org.apache.commons.math4.legacy.optim.univariate.BrentOptimizer; 028import org.apache.commons.math4.legacy.optim.univariate.SearchInterval; 029import org.apache.commons.math4.legacy.optim.univariate.SimpleUnivariateValueChecker; 030import org.apache.commons.math4.legacy.optim.univariate.UnivariateObjectiveFunction; 031import org.apache.commons.math4.legacy.optim.univariate.UnivariateOptimizer; 032import org.apache.commons.math4.legacy.optim.univariate.UnivariatePointValuePair; 033 034/** 035 * Base class for a multivariate scalar function optimizer. 036 * 037 * @since 3.1 038 */ 039public abstract class MultivariateOptimizer 040 extends BaseMultivariateOptimizer<PointValuePair> { 041 /** Objective function. */ 042 private MultivariateFunction function; 043 /** Type of optimization. */ 044 private GoalType goal; 045 /** Line search relative tolerance. */ 046 private double lineSearchRelativeTolerance = 1e-8; 047 /** Line search absolute tolerance. */ 048 private double lineSearchAbsoluteTolerance = 1e-8; 049 /** Line serach initial bracketing range. */ 050 private double lineSearchInitialBracketingRange = 1d; 051 /** Line search. */ 052 private LineSearch lineSearch; 053 054 /** 055 * @param checker Convergence checker. 056 */ 057 protected MultivariateOptimizer(ConvergenceChecker<PointValuePair> checker) { 058 super(checker); 059 } 060 061 /** 062 * {@inheritDoc} 063 * 064 * @param optData Optimization data. In addition to those documented in 065 * {@link BaseMultivariateOptimizer#parseOptimizationData(OptimizationData[]) 066 * BaseMultivariateOptimizer}, this method will register the following data: 067 * <ul> 068 * <li>{@link ObjectiveFunction}</li> 069 * <li>{@link GoalType}</li> 070 * <li>{@link LineSearchTolerance}</li> 071 * </ul> 072 * @return {@inheritDoc} 073 * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException 074 * if the maximal number of evaluations is exceeded. 075 */ 076 @Override 077 public PointValuePair optimize(OptimizationData... optData) { 078 // Set up base class and perform computation. 079 return super.optimize(optData); 080 } 081 082 /** 083 * Scans the list of (required and optional) optimization data that 084 * characterize the problem. 085 * 086 * @param optData Optimization data. 087 * The following data will be looked for: 088 * <ul> 089 * <li>{@link ObjectiveFunction}</li> 090 * <li>{@link GoalType}</li> 091 * <li>{@link LineSearchTolerance}</li> 092 * </ul> 093 */ 094 @Override 095 protected void parseOptimizationData(OptimizationData... optData) { 096 // Allow base class to register its own data. 097 super.parseOptimizationData(optData); 098 099 // The existing values (as set by the previous call) are reused if 100 // not provided in the argument list. 101 for (OptimizationData data : optData) { 102 if (data instanceof GoalType) { 103 goal = (GoalType) data; 104 continue; 105 } 106 if (data instanceof ObjectiveFunction) { 107 final MultivariateFunction delegate = ((ObjectiveFunction) data).getObjectiveFunction(); 108 function = new MultivariateFunction() { 109 @Override 110 public double value(double[] point) { 111 incrementEvaluationCount(); 112 return delegate.value(point); 113 } 114 }; 115 continue; 116 } 117 if (data instanceof LineSearchTolerance) { 118 final LineSearchTolerance tol = (LineSearchTolerance) data; 119 lineSearchRelativeTolerance = tol.getRelativeTolerance(); 120 lineSearchAbsoluteTolerance = tol.getAbsoluteTolerance(); 121 lineSearchInitialBracketingRange = tol.getInitialBracketingRange(); 122 continue; 123 } 124 } 125 } 126 127 /** 128 * Intantiate the line search implementation. 129 */ 130 protected void createLineSearch() { 131 lineSearch = new LineSearch(this, 132 lineSearchRelativeTolerance, 133 lineSearchAbsoluteTolerance, 134 lineSearchInitialBracketingRange); 135 } 136 137 /** 138 * Finds the number {@code alpha} that optimizes 139 * {@code f(startPoint + alpha * direction)}. 140 * 141 * @param startPoint Starting point. 142 * @param direction Search direction. 143 * @return the optimum. 144 * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException 145 * if the number of evaluations is exceeded. 146 */ 147 protected UnivariatePointValuePair lineSearch(final double[] startPoint, 148 final double[] direction) { 149 return lineSearch.search(startPoint, direction); 150 } 151 152 /** 153 * @return the optimization type. 154 */ 155 protected GoalType getGoalType() { 156 return goal; 157 } 158 159 /** 160 * @return a wrapper that delegates to the user-supplied function, 161 * and counts the number of evaluations. 162 */ 163 protected MultivariateFunction getObjectiveFunction() { 164 return function; 165 } 166 167 /** 168 * Computes the objective function value. 169 * This method <em>must</em> be called by subclasses to enforce the 170 * evaluation counter limit. 171 * 172 * @param params Point at which the objective function must be evaluated. 173 * @return the objective function value at the specified point. 174 * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException 175 * if the maximal number of evaluations is exceeded. 176 * 177 * @deprecated Use {@link #getObjectiveFunction()} instead. 178 */ 179 @Deprecated 180 public double computeObjectiveValue(double[] params) { 181 return function.value(params); 182 } 183 184 /** 185 * Find the minimum of the objective function along a given direction. 186 * 187 * @since 4.0 188 */ 189 private static class LineSearch { 190 /** 191 * Value that will pass the precondition check for {@link BrentOptimizer} 192 * but will not pass the convergence check, so that the custom checker 193 * will always decide when to stop the line search. 194 */ 195 private static final double REL_TOL_UNUSED = 1e-15; 196 /** 197 * Value that will pass the precondition check for {@link BrentOptimizer} 198 * but will not pass the convergence check, so that the custom checker 199 * will always decide when to stop the line search. 200 */ 201 private static final double ABS_TOL_UNUSED = Double.MIN_VALUE; 202 /** 203 * Optimizer used for line search. 204 */ 205 private final UnivariateOptimizer lineOptimizer; 206 /** 207 * Automatic bracketing. 208 */ 209 private final BracketFinder bracket = new BracketFinder(); 210 /** 211 * Extent of the initial interval used to find an interval that 212 * brackets the optimum. 213 */ 214 private final double initialBracketingRange; 215 /** 216 * Optimizer on behalf of which the line search must be performed. 217 */ 218 private final MultivariateOptimizer mainOptimizer; 219 220 /** 221 * The {@code BrentOptimizer} default stopping criterion uses the 222 * tolerances to check the domain (point) values, not the function 223 * values. 224 * The {@code relativeTolerance} and {@code absoluteTolerance} 225 * arguments are thus passed to a {@link SimpleUnivariateValueChecker 226 * custom checker} that will use the function values. 227 * 228 * @param optimizer Optimizer on behalf of which the line search 229 * be performed. 230 * Its {@link MultivariateOptimizer#getObjectiveFunction() objective 231 * function} will be called by the {@link #search(double[],double[]) 232 * search} method. 233 * @param relativeTolerance Search will stop when the function relative 234 * difference between successive iterations is below this value. 235 * @param absoluteTolerance Search will stop when the function absolute 236 * difference between successive iterations is below this value. 237 * @param initialBracketingRange Extent of the initial interval used to 238 * find an interval that brackets the optimum. 239 * If the optimized function varies a lot in the vicinity of the optimum, 240 * it may be necessary to provide a value lower than the distance between 241 * successive local minima. 242 */ 243 /* package-private */ LineSearch(MultivariateOptimizer optimizer, 244 double relativeTolerance, 245 double absoluteTolerance, 246 double initialBracketingRange) { 247 mainOptimizer = optimizer; 248 lineOptimizer = new BrentOptimizer(REL_TOL_UNUSED, 249 ABS_TOL_UNUSED, 250 new SimpleUnivariateValueChecker(relativeTolerance, 251 absoluteTolerance)); 252 this.initialBracketingRange = initialBracketingRange; 253 } 254 255 /** 256 * Finds the number {@code alpha} that optimizes 257 * {@code f(startPoint + alpha * direction)}. 258 * 259 * @param startPoint Starting point. 260 * @param direction Search direction. 261 * @return the optimum. 262 * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException 263 * if the number of evaluations is exceeded. 264 */ 265 /* package-private */ UnivariatePointValuePair search(final double[] startPoint, 266 final double[] direction) { 267 final int n = startPoint.length; 268 final MultivariateFunction func = mainOptimizer.getObjectiveFunction(); 269 final UnivariateFunction f = new UnivariateFunction() { 270 /** {@inheritDoc} */ 271 @Override 272 public double value(double alpha) { 273 final double[] x = new double[n]; 274 for (int i = 0; i < n; i++) { 275 x[i] = startPoint[i] + alpha * direction[i]; 276 } 277 return func.value(x); 278 } 279 }; 280 281 final GoalType goal = mainOptimizer.getGoalType(); 282 bracket.search(f, goal, 0, initialBracketingRange); 283 // Passing "MAX_VALUE" as a dummy value because it is the enclosing 284 // class that counts the number of evaluations (and will eventually 285 // generate the exception). 286 return lineOptimizer.optimize(new MaxEval(Integer.MAX_VALUE), 287 new UnivariateObjectiveFunction(f), 288 goal, 289 new SearchInterval(bracket.getLo(), 290 bracket.getHi(), 291 bracket.getMid())); 292 } 293 } 294}