Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints
- PDF / 562,482 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 71 Downloads / 254 Views
Series B
Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints Sunyoung Kim1 · Masakazu Kojima2 · Kim-Chuan Toh3 Received: 13 March 2019 / Accepted: 4 November 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract We propose a doubly nonnegative (DNN) relaxation for polynomial optimization problems (POPs) with binary and box constraints. This work is an extension of the work by Kim, Kojima and Toh in 2016 from quadratic optimization problems to POPs. The dense and sparse DNN relaxations are reduced to a simple conic optimization problem (COP) to which an accelerated bisection and projection (BP) algorithm is applied. The COP involves a single equality constraint in a matrix variable which is restricted to the intersection of the positive semidefinite cone and a polyhedral cone representing the algebraic properties of binary and box constraints as well as the sparsity structure of the objective polynomial. Our DNN relaxation serves as a variant of the Lasserre moment-SOS hierarchy of relaxations for binary and box constrained POPs when the size of the cones is gradually increased to compute tighter lower bounds for their optimal values. A significant part of the paper is devoted to deriving and analyzing a class of polyhedral cones to strengthen the DNN relaxation, and the design of efficient computation of the metric projections onto these cones in the accelerated BP algorithm. Numerical results on various POPs are available in Ito et al. (ACM Trans Math Softw 45, Article 34, 2019). Keywords Polynomial optimization problems with nonnegative variables · Doubly nonnegative relaxations · A class of polyhedral cones · The bisection and projection algorithm · Computational efficiency and tight bounds Mathematics Subject Classification 90C22 · 90C25 · 90C26
S.K.: The research was supported by National Research Foundation of Korea (Grant Nos. 2017R1A2B2005119, 2014-R1A2A1A11049618). M.K.: This research was supported by Grant-in-Aid for Scientific Research (A) 26242027 and the Japan Science and Technology Agency (JST), the Core Research of Evolutionary Science and Technology (CREST) research project. K.-C.T.: This research was supported by Ministry of Education - Singapore (Grant No. R-146-000-257-112). Extended author information available on the last page of the article
123
S. Kim et al.
1 Introduction Consider a polynomial optimization problem (POP) that minimizes a real-valued polynomial f (x) in x ∈ Rn over a basic semi-algebraic subset of Rn . The problem serves as a fundamental nonconvex model in global optimization, notably, quadratic optimization problems (QOPs) with continuous and binary variables are its special cases. As a relaxation method for QOPs with nonnegative variables, the semidefinite programming (SDP) relaxation with the additional nonnegative constraint on the variable matrix, known as the doubly nonnegative (DNN) relaxation, was used in [8,9,28]. The DNN relaxation approach f
Data Loading...
