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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

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

[10]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

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

[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.   Google Scholar

[17]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[24]

I. M. Pelayo, Geodesic Convexity in Graphs, SpringerBriefs in Mathematics, Springer, New York, 2013. doi: 10.1007/978-1-4614-8699-2.  Google Scholar

[25]

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

[26]

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

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

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

[10]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

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

[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.   Google Scholar

[17]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[24]

I. M. Pelayo, Geodesic Convexity in Graphs, SpringerBriefs in Mathematics, Springer, New York, 2013. doi: 10.1007/978-1-4614-8699-2.  Google Scholar

[25]

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

[26]

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

[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 & 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 & 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 & 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 & Continuous Dynamical Systems, 2019, 39 (4) : 2203-2232. doi: 10.3934/dcds.2019093

[6]

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

[7]

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

[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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 (98)
  • HTML views (156)
  • Cited by (0)

[Back to Top]