A Newton-bracketing method for a simple conic optimization problem

For the Lagrangian-DNN relaxation of quadratic optimization problems (QOPs), we propose a Newton-bracketing method to improve the performance of the bisection-projection method implemented in BBCPOP [ACM Tran. Softw., 45(3):34 (2019)]. The relaxation problem is converted into the problem of finding the largest zero (Formula presented.) of a continuously differentiable (except at (Formula presented.)) convex function (Formula presented.) such that (Formula presented.) if (Formula presented.) and (Formula presented.) otherwise. In theory, the method generates lower and upper bounds of (Formula presented.) both converging to (Formula presented.). Their convergence is quadratic if the right derivative of g at (Formula presented.) is positive. Accurate computation of (Formula presented.) is necessary for the robustness of the method, but it is difficult to achieve in practice. As an alternative, we present a secant-bracketing method. We demonstrate that the method improves the quality of the lower bounds obtained by BBCPOP and SDPNAL+ for binary QOP instances from BIQMAC. Moreover, new lower bounds for the unknown optimal values of large scale QAP instances from QAPLIB are reported.