A Successive Underestimation Method for Concave Minimization Problems

James E. Falk
James E. Falk
School of Engineering and Applied Science, Institute for Management Science and Engineering, The George Washington University, Washington, D.C.
Search for more papers by this author
,
Karla R. Hoffman
Karla R. Hoffman
School of Engineering and Applied Science, Institute for Management Science and Engineering, The George Washington University, Washington, D.C.
Search for more papers by this author

School of Engineering and Applied Science, Institute for Management Science and Engineering, The George Washington University, Washington, D.C.

Search for more papers by this author

Karla R. Hoffman

School of Engineering and Applied Science, Institute for Management Science and Engineering, The George Washington University, Washington, D.C.

Search for more papers by this author

Published Online:1 Aug 1976https://doi.org/10.1287/moor.1.3.251

Abstract

A new method designed to globally minimize concave functions over linear polyhedra is described. Properties of the method are discussed, an example problem is solved, and computational considerations are discussed.

Cited by
- New finite relaxation hierarchies for concavo-convex, disjoint bilinear programs, and facial disjunctions
  26 March 2026 | Mathematical Programming, Vol. 59
- Frank-Wolfe meets Shapley-Folkman: a systematic approach for solving nonconvex separable problems with linear constraints
  12 August 2025 | Mathematical Programming, Vol. 4
- Cutting Planes for Signomial Programming
  28 April 2025 | SIAM Journal on Optimization, Vol. 35, No. 2
- Simultaneous convexification for the planar obnoxious facility location problem
  15 January 2025 | Journal of Global Optimization, Vol. 92, No. 1
- A general purpose exact solution method for mixed integer concave minimization problems
  European Journal of Operational Research, Vol. 309, No. 3
- A Discussion on Non-Convex Optimization Problems Arising in Supply Chain Design and Finance
- SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework
  14 June 2017 | Optimization Methods and Software, Vol. 33, No. 3
- Integrated location-inventory modelling under forward and reverse product flows in the used merchandise retail sector: A multi-echelon formulation
  European Journal of Operational Research, Vol. 259, No. 2
- Energy-Aware Resource and Revenue Management in Federated Cloud: A Game-Theoretic Approach
  IEEE Systems Journal, Vol. 11, No. 2
- An Algorithm for the Singly Linearly Constrained Concave Minimization Problem with Upper Convergent Bounded Variables
  Journal of the Korea Convergence Society, Vol. 7, No. 5
- Variations and extension of the convex–concave procedure
  5 November 2015 | Optimization and Engineering, Vol. 17, No. 2
- DC Optimization Problems
  18 October 2016
- New a priori and a posteriori probabilistic bounds for robust counterpart optimization: I. Unknown probability distributions
  Computers & Chemical Engineering, Vol. 84
- Joint optimal power allocation and relay location for decode‐and‐forward multi‐hop relaying over log‐normal channel
  1 December 2015 | IET Communications, Vol. 9, No. 18
- Two New Reformulation Convexification Based Hierarchies for 0-1 MIPs
  Advances in Operations Research, Vol. 2015
- Optimization Methods for Mixed Integer Weakly Concave Programming Problems
  27 June 2014 | Journal of the Operations Research Society of China, Vol. 2, No. 2
- Fixed-Dimensional Stochastic Dynamic Programs: An Approximation Scheme and an Inventory Application
  Wei Chen,
  Milind Dawande,
  Ganesh Janakiraman
  24 February 2014 | Operations Research, Vol. 62, No. 1
- A deterministic annealing algorithm for approximating a solution of the linearly constrained nonconvex quadratic minimization problem
  Neural Networks, Vol. 39
- Solution Methods for General Quadratic Programming Problem with Continuous and Binary Variables: Overview
- Some results on the strength of relaxations of multilinear functions
  21 October 2012 | Mathematical Programming, Vol. 136, No. 2
- Fixed-Dimensional Stochastic Dynamic Programs: An Approximation Scheme and an Inventory Application
  SSRN Electronic Journal, Vol. 1
- Global Optimization
  16 June 2010
- An exact penalty on bilevel programs with linear vector optimization lower level
  European Journal of Operational Research, Vol. 197, No. 1
- Optimization of biotechnological processes. The acetic acid fermentation. Part II: Practical identifiability analysis and parameter estimation
  Biochemical Engineering Journal, Vol. 45, No. 1
