A Newton-bracketing method for a simple conic optimization problem
- 주제(키워드) Nonconvex quadratic optimization problems , conic relaxations , robust numerical algorithms , Newton-bracketing method , secant-bracketing method for generating valid bounds
- 주제(기타) Computer Science, Software Engineering
- 주제(기타) Operations Research & Management Science
- 주제(기타) Mathematics, Applied
- 설명문(일반) [Kim, Sunyoung] Ewha Womans Univ, Dept Math, 52 Ewhayeodae Gil, Seoul 120750, South Korea; [Kojima, Masakazu] Chuo Univ, Dept Ind & Syst Engn, Tokyo, Japan; [Toh, Kim-Chuan] Natl Univ Singapore, Dept Math, Singapore, Singapore; [Toh, Kim-Chuan] Natl Univ Singapore, Inst Operat Res & Analyt, Singapore, Singapore
- 관리정보기술 faculty
- 등재 SCIE, SCOPUS
- OA유형 Green Submitted
- 발행기관 TAYLOR & FRANCIS LTD
- 발행년도 2021
- 총서유형 Journal
- URI http://www.dcollection.net/handler/ewha/000000182520
- 본문언어 영어
- Published As http://dx.doi.org/10.1080/10556788.2020.1782906
초록/요약
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.
more