On the global minimization of concave functions
type: Item
instance of: scholarly article
title: On the global minimization of concave functions
zbMATH Open document ID: 0551.65043
DOI: 10.1007/BF01720068
published in: OR Spektrum
publication date: 1984-01-01T00:00:00Z
review text: Many important classes of decision models give rise to the problem of finding a global minimum of a concave function over a convex set. Since many local minima can occur, concave minimization belongs to the ''hard'' global optimization problems, where standard nonlinear programming procedures fail. After a brief survey on important specific classes of decision models that can be formulated as concave minimization problems, two main solution approaches for the general concave problem are discussed: branch-and-bound combined with convex underestimation and outer approximation by cutting planes. It should be noted that in the meantime a much more general and flexible branch-and-bound procedure is available [cf. the author, A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization. Discussion Paper, Fachbereich Mathematik/Informatik, Universität Oldenburg].
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C25
zbMATH DE Number: 3878261
zbMATH Keywords: decision models
zbMATH Keywords: global minimum
zbMATH Keywords: concave function
zbMATH Keywords: concave minimization
zbMATH Keywords: branch-and-bound
zbMATH Keywords: convex underestimation
zbMATH Keywords: cutting planes
author: Reiner Horst
MaRDI profile type: Publication
cites work: Jointly Constrained Biconvex Programming
cites work: Q5615782
cites work: Variations on a cutting plane method for solving concave minimization problems with linear constraints
cites work: Solving Certain Nonconvex Quadratic Minimization Problems by Ranking the Extreme Points
cites work: A relaxation algorithm for the minimization of a quasiconcave function on a convex polyhedron
cites work: A Successive Underestimation Method for Concave Minimization Problems
cites work: An Algorithm for Separable Nonconvex Programming Problems
cites work: Bilinear programming: An exact algorithm
cites work: Concave Programming Applied to a Special Class of 0-1 Integer Programs
cites work: A method for globally minimizing concave functions over convex sets
cites work: Q4116263
cites work: Q4105512
cites work: An algorithm for nonconvex programming problems
cites work: Q4189036
cites work: A note on the convergence of an algorithm for nonconvex programming problems
cites work: On the convexification of nonlinear programming problems: An applications-oriented survey
cites work: Convergence of a Tuy-type algorithm for concave minimization subject to linear inequality constraints
cites work: The Cutting-Plane Method for Solving Convex Programs
cites work: The Indefinite Quadratic Programming Problem
cites work: A cutting plane algorithm for solving bilinear programs
cites work: Maximization of A convex quadratic function under linear constraints
cites work: Quasi-concave minimization subject to linear constraints
cites work: On Connections Between Zero-One Integer Programming and Concave Programming Under Linear Constraints
cites work: Convex Analysis
cites work: Global Minimization of a Linearly Constrained Concave Function by Partition of Feasible Domain
cites work: A finitely convergent algorithm for bilinear programming problems using polar cuts and disjunctive face cuts
cites work: Concave minimization over a convex polyhedron
cites work: Relationship between bilinear programming and concave minimization under linear constraints
cites work: Convergent Algorithms for Minimizing a Concave Function
cites work: On outer approximation methods for solving concave minimization problems
cites work: The Supporting Hyperplane Method for Unimodal Programming
cites work: Minimum Concave-Cost Solution of Leontief Substitution Models of Multi-Facility Inventory Systems
cites work: A Deterministic Multiproduct, Multi-Facility Production and Inventory Model
cites work: Nonlinear Programming: Counterexamples to Two Global Optimization Algorithms
cites work: Global Maximization of a Convex Function with Linear Inequality Constraints
full work available at URL: https://doi.org/10.1007/bf01720068
OpenAlex ID: W180275413
description: scientific article; zbMATH DE number 3878261