fides-dev/fides

Trust Region Optimization in Python

fides's Issues

exitflags

would be nice to report some more granular exitflag that can be analysed programmatically

Subspace indexing error

prevent errors when subspace is empty.

Optimization exceeds bounds

Bounds shouldn't be exceeded, something up with breakpoint identification?

Level of stopping criterion warnings

For various stopping criteria, a warning is raised upon hitting (https://github.com/fides-dev/fides/blob/master/fides/minimize.py#L530). This leads to quite verbose outputs when using fides in a multi-start setting or e.g. for profile calculation. I'd argue that stopping is quite a natural occurrence in an optimization, therefore not requiring the raising of a warning, but rather on the level of info, reducing the verbosity.

track minimum

would be nice to actively track minimum, not necessarily the final value

Don't require user to set dimension in HessianApproximation

state that fides is only for boundary constrained problems

Reduce logging

Many logging events are on level warning or info. I was wondering whether one wants to downgrade these one step, such that most are info or debug. Reason: In multistart settings, the generated output is rather long.

Alternatively, we would simply set the default log level for e.g. fides in pypesto to error or warning.

Using a modified Lanczos method instead of full factorization for large-scale problems?

Hi @FFroehlich !

Many thanks again for your implementation!
I just had an idea, what one might want to do in the case of using Fides on a really large-scale system, where complete factorization of the Hessian may become expensive (some k variables). A version of this method which can deal well with indefinite matrices is discussed by Stephen Nash.

This is anything but a request, it's rather a question whether this might be a meaningful add-on at some point...

Best!

Implement recursive reflection

moore-penrose pseudo-inverse can (rarely) fail due to nonconvergence

Improve multithreading compatibility

Looks like having a central module specific logger instance leads to excessive lock times even when logging is not displayed.

numpy RuntimeWarnings when specifing infinite bounds

Problem Description

In the docstring for the Optimizer class, you write that parameters without bounds should get -inf / inf.

When I do this, I get a lot of RuntimeWarnings in minimize.py:640.

Analysis

The relevant lines are 634 and 640:

        v = np.sign(self.grad) + (self.grad == 0)
        bounds = ((1 + v)*self.lb + (1 - v)*self.ub)/2

The RuntimeWarning stems not from the infinite values but from a np.nan that appears when multiplying 0*np.inf.
Here is an minimal example to see this:

import numpy as np

ub = np.array([3, 3, 3, np.inf])
lb = np.array([-np.inf, 0, 0, 0])

grad = np.array([-3, 0, 3, -3])
# v: -1 where grad < 0, 1 where grad >= 0
v = np.sign(grad) + (grad == 0)

# (1 + v) / 2 = [0, 1, 1, 0], (1 - v) / 2 = [1, 0, 0, 1]
summand1 = (1 + v) / 2 * lb  # 0 * -np.inf causes the runtime warning
summand2 = (1 - v) / 2 * ub

bounds = summand1 + summand2
bounds

If I understand your code right, you are implementing an if condition: Choose the lower bounds when the gradient is weakly positive and the upper bound otherwise.

However, there is one exception to this: when the not chosen bound is +/- inf. In that case your bounds are NaN which is what causes the RuntimeWarning.

Solution Proposal

If that NaN is not wanted, a one line solution that avoids the RuntimeWarning is np.where(grad<0, ub, lb). If that NaN is important you can still get the same behavior in three lines without triggering the Warning:

bounds2 = np.where(grad<0, ub, lb)
# you need the np.logical_and here because the arrays are numpy bools
bounds2[np.logical_and(grad<0, ~np.isfinite(lb))] = np.nan
bounds2[np.logical_and(grad>=0, ~np.isfinite(ub))] = np.nan

Specification

I am using the latest numpy: 1.21.4 and the latest Fides: 0.7.1

Optional parameter names

It would be great to have the possibility to pass parameter names to fides to produce more informative messages. E.g. having a parameter name in Exceeded lower bounds for indices [213] by [3.78577988e-16] at iteration 17. instead of the index would be quite helpful.

Brentq failure

brentq linesearch sometimes fails with f(a) and f(b) must have different signs, which shouldn't happen.

Add references

would be nice to have proper references in documentation. Use https://sphinxcontrib-bibtex.readthedocs.io/en/latest/usage.html ?

Fides does not find the correct solution fo a simple sum of squares problem with binding bounds

When minimizing a simple sum of squares function with partially binding bounds, fides fails to find the correct solution. It correctly converges to the boundaries in the dimensions where the bounds are binding but fails in the dimension without bounds. Instead of converging to setting x to 0 in that dimension, it converges to 0.59.

The convergence message is:

Stopping as function difference 9.77E-15 was smaller than specified tolerances (atol=1.00E-08, rtol=1.00E-08)

Here is a minimal working example:

from fides import Optimizer
import numpy as np
from fides import BFGS


def sum_of_squares(x):
    """Return function value and gradient of the sum of squares function."""
    fval = (x ** 2).sum()
    gradient = 2 * x
    return fval, gradient


lower_bounds = np.array([1, -np.inf, -np.inf])
upper_bounds = np.array([np.inf, np.inf, -1])
start_x = np.array([3, 2, -3])

true_solution = np.array([1, 0, -1])

opt = Optimizer(
    fun=sum_of_squares,
    lb=lower_bounds,
    ub=upper_bounds,
    hessian_update=BFGS(),
    resfun=False,
)

res = opt.minimize(start_x)

# Fides believes to have found the minimum
assert opt.converged

# fides_solution is [1.0000000000000233, 0.59204316173441, -1.0000000000000233]
fval, fides_solution, grad, hess = res

fides version: 0.6.3

Include a reference to the preprint

Might good to have a link to the preprint in the README, in order to make people cite it :)

https://www.biorxiv.org/content/10.1101/2021.05.20.445065v1