Advanced

Efficient Optimization for L-infinity Problems using Pseudoconvexity

Olsson, Carl LU ; Eriksson, Anders P LU and Kahl, Fredrik LU (2007) IEEE 11th International Conference on Computer Vision, 2007. ICCV 2007 In 2007 IEEE 11th International Conference on Computer Vision, vols 1-6 p.2025-2032
Abstract
In this paper we consider the problem of solving geometric reconstruction problems with the L-infinity-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-infinity-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... (More)
In this paper we consider the problem of solving geometric reconstruction problems with the L-infinity-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-infinity-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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
2007 IEEE 11th International Conference on Computer Vision, vols 1-6
pages
2025 - 2032
conference name
IEEE 11th International Conference on Computer Vision, 2007. ICCV 2007
external identifiers
  • WOS:000255099302001
ISSN
1550-5499
language
English
LU publication?
yes
id
adbccfda-1083-4f4b-9b2b-6b3ee1918530 (old id 787821)
date added to LUP
2008-01-10 11:56:48
date last changed
2016-07-11 16:32:40
@misc{adbccfda-1083-4f4b-9b2b-6b3ee1918530,
  abstract     = {In this paper we consider the problem of solving geometric reconstruction problems with the L-infinity-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-infinity-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.},
  author       = {Olsson, Carl and Eriksson, Anders P and Kahl, Fredrik},
  issn         = {1550-5499},
  language     = {eng},
  pages        = {2025--2032},
  series       = {2007 IEEE 11th International Conference on Computer Vision, vols 1-6},
  title        = {Efficient Optimization for L-infinity Problems using Pseudoconvexity},
  year         = {2007},
}