Global Maximization of a Convex Function with Linear Inequality Constraints

Philip B. Zwart
Philip B. Zwart
Washington University, St. Louis, Missouri
Search for more papers by this author

Washington University, St. Louis, Missouri

Published Online:1 Jun 1974https://doi.org/10.1287/opre.22.3.602

Abstract

This paper presents an algorithm for the global maximization of a convex function subject to linear inequality constraints. It is computationally finite and is designed to converge rapidly on problems in which there are few local optima or the global optimum is significantly better than most of the other local optima.

Cited by
- Open/Closed-Loop Active Learning for Data-Driven Predictive Control
  IEEE Transactions on Automatic Control, Vol. 71, No. 5
- Active Data Acquisition–An Information Theoretic Approach
- On Computing the Maximum Distance to a Fixed Point Over an Intersection of Balls
  Studia Scientiarum Mathematicarum Hungarica, Vol. 61, No. 4
- Active Diagnosis of Incipient Actuator Faults for Stochastic Systems
  IEEE Transactions on Industrial Electronics, Vol. 71, No. 1
- An Algorithm for Global Minimization of Non-Convex Functions
  1 January 2024 | SSRN Electronic Journal
- Active Fault Diagnosis for Stochastic Systems Within Bayesian Minimum Risk Decision Framework
  IEEE Transactions on Industrial Informatics, Vol. 19, No. 10
- A general purpose exact solution method for mixed integer concave minimization problems
  European Journal of Operational Research, Vol. 309, No. 3
- Stealthy Hacking and Secrecy of Controlled State Estimation Systems With Random Dropouts
  IEEE Transactions on Automatic Control, Vol. 68, No. 1
- An Algorithm for Maximizing a Convex Function Based on Its Minimum
  Aharon Ben-Tal,
  Ernst Roos
  20 September 2022 | INFORMS Journal on Computing, Vol. 34, No. 6
- Convex Maximization via Adjustable Robust Optimization
  Aras Selvi,
  Aharon Ben-Tal,
  Ruud Brekelmans,
  Dick den Hertog
  17 February 2022 | INFORMS Journal on Computing, Vol. 34, No. 4
- Enterprise Digital Twin Research
- Subdeterminants and Concave Integer Quadratic Programming
  17 December 2019 | SIAM Journal on Optimization, Vol. 29, No. 4
- Delaunay-based derivative-free optimization via global surrogates, part II: convex constraints
  19 April 2016 | Journal of Global Optimization, Vol. 66, No. 3
- 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
- On Non Overlapping Segmentation of the Response Surfaces for Solving Constrained Programming Problems Through Super Convergent Line Series
  29 August 2013 | Communications in Statistics - Theory and Methods, Vol. 43, No. 2
- A weighting method for 0–1 indefinite quadratic bilevel programming
  13 October 2010 | Operational Research, Vol. 11, No. 3
- Blind Multiuser Detection for Synchronous High Rate Space-Time Block Coded Transmission
  IEEE Transactions on Wireless Communications, Vol. 10, No. 7
- An exact penalty on bilevel programs with linear vector optimization lower level
  European Journal of Operational Research, Vol. 197, No. 1
- 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
- Pivot, Cut, and Dive: a heuristic for 0-1 mixed integer programming
  7 April 2007 | Journal of Heuristics, Vol. 13, No. 5
- On the Non-Linear Multilevel Programming Problems
  6 December 2017 | OPSEARCH, Vol. 43, No. 1
- Bibliography
- A New Successive Partition Algorithm for Concave Minimization Based on Cone Decomposition and Decomposition Cuts
  Journal of Global Optimization, Vol. 29, No. 2
- A heuristic for the continuous capacity and flow assignment
  European Journal of Operational Research, Vol. 146, No. 3
- On the Convergence of Cone Splitting Algorithms with ω-Subdivisions
  Journal of Optimization Theory and Applications, Vol. 110, No. 1
