A reformulation-convexification approach for solving nonconvex quadratic programming problems

DOI10.1007/BF01100203zbMath0844.90064MaRDI QIDQ1905961

Hanif D. Sherali, Cihan H. Tuncbilek

Publication date: 8 February 1996

Published in: Journal of Global Optimization (Search for Journal in Brave)

zbMATH Keywords

outer-approximationslinearly constrained nonconvex quadratic programmingreformulation-linearization/convexification techniquetight linear programming relaxations

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Quadratic programming (90C20)

Related Items (63)

Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods ⋮ Global optimization with spline constraints: a new branch-and-bound method based on B-splines ⋮ Conic mixed-integer rounding cuts ⋮ Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO ⋮ Computable representations for convex hulls of low-dimensional quadratic forms ⋮ A parametric linearizing approach for quadratically inequality constrained quadratic programs ⋮ Utility function programs and optimization over the efficient set in multiple-objective decision making ⋮ A robust algorithm for quadratic optimization under quadratic constraints ⋮ On generalized geometric programming problems with non-positive variables ⋮ Generating cutting planes for the semidefinite relaxation of quadratic programs ⋮ New reformulation linearization/convexification relaxations for univariate and multivariate polynomial programming problems ⋮ GLOMIQO: global mixed-integer quadratic optimizer ⋮ A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity ⋮ Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach ⋮ A new global optimization algorithm for signomial geometric programming via Lagrangian relaxation ⋮ Branch-delete-bound algorithm for globally solving quadratically constrained quadratic programs ⋮ A reformulation-linearization based algorithm for the smallest enclosing circle problem ⋮ Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations ⋮ Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2 ⋮ A framework for globally optimizing mixed-integer signomial programs ⋮ Branch and cut algorithms for detecting critical nodes in undirected graphs ⋮ Dynamic Lagrangian dual and reduced RLT constructs for solving \(0-1\) mixed-integer programs ⋮ A global optimization using linear relaxation for generalized geometric programming ⋮ A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming ⋮ A reformulation-linearization technique for optimization over simplices ⋮ New bounds for nonconvex quadratically constrained quadratic programming ⋮ Canonical Duality-Triality Theory: Unified Understanding for Modeling, Problems, and NP-Hardness in Global Optimization of Multi-Scale Systems ⋮ Reduced RLT representations for nonconvex polynomial programming problems ⋮ Linear programing relaxations for a strategic pricing problem in electricity markets ⋮ Nonlinear robust optimization via sequential convex bilevel programming ⋮ A canonical dual approach for solving linearly constrained quadratic programs ⋮ Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation ⋮ Enhancing RLT-based relaxations for polynomial programming problems via a new class of \(v\)-semidefinite cuts ⋮ A global optimization algorithm for signomial geometric programming problem ⋮ Global optimization of signomial geometric programming using linear relaxation. ⋮ Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations ⋮ A novel optimization method for nonconvex quadratically constrained quadratic programs ⋮ A note on representations of linear inequalities in non-convex mixed-integer quadratic programs ⋮ Box-constrained quadratic programs with fixed charge variables ⋮ Inventory and investment in setup and quality operations under return on investment maximization ⋮ A branch-and-cut algorithm using polar cuts for solving nonconvex quadratic programming problems ⋮ New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation ⋮ Multi-objective geometric programming problem with \(\epsilon\)-constraint method ⋮ ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations ⋮ Global optimization of general nonconvex problems with intermediate polynomial substructures ⋮ A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations ⋮ RLT: A unified approach for discrete and continuous nonconvex optimization ⋮ Linearization method of global optimization for generalized geometric programming ⋮ Solving the canonical dual of box- and integer-constrained nonconvex quadratic programs via a deterministic direct search algorithm ⋮ A novel convex dual approach to three-dimensional assignment problem: theoretical analysis ⋮ A new algorithm for concave quadratic programming ⋮ Sharp upper and lower bounds for maximum likelihood solutions to random Gaussian bilateral inequality systems ⋮ Global optimization of general non-convex problems with intermediate bilinear substructures ⋮ A rigorous global filtering algorithm for quadratic constraints ⋮ A new two-level linear relaxed bound method for geometric programming problems ⋮ Polynomial optimization: tightening RLT-based branch-and-bound schemes with conic constraints ⋮ Polyhedral properties of RLT relaxations of nonconvex quadratic programs and their implications on exact relaxations ⋮ Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming ⋮ Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs ⋮ QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs ⋮ On the finite convergence of successive SDP relaxation methods ⋮ Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints ⋮ A global optimization RLT-based approach for solving the hard clustering problem

Uses Software

• MINOS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for indefinite quadratic programming
• Global optimization algorithms for linearly constrained indefinite quadratic problems
• Global minimization of indefinite quadratic problems
• Constrained global optimization: algorithms and applications
• Convergence of relaxation algorithms by averaging
• A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems
• Quadratic programming with one negative eigenvalue is NP-hard
• An algorithm for indefinite quadratic programming with convex constraints
• An analytical approach to global optimization
• A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique
• A new reformulation-linearization technique for bilinear programming problems
• New properties and computational improvement of the GOP algorithm for problems with quadratic objective functions and constraints
• Primal-relaxed dual global optimization approach
• Global optimization of a quadratic function subject to a bounded mixed integer constraint set
• Jointly Constrained Biconvex Programming
• Global minimization of a difference of two convex functions
• Lagrangean decomposition: A model yielding stronger lagrangean bounds
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• The Indefinite Quadratic Programming Problem
• Nonlinear Programming: Counterexamples to Two Global Optimization Algorithms
• A method for solving maximum-problems with a nonconcave quadratic objective function
• A Method for Solving the Indefinite Quadratic Programming Problem

This page was built for publication: A reformulation-convexification approach for solving nonconvex quadratic programming problems