A branch and bound-outer approximation algorithm for concave minimization over a convex set
From MaRDI portal
The authors consider a concave minimization problem (P): minimize f(x), subject to g(x)\(\leq 0\), where f is a concave, not necessarily separable, function on \(R^ n\), and \(g(x)=(g_ 1(x),...,g_ m(x))\). The authors propose a new algorithm for solving P which uses branch and bound and outer approximation, and is guaranteed to converge to a globally optimal solution. One of the major advantages of the algorithm is that the only significant nonlinear computation required at each iteration can be accomplished by any of a number of simple univariate search procedures. The only other major computations required involve solving either linear programming problems or systems of \((n+1)\) equations in \((n+1)\) unknowns which each have a unique solution.
Recommendations
- Concave minimization via conical partitions and polyhedral outer approximation
- A Conical Algorithm for Globally Minimizing a Concave Function Over a Closed Convex Set
- A finite algorithm for concave minimization over a polyhedron
- On outer approximation methods for solving concave minimization problems
- On the global minimization of concave functions
Cites work
- A class of exhaustive cone splitting procedures in conical algorithms for concave minmization
- A Conical Algorithm for Globally Minimizing a Concave Function Over a Closed Convex Set
- A Deterministic Multiproduct, Multi-Facility Production and Inventory Model
- A finite algorithm for concave minimization over a polyhedron
- A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization
- A method for globally minimizing concave functions over convex sets
- A Successive Underestimation Method for Concave Minimization Problems
- An algorithm for nonconvex programming problems
- An outer approximation method for globally minimizing a concave function over a compact convex set
- Convergent Algorithms for Minimizing a Concave Function
- scientific article; zbMATH DE number 3495849 (Why is no real title available?)
- scientific article; zbMATH DE number 3894826 (Why is no real title available?)
- scientific article; zbMATH DE number 3215121 (Why is no real title available?)
- scientific article; zbMATH DE number 3365044 (Why is no real title available?)
- Methods for Global Concave Minimization: A Bibliographic Survey
- Minimizing a concave function over a compact convex set
- Minimum Concave-Cost Solution of Leontief Substitution Models of Multi-Facility Inventory Systems
- On Connections Between Zero-One Integer Programming and Concave Programming Under Linear Constraints
- Outer approximation by polyhedral convex sets
- Relationship between bilinear programming and concave minimization under linear constraints
Cited in
(40)- An outer approximation method for globally minimizing a concave function over a compact convex set
- On outer approximation methods for solving concave minimization problems
- A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization
- Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and d.c. optimization problems
- Modification, implementation and comparison of three algorithms for globally solving linearly constrained concave minimization problems
- Method for minimizing a convex-concave function over a convex set
- An all-linear programming relaxation algorithm for optimizing over the efficient set
- On solving a d.c. programming problem by a sequence of linear programs
- A new simplicial cover technique in constrained global optimization
- On nonconvex optimization problems with separated nonconvex variables
- A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms
- An outer approximation algorithm guaranteeing feasibility of solutions and approximate accuracy of optimality
- A finite concave minimization algorithm using branch and bound and neighbor generation
- A composite branch and bound, cutting plane algorithm for concave minimization over a polyhedron
- A finite algorithm for global minimization of separable concave programs
- Capacity planning in networks of queues with manufacturing applications
- A new algorithm for minimizing convex functions over convex sets
- An outcome space algorithm for minimizing the product of two convex functions over a convex set
- A norm minimization-based convex vector optimization algorithm
- Separable concave minimization via partial outer approximation and branch and bound
- A simplicial branch-and-bound algorithm conscious of special structures in concave minimization problems
- Sufficient optimality criterion for linearly constrained, separable concave minimization problems
- On solving general reverse convex programming problems by a sequence of linear programs and line searches
- Computational methods for solving nonconvex block-separable constrained quadratic problems
- scientific article; zbMATH DE number 994413 (Why is no real title available?)
- scientific article; zbMATH DE number 433001 (Why is no real title available?)
- Performance of approximate algorithms for global minimization
- Deterministic methods in constrained global optimization: Some recent advances and new fields of application
- A Conical Algorithm for Globally Minimizing a Concave Function Over a Closed Convex Set
- On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
- On geometry and convergence of a class of simplicial covers
- scientific article; zbMATH DE number 1861589 (Why is no real title available?)
- scientific article; zbMATH DE number 2190131 (Why is no real title available?)
- An inner approximation method incorporating a branch and bound procedure for optimization over the weakly efficient set
- On a finite branch and bound algorithm for the global minimization of a concave power law over a polytope
- Convergence analysis of a norm minimization-based convex vector optimization algorithm
- Robust bilevel optimization for near-optimal lower-level solutions
- On the global minimization of concave functions
- Concave minimization via conical partitions and polyhedral outer approximation
- Comparison of search strategies of branch and bound algorithm for concave minimization problems under linear constraints
This page was built for publication: A branch and bound-outer approximation algorithm for concave minimization over a convex set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q757243)
