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.math3.optim.nonlinear.scalar; 018 019import org.apache.commons.math3.optim.univariate.UnivariateOptimizer; 020import org.apache.commons.math3.optim.univariate.BrentOptimizer; 021import org.apache.commons.math3.optim.univariate.BracketFinder; 022import org.apache.commons.math3.optim.univariate.UnivariatePointValuePair; 023import org.apache.commons.math3.optim.univariate.SimpleUnivariateValueChecker; 024import org.apache.commons.math3.optim.univariate.SearchInterval; 025import org.apache.commons.math3.optim.univariate.UnivariateObjectiveFunction; 026import org.apache.commons.math3.analysis.UnivariateFunction; 027import org.apache.commons.math3.optim.MaxEval; 028 029/** 030 * Class for finding the minimum of the objective function along a given 031 * direction. 032 * 033 * @since 3.3 034 */ 035public class LineSearch { 036 /** 037 * Value that will pass the precondition check for {@link BrentOptimizer} 038 * but will not pass the convergence check, so that the custom checker 039 * will always decide when to stop the line search. 040 */ 041 private static final double REL_TOL_UNUSED = 1e-15; 042 /** 043 * Value that will pass the precondition check for {@link BrentOptimizer} 044 * but will not pass the convergence check, so that the custom checker 045 * will always decide when to stop the line search. 046 */ 047 private static final double ABS_TOL_UNUSED = Double.MIN_VALUE; 048 /** 049 * Optimizer used for line search. 050 */ 051 private final UnivariateOptimizer lineOptimizer; 052 /** 053 * Automatic bracketing. 054 */ 055 private final BracketFinder bracket = new BracketFinder(); 056 /** 057 * Extent of the initial interval used to find an interval that 058 * brackets the optimum. 059 */ 060 private final double initialBracketingRange; 061 /** 062 * Optimizer on behalf of which the line search must be performed. 063 */ 064 private final MultivariateOptimizer mainOptimizer; 065 066 /** 067 * The {@code BrentOptimizer} default stopping criterion uses the 068 * tolerances to check the domain (point) values, not the function 069 * values. 070 * The {@code relativeTolerance} and {@code absoluteTolerance} 071 * arguments are thus passed to a {@link SimpleUnivariateValueChecker 072 * custom checker} that will use the function values. 073 * 074 * @param optimizer Optimizer on behalf of which the line search 075 * be performed. 076 * Its {@link MultivariateOptimizer#computeObjectiveValue(double[]) 077 * computeObjectiveValue} method will be called by the 078 * {@link #search(double[],double[]) search} method. 079 * @param relativeTolerance Search will stop when the function relative 080 * difference between successive iterations is below this value. 081 * @param absoluteTolerance Search will stop when the function absolute 082 * difference between successive iterations is below this value. 083 * @param initialBracketingRange Extent of the initial interval used to 084 * find an interval that brackets the optimum. 085 * If the optimized function varies a lot in the vicinity of the optimum, 086 * it may be necessary to provide a value lower than the distance between 087 * successive local minima. 088 */ 089 public LineSearch(MultivariateOptimizer optimizer, 090 double relativeTolerance, 091 double absoluteTolerance, 092 double initialBracketingRange) { 093 mainOptimizer = optimizer; 094 lineOptimizer = new BrentOptimizer(REL_TOL_UNUSED, 095 ABS_TOL_UNUSED, 096 new SimpleUnivariateValueChecker(relativeTolerance, 097 absoluteTolerance)); 098 this.initialBracketingRange = initialBracketingRange; 099 } 100 101 /** 102 * Finds the number {@code alpha} that optimizes 103 * {@code f(startPoint + alpha * direction)}. 104 * 105 * @param startPoint Starting point. 106 * @param direction Search direction. 107 * @return the optimum. 108 * @throws org.apache.commons.math3.exception.TooManyEvaluationsException 109 * if the number of evaluations is exceeded. 110 */ 111 public UnivariatePointValuePair search(final double[] startPoint, 112 final double[] direction) { 113 final int n = startPoint.length; 114 final UnivariateFunction f = new UnivariateFunction() { 115 /** {@inheritDoc} */ 116 public double value(double alpha) { 117 final double[] x = new double[n]; 118 for (int i = 0; i < n; i++) { 119 x[i] = startPoint[i] + alpha * direction[i]; 120 } 121 final double obj = mainOptimizer.computeObjectiveValue(x); 122 return obj; 123 } 124 }; 125 126 final GoalType goal = mainOptimizer.getGoalType(); 127 bracket.search(f, goal, 0, initialBracketingRange); 128 // Passing "MAX_VALUE" as a dummy value because it is the enclosing 129 // class that counts the number of evaluations (and will eventually 130 // generate the exception). 131 return lineOptimizer.optimize(new MaxEval(Integer.MAX_VALUE), 132 new UnivariateObjectiveFunction(f), 133 goal, 134 new SearchInterval(bracket.getLo(), 135 bracket.getHi(), 136 bracket.getMid())); 137 } 138}