December  2021, 16(4): 591-607. doi: 10.3934/nhm.2021019

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  February 2021 Revised  May 2021 Published  December 2021 Early access  June 2021

Fund Project: L.D.P. and J.D.R. partially supported by CONICET grant PIP GI No 11220150100036CO (Argentina), PICT-2018-03183 (Argentina) and UBACyT grant 20020160100155BA (Argentina). J.D.R. is also supported by MINECO MTM2015-70227-P (Spain)

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.

Citation: Leandro M. Del Pezzo, Nicolás Frevenza, Julio D. Rossi. Convex and quasiconvex functions in metric graphs. Networks and Heterogeneous Media, 2021, 16 (4) : 591-607. doi: 10.3934/nhm.2021019
References:
[1]

B. Abbasi and A. M. Oberman, A partial differential equation for the $ \epsilon $-uniformly quasiconvex envelope, IMA J. Numer. Anal., 39 (2019), 141-166.  doi: 10.1093/imanum/drx068.

[2]

B. Abbasi and A. M. Oberman, Computing the level set convex hull, J. Sci. Comput., 75 (2018), 26-42.  doi: 10.1007/s10915-017-0522-8.

[3]

E. N. BarronR. Goebel and R. R. Jensen, Functions which are quasiconvex under linear perturbations, SIAM J. Optim., 22 (2012), 1089-1108.  doi: 10.1137/110843496.

[4]

E. N. BarronR. Goebel and R. R. Jensen, Quasiconvex functions and nonlinear PDEs, Trans. Amer. Math. Soc., 365 (2013), 4229-4255.  doi: 10.1090/S0002-9947-2013-05760-1.

[5]

E. N. BarronR. Goebel and R. R. Jensen, The quasiconvex envelope through first-order partial differential equations which characterize quasiconvexity of nonsmooth functions, Discrete Contin. Dyn. Syst. Ser. B, 17 (2012), 1693-1706.  doi: 10.3934/dcdsb.2012.17.1693.

[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]

P. Blanc and J. D. Rossi, Games for eigenvalues of the Hessian and concave/convex envelopes, J. Math. Pures Appl., 127 (2019), 192-215.  doi: 10.1016/j.matpur.2018.08.007.

[8]

J. CáceresA. Márquez and M. L. Puertas, Steiner distance and convexity in graphs, European J. Combin., 29 (2008), 726-736.  doi: 10.1016/j.ejc.2007.03.007.

[9]

L. M. Del PezzoN. Frevenza and J. D. Rossi, Convex envelopes on trees, J. Convex Anal., 27 (2020), 1195-1218. 

[10]

F. Di Guglielmo, Nonconvex duality in multiobjective optimization, Math. Oper. Res., 2 (1977), 285-291.  doi: 10.1287/moor.2.3.285.

[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]

A. Elmoataz and P. Buyssens, On the connection between tug-of-war games and nonlocal PDEs on graphs, C. R. Mécanique, 345 (2017), 177-183.  doi: 10.1016/j.crme.2016.12.001.

[13]

M. Farber and R. E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Methods, 7 (1986), 433-444.  doi: 10.1137/0607049.

[14]

M. Farber and R. E. Jamison, On local convexity in graphs, Discrete Math., 66 (1987), 231-247.  doi: 10.1016/0012-365X(87)90099-9.

[15]

H. Komiya, Elementary proof for Sion's minimax theorem, Kodai Math. J., 11 (1988), 5-7.  doi: 10.2996/kmj/1138038812.

[16]

J. J. ManfrediA. M. Oberman and A. P. Sviridov, Nonlinear elliptic partial differential equations and $p-$harmonic functions on graphs, Differential Integral Equations, 28 (2015), 79-102. 

[17]

K. Murota, Discrete convex analysis, Math. Programming, 83 (1998), 313-371.  doi: 10.1007/BF02680565.

[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]

A. M. Oberman, The convex envelope is the solution of a nonlinear obstacle problem, Proc. Amer. Math. Soc., 135 (2007), 1689-1694.  doi: 10.1090/S0002-9939-07-08887-9.

[22]

A. M. Oberman and L. Silvestre, The Dirichlet problem for the convex envelope, Trans. Amer. Math. Soc., 363 (2011), 5871-5886.  doi: 10.1090/S0002-9947-2011-05240-2.

[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]

