Separable concave minimization via partial outer approximation and branch and bound
From MaRDI portal
Publication:2277369
The paper presents an algorithm for globally minimizing a separable, concave function over a compact convex set. The algorithm combines partial outer approximation and branch-and-bound in a manner specifically designed to exploit the separability of the objective function. The major computational effort required is to solve linear programming problems at some nodes of the branch-and-bound tree, and to solve simple univariate minimization problems in some iterations. The outer approximation used in the algorithm is partial in the sense that many of the cutting planes that it creates are not added as constraints in a number of the linear programming subproblems solved during the branch-and-bound search.
Recommendations
- A branch and bound-outer approximation algorithm for concave minimization over a convex set
- Concave minimization via conical partitions and polyhedral outer approximation
- A finite algorithm for global minimization of separable concave programs
- scientific article; zbMATH DE number 970356
- A Conical Algorithm for Globally Minimizing a Concave Function Over a Closed Convex Set
Cites work
- A Conical Algorithm for Globally Minimizing a Concave Function Over a Closed Convex Set
- A cutting plane algorithm for solving bilinear programs
- A finite algorithm for concave minimization over a polyhedron
- A finitely convergent algorithm for bilinear programming problems using polar cuts and disjunctive face cuts
- 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 relaxation algorithm for the minimization of a quasiconcave function on a convex polyhedron
- A Successive Underestimation Method for Concave Minimization Problems
- An algorithm for nonconvex programming problems
- An Algorithm for Separable Nonconvex Programming Problems
- An outer approximation method for globally minimizing a concave function over a compact convex set
- Concave minimization over a convex polyhedron
- Concave Minimization Via Collapsing Polytopes
- Concave minimization via conical partitions and polyhedral outer approximation
- Constrained global optimization: algorithms and applications
- Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and d.c. optimization problems
- Convergent Algorithms for Minimizing a Concave Function
- Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization, reserve convex constraints, DC-programming and Lipschitzian optimization
- Global Maximization of a Convex Function with Linear Inequality Constraints
- Global Minimization in Nonconvex All-Quadratic Programming
- scientific article; zbMATH DE number 3215121 (Why is no real title available?)
- scientific article; zbMATH DE number 3347922 (Why is no real title available?)
- Jointly Constrained Biconvex Programming
- Methods for Global Concave Minimization: A Bibliographic Survey
- On Connections Between Zero-One Integer Programming and Concave Programming Under Linear Constraints
- On finding new vertices and redundant constraints in cutting plane algorithms for global optimization
- On outer approximation methods for solving concave minimization problems
- On the convergence of two branch-and-bound algorithms for nonconvex programming problems
- On the global minimization of concave functions
- On the structure and properties of a linear multilevel programming problem
- Outer approximation by polyhedral convex sets
- Quasi-concave minimization subject to linear constraints
- Relationship between bilinear programming and concave minimization under linear constraints
- Separable concave minimization via partial outer approximation and branch and bound
- Simplicial branch-and-reduce algorithm for convex programs with a multiplicative constraint
- Variations on a cutting plane method for solving concave minimization problems with linear constraints
Cited in
(12)- A new simplicial cover technique in constrained global optimization
- Nonlinear programming for multiperiod capacity planning in a manufacturing system
- A composite branch and bound, cutting plane algorithm for concave minimization over a polyhedron
- Computational comparison of two methods for constrained global optimization
- Capacity planning in networks of queues with manufacturing applications
- A note on adapting methods for continuous global optimization to the discrete case
- Separable concave minimization via partial outer approximation and branch and bound
- Sufficient optimality criterion for linearly constrained, separable concave minimization problems
- Improved convex and concave relaxations of composite bilinear forms
- A continuous approch for globally solving linearly constrained quadratic
- New formulations of the multiple sequence alignment problem
- On a finite branch and bound algorithm for the global minimization of a concave power law over a polytope
This page was built for publication: Separable concave minimization via partial outer approximation and branch and bound
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277369)
