Convergent Algorithms for Minimizing a Concave Function

Nguyen Van Thoai
Nguyen Van Thoai
Institute of Mathematics, 208D Doi Can, Hanoi, Socialist Republic of Vietnam
Search for more papers by this author
,
Hoang Tuy
Hoang Tuy
Institute of Mathematics, 208D Doi Can, Hanoi, Socialist Republic of Vietnam
Search for more papers by this author

Nguyen Van Thoai

Institute of Mathematics, 208D Doi Can, Hanoi, Socialist Republic of Vietnam

Search for more papers by this author

Hoang Tuy

Institute of Mathematics, 208D Doi Can, Hanoi, Socialist Republic of Vietnam

Search for more papers by this author

Published Online:1 Nov 1980https://doi.org/10.1287/moor.5.4.556

Abstract

For the problem of minimizing a concave function over a polytope a class of convergent algorithms is proposed, which is based upon a combination of the branch and bound technique with the cutting method developed earlier by H. Tuy.

Cited by
- Globally solving concave quadratic programs via doubly nonnegative relaxation
  19 April 2025 | Mathematical Programming Computation, Vol. 54
- A successive linear approximation algorithm for the global minimization of a concave quadratic program
  12 September 2020 | Computational and Applied Mathematics, Vol. 39, No. 4
- Integrating Analytics Through the Big Data Information Chain: A Case From Supply Chain Management
  3 September 2018 | Journal of Business Logistics, Vol. 39, No. 3
- Minimizing Piecewise-Concave Functions Over Polyhedra
  Manlio Gaudioso,
  Giovanni Giallombardo,
  Giovanna Miglionico
  2 October 2017 | Mathematics of Operations Research, Vol. 43, No. 2
- Joint bandwidth, caching and association optimization for D2D assisted wireless networks
- Degeneracy removal in cutting plane methods for disjoint bilinear programming
  15 February 2016 | Optimization Letters, Vol. 11, No. 3
- A generalization of $$\omega $$-subdivision ensuring convergence of the simplicial algorithm
  6 January 2016 | Computational Optimization and Applications, Vol. 64, No. 2
- Variations and extension of the convex–concave procedure
  5 November 2015 | Optimization and Engineering, Vol. 17, No. 2
- DC Optimization Problems
  18 October 2016
- A convergent conical algorithm with $$\omega $$ ω -bisection for concave minimization
  10 May 2014 | Journal of Global Optimization, Vol. 61, No. 2
- Optimizing Cloud Resources for Delivering IPTV Services Through Virtualization
  IEEE Transactions on Multimedia, Vol. 15, No. 4
- Branch and Bound Algorithm Using Cutting Angle Method for Global Minimization of Increasing Positively Homogeneous Functions
- On the relation between concavity cuts and the surrogate dual for convex maximization problems
  9 July 2011 | Journal of Global Optimization, Vol. 52, No. 3
- A weighting method for 0–1 indefinite quadratic bilevel programming
  13 October 2010 | Operational Research, Vol. 11, No. 3
- Reverse Convex Programming Approach in the Space of Extreme Criteria for Optimization over Efficient Sets
  3 June 2010 | Journal of Optimization Theory and Applications, Vol. 147, No. 2
- An enumerative algorithm for non-linear multi-level integer programming problem
  Yugoslav Journal of Operations Research, Vol. 19, No. 2
- Algorithms for Network Interdiction and Fortification Games
- On the Non-Linear Multilevel Programming Problems
  6 December 2017 | OPSEARCH, Vol. 43, No. 1
- Global Optimization Method for Solving Mathematical Programs with Linear Complementarity Constraints
  Journal of Optimization Theory and Applications, Vol. 124, No. 2
- On the indefinite quadratic bilevel programming problem
  27 November 2017 | OPSEARCH, Vol. 41, No. 4
- Some recent developments in deterministic global optimization
  Operational Research, Vol. 4, No. 1
- On the Convergence of Cone Splitting Algorithms with ω-Subdivisions
  Journal of Optimization Theory and Applications, Vol. 110, No. 1
- Finitely convergent cutting planes for concave minimization
  Journal of Global Optimization, Vol. 20, No. 2
- D.C. Programming
- On Tuy’s 1964 Cone Splitting Algorithm for Concave Minimization
- Optimization over equilibrium sets ∗
  Optimization, Vol. 49, No. 1-2
- Conical Algorithm in Global Optimization for Optimizing over Efficient Sets
  Journal of Global Optimization, Vol. 18, No. 4
- Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints
  Journal of Optimization Theory and Applications, Vol. 107, No. 2
- DC Programming: Overview
  Journal of Optimization Theory and Applications, Vol. 103, No. 1
- A Simplified Convergence Proof for the Cone Partitioning Algorithm
  Journal of Global Optimization, Vol. 13, No. 4
- A Finite Algorithm for Global Minimization of Separable Concave Programs
  Journal of Global Optimization, Vol. 12, No. 1
- Decomposition approach for the global minimization of biconcave functions over polytopes
  Journal of Optimization Theory and Applications, Vol. 88, No. 3
- A Finite Algorithm for Global Minimization of Separable Concave Programs
- Decomposition methods for solving a class of nonconvex programming problems dealing with bilinear and quadratic functions
  Computational Optimization and Applications, Vol. 4, No. 3
- Network Problems
- Concave Minimization: Theory, Applications and Algorithms
- Quadratic Optimization
- Constraint decomposition algorithms in global optimization
  Journal of Global Optimization, Vol. 5, No. 4
- A composite branch and bound, cutting plane algorithm for concave minimization over a polyhedron
  Computers & Operations Research, Vol. 21, No. 7
