A Newton-bracketing method for a simple conic optimization problem
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 [to appear in ACM Tran. Softw., 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 \rightarrow R$ such that $g(y) = 0$ if $y \leq 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.
Keywords: Nonconvex quadratic optimization problems, conic relaxations, robust numerical algorithms, Newton-bracketing method, secant-bracketing method for generating valid bounds.
Category 1: Linear, Cone and Semidefinite Programming
Entry Submitted: 05/29/2019
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|