TY - JOUR
T1 - A Newton-bracketing method for a simple conic optimization problem
AU - Kim, Sunyoung
AU - Kojima, Masakazu
AU - Toh, Kim Chuan
N1 - Funding Information:
S. Kim's research has been supported by National Research Foundation of Korea - NRF 2017-R1A2B2005119; M. Kojima's research has been supported by Grants-in-Aid for Scientific Research (A) 19H00808 and K.-C. Toh's research has been supported in part by the Ministry of Education, Singapore, Academic Research Fund (Grant number: R-146-000-257-112).
Publisher Copyright:
© 2020, © 2020 Informa UK Limited, trading as Taylor & Francis Group.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - conic relaxations
KW - Newton-bracketing method
KW - Nonconvex quadratic optimization problems
KW - robust numerical algorithms
KW - secant-bracketing method for generating valid bounds
UR - http://www.scopus.com/inward/record.url?scp=85087592869&partnerID=8YFLogxK
U2 - 10.1080/10556788.2020.1782906
DO - 10.1080/10556788.2020.1782906
M3 - Article
AN - SCOPUS:85087592869
SP - 1
EP - 18
JO - Optimization Methods and Software
JF - Optimization Methods and Software
SN - 1055-6788
ER -