Skip to main content

2013 | OriginalPaper | Buchkapitel

23. Techniques and Open Questions in Computational Convex Analysis

verfasst von : Yves Lucet

Erschienen in: Computational and Analytical Mathematics

Verlag: Springer New York

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Bauschke, H.H., Goebel, R., Lucet, Y., Wang, X.: The proximal average: Basic theory. SIAM J. Optim. 19, 768–785 (2008)MathSciNetCrossRef Bauschke, H.H., Goebel, R., Lucet, Y., Wang, X.: The proximal average: Basic theory. SIAM J. Optim. 19, 768–785 (2008)MathSciNetCrossRef
3.
Zurück zum Zitat Bauschke, H.H., Lucet, Y., Trienis, M.: How to transform one convex function continuously into another. SIAM Rev. 50, 115–132 (2008)MathSciNetCrossRefMATH Bauschke, H.H., Lucet, Y., Trienis, M.: How to transform one convex function continuously into another. SIAM Rev. 50, 115–132 (2008)MathSciNetCrossRefMATH
4.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Borwein, J.M., Hamilton, C.H.: Symbolic computation of multidimensional Fenchel conjugates. In: ISSAC 2006, ACM, pp. 23–30. New York (2006) Borwein, J.M., Hamilton, C.H.: Symbolic computation of multidimensional Fenchel conjugates. In: ISSAC 2006, ACM, pp. 23–30. New York (2006)
8.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Chen, D.: Efficient geometric algorithms on the erew pram. Parallel and Distributed Systems, IEEE Transactions on 6, 41 –47 (1995)CrossRef Chen, D.: Efficient geometric algorithms on the erew pram. Parallel and Distributed Systems, IEEE Transactions on 6, 41 –47 (1995)CrossRef
12.
13.
Zurück zum Zitat Corrias, L.: Fast Legendre–Fenchel transform and applications to Hamilton–Jacobi equations and conservation laws. SIAM J. Numer. Anal. 33, 1534–1558 (1996)MathSciNetCrossRefMATH 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.
Zurück zum Zitat Deniau, L., Blanc-Talon, J.: Fractal analysis with Hausdorff distance under affine transformations. Tech. report, ETCA-CREA-SP (1995) Deniau, L., Blanc-Talon, J.: Fractal analysis with Hausdorff distance under affine transformations. Tech. report, ETCA-CREA-SP (1995)
15.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Felzenszwalb, P.F., Huttenlocher, D.P.: Distance transforms of sampled functions. Tech. Report TR2004-1963, Cornell Computing and Information Science (Sept. 2004) Felzenszwalb, P.F., Huttenlocher, D.P.: Distance transforms of sampled functions. Tech. Report TR2004-1963, Cornell Computing and Information Science (Sept. 2004)
17.
Zurück zum Zitat 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 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.
Zurück zum Zitat Gardiner, B., Lucet, Y.: Computing the conjugate of convex piecewise linear-quadratic bivariate functions. Math. Program. Ser. B 139, 161–184 (2011)MathSciNetCrossRef Gardiner, B., Lucet, Y.: Computing the conjugate of convex piecewise linear-quadratic bivariate functions. Math. Program. Ser. B 139, 161–184 (2011)MathSciNetCrossRef
19.
Zurück zum Zitat 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 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.
Zurück zum Zitat Goebel, R.: Self-dual smoothing of convex and saddle functions. J. Convex Anal. 15, 179–190 (2008)MathSciNetMATH Goebel, R.: Self-dual smoothing of convex and saddle functions. J. Convex Anal. 15, 179–190 (2008)MathSciNetMATH
21.
22.
Zurück zum Zitat Gupta, N., Sen, S.: Optimal, output-sensitive algorithms for constructing planar hulls in parallel. Comput. Geom. 8, 151–166 (1997)MathSciNetCrossRefMATH Gupta, N., Sen, S.: Optimal, output-sensitive algorithms for constructing planar hulls in parallel. Comput. Geom. 8, 151–166 (1997)MathSciNetCrossRefMATH
23.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Hiriart-Urruty, J.-B., Lucet, Y.: Parametric computation of the Legendre–Fenchel conjugate. J. Convex Anal. 14, 657–666 (2007)MathSciNet Hiriart-Urruty, J.-B., Lucet, Y.: Parametric computation of the Legendre–Fenchel conjugate. J. Convex Anal. 14, 657–666 (2007)MathSciNet
25.
26.
Zurück zum Zitat Lachand-Robert, T., Oudet, É: Minimizing within convex bodies using a convex hull method. SIAM J. Optim. 16, 368–379 (2005) (electronic) Lachand-Robert, T., Oudet, É: Minimizing within convex bodies using a convex hull method. SIAM J. Optim. 16, 368–379 (2005) (electronic)
27.
Zurück zum Zitat 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 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.
30.
Zurück zum Zitat Lucet, Y.: Faster than the Fast Legendre Transform, the Linear-time Legendre Transform. Numer. Algorithms 16, 171–185 (1997)MathSciNetCrossRefMATH Lucet, Y.: Faster than the Fast Legendre Transform, the Linear-time Legendre Transform. Numer. Algorithms 16, 171–185 (1997)MathSciNetCrossRefMATH
31.
Zurück zum Zitat 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) 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)
33.
Zurück zum Zitat Lucet, Y.: What shape is your conjugate? A survey of computational convex analysis and its applications. SIAM Rev. 52, 505–542 (2010)MathSciNetMATH Lucet, Y.: What shape is your conjugate? A survey of computational convex analysis and its applications. SIAM Rev. 52, 505–542 (2010)MathSciNetMATH
35.
Zurück zum Zitat Moreau, J.-J.: Proximité et dualité dans un espace Hilbertien. Bull. Soc. Math. France 93, 273–299 (1965)MathSciNetMATH Moreau, J.-J.: Proximité et dualité dans un espace Hilbertien. Bull. Soc. Math. France 93, 273–299 (1965)MathSciNetMATH
36.
Zurück zum Zitat Noullez, A., Vergassola, M.: A fast Legendre transform algorithm and applications to the adhesion model. J. Sci. Comput. 9, 259–281 (1994)MathSciNetCrossRefMATH Noullez, A., Vergassola, M.: A fast Legendre transform algorithm and applications to the adhesion model. J. Sci. Comput. 9, 259–281 (1994)MathSciNetCrossRefMATH
37.
Zurück zum Zitat Oberman, A.M.: Computing the convex envelope using a nonlinear partial differential equation. Math. Models Methods Appl. Sci. 18, 759–780 (2008)MathSciNetCrossRefMATH Oberman, A.M.: Computing the convex envelope using a nonlinear partial differential equation. Math. Models Methods Appl. Sci. 18, 759–780 (2008)MathSciNetCrossRefMATH
38.
Zurück zum Zitat Oberman, A.M.: The convex envelope is the solution of a nonlinear obstacle problem. Proc. Amer. Math. Soc. 135, 1689–1694 (2007) (electronic) Oberman, A.M.: The convex envelope is the solution of a nonlinear obstacle problem. Proc. Amer. Math. Soc. 135, 1689–1694 (2007) (electronic)
39.
Zurück zum Zitat Rauber, T., Rünger, G.: Parallel Programming: for Multicore and Cluster Systems. Springer Publishing Company Incorporated, New York (2010)CrossRef Rauber, T., Rünger, G.: Parallel Programming: for Multicore and Cluster Systems. Springer Publishing Company Incorporated, New York (2010)CrossRef
40.
41.
Zurück zum Zitat 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 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
Metadaten
Titel
Techniques and Open Questions in Computational Convex Analysis
verfasst von
Yves Lucet
Copyright-Jahr
2013
Verlag
Springer New York
DOI
https://doi.org/10.1007/978-1-4614-7621-4_23