search

JuliaSmoothOptimizers / OptimizationProblems.jl

Optimization Problems for Julia
Other
88 stars 48 forks source link

Discrepancies with other test suites #37

Open timholy opened 5 years ago

timholy commented 5 years ago

In #36 it was discovered that these implementations differ from CUTEst. In several cases that were checked by hand against the original paper, there were some errors in this package but also at least as many in CUTEst. Consequently one should be agnostic about how one interprets these. For the record (at the time of testing, Oct 12 2019, with 168 problems), here are the discrepancies:

A check mark means that someone has looked at the original paper and decided that the implementation here is correct, or that any discrepancies have been resolved. (Just checking against AMPL does not mean the paper has been checked.)

dpo commented 5 years ago

Screen Shot 2019-10-14 at 17 44 17

timholy commented 5 years ago

Looks like you can basically close this once that merges. Nice work!

dpo commented 5 years ago

Your script reports other discrepancies that we should investigate.

timholy commented 5 years ago

Some of those might be roundoff, but perhaps you've checked and concluded they are not. There was some manual triage, and in a couple of cases I was puzzled by what I found when I came back to it later, so possibly I got confused at some point.

danphenderson commented 3 years ago

The generalized Rosebrock function appears to differ from CUTEst by more than an offset of 1.0, as mentioned in the comments of genrose.jl.

My translation of Princeton's AMPL genrose.mod is

f = x -> begin
        N = lastindex(x)
        return 1.0 + 100sum((x[i] - x[i-1]^2)^2 for i = 2:N) + sum((x[i] - 1.0)^2 for i = 2:N)
end

which matches CUTEst (interfaced via CUTEst.jl) to a much higher precision than this repository's specification (while accounting for the shift of 1.0). Note, the difference in the summation indexing. Additionally, genrose.jl specifies the default dimension as 100 whereas GENROSE.SIF and AMPL have a default dimension of 500.

This has been rather concerning since most people think of the generalized Rosebrock as the chained rosenbrock from fletcher's article above. It appears that the CUTEst/AMPL specification yields an easier problem, from an empirical analysis of the critical structure of the two variants (in dimension n=2 to n=8).

The depth of my literature search was AMPL, and I have not dug into the original sources. (Which seems to be a futile pursuit by Dominque's comments in genrose.jl).

Has anyone else run across this discrepancy?

timholy commented 3 years ago

To be sure I understand you, the difference is the final sum over (x[i] - 1.0)^2, which runs in this package from 1:N-1 and in AMPL from 2:N? Or am I misreading something?

danphenderson commented 3 years ago

To be sure I understand you, the difference is the final sum over (x[i] - 1.0)^2, which runs in this package from 1:N-1 and in AMPL from 2:N? Or am I misreading something?

Correct! In the first summation it is a shift in indexing but not in the second.

timholy commented 3 years ago

Good. It would appear that this package has it correctly (by the article in https://github.com/JuliaSmoothOptimizers/OptimizationProblems.jl/issues/37#issuecomment-541971088), and that the Princeton AMPL needs to be corrected?

danphenderson commented 3 years ago

Good. It would appear that this package has it correctly (by the article in #37 (comment)) and that the Princeton AMPL needs to be corrected?

No, that is not what I was reporting. The comment in this repository's genrose.jl is wrong. Specifically, there is more of a difference from CUTEst than 1.0 offset. However, genrose.jl specifies a shifted variant of the generalized Rosebrock that everyone knows and loves. Whereas Princeton's AMPL specification of the generalized Rosebrock aligns with the CUTEst specification in the GENROSE.SIF file, which is different from what most people think it is.

So what are the goals of this repository? Is it to match CUTEst, or is it to specify the generalized Rosebrock that everyone knows? Regardless of the goals, the comment in this package's genrose.jl should be updated.

It is concerning that one of the most well known test problems in the CUTEr/st set is not what people think it is, and I believe it to be a slightly easier problem.

dpo commented 3 years ago

The AMPL problems are manual translations of the problems as they appeared in a relatively old version of the CUTE collection (in the late 1990s). I've never verified that they matched accurately.

The goal of this repository is not to reproduce exactly the problems of CUTEst. Many problems in this repository come from http://www.cs.cas.cz/matonoha/download/V1081.pdf, which is entitled "modified CUTE problems ...". It's certainly not impossible that there are bugs, though we tried to be careful. The comments are difficult to get right because no two papers give the same formulation of a "known" problem. Compare for example the two references in extrosnb.jl.

I wouldn't say that "most people" expect the generalized Rosenbrock function to be the chained Rosenbrock function. Over time, variations appeared. Sometimes they had different names, and sometimes not. We can certainly add variants to this repository.