You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Luc Maisonobe <Lu...@free.fr> on 2009/02/20 23:22:06 UTC
[math] optimization refactoring
Hello,
Since release of 1.2, several people have asked for advices on using the
estimation and optimization packages imported from mantissa. This showed
these packages were poorly designed (you can blame me for that). After
one of the discussions on this topic, issue MATH-177
(https://issues.apache.org/jira/browse/MATH-177) was set up to ask for a
refactoring. I also opened MATH-196
(https://issues.apache.org/jira/browse/MATH-196) for constrained
optimization, Gilles contributed Brent minimization (which was appended
to MATH-177 and committed recently in the analysis.minimization
package), and Benjamin contributed an implementation of Dantzig's
simplex method in MATH-246
((https://issues.apache.org/jira/browse/MATH-246).
As we are refactoring many packages for 2.0, I propose to refactor these
two packages too.
The existing code is :
- package o.a.c.math.analysis.minimization:
Brent minimization algorithm for univariate scalar valued functions
- package o.a.c.math.estimation:
Levenberg-Marquardt method for weighted least square minimization
of a vector of residuals
Gauss-Newton method for weighted least square minimization of a
vector of residuals
- package o.a.c.math.optimization:
Nelder-Mead simplex method for multivariate function minimization
without derivatives
Virginia Torczon's multidirectional method for multivariate
function minimization without derivatives
- attached to JIRA issue MATH-246
Dantzig's simplex method for linear systems with linear equality
and inequality constraints
Some generalization attempts have been made separately in estimation and
optimization with a few interfaces (EstimationProblem, Estimator on one
side CostFunction and ConvergenceChecker on the other side). These
interfaces seems difficult to understand to users. They were in fact
designed with a specific problem in mind (orbit determination for
spacecrafts to be precise) and are not generic enough.
Here is what I propose to do :
1) let Brent minimization in the analysis.minimization package where it
is now
2) gather everything else in a package hierarchy:
o.a.c.math.optimization with better interfaces (CostFunction may be
kept, the other should be replaced)
o.a.c.math.optimization.linear for Dantzig's simplex method
o.a.c.math.optimization.direct for direct search methods
(Nelder-Mead and Torczon)
o.a.c.math.optimization.general for everything else
3) some provisions should be made for constrained optimization in the
general case, but implementation could probably be delayed until 2.1
(the target revision for MATH-196 is already 2.1)
4) The fancy EstimatedParameter and WeightedMeasurements classes should
be dropped (i.e. deprecated) they do not belong to commons-math layer.
This is a major change. I think it is better for users to have an easy
to understand low level package rather than a big unusable bunch of
code. If this option is not chosen, it should be at least possible to
use the package at a lower level and provide these classes only as a
convenience for those whose needs fit well with this ad-hoc design.
5) the possibility to switch a parameter status between "should be
estimated" and "should not be touched at all" should be removed (I think
nobody ever realized it was possible)
6) the interfaces should define an optimization problem in terms of
simple structures (both double[] and RealVector) instead of the dropped
parameters and measurements objects.
7) the linear cost function and linear constraints should be specialized
interfaces extending more general cost and constraints interfaces from
the optimization package. This is mainly for consistency as I don't
expect many people will want to use a general solver for linear problems.
I have no idea yet of what the main interfaces should be. It is possible
nothing useful will be put in the upper level package except for
exceptions. I will have a look at this later, after we get an agreement
on the global structure and the level of service these packages should
provide.
Does this seems sensible ?
Luc
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] optimization refactoring
Posted by Ted Dunning <te...@gmail.com>.
I think that Dmitri overstates his case a bit.
This multiplication in observation space works for some algorithms, not for
others. Ordinary least squares regression is somewhat of an exception
here. Logistic regression is a simple counter-example.
It is still useful to have a vector weight and it helps users. It may be
useful in some situations to also all a full correlation matrix, but I
haven't had a need for that yet.
On Sun, Feb 22, 2009 at 11:24 AM, Dimitri Pourbaix <pourbaix@astro.ulb.ac.be
> wrote:
> Either one considers the full weighting matrix (including potential
> correlation between observations) or one does not account for any weight
> at all. By premultiplying both the function matrix and the observation
> vector by the square root of the weight matrix, one can forget about it
> completely in the rest of the computation.
>
--
Ted Dunning, CTO
DeepDyve
Re: [math] optimization refactoring
Posted by Dimitri Pourbaix <po...@astro.ulb.ac.be>.
Hi,
> The existing code is :
> - package o.a.c.math.estimation:
> Levenberg-Marquardt method for weighted least square minimization
> of a vector of residuals
Either one considers the full weighting matrix (including potential
correlation between observations) or one does not account for any weight
at all. By premultiplying both the function matrix and the observation
vector by the square root of the weight matrix, one can forget about it
completely in the rest of the computation. So, please, do not restrain
weights to a vector.
Regards,
Dim.
----------------------------------------------------------------------------
Dimitri Pourbaix *
Institut d'Astronomie et d'Astrophysique * Don't worry, be happy
CP 226, office 2.N4.211, building NO * and CARPE DIEM.
Universite Libre de Bruxelles *
Boulevard du Triomphe * Tel : +32-2-650.35.71
B-1050 Bruxelles * Fax : +32-2-650.42.26
http://sb9.astro.ulb.ac.be/~pourbaix * mailto:pourbaix@astro.ulb.ac.be
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] optimization refactoring
Posted by chengas123 <be...@gmail.com>.
Luc Maisonobe wrote:
>
>>> 1) let Brent minimization in the analysis.minimization package where it
>>> is now
>>>
>> Why not include this in optimization.general below?
> Gilles proposed to put it in analysis a few weeks ago, on the assumption
> it is strongly related to roots finding. Of course, it is related to
> optimization too, so both approaches are logical. In the later case, I
> would prefer a dedicated package optimization.univariate rather than
> optimization.general.
>
I like the idea of optimization.univariate as well since it is more specific
- the user knows exactly what they will find in that package.
--
View this message in context: http://www.nabble.com/-math--optimization-refactoring-tp22129628p22149219.html
Sent from the Commons - Dev mailing list archive at Nabble.com.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] optimization refactoring
Posted by Luc Maisonobe <Lu...@free.fr>.
Phil Steitz a écrit :
> Luc Maisonobe wrote:
>> Hello,
>>
>> Since release of 1.2, several people have asked for advices on using the
>> estimation and optimization packages imported from mantissa. This showed
>> these packages were poorly designed (you can blame me for that). After
>> one of the discussions on this topic, issue MATH-177
>> (https://issues.apache.org/jira/browse/MATH-177) was set up to ask for a
>> refactoring. I also opened MATH-196
>> (https://issues.apache.org/jira/browse/MATH-196) for constrained
>> optimization, Gilles contributed Brent minimization (which was appended
>> to MATH-177 and committed recently in the analysis.minimization
>> package), and Benjamin contributed an implementation of Dantzig's
>> simplex method in MATH-246
>> ((https://issues.apache.org/jira/browse/MATH-246).
>>
>> As we are refactoring many packages for 2.0, I propose to refactor these
>> two packages too.
>>
>> The existing code is :
>> - package o.a.c.math.analysis.minimization:
>> Brent minimization algorithm for univariate scalar valued functions
>> - package o.a.c.math.estimation:
>> Levenberg-Marquardt method for weighted least square minimization
>> of a vector of residuals
>> Gauss-Newton method for weighted least square minimization of a
>> vector of residuals
>> - package o.a.c.math.optimization:
>> Nelder-Mead simplex method for multivariate function minimization
>> without derivatives
>> Virginia Torczon's multidirectional method for multivariate
>> function minimization without derivatives
>> - attached to JIRA issue MATH-246
>> Dantzig's simplex method for linear systems with linear equality
>> and inequality constraints
>>
>> Some generalization attempts have been made separately in estimation and
>> optimization with a few interfaces (EstimationProblem, Estimator on one
>> side CostFunction and ConvergenceChecker on the other side). These
>> interfaces seems difficult to understand to users.
> I agree here.
>> They were in fact
>> designed with a specific problem in mind (orbit determination for
>> spacecrafts to be precise) and are not generic enough.
>>
>> Here is what I propose to do :
>>
>> 1) let Brent minimization in the analysis.minimization package where it
>> is now
>>
> Why not include this in optimization.general below?
Gilles proposed to put it in analysis a few weeks ago, on the assumption
it is strongly related to roots finding. Of course, it is related to
optimization too, so both approaches are logical. In the later case, I
would prefer a dedicated package optimization.univariate rather than
optimization.general.
>> 2) gather everything else in a package hierarchy:
>> o.a.c.math.optimization with better interfaces (CostFunction may be
>> kept, the other should be replaced)
>> o.a.c.math.optimization.linear for Dantzig's simplex method
>> o.a.c.math.optimization.direct for direct search methods
>> (Nelder-Mead and Torczon)
>> o.a.c.math.optimization.general for everything else
>>
>> 3) some provisions should be made for constrained optimization in the
>> general case, but implementation could probably be delayed until 2.1
>> (the target revision for MATH-196 is already 2.1)
>>
>> 4) The fancy EstimatedParameter and WeightedMeasurements classes should
>> be dropped (i.e. deprecated) they do not belong to commons-math layer.
>> This is a major change. I think it is better for users to have an easy
>> to understand low level package rather than a big unusable bunch of
>> code. If this option is not chosen, it should be at least possible to
>> use the package at a lower level and provide these classes only as a
>> convenience for those whose needs fit well with this ad-hoc design.
>>
> +1
>> 5) the possibility to switch a parameter status between "should be
>> estimated" and "should not be touched at all" should be removed (I think
>> nobody ever realized it was possible)
>>
> +0 but I don't think I ever really understood the use cases here. If
> there is real practical loss of functionality, we should think carefully
> about this.
The original use case was to allow users to try solving a problem first
with a set of parameters and later with another set, some parameters
being preset to a fixed value. There is a simpler way for users to
recover the same functionality without this difficult to understand
feature : rebuild the parameters array with a different size in the
object representing the problem. This is also safer since once the array
is provided to the solver, it is not expect to change size. The current
code allow to switch a parameter from bound to free without restriction,
even during the run of the solver, which do not expect that. I'm sure
this may trigger lots of bugs.
>> 6) the interfaces should define an optimization problem in terms of
>> simple structures (both double[] and RealVector) instead of the dropped
>> parameters and measurements objects.
>>
> +1 - this is a general topic that applies to other areas of the API as
> well. I used to think differently, but my own use cases and user
> comments have convinced me that this approach is both easier to
> understand and easier to use.
>> 7) the linear cost function and linear constraints should be specialized
>> interfaces extending more general cost and constraints interfaces from
>> the optimization package. This is mainly for consistency as I don't
>> expect many people will want to use a general solver for linear problems.
>>
> Do we need the hierarchy, then? Per comment above, we should make it as
> easy as possible for people to find their way to the best, simplest way
> to solve their problems using the API.
This is really for consistency. It helps someone who has understood one
package (say optimization.general) to understand the other one by seeing
specialized implementations of interfaces he already knows. This also
prevents questions like : "these classes seem to be similar, why don't
they implement this interface ?"
Luc
>
> Phil
>
>> I have no idea yet of what the main interfaces should be. It is possible
>> nothing useful will be put in the upper level package except for
>> exceptions. I will have a look at this later, after we get an agreement
>> on the global structure and the level of service these packages should
>> provide.
>>
>> Does this seems sensible ?
>>
>> Luc
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] optimization refactoring
Posted by Phil Steitz <ph...@gmail.com>.
Luc Maisonobe wrote:
> Hello,
>
> Since release of 1.2, several people have asked for advices on using the
> estimation and optimization packages imported from mantissa. This showed
> these packages were poorly designed (you can blame me for that). After
> one of the discussions on this topic, issue MATH-177
> (https://issues.apache.org/jira/browse/MATH-177) was set up to ask for a
> refactoring. I also opened MATH-196
> (https://issues.apache.org/jira/browse/MATH-196) for constrained
> optimization, Gilles contributed Brent minimization (which was appended
> to MATH-177 and committed recently in the analysis.minimization
> package), and Benjamin contributed an implementation of Dantzig's
> simplex method in MATH-246
> ((https://issues.apache.org/jira/browse/MATH-246).
>
> As we are refactoring many packages for 2.0, I propose to refactor these
> two packages too.
>
> The existing code is :
> - package o.a.c.math.analysis.minimization:
> Brent minimization algorithm for univariate scalar valued functions
> - package o.a.c.math.estimation:
> Levenberg-Marquardt method for weighted least square minimization
> of a vector of residuals
> Gauss-Newton method for weighted least square minimization of a
> vector of residuals
> - package o.a.c.math.optimization:
> Nelder-Mead simplex method for multivariate function minimization
> without derivatives
> Virginia Torczon's multidirectional method for multivariate
> function minimization without derivatives
> - attached to JIRA issue MATH-246
> Dantzig's simplex method for linear systems with linear equality
> and inequality constraints
>
> Some generalization attempts have been made separately in estimation and
> optimization with a few interfaces (EstimationProblem, Estimator on one
> side CostFunction and ConvergenceChecker on the other side). These
> interfaces seems difficult to understand to users.
I agree here.
> They were in fact
> designed with a specific problem in mind (orbit determination for
> spacecrafts to be precise) and are not generic enough.
>
> Here is what I propose to do :
>
> 1) let Brent minimization in the analysis.minimization package where it
> is now
>
Why not include this in optimization.general below?
> 2) gather everything else in a package hierarchy:
> o.a.c.math.optimization with better interfaces (CostFunction may be
> kept, the other should be replaced)
> o.a.c.math.optimization.linear for Dantzig's simplex method
> o.a.c.math.optimization.direct for direct search methods
> (Nelder-Mead and Torczon)
> o.a.c.math.optimization.general for everything else
>
> 3) some provisions should be made for constrained optimization in the
> general case, but implementation could probably be delayed until 2.1
> (the target revision for MATH-196 is already 2.1)
>
> 4) The fancy EstimatedParameter and WeightedMeasurements classes should
> be dropped (i.e. deprecated) they do not belong to commons-math layer.
> This is a major change. I think it is better for users to have an easy
> to understand low level package rather than a big unusable bunch of
> code. If this option is not chosen, it should be at least possible to
> use the package at a lower level and provide these classes only as a
> convenience for those whose needs fit well with this ad-hoc design.
>
+1
> 5) the possibility to switch a parameter status between "should be
> estimated" and "should not be touched at all" should be removed (I think
> nobody ever realized it was possible)
>
+0 but I don't think I ever really understood the use cases here. If
there is real practical loss of functionality, we should think carefully
about this.
> 6) the interfaces should define an optimization problem in terms of
> simple structures (both double[] and RealVector) instead of the dropped
> parameters and measurements objects.
>
+1 - this is a general topic that applies to other areas of the API as
well. I used to think differently, but my own use cases and user
comments have convinced me that this approach is both easier to
understand and easier to use.
> 7) the linear cost function and linear constraints should be specialized
> interfaces extending more general cost and constraints interfaces from
> the optimization package. This is mainly for consistency as I don't
> expect many people will want to use a general solver for linear problems.
>
Do we need the hierarchy, then? Per comment above, we should make it as
easy as possible for people to find their way to the best, simplest way
to solve their problems using the API.
Phil
> I have no idea yet of what the main interfaces should be. It is possible
> nothing useful will be put in the upper level package except for
> exceptions. I will have a look at this later, after we get an agreement
> on the global structure and the level of service these packages should
> provide.
>
> Does this seems sensible ?
>
> Luc
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org