In our paper [Vollebregt2014b] we consider the quadratic program with simple bound constraints. We presented the algorithm (plain) BCCG as a straight-forward extension of the CG algorithm, and conjecture that it works always if the underlying system matrix is non-negative.
- The conjecture is presented in
[Vollebregt2014b]. E.A.H. Vollebregt. The Bound-Constrained Conjugate Gradients method for non-negative matrices. Journal of Optimization Theory and Applications, 2014, doi: 10.1007/s10957-013-0499-x.
- More details and the application to
CONTACT are shown in
[Vollebregt2014a]. E.A.H. Vollebregt. A new solver for the elastic normal contact problem using conjugate gradients, deflation, and an FFT-based preconditioner. Journal of Computational Physics, volume 257, pages 333-351, 2014.
Unfortunately, we've not been able to prove the conjecture ourselves. We could provide only circumstantial evidence:
- The algorithm works reliably in millions of 3x3 cases where all matrix elements are positive.
- The algorithm works reliably for the elastic normal contact problem.
The Prize Competition
We invite other researchers to test the method on their application, and thereby support or invalidate our conjecture. In order to stimulate these tests we present our Matlab implementation and start a small prize competition.
We award fame and glory and a gift certificate to persons that submit conclusive data on the working of BCCG for their test problem.
- The competition ends at once if someone provides a proof for the conjecture or a theorem that provides the circumstances under which BCCG is guaranteed to converge.
- The competition also ends directly when someone provides a counter example to the conjecture: a problem consisting of a non-negative matrix, right hand side and initial guess for which BCCG does not converge.
- In the two cases above, the reporting person receives the remaining portion of the prize money.
- A gift certificate of $100,= is awarded to those that contribute conclusive data for an application where the working of BCCG was not demonstrated before.
- The total prize money is $500,=. Gift certificates are deduced from this sum at most five times, after which only fame and glory remain.
March 2014: The original Matlab code produces NaN's for several small test-cases. The reason is that a subproblem can be solved exactly, after which division by zero occurred. A new version is provided that resolves such difficulties. A number of example cases and reference output are provided as well. Check out the download bccg_files.zip.
News related to this competition will be added to this page at irregular times. It will be sent out to a mailing list too, which will not be used for any other purposes. You can register to this mailing list by filling in the following form: