Integral Methods for Quadratic Programming: Theory and Implementation
Seiten
This PhD thesis was written at ETH Zürich, in Prof. Dr. Emo Welzl's research group, under the supervision of Dr. Bernd Gärnter. It shows two theoretical results that are both related to quadratic programming.
The first one concerns the abstract optimization framework of violator spaces and the randomized procedure called Clarkson's algorithm. In a nutshell, the algorithm randomly samples from a set of constraints, computes an optimal solution subject to these constraints, and then checks whether the ignored constraints violate the solution. If not, some form of re-sampling occurs. We present the algorithm in the easiest version that can still be analyzed successfully.
The second contribution concerns quadratic programming more directly. It is well-known that a simplex-like procedure can be applied to quadratic programming. The main computational effort in this algorithm comes from solving a series of linear equation systems that change gradually. We develop the integral LU decomposition of matrices, which allows us to solve the equation systems efficiently and to exploit sparse inputs.
Last but not least, a considerable portion of the work included in this thesis was devoted to implementing the integral LU decomposition in the framework of the existing quadratic programming solver in the Computational Geometry Algorithms Library (CGAL). In the last two chapters we describe our implementation and the experimental results we obtained.
Die Kunst der Übersetzung
| Erscheint lt. Verlag | 20.3.2013 |
|---|---|
| Sprache | englisch |
| Maße | 145 x 210 mm |
| Einbandart | Paperback |
| Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
| Mathematik / Informatik ► Mathematik | |
| Schlagworte | Abstrakte Optimierungsverfahren, Abstract Optimization Frameworks • Dünne Matrizen, Sparse Matrices • Dünne Matrizen, Sparse Matrices • Konvexe Optimierung, Convex Optimization • Matrixzerlegungen, Matrix Factorizations • Quadratisches Programm, Quadratic Program |
| ISBN-10 | 3-8325-3366-4 / 3832533664 |
| ISBN-13 | 978-3-8325-3366-3 / 9783832533663 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
Buch | Softcover (2024)
Lehmanns Media (Verlag)
CHF 55,95
IT zum Anfassen für alle von 9 bis 99 – vom Navi bis Social Media
Buch | Softcover (2021)
Springer (Verlag)
CHF 41,95
Interlingua zur Gewährleistung semantischer Interoperabilität in der …
Buch | Softcover (2023)
Springer Fachmedien (Verlag)
CHF 46,15
