Testing optimization solvers with equality constraints

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Testing optimization solvers with equality constraints

Hans W Borchers-2
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

mark leeds
Hi Hans: I think  that you are missing minus signs in the 2nd and 3rd
elements of your gradient.
Also, I don't know how all of the optimixation functions work as far as
their arguments but it's best to supply
the gradient when possible. I hope it helps.






On Fri, May 21, 2021 at 11:01 AM Hans W <[hidden email]> wrote:

> Just by chance I came across the following example of minimizing
> a simple function
>
>     (x,y,z) --> 2 (x^2 - y z)
>
> on the unit sphere, the only constraint present.
> I tried it with two starting points, x1 = (1,0,0) and x2 = (0,0,1).
>
>     #-- Problem definition in R
>     f = function(x)  2 * (x[1]^2 - x[2]*x[3])   # (x,y,z) |-> 2(x^2 -yz)
>     g = function(x)  c(4*x[1], 2*x[3], 2*x[2])  # its gradient
>
>     x0 = c(1, 0, 0); x1 = c(0, 0, 1)            # starting points
>     xmin = c(0, 1/sqrt(2), 1/sqrt(2))           # true minimum -1
>
>     heq = function(x)  1-x[1]^2-x[2]^2-x[3]^2   # staying on the sphere
>     conf = function(x) {                        # constraint function
>         fun = x[1]^2 + x[2]^2 + x[3]^2 - 1
>         return(list(ceq = fun, c = NULL))
>     }
>
> I tried all the nonlinear optimization solvers in R packages that
> allow for equality constraints: 'auglag()' in alabama, 'solnl()' in
> NlcOptim, 'auglag()' in nloptr, 'solnp()' in Rsolnp, or even 'donlp2()'
> from the Rdonlp2 package (on R-Forge).
>
> None of them worked from both starting points:
>
>     # alabama
>     alabama::auglag(x0, fn = f, gr = g, heq = heq)  # right (inaccurate)
>     alabama::auglag(x1, fn = f, gr = g, heq = heq)  # wrong
>
>     # NlcOptim
>     NlcOptim::solnl(x0, objfun = f, confun = conf)  # wrong
>     NlcOptim::solnl(x1, objfun = f, confun = conf)  # right
>
>     # nloptr
>     nloptr::auglag(x0, fn = f, heq = heq)           # wrong
>     # nloptr::auglag(x1, fn = f, heq = heq)         # not returning
>
>     # Rsolnp
>     Rsolnp::solnp(x0, fun = f, eqfun = heq)         # wrong
>     Rsolnp::solnp(x1, fun = f, eqfun = heq)         # wrong
>
>     # Rdonlp2
>     Rdonlp2::donlp2(x0, fn = f, nlin = list(heq),   # wrong
>            nlin.lower = 0, nlin.upper = 0)
>     Rdonlp2::donlp2(x1, fn = f, nlin = list(heq),   # right
>            nlin.lower = 0, nlin.upper = 0)          # (fast and exact)
>
> The problem with starting point x0 appears to be that the gradient at
> that point, projected onto the unit sphere, is zero. Only alabama is
> able to handle this somehow.
>
> I do not know what problem most solvers have with starting point x1.
> The fact that Rdonlp2 is the fastest and most accurate is no surprise.
>
> If anyone with more experience with one or more of these packages can
> give a hint of what I made wrong, or how to change calling the solver
> to make it run correctly, please let me know.
>
> Thanks  -- HW
>
> ______________________________________________
> [hidden email] mailing list -- To UNSUBSCRIBE and more, see
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>

        [[alternative HTML version deleted]]

______________________________________________
[hidden email] mailing list -- To UNSUBSCRIBE and more, see
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

Hans W Borchers-2
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

mark leeds
Hi Hans: I can't help as far as the projection of the gradient onto the
constraint but it may give insight just to see what the value of
the gradient itself is when the optimization stops.

John Nash ( definitely one of THE expeRts when it comes to optimization in
R )
often strongly recommends  to supply gradients so I'm   not sure what those
functions are
doing that don't allow it as an argument. I guess some numerical
approximation.

Hopefully John or Ravi will chime in with their expertise when they see
this posting.


Mark

P.S: You may want to try Rvminb. John wrote that one and it allows for
constraints ( I remember it
working nicely  for me when I had problems with some other ones but I don't
remember which ones ) but
I'm not certain  whether it can handle equalities.






On Fri, May 21, 2021 at 2:06 PM Hans W <[hidden email]> wrote:

> Mark, you're right, and it's a bit embarrassing as I thought I had
> looked at it closely enough.
>
> This solves the problem for 'alabama::auglag()' in both cases, but NOT for
>
>   * NlcOptim::solnl     -- with x0
>   * nloptr::auglag      -- both x0, x1
>   * Rsolnp::solnp       -- with x0
>   * Rdonlp::donlp2      -- with x0
>
> as for these solver calls the gradient function g was *not* used.
>
> Actually, 'solnl()' and 'solnp()' do not allow a gradient argument,
> 'nloptr::auglag()' says it does not use a supplied gradient, and
> 'donlp2' again does not provide it.
> Gradients, if needed, are computed internally which in most cases is
> sufficient, anyway.
>
> So the question remains:
> Is the fact that the projection of the gradient onto the constraint is
> zero, is this the reason for the solvers not finding the minimum?
>
> And how to avoid this? Except, maybe, checking the gradient for all
> the given constraints
>
> Thanks  --HW
>
>
>
> On Fri, 21 May 2021 at 17:58, Mark Leeds <[hidden email]> wrote:
> >
> > Hi Hans: I think  that you are missing minus signs in the 2nd and 3rd
> elements of your gradient.
> > Also, I don't know how all of the optimixation functions work as far as
> their arguments but it's best to supply
> > the gradient when possible. I hope it helps.
> >
>

        [[alternative HTML version deleted]]

______________________________________________
[hidden email] mailing list -- To UNSUBSCRIBE and more, see
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

J C Nash
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

Abbs Spurdle
In reply to this post by Hans W Borchers-2
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

Hans W Borchers-2
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

Abbs Spurdle
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

Abbs Spurdle
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

Abbs Spurdle
In reply to this post by Abbs Spurdle
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

J C Nash
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

Abbs Spurdle
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

Abbs Spurdle
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

Abbs Spurdle
CONTENTS DELETED
The author has deleted this message.
Reply | Threaded
Open this post in threaded view
|

Re: Testing optimization solvers with equality constraints

Gabor Grothendieck
In reply to this post by Hans W Borchers-2
CONTENTS DELETED
The author has deleted this message.