Add benchmark option maros_meszaros_dense_posdef for running dense convex problems only

[ottapav]

Please consider the feature of running only strictly convex problems, as some solvers can solve QP with strictly positive definite Hessian (P>0) only. If those solvers are running a complete set of problems, the results may look (unfairly) unattractive:

For example, ECOS warns that you cannot solve some of the problems in the command line:

[stephane-caron]

Yes, Maros-Meszaros problems are designed to be difficult so many problems are not strictly convex.

If it's relevant to your use case, it's totally possible to add a maros_meszaros_dense_posdef subset of the test set to the benchmark. You can take a look at how maros_meszaros_dense.py defines a

class MarosMeszarosDense(MarosMeszaros):

Similarly, a maros_meszaros_dense_posdef.py could define

class MarosMeszarosDensePosDef(MarosMeszarosDense):

And then wire this new test set up to benchmark.py at the root of the repository.

⚠️ Don't forget to indicate in the description all assumptions that make it a subset of the full Maros-Meszaros test set, e.g.

    @property
    def description(self) -> str:
        """Description of the test set."""
        return (
            "Subset of the Maros-Meszaros test set "
            "restricted to smaller dense problems "
            "and strictly positive definite Hessian matrices."
        )

In benchmarking, it is of prime importance to state the additional assumptions clearly when using subsets of well-known test sets.

[bodono]

You should be able to convert positive semi-definite matrices to second-order cone form too, using a Cholesky factorization where you throw away the zero columns (corresponding to zero eigenvalues). Ideally the timing to do this conversion would count towards the solvers total time, but that might be a pain.

[ottapav]

You should be able to convert positive semi-definite matrices to second-order cone form too, using a Cholesky factorization where you throw away the zero columns (corresponding to zero eigenvalues). Ideally the timing to do this conversion would count towards the solvers total time, but that might be a pain.

Does it mean there is a approximation from convex to strictly convex QP? That would be great! Second-order cone is a new topic for me. Can you suggest an ilustrating reference, please? I can possibly implement inside the solver...

[bodono]

I just mean that here for positive semi-definite matrices we could just use a different decomp (looks like numpy cholesky only supports positive definite, so would have to use something else like svd).

[stephane-caron]

For instance Eigen's Cholesky decompositions are available in Python via eigenpy, including the LDLT which doesn't require the matrix to be definite.

We could definitely make it available in qpsolvers to improve the interface for ECOS. I've opened an issue at qpsolvers/qpsolvers#179, I'll gladly help support a PR if somebody is willing to try it out.

[aescande]

Ideally the timing to do this conversion would count towards the solvers total time, but that might be a pain.

To me it is essential that it does, the problem being that it should not take into account the possible python overhead.

[stephane-caron]

Thanks for your feedback! Let's continue this discussion in #60 (ECOS) and #12 (all solvers).

Back to this issue's initial topic: adding a maros_meszaros_dense_posdef subset to focus on solvers that require strictly-convex problems (e.g. quadprog has this requirement).