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.noderiv; 018 019import java.util.Comparator; 020 021import org.apache.commons.math3.analysis.MultivariateFunction; 022import org.apache.commons.math3.optim.PointValuePair; 023 024/** 025 * This class implements the multi-directional direct search method. 026 * 027 * @since 3.0 028 */ 029public class MultiDirectionalSimplex extends AbstractSimplex { 030 /** Default value for {@link #khi}: {@value}. */ 031 private static final double DEFAULT_KHI = 2; 032 /** Default value for {@link #gamma}: {@value}. */ 033 private static final double DEFAULT_GAMMA = 0.5; 034 /** Expansion coefficient. */ 035 private final double khi; 036 /** Contraction coefficient. */ 037 private final double gamma; 038 039 /** 040 * Build a multi-directional simplex with default coefficients. 041 * The default values are 2.0 for khi and 0.5 for gamma. 042 * 043 * @param n Dimension of the simplex. 044 */ 045 public MultiDirectionalSimplex(final int n) { 046 this(n, 1d); 047 } 048 049 /** 050 * Build a multi-directional simplex with default coefficients. 051 * The default values are 2.0 for khi and 0.5 for gamma. 052 * 053 * @param n Dimension of the simplex. 054 * @param sideLength Length of the sides of the default (hypercube) 055 * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}. 056 */ 057 public MultiDirectionalSimplex(final int n, double sideLength) { 058 this(n, sideLength, DEFAULT_KHI, DEFAULT_GAMMA); 059 } 060 061 /** 062 * Build a multi-directional simplex with specified coefficients. 063 * 064 * @param n Dimension of the simplex. See 065 * {@link AbstractSimplex#AbstractSimplex(int,double)}. 066 * @param khi Expansion coefficient. 067 * @param gamma Contraction coefficient. 068 */ 069 public MultiDirectionalSimplex(final int n, 070 final double khi, final double gamma) { 071 this(n, 1d, khi, gamma); 072 } 073 074 /** 075 * Build a multi-directional simplex with specified coefficients. 076 * 077 * @param n Dimension of the simplex. See 078 * {@link AbstractSimplex#AbstractSimplex(int,double)}. 079 * @param sideLength Length of the sides of the default (hypercube) 080 * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}. 081 * @param khi Expansion coefficient. 082 * @param gamma Contraction coefficient. 083 */ 084 public MultiDirectionalSimplex(final int n, double sideLength, 085 final double khi, final double gamma) { 086 super(n, sideLength); 087 088 this.khi = khi; 089 this.gamma = gamma; 090 } 091 092 /** 093 * Build a multi-directional simplex with default coefficients. 094 * The default values are 2.0 for khi and 0.5 for gamma. 095 * 096 * @param steps Steps along the canonical axes representing box edges. 097 * They may be negative but not zero. See 098 */ 099 public MultiDirectionalSimplex(final double[] steps) { 100 this(steps, DEFAULT_KHI, DEFAULT_GAMMA); 101 } 102 103 /** 104 * Build a multi-directional simplex with specified coefficients. 105 * 106 * @param steps Steps along the canonical axes representing box edges. 107 * They may be negative but not zero. See 108 * {@link AbstractSimplex#AbstractSimplex(double[])}. 109 * @param khi Expansion coefficient. 110 * @param gamma Contraction coefficient. 111 */ 112 public MultiDirectionalSimplex(final double[] steps, 113 final double khi, final double gamma) { 114 super(steps); 115 116 this.khi = khi; 117 this.gamma = gamma; 118 } 119 120 /** 121 * Build a multi-directional simplex with default coefficients. 122 * The default values are 2.0 for khi and 0.5 for gamma. 123 * 124 * @param referenceSimplex Reference simplex. See 125 * {@link AbstractSimplex#AbstractSimplex(double[][])}. 126 */ 127 public MultiDirectionalSimplex(final double[][] referenceSimplex) { 128 this(referenceSimplex, DEFAULT_KHI, DEFAULT_GAMMA); 129 } 130 131 /** 132 * Build a multi-directional simplex with specified coefficients. 133 * 134 * @param referenceSimplex Reference simplex. See 135 * {@link AbstractSimplex#AbstractSimplex(double[][])}. 136 * @param khi Expansion coefficient. 137 * @param gamma Contraction coefficient. 138 * @throws org.apache.commons.math3.exception.NotStrictlyPositiveException 139 * if the reference simplex does not contain at least one point. 140 * @throws org.apache.commons.math3.exception.DimensionMismatchException 141 * if there is a dimension mismatch in the reference simplex. 142 */ 143 public MultiDirectionalSimplex(final double[][] referenceSimplex, 144 final double khi, final double gamma) { 145 super(referenceSimplex); 146 147 this.khi = khi; 148 this.gamma = gamma; 149 } 150 151 /** {@inheritDoc} */ 152 @Override 153 public void iterate(final MultivariateFunction evaluationFunction, 154 final Comparator<PointValuePair> comparator) { 155 // Save the original simplex. 156 final PointValuePair[] original = getPoints(); 157 final PointValuePair best = original[0]; 158 159 // Perform a reflection step. 160 final PointValuePair reflected = evaluateNewSimplex(evaluationFunction, 161 original, 1, comparator); 162 if (comparator.compare(reflected, best) < 0) { 163 // Compute the expanded simplex. 164 final PointValuePair[] reflectedSimplex = getPoints(); 165 final PointValuePair expanded = evaluateNewSimplex(evaluationFunction, 166 original, khi, comparator); 167 if (comparator.compare(reflected, expanded) <= 0) { 168 // Keep the reflected simplex. 169 setPoints(reflectedSimplex); 170 } 171 // Keep the expanded simplex. 172 return; 173 } 174 175 // Compute the contracted simplex. 176 evaluateNewSimplex(evaluationFunction, original, gamma, comparator); 177 178 } 179 180 /** 181 * Compute and evaluate a new simplex. 182 * 183 * @param evaluationFunction Evaluation function. 184 * @param original Original simplex (to be preserved). 185 * @param coeff Linear coefficient. 186 * @param comparator Comparator to use to sort simplex vertices from best 187 * to poorest. 188 * @return the best point in the transformed simplex. 189 * @throws org.apache.commons.math3.exception.TooManyEvaluationsException 190 * if the maximal number of evaluations is exceeded. 191 */ 192 private PointValuePair evaluateNewSimplex(final MultivariateFunction evaluationFunction, 193 final PointValuePair[] original, 194 final double coeff, 195 final Comparator<PointValuePair> comparator) { 196 final double[] xSmallest = original[0].getPointRef(); 197 // Perform a linear transformation on all the simplex points, 198 // except the first one. 199 setPoint(0, original[0]); 200 final int dim = getDimension(); 201 for (int i = 1; i < getSize(); i++) { 202 final double[] xOriginal = original[i].getPointRef(); 203 final double[] xTransformed = new double[dim]; 204 for (int j = 0; j < dim; j++) { 205 xTransformed[j] = xSmallest[j] + coeff * (xSmallest[j] - xOriginal[j]); 206 } 207 setPoint(i, new PointValuePair(xTransformed, Double.NaN, false)); 208 } 209 210 // Evaluate the simplex. 211 evaluate(evaluationFunction, comparator); 212 213 return getPoint(0); 214 } 215}