Convex and quasiconvex functions in metric graphs

Leandro M. Del Pezzo; Nicolás Frevenza; Julio D. Rossi; Leandro M. Del Pezzo; Nicolás Frevenza; Julio D. Rossi

doi:10.3934/nhm.2021019

Networks and Heterogeneous Media

2021, Volume 16, Issue 4: 591-607. doi: 10.3934/nhm.2021019

Previous Article Next Article

Convex and quasiconvex functions in metric graphs

1.
CONICET and Departamento de Matemática, FCEyN, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria (1428), Buenos Aires, Argentina
2.
Departamento de Métodos Matemáticos y Cuantitativos, FCEA, Universidad de la República, Gonzalo Ramírez 1926 (11200), Montevideo, Uruguay

Received: 01 February 2021 Revised: 01 May 2021 Published: 28 June 2021
Primary: 05C12, 52A41

We study convex and quasiconvex functions on a metric graph. Given a set of points in the metric graph, we consider the largest convex function below the prescribed datum. We characterize this largest convex function as the unique largest viscosity subsolution to a simple differential equation, $ u'' = 0 $ on the edges, plus nonlinear transmission conditions at the vertices. We also study the analogous problem for quasiconvex functions and obtain a characterization of the largest quasiconvex function that is below a given datum.
- Convexity,
- quasiconvexity,
- metric graph,
- convex envelope,
- quasiconvex envelope
Citation: Leandro M. Del Pezzo, Nicolás Frevenza, Julio D. Rossi. Convex and quasiconvex functions in metric graphs[J]. Networks and Heterogeneous Media, 2021, 16(4): 591-607. doi: 10.3934/nhm.2021019

Related Papers:

Abstract

We study convex and quasiconvex functions on a metric graph. Given a set of points in the metric graph, we consider the largest convex function below the prescribed datum. We characterize this largest convex function as the unique largest viscosity subsolution to a simple differential equation, $ u'' = 0 $ on the edges, plus nonlinear transmission conditions at the vertices. We also study the analogous problem for quasiconvex functions and obtain a characterization of the largest quasiconvex function that is below a given datum.

References

[1]	A partial differential equation for the \begin{document}$ \epsilon $\end{document}-uniformly quasiconvex envelope. IMA J. Numer. Anal. (2019) 39: 141-166.
[2]	Computing the level set convex hull. J. Sci. Comput. (2018) 75: 26-42.
[3]	Functions which are quasiconvex under linear perturbations. SIAM J. Optim. (2012) 22: 1089-1108.
[4]	Quasiconvex functions and nonlinear PDEs. Trans. Amer. Math. Soc. (2013) 365: 4229-4255.
[5]	The quasiconvex envelope through first-order partial differential equations which characterize quasiconvexity of nonsmooth functions. Discrete Contin. Dyn. Syst. Ser. B (2012) 17: 1693-1706.
[6]	G. Berkolaiko and P. Kuchment, Introduction to Quantum Graphs, Mathematical Surveys and Monographs, 186, American Mathematical Society, Providence, RI, 2013. doi: 10.1090/surv/186
[7]	Games for eigenvalues of the Hessian and concave/convex envelopes. J. Math. Pures Appl. (2019) 127: 192-215.
[8]	Steiner distance and convexity in graphs. European J. Combin. (2008) 29: 726-736.
[9]	Convex envelopes on trees. J. Convex Anal. (2020) 27: 1195-1218.
[10]	Nonconvex duality in multiobjective optimization. Math. Oper. Res. (1977) 2: 285-291.
[11]	A. Eberhard and C. E. M. Pearce, Class-inclusion properties for convex functions, in Progress in Optimization ({P}erth, 1998), Appl. Optim., 39, Kluwer Acad. Publ., Dordrecht, 2000,129-133. doi: 10.1007/978-1-4613-0301-5_9
[12]	On the connection between tug-of-war games and nonlocal PDEs on graphs. C. R. Mécanique (2017) 345: 177-183.
[13]	Convexity in graphs and hypergraphs. SIAM J. Algebraic Discrete Methods (1986) 7: 433-444.
[14]	On local convexity in graphs. Discrete Math. (1987) 66: 231-247.
[15]	Elementary proof for Sion's minimax theorem. Kodai Math. J. (1988) 11: 5-7.
[16]	Nonlinear elliptic partial differential equations and $p-$harmonic functions on graphs. Differential Integral Equations (2015) 28: 79-102.
[17]	Discrete convex analysis. Math. Programming (1998) 83: 313-371.
[18]	K. Murota, Discrete Convex Analysis, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2003. doi: 10.1137/1.9780898718508
[19]	K. Murota, Recent developments in discrete convex analysis, in Research Trends in Combinatorial Optimization, Springer, Berlin, 2009,219-260. doi: 10.1007/978-3-540-76796-1_11
[20]	C. P. Niculescu and L.-E. Persson, Convex Functions and Their Applications, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 23, Springer, New York, 2006., doi: 10.1007/0-387-31077-0
[21]	The convex envelope is the solution of a nonlinear obstacle problem. Proc. Amer. Math. Soc. (2007) 135: 1689-1694.
[22]	The Dirichlet problem for the convex envelope. Trans. Amer. Math. Soc. (2011) 363: 5871-5886.
[23]	C. E. M. Pearce, Quasiconvexity, fractional programming and extremal traffic congestion, in Frontiers in Global Optimization, Nonconvex Optim. Appl., 74, Kluwer Acad. Publ., Boston, MA, 2004,403-409. doi: 10.1007/978-1-4613-0251-3_22
[24]	I. M. Pelayo, Geodesic Convexity in Graphs, SpringerBriefs in Mathematics, Springer, New York, 2013. doi: 10.1007/978-1-4614-8699-2
[25]	On general minimax theorems. Pacific J. Math. (1958) 8: 171-176.
[26]	M. L. J. van de Vel, Theory of Convex Structures, North-Holland Mathematical Library, 50, North-Holland Publishing Co., Amsterdam, 1993.

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)