- Mixed-Integer Nonlinear Programming Models and Algorithms for Large-Scale Supply Chain Design with Stochastic Inventory Management
  25 September 2008 | Industrial & Engineering Chemistry Research, Vol. 47, No. 20
- Existence and sum decomposition of vertex polyhedral convex envelopes
  9 November 2007 | Optimization Letters, Vol. 2, No. 3
- Convex Envelopes in Optimization Problems
- Fractional programming with convex quadratic forms and functions
  European Journal of Operational Research, Vol. 173, No. 2
- Maximizing the ratio of two convex functions over a convex set
  9 March 2006 | Naval Research Logistics (NRL), Vol. 53, No. 4
- Duality Bound Methods in Global Optimization
- General Quadratic Programming
- On the existence of polyhedral convex envelopes
- Simplicially-Constrained DC Optimization over Efficient and Weakly Efficient Sets
  Journal of Optimization Theory and Applications, Vol. 117, No. 3
- A heuristic for the continuous capacity and flow assignment
  European Journal of Operational Research, Vol. 146, No. 3
- Shortest‐path network interdiction
  5 August 2002 | Networks, Vol. 40, No. 2
- Least trimmed squares regression, least median squares regression, and mathematical programming
  Mathematical and Computer Modelling, Vol. 35, No. 9-10
- Convergence and Application of a Decomposition Method Using Duality Bounds for Nonconvex Global Optimization
  Journal of Optimization Theory and Applications, Vol. 113, No. 1
- Quasiconvex relaxations based on interval arithmetic
  Linear Algebra and its Applications, Vol. 324, No. 1-3
- Linear Approximations in a Dynamic Programming Approach for the Uncapacitated Single-Source Minimum Concave Cost Network Flow Problem in Acyclic Networks
  Journal of Global Optimization, Vol. 19, No. 2
- Convex Envelopes in Optimization Problems
- Quasi Convex-Concave Extensions
- Monotone Variable–Metric Algorithm for Linearly Constrained Nonlinear Programming
  Journal of Optimization Theory and Applications, Vol. 104, No. 2
- A combined cutting-stock and lot-sizing problem
  European Journal of Operational Research, Vol. 120, No. 2
- DC Programming: Overview
  Journal of Optimization Theory and Applications, Vol. 103, No. 1
- An Outer Approximation Algorithm Guaranteeing Feasibility of Solutions and Approximate Accuracy of Optimality
  Journal of Global Optimization, Vol. 14, No. 3
- MEAN-ABSOLUTE DEVIATION PORTFOLIO OPTIMIZATION MODEL UNDER TRANSACTION COSTS
  Journal of the Operations Research Society of Japan, Vol. 42, No. 4
- Cutting Plane/Tabu Search Algorithms for Low Rank Concave Quadratic Programming Problems
  Journal of Global Optimization, Vol. 13, No. 3
- Solution of the Multisource Weber and Conditional Weber Problems by D.-C. Programming
  Pey-Chun Chen,
  Pierre Hansen,
  Brigitte Jaumard,
  Hoang Tuy,
  1 August 1998 | Operations Research, Vol. 46, No. 4
- Global Optimization Techniques for Solving the General Quadratic Integer Programming Problem
  Computational Optimization and Applications, Vol. 10, No. 2
- An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem
  Journal of Global Optimization, Vol. 13, No. 1
- A Finite Algorithm for Global Minimization of Separable Concave Programs
  Journal of Global Optimization, Vol. 12, No. 1
- A Parallel Algorithm for Linear Programs with an Additional Reverse Convex Constraint
  Journal of Parallel and Distributed Computing, Vol. 45, No. 2
- Pénalisation dans l'optimisation sur l'ensemble faiblement efficient
  29 March 2011 | RAIRO - Operations Research, Vol. 31, No. 3
- A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem
  European Journal of Operational Research, Vol. 94, No. 2
- Subdivision of simplices relative to a cutting plane and finite concave minimization
  Journal of Global Optimization, Vol. 9, No. 1
- A Finite Algorithm for Global Minimization of Separable Concave Programs
- A new algorithm for solving the general quadratic programming problem
  Computational Optimization and Applications, Vol. 5, No. 1
- A multiple‐objective dispersion problem
  20 September 2006 | Journal of Multi-Criteria Decision Analysis, Vol. 4, No. 4
- Canonical DC programming problem: Outer approximation methods revisited
  Operations Research Letters, Vol. 18, No. 2
- Multiple‐objective weighting factor auxiliary optimization problems
  20 September 2006 | Journal of Multi-Criteria Decision Analysis, Vol. 4, No. 2
