View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math3.optim.nonlinear.scalar;
18  
19  import org.apache.commons.math3.analysis.MultivariateFunction;
20  import org.apache.commons.math3.exception.DimensionMismatchException;
21  import org.apache.commons.math3.exception.NumberIsTooSmallException;
22  import org.apache.commons.math3.util.FastMath;
23  import org.apache.commons.math3.util.MathUtils;
24  
25  /**
26   * <p>Adapter extending bounded {@link MultivariateFunction} to an unbouded
27   * domain using a penalty function.</p>
28   *
29   * <p>
30   * This adapter can be used to wrap functions subject to simple bounds on
31   * parameters so they can be used by optimizers that do <em>not</em> directly
32   * support simple bounds.
33   * </p>
34   * <p>
35   * The principle is that the user function that will be wrapped will see its
36   * parameters bounded as required, i.e when its {@code value} method is called
37   * with argument array {@code point}, the elements array will fulfill requirement
38   * {@code lower[i] <= point[i] <= upper[i]} for all i. Some of the components
39   * may be unbounded or bounded only on one side if the corresponding bound is
40   * set to an infinite value. The optimizer will not manage the user function by
41   * itself, but it will handle this adapter and it is this adapter that will take
42   * care the bounds are fulfilled. The adapter {@link #value(double[])} method will
43   * be called by the optimizer with unbound parameters, and the adapter will check
44   * if the parameters is within range or not. If it is in range, then the underlying
45   * user function will be called, and if it is not the value of a penalty function
46   * will be returned instead.
47   * </p>
48   * <p>
49   * This adapter is only a poor-man's solution to simple bounds optimization
50   * constraints that can be used with simple optimizers like
51   * {@link org.apache.commons.math3.optim.nonlinear.scalar.noderiv.SimplexOptimizer
52   * SimplexOptimizer}.
53   * A better solution is to use an optimizer that directly supports simple bounds like
54   * {@link org.apache.commons.math3.optim.nonlinear.scalar.noderiv.CMAESOptimizer
55   * CMAESOptimizer} or
56   * {@link org.apache.commons.math3.optim.nonlinear.scalar.noderiv.BOBYQAOptimizer
57   * BOBYQAOptimizer}.
58   * One caveat of this poor-man's solution is that if start point or start simplex
59   * is completely outside of the allowed range, only the penalty function is used,
60   * and the optimizer may converge without ever entering the range.
61   * </p>
62   *
63   * @see MultivariateFunctionMappingAdapter
64   *
65   * @version $Id: MultivariateFunctionPenaltyAdapter.java 1435539 2013-01-19 13:27:24Z tn $
66   * @since 3.0
67   */
68  public class MultivariateFunctionPenaltyAdapter
69      implements MultivariateFunction {
70      /** Underlying bounded function. */
71      private final MultivariateFunction bounded;
72      /** Lower bounds. */
73      private final double[] lower;
74      /** Upper bounds. */
75      private final double[] upper;
76      /** Penalty offset. */
77      private final double offset;
78      /** Penalty scales. */
79      private final double[] scale;
80  
81      /**
82       * Simple constructor.
83       * <p>
84       * When the optimizer provided points are out of range, the value of the
85       * penalty function will be used instead of the value of the underlying
86       * function. In order for this penalty to be effective in rejecting this
87       * point during the optimization process, the penalty function value should
88       * be defined with care. This value is computed as:
89       * <pre>
90       *   penalty(point) = offset + &sum;<sub>i</sub>[scale[i] * &radic;|point[i]-boundary[i]|]
91       * </pre>
92       * where indices i correspond to all the components that violates their boundaries.
93       * </p>
94       * <p>
95       * So when attempting a function minimization, offset should be larger than
96       * the maximum expected value of the underlying function and scale components
97       * should all be positive. When attempting a function maximization, offset
98       * should be lesser than the minimum expected value of the underlying function
99       * and scale components should all be negative.
100      * minimization, and lesser than the minimum expected value of the underlying
101      * function when attempting maximization.
102      * </p>
103      * <p>
104      * These choices for the penalty function have two properties. First, all out
105      * of range points will return a function value that is worse than the value
106      * returned by any in range point. Second, the penalty is worse for large
107      * boundaries violation than for small violations, so the optimizer has an hint
108      * about the direction in which it should search for acceptable points.
109      * </p>
110      * @param bounded bounded function
111      * @param lower lower bounds for each element of the input parameters array
112      * (some elements may be set to {@code Double.NEGATIVE_INFINITY} for
113      * unbounded values)
114      * @param upper upper bounds for each element of the input parameters array
115      * (some elements may be set to {@code Double.POSITIVE_INFINITY} for
116      * unbounded values)
117      * @param offset base offset of the penalty function
118      * @param scale scale of the penalty function
119      * @exception DimensionMismatchException if lower bounds, upper bounds and
120      * scales are not consistent, either according to dimension or to bounadary
121      * values
122      */
123     public MultivariateFunctionPenaltyAdapter(final MultivariateFunction bounded,
124                                               final double[] lower, final double[] upper,
125                                               final double offset, final double[] scale) {
126 
127         // safety checks
128         MathUtils.checkNotNull(lower);
129         MathUtils.checkNotNull(upper);
130         MathUtils.checkNotNull(scale);
131         if (lower.length != upper.length) {
132             throw new DimensionMismatchException(lower.length, upper.length);
133         }
134         if (lower.length != scale.length) {
135             throw new DimensionMismatchException(lower.length, scale.length);
136         }
137         for (int i = 0; i < lower.length; ++i) {
138             // note the following test is written in such a way it also fails for NaN
139             if (!(upper[i] >= lower[i])) {
140                 throw new NumberIsTooSmallException(upper[i], lower[i], true);
141             }
142         }
143 
144         this.bounded = bounded;
145         this.lower   = lower.clone();
146         this.upper   = upper.clone();
147         this.offset  = offset;
148         this.scale   = scale.clone();
149     }
150 
151     /**
152      * Computes the underlying function value from an unbounded point.
153      * <p>
154      * This method simply returns the value of the underlying function
155      * if the unbounded point already fulfills the bounds, and compute
156      * a replacement value using the offset and scale if bounds are
157      * violated, without calling the function at all.
158      * </p>
159      * @param point unbounded point
160      * @return either underlying function value or penalty function value
161      */
162     public double value(double[] point) {
163 
164         for (int i = 0; i < scale.length; ++i) {
165             if ((point[i] < lower[i]) || (point[i] > upper[i])) {
166                 // bound violation starting at this component
167                 double sum = 0;
168                 for (int j = i; j < scale.length; ++j) {
169                     final double overshoot;
170                     if (point[j] < lower[j]) {
171                         overshoot = scale[j] * (lower[j] - point[j]);
172                     } else if (point[j] > upper[j]) {
173                         overshoot = scale[j] * (point[j] - upper[j]);
174                     } else {
175                         overshoot = 0;
176                     }
177                     sum += FastMath.sqrt(overshoot);
178                 }
179                 return offset + sum;
180             }
181         }
182 
183         // all boundaries are fulfilled, we are in the expected
184         // domain of the underlying function
185         return bounded.value(point);
186     }
187 }