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 + ∑<sub>i</sub>[scale[i] * √|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 }