- Concave Minimization: Theory, Applications and Algorithms
- Quadratic Optimization
- A method for solving d.c. programming problems. Application to fuel mixture nonconvex optimization problem
  Journal of Global Optimization, Vol. 6, No. 1
- Some concave-convex representations of the quadratic assignment problem
  European Journal of Operational Research, Vol. 80, No. 2
- Algorithms for globally solving DC minimization problems via concave programming
- A mathematical programming approach to a problem in variance penalised Markov decision processes
  OR Spektrum, Vol. 15, No. 4
- A composite branch and bound, cutting plane algorithm for concave minimization over a polyhedron
  Computers & Operations Research, Vol. 21, No. 7
- A generalization of the construction of test problems for nonconvex optimization
  Journal of Global Optimization, Vol. 5, No. 1
- Calculating a minimal sphere containing a polytope defined by a system of linear inequalities
  Computational Optimization and Applications, Vol. 3, No. 2
- An algorithm and new penalties for concave integer minimization over a polyhedron
  Naval Research Logistics, Vol. 41, No. 3
- Concave extensions for nonlinear 0–1 maximization problems
  Mathematical Programming, Vol. 61, No. 1-3
- Minimization of a quasi-concave function over an efficient set
  Mathematical Programming, Vol. 61, No. 1-3
- A generalized duality and applications
  Journal of Global Optimization, Vol. 3, No. 3
- D.c. sets, d.c. functions and nonlinear equations
  Mathematical Programming, Vol. 58, No. 1-3
- Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming
  Annals of Operations Research, Vol. 34, No. 1
- A linear programming approach to solving bilinear programmes
  Mathematical Programming, Vol. 56, No. 1-3
- Linear multiplicative programming
  Mathematical Programming, Vol. 56, No. 1-3
- Computational approaches to variance-penalised Markov decision processes
  1 June 1992 | Operations-Research-Spektrum, Vol. 14, No. 2
- On-line and off-line vertex enumeration by adjacency lists
  Operations Research Letters, Vol. 10, No. 7
- Quasiconjugates of functions, duality relationship between Quasiconvex Minimization under a Reverse Convex Constraint and Quasiconvex Maximization under a Convex Constraint, and applications
  Journal of Mathematical Analysis and Applications, Vol. 159, No. 2
- On the minimization of a quasi-concave function subject to linear constraints
  Operations Research Letters, Vol. 10, No. 3
- Multi-level programming and conflict resolution
  European Journal of Operational Research, Vol. 51, No. 2
- A parametric successive underestimation method for convex multiplicative programming problems
  Journal of Global Optimization, Vol. 1, No. 3
- Efficient algorithms for solving rank two and rank three bilinear programming problems
  Journal of Global Optimization, Vol. 1, No. 2
- A branch and bound-outer approximation algorithm for concave minimization over a convex set
  Computers & Mathematics with Applications, Vol. 21, No. 6-7
- A variant of Tuy's decomposition algorithm for solving a class of concave minimization problems
  Optimization, Vol. 22, No. 4
- A decomposition approach for global optimum search in QP, NLP and MINLP problems
  Annals of Operations Research, Vol. 25, No. 1
- A note on adapting methods for continuous global optimization to the discrete case
  Annals of Operations Research, Vol. 25, No. 1
- Separable concave minimization via partial outer approximation and branch and bound
  Operations Research Letters, Vol. 9, No. 6
- Deterministic methods in constrained global optimization: Some recent advances and new fields of application
  Naval Research Logistics, Vol. 37, No. 4
- An algorithm for concave integer minimization over a polyhedron
  Naval Research Logistics, Vol. 37, No. 4
- An algorithm for quadratic zero-one programs
  Naval Research Logistics, Vol. 37, No. 4
- A two‐phase decomposition method for optimal design of looped water distribution networks
  9 July 2010 | Water Resources Research, Vol. 26, No. 4
- Convex minimization under Lipschitz constraints
  Journal of Optimization Theory and Applications, Vol. 64, No. 3
- A new algorithm to find all vertices of a polytope
  Operations Research Letters, Vol. 8, No. 5
- Modification, implementation and comparison of three algorithms for globally solving linearly constrained concave minimization problems
  Computing, Vol. 42, No. 2-3
- On the structure and properties of a linear multilevel programming problem
  Journal of Optimization Theory and Applications, Vol. 60, No. 3
