A Newton-bracketing method for a simple conic optimization problem

Sunyoung Kim, Masakazu Kojima, Kim Chuan Toh

Research output: Contribution to journalArticlepeer-review

1 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

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