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

[AveryLevin]

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

[88d52bdba0366127fffca9dfa93895]

Great, let me check.