A Newton-bracketing method for a simple conic optimization problem. (4th May 2021)

• Record Type: Journal Article
• Authors: Kim, Sunyoung; Kojima, Masakazu; Toh, Kim-Chuan
• Is Part Of: Optimization methods and software. Volume 36:Number 2/3(2021)
• Page Start: 371
• Page End: 388
• Publication Date: 2021-05-04
• Subjects: Nonconvex quadratic optimization problems -- conic relaxations -- robust numerical algorithms -- Newton-bracketing method -- secant-bracketing method for generating valid bounds; 90C20 -- 90C22 -- 90C25; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1782906
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : 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 y ∗ of a continuously differentiable (except at y ∗ ) convex function g : R → R such that g ( y ) = 0 if y ≤ y ∗ and g ( y ) > 0 otherwise. In theory, the method generates lower and upper bounds of y ∗ both converging to y ∗ . Their convergence is quadratic if the right derivative of g at y ∗ is positive. Accurate computation of g ′ ( y ) 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.