90C26 Nonconvex programming, global optimization
Refine
Year of publication
Document Type
- ZIB-Report (22)
- Doctoral Thesis (2)
Is part of the Bibliography
- no (24)
Keywords
- Pooling Problem (4)
- nonconvex (3)
- Cutting Planes (2)
- Large Neighborhood Search (2)
- MINLP (2)
- Nonconvexity (2)
- Primal Heuristic (2)
- Quadratic Programming (2)
- Relaxation (2)
- Relaxations (2)
- Standard Quadratic Programming (2)
- global optimization (2)
- mixed-integer quadratically constrained programming (2)
- Computations (1)
- Decomposition (1)
- Extreme Points (1)
- Feasibility Pump (1)
- Gas Network Planning (1)
- Intersection cuts (1)
- LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl (1)
- MINLP, global optimization, operative planning, water supply networks (1)
- MIP (1)
- MIQCP (1)
- Mixed Integer Nonlinear Programming (1)
- Mixed-Integer Quadratically Constrained Programming (1)
- Mixed-Integer Nonlinear Programming (1)
- Nonconvex Optimization (1)
- OBBT (1)
- QCQPs (1)
- Quadratic-free sets (1)
- Robust Optimization (1)
- SCIP, MIP, MINLP, CIP, LP, modeling, optimization (1)
- Uncertainty (1)
- Valid Inequalities (1)
- bivariate functions (1)
- branch-and-cut (1)
- branching rule (1)
- computational (1)
- constraint integer programming (1)
- convex envelope (1)
- convex relaxation (1)
- large neighborhood search (1)
- linear underestimator (1)
- mixed integer nonlinear programming (1)
- mixed integer programming (1)
- mixed integer quadratically constrained programming (1)
- mixed-integer programming (1)
- optimality-based bound tightening (1)
- optimization-based bound tightening (1)
- perspective cuts, mixed-integer nonlinear programming, nonconvex optimization, computational study (1)
- primal heuristic (1)
- propagation (1)
- solver software (1)
Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into alternative certificates and approaches to global optimization. We consider sums of nonnegative circuit polynomials (SONC) certificates, which are well-suited for sparse problems since the computational cost depends on the number of terms in the polynomials and does not depend on the degrees of the polynomials. We propose a method that guarantees that given finite variable domains, a SONC relaxation will yield a finite dual bound. This method opens up a new approach to utilizing variable bounds in SONC-based methods, which is particularly crucial for integrating SONC relaxations into branch-and-bound algorithms. We report on computational experiments with incorporating SONC relaxations into the spatial branch-and-bound algorithm of the mixed-integer nonlinear programming framework SCIP. Applying our strengthening method increases the number of instances where the SONC relaxation of the root node yielded a finite dual bound from 9 to 330 out of 349 instances in the test set.