(Global) optimization: historical notes and recent developments

DOI10.1016/j.ejco.2021.100012zbMath1530.90084OpenAlexW3204035720MaRDI QIDQ6114910

Marco Locatelli, Fabio Schoen

Publication date: 12 July 2023

Published in: EURO Journal on Computational Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejco.2021.100012

zbMATH Keywords

global optimizationheuristicsexact methods

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) History of operations research and mathematical programming (90-03)

Related Items

Revisiting `survival of the fittest' principle in global stochastic optimisation: incorporating anisotropic mutations, Hesitant adaptive search with estimation and quantile adaptive search for global optimization with noise

Cites Work

• Theoretical and computational results about optimality-based domain reductions
• Non polyhedral convex envelopes for 1-convex functions
• Interval branch-and-bound algorithms for optimization and constraint satisfaction: a survey and prospects
• On conic QPCCs, conic QCQPs and completely positive programs
• Exactness conditions for an SDP relaxation of the extended trust region problem
• Adaptive differential evolution algorithm with novel mutation strategies in multiple sub-populations
• Computational investigation of simple memetic approaches for continuous global optimization
• An FPTAS for optimizing a class of low-rank functions over a polytope
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Copositivity and constrained fractional quadratic problems
• Convex envelopes of products of convex and component-wise concave functions
• Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
• Representing quadratically constrained quadratic programs as generalized copositive programs
• The generalized trust region subproblem
• Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization
• Bound constrained interval global optimization in the COCONUT environment
• Extended formulations for convex envelopes
• Globally convergent evolution strategies
• Reverse propagation of McCormick relaxations
• Bounds tightening based on optimality conditions for nonconvex box-constrained optimization
• A Bayesian approach to constrained single- and multi-objective optimization
• How to convexify the intersection of a second order cone and a nonconvex quadratic
• Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
• Three enhancements for optimization-based bound tightening
• Approximation of linear fractional-multiplicative problems
• Generalized McCormick relaxations
• Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations
• Faster, but weaker, relaxations for quadratically constrained quadratic programs
• Interval analysis on directed acyclic graphs for global optimization
• Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound
• Semidefinite representations for finite varieties
• A population-based approach for hard global optimization problems based on dissimilarity measures
• Globally convergent evolution strategies for constrained optimization
• Existence and sum decomposition of vertex polyhedral convex envelopes
• Comparison between Baumann and admissible simplex forms in interval analysis
• A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid
• Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming
• Interval propagation and search on directed acyclic graphs for numerical constraint solving
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique
• Efficient global optimization of expensive black-box functions
• Handbook of test problems in local and global optimization
• Handbook of global optimization
• A convex envelope formula for multilinear functions
• A semidefinite framework for trust region subproblems with applications to large scale minimization
• Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
• Ellipsoidal approach to box-constrained quadratic problems
• Safe bounds in linear and mixed-integer linear programming
• An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints
• Multisection in interval branch-and-bound methods for global optimization. I: Theoretical results
• A symmetrical linear maxmin approach to disjoint bilinear programming
• Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
• Basin hopping networks of continuous global optimization problems
• Best practices for comparing optimization algorithms
• Deriving convex hulls through lifting and projection
• SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices
• On decomposability of multilinear sets
• Quadratic programs with hollows
• Arbitrarily tight \(\alpha \mathrm{BB}\) underestimators of general non-linear functions over sub-optimal domains
• A fresh CP look at mixed-binary QPs: new formulations and relaxations
• Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization
• Globally solving nonconvex quadratic programming problems via completely positive programming
• Safe and tight linear estimators for global optimization
• A polyhedral study of nonconvex quadratic programs with box constraints
• A branch-and-cut algorithm for nonconvex quadratic programs with box constraints
• Convex envelopes for edge-concave functions
• A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs
• A comparison of complete global optimization solvers
• Some results for quadratic problems with one or two quadratic constraints
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
• Improving interval analysis bounds by translations
• Some results on the strength of relaxations of multilinear functions
• On convex relaxations for quadratically constrained quadratic programming
• Approximation algorithm for a class of global optimization problems
• Convex envelopes generated from finitely many compact convex sets
• Separation and relaxation for cones of quadratic forms
• Explicit convex and concave envelopes through polyhedral subdivisions
• Global optimization problems and domain reduction strategies
• Basin hopping with synched multi L-BFGS local searches. Parallel implementation in multi-CPU and GPUs
• Branching and bounding improvements for global optimization algorithms with Lipschitz continuity properties
• (Non) convergence results for the differential evolution method
• Expected improvement for expensive optimization: a review
• Global optimization via inverse distance weighting and radial basis functions
• Efficient large scale global optimization through clustering-based population methods
• Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems
• On the tightness of SDP relaxations of QCQPs
• On monotonicity and search strategies in face-based copositivity detection algorithms
• Optimality-based domain reduction for inequality-constrained NLP and MINLP problems
• Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
• Outer-product-free sets for polynomial optimization and oracle-based cuts
• Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations
• QPLIB: a library of quadratic programming instances
• Dynamic search trajectory methods for global optimization
• High-dimensional Bayesian optimization with projections using quantile Gaussian processes
• Convex envelope of bivariate cubic functions over rectangular regions
• On the choice of the low-dimensional domain for global optimization via random embeddings
• Combining Bayesian optimization and Lipschitz optimization
• On the complexity of quadratic programming with two quadratic constraints
• Feasibility testing for systems of real quadratic equations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On an efficient use of gradient information for accelerating interval global optimization algorithms
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Derivative-free optimization: a review of algorithms and comparison of software implementations
• On interval branch-and-bound for additively separable functions with common variables
• A branch and bound algorithm for the global optimization of Hessian Lipschitz continuous functions
• Certifying convergence of Lasserre's hierarchy via flat truncation
• Hidden conic quadratic representation of some nonconvex quadratic optimization problems
• Relaxations of factorable functions with convex-transformable intermediates
• A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
• New interval methods for constrained global optimization
• Minimizing polynomials via sum of squares over the gradient ideal
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• The trust region subproblem with non-intersecting linear constraints
• A new class of improved convex underestimators for twice continuously differentiable constrained NLPs
• Convex underestimation of twice continuously differentiable functions by piecewise quadratic perturbation: spline \(\alpha\)BB underestimators
• A revision of the trapezoidal branch-and-bound algorithm for linear sum-of-atios problems
• Computable representations for convex hulls of low-dimensional quadratic forms
• Copositivity cuts for improving SDP bounds on the clique number
• Introduction to nonlinear and global optimization
• Global Optimization with Polynomials and the Problem of Moments
• Lectures on Modern Convex Optimization
• Approximation of the Stability Number of a Graph via Copositive Programming
• A Note on Polynomial Solvability of the CDT Problem
• Bayesian Optimization in a Billion Dimensions via Random Embeddings
• A Two-Variable Approach to the Two-Trust-Region Subproblem
• Solving Generalized CDT Problems via Two-Parameter Eigenvalues
• Simplicial Global Optimization
• Alternative branching rules for some nonconvex problems
• Improved Convergence Rates for Lasserre-Type Hierarchies of Upper Bounds for Box-Constrained Polynomial Optimization
• Kronecker Product Constraints with an Application to the Two-Trust-Region Subproblem
• Interval computations, rigour and non-rigour in deterministic continuous global optimization
• Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
• On the Significance of Solving Linear Programming Problems with Some Integer Variables
• Variance Regularization in Sequential Bayesian Optimization
• The Convex Envelope of (n–1)-Convex Functions
• Branching and bounds tighteningtechniques for non-convex MINLP
• An Ellipsoidal Branch and Bound Algorithm for Global Optimization
• On Nonconvex Quadratic Programming with Box Constraints
• Rigorous Error Bounds for the Optimal Value in Semidefinite Programming
• Global Optimization of Polynomials Using the Truncated Tangency Variety and Sums of Squares
• Strong Duality for the CDT Subproblem: A Necessary and Sufficient Condition
• Global optimization using special ordered sets
• An algorithm for nonconvex programming problems
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• New Results on Quadratic Minimization
• Exact Second-Order Cone Programming Relaxations for Some Nonconvex Minimax Quadratic Optimization Problems
• Sum-of-Squares Optimization without Semidefinite Programming
• Solving Quadratic Programming by Cutting Planes
• A new branch-and-bound algorithm for standard quadratic programming problems
• An algorithm for finding the absolute extremum of a function
• Strong Convex Nonlinear Relaxations of the Pooling Problem
• The Convex Hull of a Quadratic Constraint over a Polytope
• Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques
• An Adaptive Linear Approximation Algorithm for Copositive Programs
• Clustering methods for large scale geometrical global optimization
• Exactness of Semidefinite Relaxations for Nonlinear Optimization Problems with Underlying Graph Structure
• Complete search in continuous global optimization and constraint satisfaction
• Second-Order-Cone Constraints for Extended Trust-Region Subproblems
• Polynomial Programming: LP-Relaxations Also Converge
• A New Verified Optimization Technique for the "Packing Circles in a Unit Square" Problems
• Maxima for Graphs and a New Proof of a Theorem of Turán
• A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants
• Simultaneous Convexification of Bilinear Functions over Polytopes with Application to Network Interdiction
• Bound-Constrained Polynomial Optimization Using Only Elementary Calculations
• Polynomial Solvability of Variants of the Trust-Region Subproblem
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• A Sum of Squares Approximation of Nonnegative Polynomials
• Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems
• An Algorithm for Separable Nonconvex Programming Problems
• An Algorithm for Separable Nonconvex Programming Problems II: Nonconvex Constraints
• A Sequential Method Seeking the Global Maximum of a Function
• Deterministic global optimization using interval constraint propagation techniques
• On Cones of Nonnegative Quadratic Functions
• New Results on Narrowing the Duality Gap of the Extended Celis--Dennis--Tapia Problem
• A Polyhedral Study of Binary Polynomial Programs
• On copositive programming and standard quadratic optimization problems
• Semidefinite relaxations of fractional programs via novel convexification techniques
• Constraint aggregation for rigorous global optimization
• On refinement of the unit simplex using regular simplices