- Quantitative Modelle und Verfahren zur Lösung strategischer Distributionsprobleme
- Quadratic functions of binary variables
  28 September 2006
- A bound on the roof-duality gap
  28 September 2006
- Improvement and implementation of some algorithms for nonconvex optimization problems
- On an outer approximation concept in global optimization
  Optimization, Vol. 20, No. 3
- Using convex envelopes to solve the interactive fixed-charge linear programming problem
  Journal of Optimization Theory and Applications, Vol. 59, No. 2
- Minimizing a quasi-concave function subject to a reverse convex constraint
  Applied Mathematics & Optimization, Vol. 18, No. 1
- Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and D.C. Optimization problems
  Mathematical Programming, Vol. 41, No. 1-3
- A parallel algorithm for constrained concave quadratic global minimization
  Mathematical Programming, Vol. 42, No. 1-3
- On finding new vertices and redundant constraints in cutting plane algorithms for global optimization
  Operations Research Letters, Vol. 7, No. 2
- Outer Cut Methods in Global Optimization
- Outer approximation by polyhedral convex sets
  OR Spektrum, Vol. 9, No. 3
- Generation of large-scale quadratic programs for use as global optimization test problems
  1 June 1987 | ACM Transactions on Mathematical Software, Vol. 13, No. 2
- Convex programs with an additional reverse convex constraint
  Journal of Optimization Theory and Applications, Vol. 52, No. 3
- Convex sets and functions
- Branch and bound methods
- Large scale problems
- Global minimization of a difference of two convex functions
  27 February 2009
- Methods for Global Concave Minimization: A Bibliographic Survey
  SIAM Review, Vol. 28, No. 3
- An algorithm for optimizing over the weakly-efficient set
  European Journal of Operational Research, Vol. 25, No. 2
- Global minimization of large-scale constrained concave quadratic problems by separable programming
  Mathematical Programming, Vol. 34, No. 2
- Construction of large-scale global minimum concave quadratic test problems
  Journal of Optimization Theory and Applications, Vol. 48, No. 2
- A finite algorithm for concave minimization over a polyhedron
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 32, No. 1
- A Finite Algorithm for Solving Linear Programs with an Additional Reverse Convex Constraint
- Concave minimization under linear constraints with special structure
  27 June 2007 | Optimization, Vol. 16, No. 3
- On the global minimization of concave functions
  1 December 1984 | Operations-Research-Spektrum, Vol. 6, No. 4
- Convergence of a subgradient method for computing the bound norm of matrices
  Linear Algebra and its Applications, Vol. 62
- Optimization over the efficient set
  Journal of Mathematical Analysis and Applications, Vol. 98, No. 2
- Performance of approximate algorithms for global minimization
  26 February 2009
- Penalty for zero–one integer equivalent problem
  Mathematical Programming, Vol. 24, No. 1
- Global minimum test problem construction
  Mathematical Programming, Vol. 24, No. 1
- Algorithms for parametric nonconvex programming
  Journal of Optimization Theory and Applications, Vol. 38, No. 3
- Closed form solutions to nonserial, nonconvex quadratic programming problems using dynamic programming
  Journal of Mathematical Analysis and Applications, Vol. 86, No. 2
- Konkave Minimierungsprobleme In Operations Research
- A method for globally minimizing concave functions over convex sets
  Mathematical Programming, Vol. 20, No. 1
- Convergence of a Tuy-type algorithm for concave minimization subject to linear inequality constraints
  Applied Mathematics & Optimization, Vol. 7, No. 1
- Bounding a class of nonconvex linearly-constrained resource allocation problems via the surrogate dual
  Mathematical Programming, Vol. 18, No. 1
- A note on the duality gap in nonconvex optimization and a very simple procedure for bid evaluation type problems
  European Journal of Operational Research, Vol. 5, No. 3
- A relaxation algorithm for the minimization of a quasiconcave function on a convex polyhedron
  Mathematical Programming, Vol. 13, No. 1

cover image Mathematics of Operations Research

Volume 1, Issue 3

August 1976

Pages 197-298

Article Information

Metrics

Information

Published Online:August 01, 1976

Cite as

James E. Falk, Karla R. Hoffman, (1976) A Successive Underestimation Method for Concave Minimization Problems. Mathematics of Operations Research 1(3):251-259.

https://doi.org/10.1287/moor.1.3.251

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

A Successive Underestimation Method for Concave Minimization Problems

Abstract

Volume 1, Issue 3

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News