Convex lower bound functions and their use in global optimization
Final Report Abstract
In dem Forschungsvorhaben wurden Verfahren zu Konstruktion von konstanten und affinen unteren Schrankenfunktionen für Polynome in mehreren Variablen entwickelt, die auf der Entwicklung eines Polynoms in Bernstein-Polynome beruhen. Die Verfahren können im Rahmen von branch and bound-Verfahren zur Lösung von restringierten polynomialen globalen Optimierungsproblemen oder von polynomialen Gleichungssystemen eingesetzt werden. Die erhaltenen Schrankenfunktionen können auch garantiert werden hinsichtlich aller während der Rechnung auftretenden Rundungsfehler und sogar hinsichtlich Ungenauigkeiten in den Polynomkoeffizienten. Für den Abstand des gegebenen Polynoms von der Schrankenfunktion wurden obere Schranken angegeben. Es wurde ein Softwarepaket erstellt, welches in eine Programmbibliothek integriert und so interessierten Nutzern zugänglich ist. Die Ergebnisse wurden in einer Reihe von Arbeiten publiziert und in zahlreichen Vorträgen auf internationalen Tagungen einem größeren Publikum vorgestellt. Die Höhe des Grades der Polynome scheint kein Problem für die Verfahren zu sein; es wurden allerdings in der Literatur auch keine Probleme hohen Grades gefunden. In den Anwendungen treten sehr häufig dünnbesetzte Polynome auf; fiir diese lassen sich auch bei großer Anzahl der Variablen noch problemlos konstante untere Schrankenfunktionen angeben. Die Verfahren wurden angewendet zur Parameterschätzung bei Modellen, welche auf Exponentialsummen beruhen. Die dort angewendeten Methoden wurden erweitert zur Einschließung der Lösungen von parametrischen linearen Gleichungssystemen.
Publications
- A Method for the Computation of Guaranteed Affine Bound Functions for Smooth Functions 12th GAMM - IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (SCAN 2006), 26, - 29. 9. 2006, Duisburg
- Affine Lower Bound Functions for Polynomials and Their Use in Global Optimization 8th International Workshop on High Performance Optimization Techniques - Optimization and Polynomials (HPOPT 2004), 23. - 25.6.04, Amsterdam
- J. Garloff und A. P. Smith A Comparison of Methods for the Computation of Affine Lower Bound Functions for Polynomials in 'Global Optimization and Constraint Satisfaction', hrsg. von C. Jermann, A. Neumaier und D. Sam, Lecture Notes in Computer Science Nr. 3478, Springer- Verlag, Berlin, Heidelberg, S. 71-85 (2005)
- J. Garloff und A. P. Smith Rigorous Affine Lower Bound Functions for Multivariate Polynomials and Their Use in Global Optimisation in 'Global Optimization, Proceedings Intern. Workshop on Global Optimization, Almeria, Spanien, 18.-22. Sept. 2005', hrsg. von L. G. Casado, I. Garcia, E. M. T. Hendrix undB. Töth, S. 109-113 (2005)
- J. Garloff, I. Idriss und A. P. Smith Guaranteed Parameter Set Estimation for Exponential Sums: The Three-terms Case Reliable Computing 13, S. 351-359 (2007)
- J. Garloff, I. Idriss und A. P. Smith Parametermengenschätzung bei Exponentialsummen Horizonte 27, 8-11 (2005)
- J. Garloff, L. Granvilliers und A. P. Smith Accelerating Consistency Techniques and Prony's Method for Reliable Parameter Estimation of Exponential Sums in 'Global Optimization and Constraint Satisfaction', hrsg. von C. Jermann, A. Neumaier und D. Sam, Lecture Notes in Computer Science Nr. 3478, Springer- Verlag, Berlin, Heidelberg, S. 31-45 (2005)
- J. GarloffundA.P. Smith An Improved Method for the Computation of Affine Lower Bound Functions for Polynomials in 'Frontiers in Global Optimization', hrsg. von C. A. Floudas und P. M. Pardalos, Reihe Nonconvex Optimization and Its Applications, Kluwer Academic Publishers, Dordrecht, Boston, London, S. 135-144 (2004)
- Rigorous Affine Lower Bound Functions for Multivariate Polynomials and Their Use in Global Optimisation 21th European Conference on Operational Research (EURO XXI), 2. - 5. 7.2006, Reykjavik, Island
- Rigorous Affine Underestimators for Smooth Functions International Workshop 'Global Optimization - Integrating Convexity, Optimization, Logic Programming, and Computational Algebraic Geometry', 4. - 8.12.2006, Wien.
