A Newton-bracketing method for a simple conic optimization problem

Sunyoung Kim, Masakazu Kojima, Kim Chuan Toh

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 (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.

Original languageEnglish
Pages (from-to)1-18
Number of pages18
JournalOptimization Methods and Software
DOIs
StatePublished - 2020

Bibliographical note

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.

Keywords

  • conic relaxations
  • Newton-bracketing method
  • Nonconvex quadratic optimization problems
  • robust numerical algorithms
  • secant-bracketing method for generating valid bounds

Fingerprint

Dive into the research topics of 'A Newton-bracketing method for a simple conic optimization problem'. Together they form a unique fingerprint.

Cite this