- A branch bound method for subset sum problem
  Acta Mathematicae Applicatae Sinica, Vol. 10, No. 3
- Groundwater management using numerical simulation and the outer approximation method for global optimization
  9 July 2010 | Water Resources Research, Vol. 29, No. 10
- A comprehensive approach of planning and scheduling based on petri nets
  1 September 2006 | Applied Stochastic Models and Data Analysis, Vol. 9, No. 3
- An algorithm for solving convex programs with an additional convex—concave constraint
  Mathematical Programming, Vol. 61, No. 1-3
- Principles of system modeling
- Performance evaluation of manufacturing systems
- A generalized duality and applications
  Journal of Global Optimization, Vol. 3, No. 3
- Combined branch-and-bound and cutting plane methods for solving a class of nonlinear programming problems
  Journal of Global Optimization, Vol. 3, No. 3
- D.c. sets, d.c. functions and nonlinear equations
  Mathematical Programming, Vol. 58, No. 1-3
- Conical algorithm for the global minimization of linearly constrained decomposable concave minimization problems
  Journal of Optimization Theory and Applications, Vol. 74, No. 3
- Linear multiplicative programming
  Mathematical Programming, Vol. 56, No. 1-3
- Convergence qualification of adaptive partition algorithms in global optimization
  Mathematical Programming, Vol. 56, No. 1-3
- Optimisation of invariant criteria for event graphs
  IEEE Transactions on Automatic Control, Vol. 37, No. 5
- A finite, nonadjacent extreme-point search algorithm for optimization over the efficient set
  Journal of Optimization Theory and Applications, Vol. 73, No. 1
- 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 design of maximally sparse beamforming arrays
  IEEE Transactions on Antennas and Propagation, Vol. 39, No. 8
- Normal conical algorithm for concave minimization over polytopes
  Mathematical Programming, Vol. 51, No. 1-3
- RELIABILITY-BASED PLASTIC SYNTHESIS OF PORTAL FRAMES
  Engineering Optimization, Vol. 17, No. 3
- Concave minimization via conical partitions and polyhedral outer approximation
  Mathematical Programming, Vol. 50, No. 1-3
- Efficient algorithms for solving rank two and rank three bilinear programming problems
  Journal of Global Optimization, Vol. 1, No. 2
- Effect of the subdivision strategy on convergence and efficiency of some global optimization algorithms
  Journal of Global Optimization, Vol. 1, No. 1
- An all-linear programming relaxation algorithm for optimizing over the efficient set
  Journal of Global Optimization, Vol. 1, No. 1
- A branch and bound-outer approximation algorithm for concave minimization over a convex set
  Computers & Mathematics with Applications, Vol. 21, No. 6-7
- On solving general reverse convex programming problems by a sequence of linear programs and line searches
  Annals of Operations Research, Vol. 25, No. 1
- Minimum concave-cost network flow problems: Applications, complexity, and algorithms
  Annals of Operations Research, Vol. 25, No. 1
- A decomposition approach for global optimum search in QP, NLP and MINLP problems
  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
- Convex minimization under Lipschitz constraints
  Journal of Optimization Theory and Applications, Vol. 64, No. 3
- New Algorithms for Concave Minimization Problems
- 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
- Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization, reverse convex constraints, DC-programming, and Lipschitzian optimization
  Journal of Optimization Theory and Applications, Vol. 58, No. 1
- 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 finite method for globally minimizing a concave function over an unbounded polyhedral convex set and its applications
  Acta Mathematica Hungarica, Vol. 52, No. 1-2
- Conical algorithms for solving a concave programming problem and some generalizations
  USSR Computational Mathematics and Mathematical Physics, Vol. 28, No. 4
- On a class of functions attaining their maximum at the vertices of a polyhedron
  Discrete Applied Mathematics, Vol. 22, No. 2
- On the convergence of global methods in multiextremal optimization
  Journal of Optimization Theory and Applications, Vol. 54, No. 2
- On the nonconvexity of the reservoir design problem
  9 July 2010 | Water Resources Research, Vol. 23, No. 8
- Global minimization of a difference of two convex functions
  27 February 2009
- A class of exhaustive cone splitting procedures in conical algorithms for concave minmization
  27 June 2007 | Optimization, Vol. 18, No. 6
- A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization
  Journal of Optimization Theory and Applications, Vol. 51, No. 2
- Methods for Global Concave Minimization: A Bibliographic Survey
  SIAM Review, Vol. 28, No. 3
- Global minimization of large-scale constrained concave quadratic problems by separable programming
  Mathematical Programming, Vol. 34, No. 2
- A branch and bound algorithm for extreme point mathematical programming problems
  Discrete Applied Mathematics, Vol. 11, No. 3
- A finite algorithm for concave minimization over a polyhedron
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 32, No. 1
- On Methods for Solving Optimization Problems without Using Derivatives
- 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
- Global Minimization of a Difference of Two Convex Functions
- Performance of approximate algorithms for global minimization
  26 February 2009
- Solving the linear complementarity problem through concave programming
  USSR Computational Mathematics and Mathematical Physics, Vol. 23, No. 3
- Indirect identification of yield limits by mathematical programming
  Engineering Structures, Vol. 4, No. 2
- Cutting plane methods
- Management of manufacturing systems based on Petri nets

cover image Mathematics of Operations Research

Volume 5, Issue 4

November 1980

Pages 481-602

Article Information

Metrics

Information

Published Online:November 01, 1980

Cite as

Nguyen Van Thoai, Hoang Tuy, (1980) Convergent Algorithms for Minimizing a Concave Function. Mathematics of Operations Research 5(4):556-566.

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

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Convergent Algorithms for Minimizing a Concave Function

Abstract

Volume 5, Issue 4

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News