Global optimization. Deterministic approaches
bilinear programmingconcavity cutscutting methodsd.c. programmingglobal optimizationLipschitzian optimizationouter approximationrelaxationsuccessive approximationsuccessive partition
Numerical mathematical programming methods (65K05) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Sensitivity, stability, parametric optimization (90C31) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)
The goal of this extensive monograph is to give a coherent presentation of algorithms elaborated in recent years for solving global optimization problems. A global optimization problem is defined as follows: given a nonempty set \(A\subset {\mathbb{R}}^ n\), a function f: \(A\to {\mathbb{R}}\), and a set \(D\subset A\), find at least one point \(x^*\in D\) satisfying \(f(x^*)\leq f(x)\) for all \(x\in D\) or show that such a point does not exist. In most cases the feasible set D is determined by a system of inequalities and equalities. Usually the standard nonlinear programming techniques are not applicable to solve the global optimization problems because they yield at most local minima and, in general, local minimizers are not global solutions. For these reasons the specific methods excellently described in the present book are of great interest to everyone seeking solutions of global optimization problems. The book is divided into eleven chapters, which are arranged in three parts. Part A consists of four chapters. In Chapter I the main classes of global optimization problems that will be studied in the book are introduced: concave minimization, minimization problems involving functions which can be expressed as a difference of two convex functions (d.c. programming problems), and Lipschitzian optimization. Furthermore, some basic properties of these problems and various applications are discussed. In Chapter II the authors present a large class of methods which are among the basic tools in many fields of optimization and which are used in many variants. In these methods, called outer approximation or relaxation methods, the feasible set is approximated from the outside by a sequence of nested sets. This technique is most successfull when the feasible set is convex. Nevertheless, it is adaptable for nonconvex objective functions or nonconvex constraints as shown by the authors in the next chapter, in which they discuss the so-called concavity cuts and use these in cutting procedures. The last chapter of Part A is devoted to the branch and bound methods, in which the feasible set is relaxed and subsequently split into parts over which lower (and often also upper) bounds of the objective function values can be determined. Part B includes the Chapters V-IX and deals with methods for solving concave minimization problems. The methods described in the Chapters V- VII refer to minimizing an arbitrary concave function over a polyhedron or subject to a convex constraint as well as to minimizing a concave quadratic function over a polyhedron. These methods fall into three main categories: cutting methods, successive approximation methods, and successive partition methods. Chapter VIII is devoted to algorithms for finding global minimizers over a polyhedron of functions which are the sum of two parts: a linear part involving most of the variables of the problem and a concave part involving only a relatively small number of variables. Other special concave minimization problems are studied in Chapter IX. It is shown that many optimization problems (e.g. the bilinear programming problem, the concave complementarity problem, the parametric concave programming problem) can be reduced to concave minimization problems of a special form and solved by specialized concave minimization methods. In Part C, built up from the Chapters X and XI, very general global optimization problems are considered. Several outer approximation algorithms, branch and bound procedures and combinations thereof are developed for solving d.c. programming and Lipschitzian optimization problems. Among the applications given in this part of the book are design centering problems, biconvex programming problems, and optimization of concave functions subject to separable quadratic constraints. Based on an extensive bibliography, the present book provides an up-to- date treatment of global solution methods, leading up to the latest developments concerning these methods. It can serve as a valuable reference work for all researchers in this area and for all practitioners interested in solving global optimization problems.
- scientific article; zbMATH DE number 914364
- Introduction to global optimization
- Deterministic methods in constrained global optimization: Some recent advances and new fields of application
- On the global minimization of concave functions
- On outer approximation methods for solving concave minimization problems
- Convergent Lagrangian and domain cut method for nonlinear knapsack problems
- On the subdifferentiability of the difference of two functions and local minimization
- Conditions for boundedness in concave programming under reverse convex and convex constraints
- Tight convex underestimators for \({{\mathcal C}^2}\)-continuous problems. I: Univariate functions
- Tight convex underestimators for \({\mathcal{C}^2}\)-continuous problems. II: Multivariate functions
- On generalization performance and non-convex optimization of extended \(\nu \)-support vector machine
- On outer approximation methods for solving concave minimization problems
- Global optimization on convex sets
- Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization, reserve convex constraints, DC-programming and Lipschitzian optimization
- Constrained global optimization: algorithms and applications
- Effect of the subdivision strategy on convergence and efficiency of some global optimization algorithms
- An all-linear programming relaxation algorithm for optimizing over the efficient set
- Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming
- Level-constrained programming
- What can interval analysis do for global optimization?
- Mathematical programs with a two-dimensional reverse convex constraint
- On solving a d.c. programming problem by a sequence of linear programs
- A new simplicial cover technique in constrained global optimization
- The complementary convex structure in global optimization
- Reduction of indefinite quadratic programs to bilinear programs
- Global optimization of a nonconvex single facility location problem by sequential unconstrained convex minimization
- A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique
- On nonconvex optimization problems with separated nonconvex variables
- An optimality criterion for global quadratic optimization
- Convergence qualification of adaptive partition algorithms in global optimization
- Generalized bilinear programming. I: Models, applications and linear programming relaxation
- A global optimization approach for solving the convex multiplicative programming problem
- An application of Lipschitzian global optimization to product design
- Polyhedral annexation, dualization and dimension reduction technique in global optimization
- A parametric successive underestimation method for convex multiplicative programming problems
- A new reformulation-linearization technique for bilinear programming problems
- Some further duality theorems for optimization problems with reverse convex constraint sets
- A global optimization approach for the linear two-level program
- Calculation of bounds on variables satisfying nonlinear inequality constraints
- A bisection-extreme point search algorithm for optimizing over the efficient set in the linear dependence case
- Linear multiplicative programming
- Set inversion via interval analysis for nonlinear bounded-error estimation
- A multi-local optimization algorithm
- Generalized bilinear programming: An application in farm management
- Finding robust solutions for product design problems
- A formula on the conjugate of the max of a convex functions and a concave function
- Capacity planning in manufacturing and computer networks
- A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem
- Nonlinear programming for multiperiod capacity planning in a manufacturing system
- Weber problems with alternative transportation systems
- Global one-dimensional optimization using smooth auxiliary functions
- Second-order global optimality conditions for convex composite optimization
- A branch and bound method for stochastic global optimization
- An approximate approach of global optimization for polynomial programming problems
- Extensions of Dinkelbach's algorithm for solving nonlinear fractional programming problems
- Parallel computing in nonconvex programming
- A penalty function approach for solving bi-level linear programs
- New properties and computational improvement of the GOP algorithm for problems with quadratic objective functions and constraints
- Experiments using interval analysis for solving a circuit design problem
- A new version of Farkas' lemma and global convex maximization
- A finite algorithm for solving general quadratic problems
- Global minimization of a generalized convex multiplicative function
- Image space analysis of generalized fractional programs
- The simplex method as a global optimizer: A C-programming perspective
- Globally determining a minimum-area rectangle enclosing the projection of a higher-dimensional set
- A quasiconcave minimization method for solving linear two-level programs
- Optimization methods for computing global minima of nonconvex potential energy functions
- Global minimum potential energy conformations of small molecules
- A finite, nonadjacent extreme-point search algorithm for optimization over the efficient set
- Conical algorithm for the global minimization of linearly constrained decomposable concave minimization problems
- Primal-relaxed dual global optimization approach
- Optimization over the efficient set: Four special cases
- A generalized Dantzig-Wolfe decomposition principle for a class of nonconvex programming problems
- A priority measure in interval methods for constrained global optimization
- Calculating a minimal sphere containing a polytope defined by a system of linear inequalities
- Application of Bayesian approach to numerical methods of global and stochastic optimization
- Linear programs with an additional rank two reverse convex constraint
- A finite concave minimization algorithm using branch and bound and neighbor generation
- On the role of continuously differentiable exact penalty functions in constrained global optimization
- Chebyshev approximation of a point set by a straight line
- A composite branch and bound, cutting plane algorithm for concave minimization over a polyhedron
- An algorithm for solving general D. C. programming problems
- Branch-and-bound decomposition approach for solving quasiconvex-concave programs
- Convex programs with an additional constraint on the product of several convex functions
- Decomposition based and branch and bound global optimization approaches for the phase equilibrium problem
- Global optimization in biology and medicine
- Combinatorial algorithms for some 1-facility median problems in the plane
- Computational comparison of two methods for constrained global optimization
- Constraint decomposition algorithms in global optimization
- Topographical multilevel single linkage
- Global optimization conditions for certain nonconvex minimization problems
- Finding maximum likelihood estimators for the three-parameter Weibull distribution
- On the construction of test problems for concave minimization algorithms
- Some outer approximation methods for semi-infinite optimization problems
- Minimum-volume ellipsoids containing compact sets: Application to parameter bounding
- D.C. representability of closed sets in reflexive Banach spaces and applications to optimization problems
- Minimizing a linear multiplicative-type function under network flow constraints
- Multiplicative programming problems: Analysis and efficient point search heuristic
- Characterization and generation of \(\alpha\)-dense curves
- Levels sets infimal convolution and level addition
- Formulation assistance for global optimization problems
- Application of stochastic global optimization algorithms to practical problems
- Global optimization and multi knapsack: a percolation algorithm.
- Optimization over the efficient set of a parametric multiple objective linear programming problem
- Global optimization with non-convex constraints. Sequential and parallel algorithms
This page was built for publication: Global optimization. Deterministic approaches
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3997222)