fides-dev/fides

Trust Region Optimization in Python

Fides - A python package for Trust Region Optimization

About Fides

Fides implements an Interior Trust Region Reflective for boundary constrained optimization problems based on the papers ColemanLi1994 and ColemanLi1996. Accordingly, Fides is named after the Roman goddess of trust and reliability.

Fides can be installed via pip install fides. Further documentation is available at Read the Docs.

Features

• Boundary constrained and unconstrained interior trust-region optimization
• Reflective, truncated and optimization based boundary heuristics
• Exact, 2D and CG subproblem solvers
• BFGS, DFP, SR1, Broyden (good and bad) and Broyden class iterative Hessian Approximation schemes
• SSM, TSSM, FX, GNSBFGS and custom hybrid Hessian Approximations schemes

fides's Issues

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

Optimization exceeds bounds

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

Implement recursive reflection

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!

Don't require user to set dimension in HessianApproximation

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

state that fides is only for boundary constrained problems

Brentq failure

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

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

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.

exitflags

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

track minimum

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

Improve multithreading compatibility

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

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.

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.

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

Subspace indexing error

prevent errors when subspace is empty.