Issues affecting changes in line search methods

[timholy]

In an attempt to fix JuliaNLSolvers/LineSearches.jl#173 and JuliaNLSolvers/LineSearches.jl#175 (see JuliaNLSolvers/LineSearches.jl#180), I've concluded that the best option is to rewrite HagerZhang from scratch. I've actually done this, and the new implementation passes all the tests in LineSearches.jl.

However, many tests in Optim fail. Here's a to-be-updated list of issues that need discussion and/or resolution:

• some tests depend on every minor detail of the algorithms. In this case where we deliberately limit the number of iterations, the new implementation gets to a lower minimum with fewer function calls, and yet because of how that test is written it's counted as a failure. I've already addressed this one (it's easy).
• there are a ton of tests that have bespoke exceptions granted with no obvious rhyme or reason. One example:

  Optim.jl/test/multivariate/solvers/first_order/accelerated_gradient_descent.jl

  Lines 14 to 32 in 658c39a

  	# TODO: Check why skip problems fail
  	skip = ("Trigonometric", "Large Polynomial", "Parabola", "Paraboloid Random Matrix",
  	"Paraboloid Diagonal", "Extended Rosenbrock", "Penalty Function I", "Beale",
  	"Extended Powell",
  	)
  	run_optim_tests(AcceleratedGradientDescent();
  	skip = skip,
  	convergence_exceptions = (("Rosenbrock", 1),("Rosenbrock", 2)),
  	minimum_exceptions = (("Rosenbrock", 2),),
  	minimizer_exceptions = (("Rosenbrock", 2),),
  	iteration_exceptions = (("Powell", 1100),
  	("Rosenbrock", 10000),
  	("Polynomial", 1500),
  	("Fletcher-Powell", 10000),
  	("Extended Powell", 8000)),
  	f_increase_exceptions = ("Hosaki", "Polynomial", "Powell", "Himmelblau",
  	"Extended Powell", "Fletcher-Powell",
  	"Quadratic Diagonal", "Rosenbrock"),
  	show_name=debug_printing)#,

  The test/multivariate directory is full of examples like these. Since HagerZhang is the default line search algorithm, any subtle change can cause shifts in the things that require exceptions. I will wager that something things that previously failed will pass, and I know that some things that previously passed will fail. In the one case I've looked at in detail, it actually does reach the minimum, but it bounces around without triggering the convergence criterion. Somehow the old implementation happened to trigger it, but given the hand-granted exceptions I'm guessing that's more random than systematic.
  Proposed solutions:
  • echoing warn people that g_tol often needs to be set #1102, one option is that the convergence criteria should be part of the problem formulation, stored as a field in OptimizationProblem. Or at least, something that would allow you to compute problem-specific convergence criteria.
  • alternatively, perhaps we could compute the criteria from the Hessian evaluated at the minimum, if all the problems are in fact second-order differentiable. This doesn't adequately incorporate roundoff error (which can have a big impact), so it may not actually work in practice. Perhaps we could do something clever with IntervalArithmetic to estimate the impact of roundoff error, though again there are caveats.

I'd absolutely love some help with some of these. I could easily imagine spending a week just rationalizing the existing test suite, and that may stand in the way of actually fixing outstanding issues.

CC @mateuszbaran @kbarros @stevengj

[pkofod]

Yeah, that test setup is far from optimal. It basically only measures if given some options the solution found is no worse (or something close to that, cannot remember the exact setup).

[pkofod]

Is the re-implementation present anywhere?

[timholy]

JuliaNLSolvers/LineSearches.jl#180