Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Normal Numbers and Pseudorandom Generators Read chapter Read first chapter

2013 | OriginalPaper | Chapter

23. Techniques and Open Questions in Computational Convex Analysis

Author : Yves Lucet

Published in: Computational and Analytical Mathematics

Publisher: Springer New York

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We present several techniques that take advantage of convexity and use optimal computational geometry algorithms to build fast (log-linear or linear) time algorithms in computational convex analysis. The techniques that have strong potential to be reused include: monotonicity of the argmax and injecting convexity to use that monotonicity, Lipschitzness of the argmin, exploiting various formulas in convex analysis, using a graph data structure to vectorize computation, and building a parametrization of the graph. We also point out the potential for parallelization. The techniques can be used as a check list on open problems to find an efficient algorithm. Finally, we list several currently open questions in computational convex analysis with links to computational geometry.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter On the Convergence of Iteration Processes for Semigroups of Nonlinear Mappings in Banach Spaces
next chapter Existence and Approximation of Fixed Points of Right Bregman Nonexpansive Operators
Literature
1.
Balaban, I.J.: An optimal algorithm for finding segments intersections. In: Proceedings of the Eleventh Annual Symposium on Computational Geometry, SCG ’95, pp. 211–219. ACM, New York (1995)
2.
Bauschke, H.H., Goebel, R., Lucet, Y., Wang, X.: The proximal average: Basic theory. SIAM J. Optim. 19, 768–785 (2008)MathSciNetCrossRef
3.
Bauschke, H.H., Lucet, Y., Trienis, M.: How to transform one convex function continuously into another. SIAM Rev. 50, 115–132 (2008)MathSciNetCrossRefMATH
4.
Bauschke, H.H., Lucet, Y., Wang, X.: Primal-dual symmetric intrinsic methods for finding antiderivatives of cyclically monotone operators. SIAM J. Control Optim. 46, 2031–2051 (2007)MathSciNetCrossRefMATH
5.
Bauschke, H.H., Moffat, S.M., Wang, X.: Self-dual smooth approximations of convex functions via the proximal average. In: Bauschke, H.H., Burachik, R.S., Combettes, P.L., Elser, V., Luke, D.R., Wolkowicz, H. (eds.) Fixed-Point Algorithms for Inverse Problems in Science and Engineering. Springer Optimization and Its Applications 49, pp. 23–32. Springer, New York (2011)CrossRef
6.
Berkman, O., Schieber, B., Vishkin, U.: A fast parallel algorithm for finding the convex hull of a sorted point set. Internat. J. Comput. Geom. Appl. 6, 231–241 (1996)MathSciNetCrossRefMATH
7.
Borwein, J.M., Hamilton, C.H.: Symbolic computation of multidimensional Fenchel conjugates. In: ISSAC 2006, ACM, pp. 23–30. New York (2006)
8.
Bremner, D., Chan, T.M., Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., Taslakian, P.: Necklaces, convolutions, and X + Y. In: Algorithms—ESA 2006, Lecture Notes in Computer Science, vol. 4168, pp. 160–171. Springer, Berlin (2006)
9.
Brenier, Y.: Un algorithme rapide pour le calcul de transformées de Legendre–Fenchel discrètes. C. R. Acad. Sci. Paris Sér. I Math. 308, 587–589 (1989)MathSciNetMATH
10.
Chan, T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete Comput. Geom. 16, 361–368 (1996). Eleventh Annual Symposium on Computational Geometry (Vancouver, BC, 1995)
11.
Chen, D.: Efficient geometric algorithms on the erew pram. Parallel and Distributed Systems, IEEE Transactions on 6, 41 –47 (1995)CrossRef
12.
13.
Corrias, L.: Fast Legendre–Fenchel transform and applications to Hamilton–Jacobi equations and conservation laws. SIAM J. Numer. Anal. 33, 1534–1558 (1996)MathSciNetCrossRefMATH
14.
Deniau, L., Blanc-Talon, J.: Fractal analysis with Hausdorff distance under affine transformations. Tech. report, ETCA-CREA-SP (1995)
15.
Eppstein, D., Goodrich, M.T., Strash, D.: Linear-time algorithms for geometric graphs with sublinearly many crossings. In: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 150–159. SIAM, Philadelphia, PA (2009)
16.
Felzenszwalb, P.F., Huttenlocher, D.P.: Distance transforms of sampled functions. Tech. Report TR2004-1963, Cornell Computing and Information Science (Sept. 2004)
17.
Gardiner, B., Lucet, Y.: Convex hull algorithms for piecewise linear-quadratic functions in computational convex analysis. Set-Valued Var. Anal. 18, 467–482 (2010)MathSciNetCrossRefMATH
18.
Gardiner, B., Lucet, Y.: Computing the conjugate of convex piecewise linear-quadratic bivariate functions. Math. Program. Ser. B 139, 161–184 (2011)MathSciNetCrossRef
19.
Gardiner, B., Lucet, Y.: Graph-matrix calculus for computational convex analysis. In: Bauschke, H.H., Burachik, R.S., Combettes, P.L., Elser, V., Luke, D.R., Wolkowicz, H.(eds). Fixed-Point Algorithms for Inverse Problems in Science and Engineering. Springer Optimization and Its Applications, vol. 49, pp. 243–259. Springer, New York (2011)CrossRef
20.
Goebel, R.: Self-dual smoothing of convex and saddle functions. J. Convex Anal. 15, 179–190 (2008)MathSciNetMATH
21.
22.
Gupta, N., Sen, S.: Optimal, output-sensitive algorithms for constructing planar hulls in parallel. Comput. Geom. 8, 151–166 (1997)MathSciNetCrossRefMATH
23.
Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms, Vol. I: Fundamentals, Vol. II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] vol. 305–306, Springer, Berlin (1993)
24.
Hiriart-Urruty, J.-B., Lucet, Y.: Parametric computation of the Legendre–Fenchel conjugate. J. Convex Anal. 14, 657–666 (2007)MathSciNet
25.
26.
Lachand-Robert, T., Oudet, É: Minimizing within convex bodies using a convex hull method. SIAM J. Optim. 16, 368–379 (2005) (electronic)
27.
Lachand-Robert, T., Peletier, M.A.: The minimum of quadratic functionals of the gradient on the set of convex functions. Calc. Var. Part. Differ. Equat. 15, 289–297 (2002)MathSciNetCrossRefMATH
28.
29.
30.
31.
Lucet, Y.: A linear Euclidean distance transform algorithm based on the Linear-time Legendre Transform. In: Proceedings of the Second Canadian Conference on Computer and Robot Vision (CRV 2005), pp. 262–267, IEEE Computer Society Press, Victoria BC (2005)
32.
33.
Lucet, Y.: What shape is your conjugate? A survey of computational convex analysis and its applications. SIAM Rev. 52, 505–542 (2010)MathSciNetMATH
34.
35.
Moreau, J.-J.: Proximité et dualité dans un espace Hilbertien. Bull. Soc. Math. France 93, 273–299 (1965)MathSciNetMATH
36.
Noullez, A., Vergassola, M.: A fast Legendre transform algorithm and applications to the adhesion model. J. Sci. Comput. 9, 259–281 (1994)MathSciNetCrossRefMATH
37.
Oberman, A.M.: Computing the convex envelope using a nonlinear partial differential equation. Math. Models Methods Appl. Sci. 18, 759–780 (2008)MathSciNetCrossRefMATH
38.
Oberman, A.M.: The convex envelope is the solution of a nonlinear obstacle problem. Proc. Amer. Math. Soc. 135, 1689–1694 (2007) (electronic)
39.
Rauber, T., Rünger, G.: Parallel Programming: for Multicore and Cluster Systems. Springer Publishing Company Incorporated, New York (2010)CrossRef
40.
41.
Wang, Y.-R., Horng, S.-J.: An O(1)time algorithm for the 3D Euclidean distance transform on the CRCW PRAM model. IEEE Trans. Parallel Distr. Syst. 14, 973–982 (2003)CrossRef
Metadata
Title
Techniques and Open Questions in Computational Convex Analysis
Author
Yves Lucet
Copyright Year
2013
Publisher
Springer New York
Book
Computational and Analytical Mathematics

Print ISBN: 978-1-4614-7620-7

Electronic ISBN: 978-1-4614-7621-4

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-1-4614-7621-4_23

Premium Partner

    Image Credits