Abstract

Fitzpatrick functions provide insights into the structure of operators. To help understand their information, we investigate their efficient numerical computation on a grid for operators with finite graphs defined on the real line. Our algorithms take advantage of existing computational Convex Analysis frameworks to improve previous worst-case time complexity results from quartic to quadratic. We also provide a linear-time algorithm for the computation of antiderivatives based on the Fitzpatrick function of infinite order

Author information

Contact details are reproduced from the original publication and may be historical.

Bryan Gardiner

Dept. of Computer Science, I. K. Barber School of Arts and Sciences, University of British Columbia, 3333 University Way, Kelowna BC V1V 1V7, Canada

Yves Lucet

Dept. of Computer Science, I. K. Barber School of Arts and Sciences, University of British Columbia, 3333 University Way, Kelowna BC V1V 1V7, Canada

yves.lucet@ubc.ca

References

  1. E. Asplund: A monotone convergence theorem for sequences of nonlinear mappings, in: Nonlinear Functional Analysis (Chicago, 1968), Proc. Sympos. Pure Math. 18, Part 1, Amer. Math. Soc., Providence (1970) 1–9.https://doi.org/10.1090/pspum/018.1/0275240Google Scholar
  2. S. Bartz, H. H. Bauschke, J. M. Borwein, S. Reich, X. Wang: Fitzpatrick functions, cyclic monotonicity and Rockafellar’s antiderivative, Nonlinear Anal., Theory Methods Appl. 66A (2007) 1198–1223.https://doi.org/10.1016/j.na.2006.01.013Google Scholar
  3. H. H. Bauschke: Fenchel duality, Fitzpatrick functions and the extension of firmly nonexpansive mappings, Proc. Amer. Math. Soc. 135 (2007) 135–139.https://doi.org/10.1090/S0002-9939-06-08770-3Google Scholar
  4. H. H. Bauschke, J. M. Borwein, X. Wang: Fitzpatrick functions and continuous linear monotone operators, SIAM J. Optim. 18 (2007) 789–809.https://doi.org/10.1137/060655468Google Scholar
  5. H. H. Bauschke, Y. Lucet, X. Wang: Primal-dual symmetric intrinsic methods for finding antiderivatives of cyclically monotone operators, SIAM J. Control Optim. 46 (2007) 2031–2051.https://doi.org/10.1137/060675794Google Scholar
  6. H. H. Bauschke, D. A. McLaren, H. S. Sendov: Fitzpatrick functions: inequalities, examples, and remarks on a problem by S. Fitzpatrick, J. Convex Analysis 13 (2006) 499–523.https://doi.org/10.68381/jca13043Google Scholar
  7. H. H. Bauschke, X. Wang: A convex-analytical approach to extension results for n-cyclically monotone operators, Set-Valued Anal. 15 (2007) 297–306.https://doi.org/10.1007/s11228-006-0029-1Google Scholar
  8. J. M. Borwein: Maximal monotonicity via convex analysis, J. Convex Analysis 13 (2006) 561–586.https://doi.org/10.68381/jca13045Google Scholar
  9. J. M. Borwein, C. H. Hamilton: Symbolic Fenchel conjugation, Math. Program., Ser. B 116 (2009) 17–35.https://doi.org/10.1007/s10107-007-0134-4Google Scholar
  10. R. I. Boţ, E. R. Csetnek, G. Wanka: A new condition for maximal monotonicity via representative functions, Nonlinear Anal., Theory Methods Appl. 67A (2007) 2390–2402.https://doi.org/10.1016/j.na.2006.09.006Google Scholar
  11. P. F. Felzenszwalb, D. P. Huttenlocher: Distance transforms of sampled functions, Tech. Rep. TR2004-1963, Cornell Computing and Information Science (Sept. 2004).Google Scholar
  12. S. Fitzpatrick: Representing monotone operators by convex functions, in: Functional Analysis and Optimization, Workshop / Miniconference (Canberra, 1988), Proc. Cent. Math. Anal. Aust. Natl. Univ. 20, Australian National University, Canberra (1988) 59–65.Google Scholar
  13. D. Lambert, J.-P. Crouzeix, V. H. Nguyen, J.-J. Strodiot: Finite convex integration, J. Convex Analysis 11 (2004) 131–146.https://doi.org/10.68381/jca11009Google Scholar
  14. Y. Lucet: Faster than the fast Legendre transform, the linear-time Legendre transform, Numer. Algorithms 16 (1997) 171–185.https://doi.org/10.1023/A:1019191114493Google Scholar
  15. Y. Lucet, H. H. Bauschke, M. Trienis: The piecewise linear-quadratic model for computational convex analysis, Comput. Optim. Appl. 43 (2009) 95–118.https://doi.org/10.1007/s10589-007-9124-yGoogle Scholar
  16. J.-P. Penot, C. Zălinescu: Continuity of the Legendre-Fenchel transform for some variational convergences, Optimization 53 (2004) 549–562.https://doi.org/10.1080/02331930412331329533Google Scholar
  17. S. Reich, S. Simons: Fenchel duality, Fitzpatrick functions and the Kirszbraun-Valentine extension theorem, Proc. Amer. Math. Soc. 133 (2005) 2657–2660.https://doi.org/10.1090/S0002-9939-05-07983-9Google Scholar
  18. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  19. R. T. Rockafellar: On the maximal monotonicity of subdifferential mappings, Pacific J. Math. 33 (1970) 209–216.https://doi.org/10.2140/pjm.1970.33.209Google Scholar
  20. S. Simons: Dualized and scaled Fitzpatrick functions, Proc. Amer. Math. Soc. 134 (2006) 2983–2987.https://doi.org/10.1090/S0002-9939-06-08363-8Google Scholar
  21. S. Simons: The Fitzpatrick function and nonreflexive spaces, J. Convex Analysis 13 (2006) 861–881.https://doi.org/10.68381/jca13064Google Scholar
  22. S. Simons, C. Zălinescu: Fenchel duality, Fitzpatrick functions and maximal monotonicity, J. Nonlinear Convex Anal. 6 (2005) 1–22.Google Scholar
  23. M. D. Voisei: Extension theorems for k-monotone operators, Stud. Cercet. Ştiinţ., Ser. Mat., Univ. Bacău 9 (1999) 235–242Google Scholar
  24. C. Zălinescu: A new proof of the maximal monotonicity of the sum using the Fitzpatrick function, in: Variational Analysis and Applications, F. Giannessi, A. Maugeri (eds.), Nonconvex Optim. Appl. 79, Springer, New York (2005) 1159–1172.https://doi.org/10.1007/0-387-24276-7_66Google Scholar

Suggested citation

B. Gardiner, Y. Lucet. “Numerical Computation of Fitzpatrick Functions.” Journal of Convex Analysis 16 (2009), No. 3&4, 779–790. https://doi.org/10.68381/jca16047

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2009. Rights now held by Banach Press.