M. Sion, On general minimax theorems, Pacific J. Math., 8 (1958), 171-176.  doi: 10.2140/pjm.1958.8.171.

[26]

M. L. J. van de Vel, Theory of Convex Structures, North-Holland Mathematical Library, 50, North-Holland Publishing Co., Amsterdam, 1993.

show all references

References:
[1]

B. Abbasi and A. M. Oberman, A partial differential equation for the $ \epsilon $-uniformly quasiconvex envelope, IMA J. Numer. Anal., 39 (2019), 141-166.  doi: 10.1093/imanum/drx068.

[2]

B. Abbasi and A. M. Oberman, Computing the level set convex hull, J. Sci. Comput., 75 (2018), 26-42.  doi: 10.1007/s10915-017-0522-8.

[3]

E. N. BarronR. Goebel and R. R. Jensen, Functions which are quasiconvex under linear perturbations, SIAM J. Optim., 22 (2012), 1089-1108.  doi: 10.1137/110843496.

[4]

E. N. BarronR. Goebel and R. R. Jensen, Quasiconvex functions and nonlinear PDEs, Trans. Amer. Math. Soc., 365 (2013), 4229-4255.  doi: 10.1090/S0002-9947-2013-05760-1.

[5]

E. N. BarronR. Goebel and R. R. Jensen, The quasiconvex envelope through first-order partial differential equations which characterize quasiconvexity of nonsmooth functions, Discrete Contin. Dyn. Syst. Ser. B, 17 (2012), 1693-1706.  doi: 10.3934/dcdsb.2012.17.1693.

[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]

P. Blanc and J. D. Rossi, Games for eigenvalues of the Hessian and concave/convex envelopes, J. Math. Pures Appl., 127 (2019), 192-215.  doi: 10.1016/j.matpur.2018.08.007.

[8]

J. CáceresA. Márquez and M. L. Puertas, Steiner distance and convexity in graphs, European J. Combin., 29 (2008), 726-736.  doi: 10.1016/j.ejc.2007.03.007.

[9]

L. M. Del PezzoN. Frevenza and J. D. Rossi, Convex envelopes on trees, J. Convex Anal., 27 (2020), 1195-1218. 

[10]

F. Di Guglielmo, Nonconvex duality in multiobjective optimization, Math. Oper. Res., 2 (1977), 285-291.  doi: 10.1287/moor.2.3.285.

[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]

A. Elmoataz and P. Buyssens, On the connection between tug-of-war games and nonlocal PDEs on graphs, C. R. Mécanique, 345 (2017), 177-183.  doi: 10.1016/j.crme.2016.12.001.

[13]

M. Farber and R. E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Methods, 7 (1986), 433-444.  doi: 10.1137/0607049.

[14]

M. Farber and R. E. Jamison, On local convexity in graphs, Discrete Math., 66 (1987), 231-247.  doi: 10.1016/0012-365X(87)90099-9.

[15]

H. Komiya, Elementary proof for Sion's minimax theorem, Kodai Math. J., 11 (1988), 5-7.  doi: 10.2996/kmj/1138038812.

[16]

J. J. ManfrediA. M. Oberman and A. P. Sviridov, Nonlinear elliptic partial differential equations and $p-$harmonic functions on graphs, Differential Integral Equations, 28 (2015), 79-102. 

[17]

K. Murota, Discrete convex analysis, Math. Programming, 83 (1998), 313-371.  doi: 10.1007/BF02680565.

[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]

A. M. Oberman, The convex envelope is the solution of a nonlinear obstacle problem, Proc. Amer. Math. Soc., 135 (2007), 1689-1694.  doi: 10.1090/S0002-9939-07-08887-9.

[22]

A. M. Oberman and L. Silvestre, The Dirichlet problem for the convex envelope, Trans. Amer. Math. Soc., 363 (2011), 5871-5886.  doi: 10.1090/S0002-9947-2011-05240-2.

[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]

M. Sion, On general minimax theorems, Pacific J. Math., 8 (1958), 171-176.  doi: 10.2140/pjm.1958.8.171.

[26]

M. L. J. van de Vel, Theory of Convex Structures, North-Holland Mathematical Library, 50, North-Holland Publishing Co., Amsterdam, 1993.

[1]

Emmanuel N. Barron, Rafal Goebel, Robert R. Jensen. The quasiconvex envelope through first-order partial differential equations which characterize quasiconvexity of nonsmooth functions. Discrete and Continuous Dynamical Systems - B, 2012, 17 (6) : 1693-1706. doi: 10.3934/dcdsb.2012.17.1693

