Global optimization algorithms for linearly constrained indefinite quadratic problems
From MaRDI portal
One considers the problem of finding a globally optimal solution to nonconvex quadratic problems of the form \[ (1)\quad global\quad \min_{x\in P}f(x)=c^ Tx+{1\over2}x^ TQx, \] where Q is an indefinite symmetric matrix, c, \(x\in R^ n\) and P is a bounded polyhedron in \(R^ n.\) The author shows that the optimal solution of problem (1) occurs at some boundary point of the feasible domain P and that if \(x^*\) solves (1), then \(x^*\) is also optimal for the linear program \(\min_{x\in P}(\nabla f(x^*))^ Tx.\) An overview of the most important methods used, including Benders decomposition, concave programming approaches, enumerative techniques, and bilinear programming, is given.
Recommendations
- A method of global optimization for indefinite quadratic programming problems
- Global minimization of indefinite quadratic problems
- Decomposition branch and bound method for globally solving linearly constrained indefinite quadratic minimization problems
- A new global optimization algorithm for indefinite quadratic programs
- On globally solving linearly constrained indefinite quadratic minimization problems by decomposition branch and bound method
Cites work
- A cutting plane algorithm for solving bilinear programs
- A cutting plane algorithm for the bilinear programming problem
- A finitely convergent algorithm for bilinear programming problems using polar cuts and disjunctive face cuts
- A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization
- A method for solving maximum-problems with a nonconcave quadratic objective function
- A Method for Solving the Indefinite Quadratic Programming Problem
- A relaxation algorithm for the minimization of a quasiconcave function on a convex polyhedron
- A Variable-Complexity Norm Maximization Problem
- An Algorithm for Global Minimization of Linearly Constrained Concave Quadratic Functions
- An algorithm for nonconvex programming problems
- An Algorithm for Separable Nonconvex Programming Problems
- An Algorithm for Separable Nonconvex Programming Problems II: Nonconvex Constraints
- Bemerkungen zum Problem der nichtkonvexen Programmierung
- Bilinear programming: An exact algorithm
- Checking local optimality in constrained quadratic programming is NP- hard
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- Constrained global optimization: algorithms and applications
- Dualität und Approximation bei konvexen Optimierungsproblemen
- Enumerative techniques for solving some nonconvex global optimization problems
- Generalized Benders decomposition
- Generation of large-scale quadratic programs for use as global optimization test problems
- Global minimization of a difference of two convex functions
- Global minimization of indefinite quadratic problems
- Global minimization of large-scale constrained concave quadratic problems by separable programming
- Global Optimization Approach to the Linear Complementarity Problem
- Globally convergent decomposition methods for nonconvex optimization problems
- scientific article; zbMATH DE number 4133837 (Why is no real title available?)
- scientific article; zbMATH DE number 3848975 (Why is no real title available?)
- scientific article; zbMATH DE number 4164557 (Why is no real title available?)
- scientific article; zbMATH DE number 3898606 (Why is no real title available?)
- scientific article; zbMATH DE number 3945889 (Why is no real title available?)
- scientific article; zbMATH DE number 3950216 (Why is no real title available?)
- scientific article; zbMATH DE number 4039291 (Why is no real title available?)
- scientific article; zbMATH DE number 3520156 (Why is no real title available?)
- scientific article; zbMATH DE number 3435270 (Why is no real title available?)
- scientific article; zbMATH DE number 3799408 (Why is no real title available?)
- scientific article; zbMATH DE number 3799409 (Why is no real title available?)
- scientific article; zbMATH DE number 3892947 (Why is no real title available?)
- scientific article; zbMATH DE number 3231716 (Why is no real title available?)
- scientific article; zbMATH DE number 3231717 (Why is no real title available?)
- scientific article; zbMATH DE number 3338972 (Why is no real title available?)
- Indefinite Quadratic Solid Transportation Problem
- Jointly Constrained Biconvex Programming
- Jointly constrained bilinear programs and related problems: An overview
- Methods for Global Concave Minimization: A Bibliographic Survey
- Nonconvex Quadratic Programming via Generalized Polars
- Nonlinear cost network models in transportation analysis
- Nonlinear Programming: Counterexamples to Two Global Optimization Algorithms
- On a class of quadratic programs
- On the convergence of cutting plane algorithms for a class of nonconvex mathematical programs
- On the convergence of global methods in multiextremal optimization
- On the convergence of two branch-and-bound algorithms for nonconvex programming problems
- On the convexification of nonlinear programming problems: An applications-oriented survey
- On the generation of deep disjunctive cutting planes
- On the global minimization of concave functions
- Optimization with disjunctive constraints
- Parallel search algorithms in global optimization
- Partitioning procedures for solving mixed-variables programming problems
- Quadratic problems defined on a convex hull of points
- Quadratic Programming with a Quasiconvex Objective Function
- Quasi-concave minimization subject to linear constraints
- Quasi-Concave Programming
- Relationship between bilinear programming and concave minimization under linear constraints
- Solving Certain Nonconvex Quadratic Minimization Problems by Ranking the Extreme Points
- Solving the Fixed Charge Problem by Ranking the Extreme Points
- Stationary points of quadratic maximum-problems
- The bilinear programming problem
- The Indefinite Quadratic Programming Problem
- The Variable Reduction Method for Nonlinear Programming
- Variational principles in exotic topological spaces
Cited in
(43)- Reduction of indefinite quadratic programs to bilinear programs
- Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial
- A finite algorithm for solving general quadratic problems
- Solving a class of linearly constrained indefinite quadratic problems by DC algorithms
- An algorithm for global minimization of linearly constrained quadratic functions
- A decomposition method for global and local quadratic minimization
- On global optimization with indefinite quadratics
- New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation
- Globally solving nonconvex quadratic programming problems via completely positive programming
- A reformulation-convexification approach for solving nonconvex quadratic programming problems
- Decomposition branch and bound method for globally solving linearly constrained indefinite quadratic minimization problems
- Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations
- An efficient global algorithm for worst-case linear optimization under uncertainties based on nonlinear semidefinite relaxation
- Adaptive global algorithm for solving box-constrained non-convex quadratic minimization problems
- The bounds of feasible space on constrained nonconvex quadratic programming
- A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
- On solving general reverse convex programming problems by a sequence of linear programs and line searches
- Global solutions to folded concave penalized nonconvex learning
- scientific article; zbMATH DE number 4018776 (Why is no real title available?)
- An efficient global algorithm for a class of indefinite separable quadratic programs
- A method of global optimization for indefinite quadratic programming problems
- A new global optimization algorithm for indefinite quadratic programs
- Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO
- scientific article; zbMATH DE number 4164557 (Why is no real title available?)
- Canonical duality theory: connections between nonconvex mechanics and global optimization
- Global optimization: A quadratic programming perspective
- GLOMIQO: global mixed-integer quadratic optimizer
- On globally solving linearly constrained indefinite quadratic minimization problems by decomposition branch and bound method
- Complexity Results and Effective Algorithms for Worst-Case Linear Optimization Under Uncertainties
- A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity
- On Conic Relaxations of Generalization of the Extended Trust Region Subproblem
- Relaxing the optimality conditions of box QP
- A global optimization algorithm for indefinite quadratically constrained quadratic programs
- scientific article; zbMATH DE number 7647868 (Why is no real title available?)
- On the solution of generalized multiplicative extremum problems
- Indiscriminate disruption of conditional inference on multivariate Gaussians
- Quasi-static loading of granular media as a linear complementarity problem
- Data-driven predictor of control-affine nonlinear dynamics: finite discrete-time bilinear approximation of Koopman operator
- Decomposition methods for solving nonconvex quadratic programs via branch and bound
- Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound
- Bilinear modeling solution approach for fixed charge network flow problems
- A computational comparison of some branch and bound methods for indefinite quadratic programs
- An outcome space approach for generalized convex multiplicative programs
This page was built for publication: Global optimization algorithms for linearly constrained indefinite quadratic problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q810370)
