Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

ArpackNoConvergence: ARPACK error -1: No convergence (951 iterations, 0/1 eigenvectors converged) #544

Open
AveryLevin opened this issue Jun 28, 2023 · 1 comment · May be fixed by #543
Open

ArpackNoConvergence: ARPACK error -1: No convergence (951 iterations, 0/1 eigenvectors converged) #544

AveryLevin opened this issue Jun 28, 2023 · 1 comment · May be fixed by #543
Assignees
@88d52bdba0366127fffca9dfa93895
Labels
bug Something isn't working

Comments

@AveryLevin
Copy link

Describe the bug

There appears to be an underlying issue with how the CVXPY library checks that the matrix in the problem is Positive Semi-Definite. In short, CVXPY calls scipy.sparse.linalg.eigsh to determine if the min eigenvalue is negative, using Arnoldi Iteration. However, CVXPY relies on SciPy's default maxiter argument for eigsh which is simply the matrix's dimension multiplied by 10.

While it appears this heuristic works for smaller matrices, the larger ones can fail to converge within that max number of iterations. See the full stacktrace below for an example call to EfficientFrontier.min_volatility with a covariance matrix of 95 assets.

File "/usr/local/lib/python3.8/dist-packages/pypfopt/efficient_frontier/efficient_frontier.py", line 203, in min_volatility
    return self._solve_cvxpy_opt_problem()
  File "/usr/local/lib/python3.8/dist-packages/pypfopt/base_optimizer.py", line 307, in _solve_cvxpy_opt_problem
    self._opt.solve(
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/problems/problem.py", line 493, in solve
    return solve_func(self, *args, **kwargs)
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/problems/problem.py", line 1054, in _solve
    data, solving_chain, inverse_data = self.get_problem_data(
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/problems/problem.py", line 631, in get_problem_data
    solving_chain = self._construct_chain(
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/problems/problem.py", line 883, in _construct_chain
    return construct_solving_chain(self, candidate_solvers, gp=gp,
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/reductions/solvers/solving_chain.py", line 184, in construct_solving_chain
    reductions = _reductions_for_problem_class(problem, candidates, gp, solver_opts)
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/reductions/solvers/solving_chain.py", line 94, in _reductions_for_problem_class
    if not gp and not problem.is_dcp():
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/utilities/performance_utils.py", line 73, in _compute_once
    result = func(self, *args, **kwargs)
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/problems/problem.py", line 254, in is_dcp
    return all(
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/problems/problem.py", line 255, in <genexpr>
    expr.is_dcp(dpp) for expr in self.constraints + [self.objective])
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/problems/objective.py", line 153, in is_dcp
    return self.args[0].is_convex()
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/utilities/performance_utils.py", line 73, in _compute_once
    result = func(self, *args, **kwargs)
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/atoms/atom.py", line 176, in is_convex
    elif self.is_atom_convex():
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/atoms/quad_form.py", line 68, in is_atom_convex
    return P.is_constant() and P.is_psd()
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/utilities/performance_utils.py", line 73, in _compute_once
    result = func(self, *args, **kwargs)
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/expressions/constants/constant.py", line 222, in is_psd
    self._psd_test = eig_util.is_psd_within_tol(self.value, EIGVAL_TOL)
  File "/usr/local/lib/python3.8/dist-packages/cvxpy/utilities/linalg.py", line 96, in is_psd_within_tol
    raise sparla.ArpackNoConvergence(error_with_note, e.eigenvalues, e.eigenvectors)
scipy.sparse.linalg.eigen.arpack.arpack.ArpackNoConvergence: ARPACK error -1: ARPACK error -1: No convergence (951 iterations, 0/1 eigenvectors converged)


        CVXPY note: This failure was encountered while trying to certify
        that a matrix is positive semi-definite (see [1] for a definition).
        In rare cases, this method fails for numerical reasons even when the matrix is
        positive semi-definite. If you know that you're in that situation, you can
        replace the matrix A by cvxpy.psd_wrap(A).

        [1] https://en.wikipedia.org/wiki/Definite_matrix

Expected behavior

This problem seems to originate in CVXPY, but since the covariance matrices being sent to CVXPY are already checked for PSD, we can use the assume_PSD flag when calling cp.quad_form. I added this in my fork of this repo and have been using it without error for the past week.

I have opened a PR that adds this change: #543

Code sample

Since this issue appears most commonly with large matrices, the "minimal reproducible example" I could find was still quite large:
https://github.com/AveryLevin/PyPortfolioOpt/blob/PSD_check_fail/test_script/example/example_arpack_error.py

Operating system, python version, PyPortfolioOpt version

Ubuntu 20.04, python 3.8.10, PyPortfolioOpt 1.5.4
@AveryLevin AveryLevin added the bug Something isn't working label Jun 28, 2023
@AveryLevin AveryLevin linked a pull request Jun 28, 2023 that will close this issue
Open
@88d52bdba0366127fffca9dfa93895
Copy link
Collaborator

Great, let me check.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@88d52bdba0366127fffca9dfa93895 88d52bdba0366127fffca9dfa93895

Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Add the assume_PSD flag in calls to cvxpy.quad_form AveryLevin/PyPortfolioOpt
2 participants
@88d52bdba0366127fffca9dfa93895 @AveryLevin