- On Tuy’s 1964 Cone Splitting Algorithm for Concave Minimization
- A Simple Finite Cone Covering Algorithm for Concave Minimization
  Journal of Global Optimization, Vol. 18, No. 4
- 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
- Pénalisation dans l'optimisation sur l'ensemble faiblement efficient
  29 March 2011 | RAIRO - Operations Research, Vol. 31, No. 3
- A Finite Algorithm for Global Minimization of Separable Concave Programs
- Global Optimization of Nonconvex MINLP’s by Interval Analysis
- Concave Minimization: Theory, Applications and Algorithms
- D.C. Optimization: Theory, Methods and Algorithms
- Quadratic Optimization
- Global optimization of nonconvex nonlinear programs via interval analysis
  Computers & Chemical Engineering, Vol. 18, No. 10
- A composite branch and bound, cutting plane algorithm for concave minimization over a polyhedron
  Computers & Operations Research, Vol. 21, No. 7
- Calculating a minimal sphere containing a polytope defined by a system of linear inequalities
  Computational Optimization and Applications, Vol. 3, No. 2
- Bibliography
- Minimization of a quasi-concave function over an efficient set
  Mathematical Programming, Vol. 61, No. 1-3
- Linear multiplicative programming
  Mathematical Programming, Vol. 56, No. 1-3
- A GLOBAL OPTIMIZATION APPROACH TO RATIONALLY CONSTRAINED RATIONAL PROGRAMMING
  30 March 2007 | Chemical Engineering Communications, Vol. 115, No. 1
- 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
- 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
- The relief indicator method for constrained global optimization
  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
- 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
- Using convex envelopes to solve the interactive fixed-charge linear programming problem
  Journal of Optimization Theory and Applications, Vol. 59, No. 2
- 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
- On a class of functions attaining their maximum at the vertices of a polyhedron
  Discrete Applied Mathematics, Vol. 22, No. 2
- On the nonconvexity of the reservoir design problem
  9 July 2010 | Water Resources Research, Vol. 23, No. 8
- 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
- The interactive fixed charge linear programming problem
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 33, No. 2
- A finite algorithm for concave minimization over a polyhedron
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 32, No. 1
- 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
- Segregation index: An orsametric for measuring discrimination against minorities
  Socio-Economic Planning Sciences, Vol. 17, No. 2
- Convergence of a Tuy-type algorithm for concave minimization subject to linear inequality constraints
  Applied Mathematics & Optimization, Vol. 7, No. 1
- A survey of methodology for the global minimization of concave functions subject to convex constraints
  Omega, Vol. 9, No. 3
- A finitely convergent algorithm for bilinear programming problems using polar cuts and disjunctive face cuts
  Mathematical Programming, Vol. 19, No. 1
- Bounding a class of nonconvex linearly-constrained resource allocation problems via the surrogate dual
  Mathematical Programming, Vol. 18, No. 1
- A relaxation algorithm for the minimization of a quasiconcave function on a convex polyhedron
  Mathematical Programming, Vol. 13, No. 1
- Maximization of A convex quadratic function under linear constraints
  Mathematical Programming, Vol. 11, No. 1
- The bilinear programming problem
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 23, No. 2
- Maximization of linearly constrained posynomials
  Computers & Mathematics with Applications, Vol. 2, No. 2
- Cutting plane methods
- On the convergence of the modified tui algorithm for minimizing a concave function on a bounded convex polyhedron

Volume 22, Issue 3

May-June 1974

Pages 455-676

Article Information

Metrics

Information

Published Online:June 01, 1974

Cite as

Philip B. Zwart, (1974) Global Maximization of a Convex Function with Linear Inequality Constraints. Operations Research 22(3):602-609.

https://doi.org/10.1287/opre.22.3.602

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Global Maximization of a Convex Function with Linear Inequality Constraints

Abstract

Volume 22, Issue 3

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News