| Title: | Efficient Optimization for L-infinity Problems using Pseudoconvexity |
| Fulltext: |  |
| Authors: | Olsson, Carl and Eriksson, Anders and Kahl, Fredrik |
| Year: | 2007 |
| Document Type: | Conference Paper |
| Conference: | International Conference on Computer Vision |
| Conference location: | Rio de Janeiro |
| Status: | In Press |
| Refereed: | Yes |
| BibTeX item: |  |
| Abstract: | In this paper we consider the problem of solving geometric reconstruction problems with the $L_infty$-norm. Previous work has shown that globally optimal solutions can be computed reliably for a series of such problems. The methods for computing the solutions have relied on the property of quasiconvexity. For quasiconvex problems, checking if there exists a solution below a certain objective value can be posed as a convex feasibility problem. To solve the $L_infty$-problem one typically employs a bisection algorithm, generating a sequence of convex problems. In this paper we present more efficient ways of computing the solutions. We derive necessary and sufficient conditions for a global optimum. A key property is that of pseudoconvexity, which is a stronger condition than quasiconvexity. The results open up the possibility of using local optimization methods for more efficient computations. We present two such algorithms. The first one is an interior point method that uses the KKT conditions and the second one is similar to the bisection method in the sense it solves a sequence of SOCP problems. Results are presented and compared to the standard bisection algorithm on real data for various problems and scenarios with improved performance. |
Similar Publications
- Journal paper:
Verifying Global Minima for L2 Minimization Problems in Multiple View Geometry
Richard Hartley
Fredrik Kahl
Carl Olsson
Yongduek Seo - Journal paper:
An Efficient Optimization Framework for Multi-Region Segmentation based on Lagrangian Duality
Johannes Ulén
Petter Strandmark
Fredrik Kahl - Conference paper:
Pseudo-Boolean Optimization: Theory and Applications in Vision
Petter Strandmark
Fredrik Kahl
Questions: webmaster
Last updated: 2012-01-17
Centre for Mathematical Sciences, Box 118, SE-22100, Lund. Phone: 046-222 00 00