[2]

Ernesto Aranda, Pablo Pedregal. Constrained envelope for a general class of design problems. Conference Publications, 2003, 2003 (Special) : 30-41. doi: 10.3934/proc.2003.2003.30

[3]

Feishe Chen, Lixin Shen, Yuesheng Xu, Xueying Zeng. The Moreau envelope approach for the L1/TV image denoising model. Inverse Problems and Imaging, 2014, 8 (1) : 53-77. doi: 10.3934/ipi.2014.8.53

[4]

Alejandro B. Aceves, Rondald Chen, Yeojin Chung, Thomas Hagstrom, Michelle Hummel. Analysis of supercontinuum generation under general dispersion characteristics and beyond the slowly varying envelope approximation. Discrete and Continuous Dynamical Systems - S, 2011, 4 (5) : 957-973. doi: 10.3934/dcdss.2011.4.957

[5]

Roy H. Goodman. NLS bifurcations on the bowtie combinatorial graph and the dumbbell metric graph. Discrete and Continuous Dynamical Systems, 2019, 39 (4) : 2203-2232. doi: 10.3934/dcds.2019093

[6]

Liran Rotem. Banach limit in convexity and geometric means for convex bodies. Electronic Research Announcements, 2016, 23: 41-51. doi: 10.3934/era.2016.23.005

[7]

Yunping Jiang. Global graph of metric entropy on expanding Blaschke products. Discrete and Continuous Dynamical Systems, 2021, 41 (3) : 1469-1482. doi: 10.3934/dcds.2020325

[8]

Kamran Jalilian, Kameleh Nasiri Pirbazari. Convex optimization without convexity of constraints on non-necessarily convex sets and its applications in customer satisfaction in automotive industry. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021020

[9]

Chuanqiang Chen. On the microscopic spacetime convexity principle of fully nonlinear parabolic equations I: Spacetime convex solutions. Discrete and Continuous Dynamical Systems, 2014, 34 (9) : 3383-3402. doi: 10.3934/dcds.2014.34.3383

[10]

Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Existence results and stability analysis for a nonlinear fractional boundary value problem on a circular ring with an attached edge : A study of fractional calculus on metric graph. Networks and Heterogeneous Media, 2021, 16 (2) : 155-185. doi: 10.3934/nhm.2021003

[11]

Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063

[12]

Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047

[13]

Bernard Dacorogna, Giovanni Pisante, Ana Margarida Ribeiro. On non quasiconvex problems of the calculus of variations. Discrete and Continuous Dynamical Systems, 2005, 13 (4) : 961-983. doi: 10.3934/dcds.2005.13.961

[14]

S. S. Dragomir, C. E. M. Pearce. Jensen's inequality for quasiconvex functions. Numerical Algebra, Control and Optimization, 2012, 2 (2) : 279-291. doi: 10.3934/naco.2012.2.279

[15]

Byung-Soo Lee. A convergence theorem of common fixed points of a countably infinite family of asymptotically quasi-$f_i$-expansive mappings in convex metric spaces. Numerical Algebra, Control and Optimization, 2013, 3 (3) : 557-565. doi: 10.3934/naco.2013.3.557

[16]

Daniel T. Wise. Research announcement: The structure of groups with a quasiconvex hierarchy. Electronic Research Announcements, 2009, 16: 44-55. doi: 10.3934/era.2009.16.44

[17]

Christopher Goodrich, Carlos Lizama. Positivity, monotonicity, and convexity for convolution operators. Discrete and Continuous Dynamical Systems, 2020, 40 (8) : 4961-4983. doi: 10.3934/dcds.2020207

[18]

Baojun Bian, Pengfei Guan. A structural condition for microscopic convexity principle. Discrete and Continuous Dynamical Systems, 2010, 28 (2) : 789-807. doi: 10.3934/dcds.2010.28.789

[19]

Arrigo Cellina, Carlo Mariconda, Giulia Treu. Comparison results without strict convexity. Discrete and Continuous Dynamical Systems - B, 2009, 11 (1) : 57-65. doi: 10.3934/dcdsb.2009.11.57

[20]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

2020 Impact Factor: 1.213

Metrics

  • PDF downloads (205)
  • HTML views (283)
  • Cited by (0)

[Back to Top]