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.

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

Emit warnings on invalid problems #78

Closed
ericphanson opened this issue Apr 24, 2019 · 5 comments
Closed

Emit warnings on invalid problems #78

ericphanson opened this issue Apr 24, 2019 · 5 comments
Labels
enhancement New feature or request

Comments

@ericphanson
Copy link
Contributor

It would be nice to emit a warning when e.g. P is not positive semi-definite. When the problem is put together through JuMP for example, it's not immediately clear how P is assembled, so you might not know whether or not P is PSD. From my JuMP model model I eventually could find P via

model.moi_backend.optimizer.model.optimizer.inner.p.P

and then check it's eigenvalues for example, but it would be nice if COSMO just emitted a warning when optimize! is called in such a case. In my example with my non-PSD P, it quickly reports it found an "optimal" solution and gives a valid feasible point as the solution, but since I know the true optimum in this case, I can see it's way off. Of course, COSMO isn't at fault since my problem doesn't fit the assumptions, but since optimal is such a strong word it would be nice if there was a warning to counter that.

@migarstka migarstka added the enhancement New feature or request label Apr 24, 2019
@migarstka
Copy link
Member

migarstka commented Apr 24, 2019

I think this is a good idea. I would like to keep the test outside the solver and have the check in the MOI-wrapper when the COSMO model is assembled.

One thing that I am unsure of is how to efficiently test if P is positive semidefinite symmetric. Julia only has a isposdef()function that doesn't account for a matrix P with zero-eigenvalues which COSMO allows.

Since P is handled as a sparse matrix there is currently no Julia Base function available that computes the eigenvalues of P without converting it to a full matrix. I would like to avoid the conversion since that could be potentially slow for very large problems.

eigs() could be used but has been moved to a separate package and I am not sure if it's worth adding an extra dependency just for that.

Edit: Until we find a better option: aeab91c

@ericphanson
Copy link
Contributor Author

ericphanson commented Apr 24, 2019

Thanks for the quick response! That seems helpful. Another idea would be to keep it entirely opt-in and provide some function

check_valid(::JuMP.AbstractModel)

and then at the start or end of the optimization (if in verbose mode) print something to tell the user that they can call check_valid on their model to verify the assumptions. That could get annoying though, since it would be printing every time.

edit: or instead of printing every time, maybe it would be enough to mention it in the docs

@goulart-paul
Copy link
Member

One thing that I am unsure of is how to efficiently test if P is positive semidefinite symmetric. Julia only has a isposdef()function that doesn't account for a matrix P with zero-eigenvalues which COSMO allows.

Since P is handled as a sparse matrix there is currently no Julia Base function available that computes the eigenvalues of P without converting it to a full matrix. I would like to avoid the conversion since that could be potentially slow for very large problems.

It is not necessary to do this, since semidefiniteness of P can be inferred from the inertia of the KKT matrix. The KKT matrix is quasidefinite and will have a number of positive pivots equal to the dimension of P as long as P is semidefinite (strictly speaking, the number of positive pivots should equal the number of positive eigenvalues in P+sigma*I). For an LDL factorisation, checking for convexity therefore amounts to counting the positive elements in D.

Both QDLDL and Pardiso report information about matrix inertia as a side effect of factorization. This is used to throw an error about problem non-convexity when using either solver in the pg/lin_solvers branch.

@goulart-paul
Copy link
Member

Edit: Until we find a better option: aeab91c

I think that this is not a good long-term solution, since P might be very large (or even just a Linear Map object). In cases where that's not true, we can catch indefiniteness as a side effect of the linear solves as explained above.

@migarstka
Copy link
Member

Since QDLDL is now the default KKT system solver, we get the semidefiniteness check of P for free. This wasn't the case before.

Relevant: #85

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

3 participants