Subdivision of simplices relative to a cutting plane and finite concave minimization
| Autor: | Michael Nast |
|---|---|
| Rok vydání: | 1996 |
| Předmět: |
Control and Optimization
Branch and bound Concave function Applied Mathematics Regular polygon Barycentric subdivision Management Science and Operations Research Computer Science Applications Combinatorics Polyhedron Triangulation (geometry) Cutting-plane method Mathematics Simplicial approximation theorem |
| Zdroj: | Journal of Global Optimization. 9:65-93 |
| ISSN: | 1573-2916 0925-5001 |
| DOI: | 10.1007/bf00121751 |
| Popis: | In this article, our primary concern is the classical problem of minimizing globally a concave function over a compact polyhedron (Problem (P)). We present a new simplicial branch and bound approach, which combines triangulations of intersections of simplices with halfspaces and ideas from outer approximation in such a way, that a class of finite algorithms for solving (P) results. For arbitrary compact convex feasible sets one obtains a not necessarily finite but convergent algorithm. Theoretical investigations include determination of the number of simplices in each applied triangulation step and bounds on the number of iterations in the resulting algorithms. Preliminary numerical results are given, and additional applications are sketched. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink