el0ps.solver.BoundSolver¶

class el0ps.solver.BoundSolver(iter_limit=None, relative_tol=0.0001, workingset=True, dualpruning=True, screening=True, simpruning=True)¶

Bounding solver for the BnbSolver.

The solver solves convex optimization problems of the form

\[\textstyle\min_{\mathbf{x} \in \mathbb{R}^{n}} f(\mathbf{Ax}) + g(\mathbf{x})\]

where \(f\) is a el0ps.datafit.BaseDatafit function, \(\mathbf{A} \in \mathbb{R}^{m \times n}\) is a matrix, \(g\) is a regularization function that depends on the current node treated by the BnbSolver solver. The problem is solved using a coordinate-descent method, potentially combined with an active-set strategy.

Parameters:

iter_limit: int, default=sys.maxsize: Maximum number of iterations for the inner solver.
relative_tol: float, default=1e-4: Relative tolerance on the problem objective value.
workingset: bool, default=True: Toggle the use of a working-set method.
dualpruning: bool, default=True: If True, the solver checks after each working-set update if the dual bound is greater than the best upper bound known during the Branch-and-Bound algorithm. If so, the node currently treated is pruned. See “Techniques for accelerating Branch-and-Bound algorithms dedicated to sparse optimization” by G. Samain et al. for more details.
screening: bool, default=True: If True, the solver performs screening tests after each working-set update to identify variables that can be fixed to zero to reduce the computational load. See “One to beat them all: RYU–a unifying framework for the construction of safe balls” by T.L. Tran et al. for more details. Only works if the loss function has a gradient with finite Lipschitz constant.
simpruning: bool, default=True: If True, the solver performs simultaneous pruning tests after each working-set update. This allows to identify new branchings that can be performed on the current node. This in done in-place during the bounding process. See “A New Branch-and-bound pruning framework for L0-regularized problems” by T. Guyard et al. for more details.

__init__(iter_limit=None, relative_tol=0.0001, workingset=True, dualpruning=True, screening=True, simpruning=True)¶

Methods

`__init__`([iter_limit, relative_tol, ...])
`bound`(datafit, penalty, A, lmbd, S0, S1, Sb, ...)	Solve the bounding problem.
`get_spec`()	Specify the numba types of the class attributes.
`inner_loop`(datafit, penalty, A)
`inner_stopping_criterion`()
`outer_stopping_criterion`()
`params_to_dict`()	Returns the parameters name and value used to initialize the class instance.
`screening_tests`(datafit, A)
`setup`(datafit, penalty, A, lmbd)	Setup the bounding solver with problem data.
`simpruning_tests`(datafit, penalty, A, lmbd)
`update_dv`(datafit, penalty, A, lmbd)
`update_pv`(datafit, penalty, lmbd)
`workingset_update`(A)