[R] Testing optimization solvers with equality constraints

[J C Nash]

As someone who works on trying to improve the optimization codes in R,
though mainly in the unconstrained and bounds-constrained area, I think my
experience is more akin to that of HWB. That is, for some problems -- and
the example in question does have a reparametrization that removes the
constraint, so it could be considered artificial -- there seem to be
many more "bad" starting points than "good" ones. Abby's experience may
be very different, which is more or less the way things are in this type
of work. Or things will work for several years with a class of problems,
then the alligator of an unanticipated "bad" result will take a chunk out
of your posterior.

R users often have advanced expertise in different areas, so I suspect
a lot of cases involve using a poor parameterization. To my mind, the
real issue is less "the program should just work" than "the program
should let the user know there may be issues with the proposed solution".
Such diagnostics are very tricky to devise, and even more awkward to
implement in a way that doesn't become intrusive and time-wasting.
For example, in the optimx package, we can compute the KKT conditions
(first and second derivative checks on proposed solutions), but that
can often take many times the computing effort of finding the solution.
And when there are constraints, KKT conditions are less useful, since
they are for optima "not on the constraint".

This is going to be an ongoing challenge, and it affects a lot of areas
of work now that very complicated calculations are being carried out in
the name of AI and ML (either machine learning or maximum likelihood --
your choice). I'll welcome off-list ideas and efforts to devise better
diagnostics for proposed optimization solutions. We'll need them.

Best, John Nash


On 2021-05-24 10:47 p.m., Abby Spurdle wrote:
> I received an off-list email, questioning the relevance of my post.
> So, I thought I should clarify.
> 
> If an optimization algorithm is dependent on the starting point (or
> other user-selected parameters), and then fails to find the "correct"
> solution because the starting point (or other user-selected
> parameters) are unsuitable, then that, in itself, does not indicate a
> problem with the algorithm.
> 
> In other words, the R's packages listed in this thread appear to be
> working fine.
> (Or at least, there's no clear counter-evidence against).
> 
> One solution is to project the surface (here, equality constraints) on
> to lower dimensions, as already suggested.
> Another much simpler solution, is to use two algorithms, where one
> selects one or more starting points.
> (These could be the solution to an initial optimization, or chosen at
> random, or a combination of both).
> 
> Both of these approaches generalize to a broader set of problems.
> And I assume that there are other (possibly much better) approaches.
> However, that's an off-list discussion...
> 
> All and all, I would say R has extremely good numerical capabilities.
> Which are even more useful still, with the use of well chosen
> mathematical and statistical graphics.
> 
> 
> On Sun, May 23, 2021 at 5:25 PM Abby Spurdle <spurdle.a using gmail.com> wrote:
>>
>> For a start, there's two local minima.
>>
>> Add to that floating point errors.
>> And possible assumptions by the package authors.
>>
>> ----begin code----
>> f <- function (x, y, sign)
>> {   unsign.z <- sqrt (1 - x^2 - y^2)
>>     2 * (x^2 - sign * y * unsign.z)
>> }
>>
>> north.f <- function (x, y) f (x, y, +1)
>> south.f <- function (x, y) f (x, y, -1)
>>
>> N <- 100
>> p0 <- par (mfrow = c (1, 2) )
>> plotf_cfield (north.f, c (-1.1, 1.1),
>>     main="north",
>>     ncontours=10, n=N, raster=TRUE, hcv=TRUE)
>> plotf_cfield (south.f, c (-1.1, 1.1),
>>     main="south",
>>     ncontours=10, n=N, raster=TRUE, hcv=TRUE)
>> par (p0)
>> ----end code ----
>>
>> Please ignore R warnings.
>> I'm planning to reinvent this package soon.
>> And also, it wasn't designed for circular heatmaps.
>>
>>
>> On Sat, May 22, 2021 at 8:02 PM Hans W <hwborchers using gmail.com> wrote:
>>>
>>> Yes. "*on* the unit sphere" means on the surface, as you can guess
>>> from the equality constraint. And 'auglag()' does find the minimum, so
>>> no need for a special approach.
>>>
>>> I was/am interested in why all these other good solvers get stuck,
>>> i.e., do not move away from the starting point. And how to avoid this
>>> in general, not only for this specific example.
>>>
>>>
>>> On Sat, 22 May 2021 at 09:44, Abby Spurdle <spurdle.a using gmail.com> wrote:
>>>>
>>>> Sorry, this might sound like a poor question:
>>>> But by "on the unit sphere", do you mean on the ***surface*** of the sphere?
>>>> In which case, can't the surface of a sphere be projected onto a pair
>>>> of circles?
>>>> Where the cost function is reformulated as a function of two (rather
>>>> than three) variables.
>>>>
> 
> ______________________________________________
> R-help using r-project.org 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.
>