Heuristic optimization methods for three matrix problems
(2012)
Files
th_final.pdf
Open Access - Adobe PDF
- 2.95 MB
Details
- Authors
- Supervisors
- Blondel, Vincent
- Abstract
- (en) Optimization is a major field in applied mathematics. Many applications involve the search of the best solution to a problem according to some criterion. Depending on the considered optimization problem, finding the best solution is not always possible in a reasonable amount of time. Heuristic algorithms are often used when the problem is too difficult to solve exactly. These methods are used to speed up the search for a good solution but they do not guarantee that an optimal solution will be found. In this thesis, we explore such heuristic approaches for three different matrix problems. First, we study the minimum-volume bounding box problem, which consists in finding the smallest rectangular parallelepiped enclosing a given set of points in the three-dimensional space. This problem appears for example in collision detection, which is a very important issue in computational geometry and computer graphics. In these applications, a solution has to be determined in a very short amount of time. We propose a new hybrid algorithm able to approximate optimal bounding boxes at a low computational cost. In particular, it is several orders of magnitude faster than the only currently known exact algorithm. Second, we investigate the subset selection problem. Given a large set of features, we want to choose a small subset containing the most relevant features while removing the redundant ones. This problem has applications in data mining since this can be seen as a dimensionality reduction problem. We develop several windowed algorithms that tackle the subset selection problem for the maximum-volume criterion, which is NP-hard. Finally, we address the topic of the approximation of the joint spectral radius. This quantity characterizes the growth rate of product of matrices and is NP-hard to approximate. The joint spectral radius appears in many fields, including system theory, graph theory, combinatorics, language theory... We present an experimental study of existing approaches and propose a new genetic-based algorithm that is able to find bounds on the joint spectral radius in a short amount of time.
- Affiliations
Citations
Chang, C.-T. (2012). Heuristic optimization methods for three matrix problems. https://hdl.handle.net/2078.5/159663