What Shape is your Conjugate? A Survey of Computational Convex Analysis and its Applications

Yves Lucet (yves.lucetubc.ca)

Abstract: Computational Convex Analysis algorithms have been rediscovered several times in the past by researchers from different fields. To further communications between practitioners, we review the field of computational convex analysis, which focuses on the numerical computation of fundamental transforms arising from convex analysis. Current models use symbolic, numeric, and hybrid symbolic-numeric algorithms. Our objective is to disseminate widely the most efficient numerical algorithms, and to further communications between several fields benefiting from the same techniques. We survey applications of the algorithms which have been applied to problems arising from image processing (distance transform, generalized distance transform, mathematical morphology), partial differential equations (solving Hamilton-Jacobi equations, and using differential equations numerical schemes to compute the convex envelope), max-plus algebra, multi-fractal analysis, and several others. They span a wide range of applications in computer vision, robot navigation, phase transition in thermodynamics, electrical networks, medical imaging, network communications, discrete event systems, etc.

Keywords: Computational Convex Analysis, Fast Algorithms, Legendre-Fenchel Transform, Convex Envelope, Partial Differential Equations, Max-plus Algebra, Mathematical Morphology

Category 1: Applications -- OR and Management Sciences (Other )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Computer Science, UBC Okanagan, 3333 University Way, Kelowna BC V1V 1V7 December 2007

Download: [PDF]

Entry Submitted: 12/28/2007
Entry Accepted: 12/28/2007
Entry Last Modified: 02/20/2008

Modify/Update this entry