Hi all, Le 30/11/2012 17:33, Konstantin Berlin a écrit : > As a user of the optimization algorithms I am completely confused by > the change. It seems different from how optimization function are > typically used and seems to be creating a barrier for no reason.
The reason is that the framework has been done for several uses, not only optimization. > > I am not clear why you can't just leave the standard interface to an > optimizer be a function that computes the value and the Jacobian (in > case of least-squares), the gradient (for quasi-Newton methods) and > if you actually have a full newton method, also the Hessian. > > If the user wants to compute the Jacobian (gradient) using finite > differences they can do it themselves, or wrap it into a class that > you can provide them that will compute finite differences using the > desired algorithm. This is already what many people do, and it can be done with both the older and the newer API. Nothing prevents users to use finite differences in the objects they pass to the optimizer. > > Also I can image a case when computation of the Jacobian can be sped > up if the function value is known, yet if you have two separate > functions handle the derivatives and the actual function value. For > example f^2(x). You can probably derive some kind of caching scheme, > but still. > > Maybe I am missing something, but I spend about an hour trying to > figure out how change my code to adapt to your new framework. Still > haven't figured it out. I can easily understand. It is really new and needs some polishing and documenting. I am sorry for that. In your case, if you already have two different functions, you can merge them to create a MultivariateDifferentiableVectorFunction and pass this to the optimizer. See how FunctionUtils.toMultivariateDifferentiableVectorFunctiontoMultivariateDifferentiableVectorFunction does it, starting from a DifferentiableMultivariateVectorFunction. See below about the deprecation of this converter method, though. Note that the new API is simply another way to represent the same information. The former way was limited to first derivatives and was really awkward when multiple dimensions were involved (as you derive with respect to several variables, a real function becomes a vector function (a gradient), a vector function becomes a matrix function and it becomes quickly untrackable. If you start thinking about second derivative, it is worse. It was also difficult when you combine functions, for example if you compute f(u), it looks like a univariate function, but if you see that u = g(x, y, z), it is really a multivariate function. When computing differentials, you have some problems pushing all partial differentials du/dx, du/dy, du/dz to the df/du function, there is a bottleneck. The only solution people had was to do the composition outside by themselves. The new API avoids that, it doesn care if u is a simple canonical variable or by itself a function from some former computations. For information, the original proposal from July about the differentiation framework is here: <http://mail-archives.apache.org/mod_mbox/commons-dev/201207.mbox/%3C500C2BBF.2020806%40spaceroots.org%3E>. > > On Nov 30, 2012, at 11:11 AM, Gilles Sadowski > <gil...@harfang.homelinux.org> wrote: > >> Hello. >> >> Context: >> 1. A user application computes the Jacobian of a >> multivariate vector function (the output of a simulation) using >> finite differences. >> 2. The covariance matrix is obtained from >> "AbstractLeastSquaresOptimizer". In the new API, the Jacobian is >> supposed to be "automatically" computed from the >> "MultivariateDifferentiableVectorFunction" objective function. >> 3. The converter from "toMultivariateDifferentiableVectorFunction" >> to "MultivariateDifferentiableVectorFunction" (in "FunctionUtils") >> is deprecated. It was both introduced in 3.1 and deprecated at the same time. It's not the converter per se which is considered wrong, it is the DifferentiableMultivariateVectorFunction interface which is deprecated, hence the converter using this interface is deprecated as a consequence. >> 4. A "FiniteDifferencesDifferentiator" operator currently exists >> but only for univariate functions. >> Unles I'm mistaken, a direct extension to multiple variables won't >> do: >> * because the implementation uses the symmetric formula, but in >> some cases (bounded parameter range), it will fail, and >> * because of the floating point representation of real values, the >> delta for sampling the function should depend on the magnitude of >> of the parameter value around which the sampling is done whereas >> the "stepSize" is constant in the implementation. >> >> Questions: >> 1. Shouldn't we keep the converters so that users can keep their >> "home-made" (first-order) derivative computations? [Converters >> exist for gradient of "DifferentiableMultivariateFunction" and >> Jacobian of "DifferentiableMultivariateVectorFunction".] We could decide to not deprecate the older interface and hence not deprecate these converters. We could also set up a converter that would not use a DifferentiableMultivariateVectorFunction but could use instead two parameters: one MultivariateVectorFunction and one MultivariateMatrixFunction. I'm not sure about this. I would really like to get rid of the former interface which is confusing as we introduced the new one. >> 2. Is it worth creating the multivariate equivalent of the >> univariate "FiniteDifferencesDifferentiator", assuming that higher >> orders will rarely be used because of >> * the loss of accuracy (as stated in the doc), and/or >> * the sometimes prohibitively expensive number of evaluations of >> the objective function? [1] Yes, I think it is worth doing, using separate step sizes for each components (as they may have very different behaviour and units). >> 3. As current CM optimization algorithms need only the gradient or >> Jacobian, would it be sufficient to only provide a limited >> (two-points first-order) finite differences operator (with the >> possiblity to choose either "symmetric", "forward" or "backward" >> formula for each parameter)? I'm not sure. As I explained above, the framework was not done with only the optimizers in mind (they are an important use of differentials, but are not the only one). This framework is also used on its own as a [math] feature, directly from user code. The underlying computation for derivatives using finite differences can be easily improved to use non-symmetric points, even for high order derivatives. It is sufficient to compute the abscissae correctly by changing the single line : final double xi = t0 + stepSize * (i - 0.5 * (nbPoints - 1)); Once the xi are computed, the remaining formulas are valid and they do not suppose the xi are around the point (they may even not be regularly spaced). The only constraint is that all xi are different from each other. So it would be possible to first add a enumerate : Formula with values CENTERED, BACKWARD, FORWARD as a constructor parameter to the existing univariate FiniteDifferencesDifferentiator and then to add another differentirator for multivariate functions, using an array of stepsized and an array of Formula enumerates so all components are computed according to their constraints. I think we could use the same number of points for all components, but it would also be possible to have a different number of points if needed. Would you like me to do that? Luc >> >> >> Best regards, Gilles >> >> [1] And this cost is somewhat "hidden" (as the >> "DerivativeStructure" is supposed to provide the derivatives for >> free, which is not true in this case). >> >> --------------------------------------------------------------------- >> >> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org >> For additional commands, e-mail: dev-h...@commons.apache.org >> > > > --------------------------------------------------------------------- > > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org