January  2015, 14(1): 167-184. doi: 10.3934/cpaa.2015.14.167

General existence of solutions to dynamic programming equations

1. 

Department of Mathematics, University of Pittsburgh, Pittsburgh, PA 15260

2. 

Max-Planck Institut MiS Leipzig, Inselstr. 22, 04103 Leipzig, Germany

Received  December 2013 Revised  January 2014 Published  September 2014

We provide an alternative approach to the existence of solutions to dynamic programming equations arising in the discrete game-theoretic interpretations for various nonlinear partial differential equations including the infinity Laplacian, mean curvature flow and Hamilton-Jacobi type. Our general result is similar to Perron's method but adapted to the discrete situation.
Citation: Qing Liu, Armin Schikorra. General existence of solutions to dynamic programming equations. Communications on Pure & Applied Analysis, 2015, 14 (1) : 167-184. doi: 10.3934/cpaa.2015.14.167
References:
[1]

T. Antunović, Y. Peres, S. Sheffield and S. Somersille, Tug-of-war and infinity Laplace equation with vanishing Neumann boundary condition,, \emph{Comm. Partial Differential Equations}, 37 (2012), 1839.  doi: 10.1080/03605302.2011.642450.  Google Scholar

[2]

S. N. Armstrong and C. K. Smart, An easy proof of Jensen's theorem on the uniqueness of infinity harmonic functions,, \emph{Calc. Var. Partial Differential Equations}, 37 (2010), 381.  doi: 10.1007/s00526-009-0267-9.  Google Scholar

[3]

S. N. Armstrong and C. K. Smart, A finite difference approach to the infinity Laplace equation and tug-of-war games,, \emph{Trans. Amer. Math. Soc.}, 364 (2012), 595.  doi: 10.1090/S0002-9947-2011-05289-X.  Google Scholar

[4]

S. N. Armstrong, C. K. Smart and S. J. Somersille, An infinity Laplace equation with gradient term and mixed boundary conditions,, \emph{Proc. Amer. Math. Soc.}, 139 (2011), 1763.  doi: 10.1090/S0002-9939-2010-10666-4.  Google Scholar

[5]

M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations,, Systems & Control: Foundations & Applications, (1997).  doi: 10.1007/978-0-8176-4755-1.  Google Scholar

[6]

G. Barles and P. E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations,, \emph{Asymptotic Anal.}, 4 (1991), 271.   Google Scholar

[7]

F. Charro, J. García Azorero and J. D. Rossi, A mixed problem for the infinity Laplacian via tug-of-war games,, \emph{Calc. Var. Partial Differential Equations}, 34 (2009), 307.  doi: 10.1007/s00526-008-0185-2.  Google Scholar

[8]

M. G. Crandall, H. Ishii and P.-L. Lions, User's guide to viscosity solutions of second order partial differential equations,, \emph{Bull. Amer. Math. Soc. (N.S.)}, 27 (1992), 1.  doi: 10.1090/S0273-0979-1992-00266-5.  Google Scholar

[9]

Y. Giga and Q. Liu, A billiard-based game interpretation of the Neumann problem for the curve shortening equation,, \emph{Adv. Differential Equations}, 14 (2009), 201.   Google Scholar

[10]

H. Ishii, Perron's method for Hamilton-Jacobi equations,, \emph{Duke Math. J.}, 55 (1987), 369.  doi: 10.1215/S0012-7094-87-05521-9.  Google Scholar

[11]

H. Ishii, A simple, direct proof of uniqueness for solutions of the Hamilton-Jacobi equations of eikonal type,, \emph{Proc. Amer. Math. Soc.}, 100 (1987), 247.  doi: 10.2307/2045953.  Google Scholar

[12]

R. V. Kohn and S. Serfaty, A deterministic-control-based approach to motion by curvature,, \emph{Comm. Pure Appl. Math.}, 59 (2006), 344.  doi: 10.1002/cpa.20101.  Google Scholar

[13]

R. V. Kohn and S. Serfaty, A deterministic-control-based approach to fully nonlinear parabolic and elliptic equations,, \emph{Comm. Pure Appl. Math.}, 63 (2010), 1298.  doi: 10.1002/cpa.20336.  Google Scholar

[14]

S. Koike, A Beginner's Guide to the Theory of Viscosity Solutions,, vol. 13 of MSJ Memoirs, (2004).   Google Scholar

[15]

E. Le Gruyer and J. C. Archer, Harmonious extensions,, \emph{SIAM J. Math. Anal.}, 29 (1998), 279.  doi: 10.1137/S0036141095294067.  Google Scholar

[16]

Q. Liu, Waiting time effect for motion by positive second derivatives and applications,, \emph{Nonlinear Differential Equations Appl.}, 21 (2014), 589.  doi: 10.1007/s00030-013-0259-5.  Google Scholar

[17]

Q. Liu, Fattening and comparison principle for level-set equations of mean curvature type,, \emph{SIAM J. Control Optim.}, 49 (2011), 2518.  doi: 10.1137/100814330.  Google Scholar

[18]

Q. Liu and A. Schikorra, A game-tree approach to discrete infinity Laplacian with running costs,, preprint., ().   Google Scholar

[19]

H. Luiro, M. Parviainen and E. Saksman, On the existence and uniqueness of p-harmonious functions,, \emph{Differential and Integral Equations}, 27 (2014), 201.   Google Scholar

[20]

J. J. Manfredi, M. Parviainen and J. D. Rossi, An asymptotic mean value characterization for a class of nonlinear parabolic equations related to tug-of-war games,, \emph{SIAM J. Math. Anal.}, 42 (2010), 2058.  doi: 10.1137/100782073.  Google Scholar

[21]

J. J. Manfredi, M. Parviainen and J. D. Rossi, An asymptotic mean value characterization for p-harmonic functions,, \emph{Proc. Amer. Math. Soc.}, 138 (2010), 881.  doi: 10.1090/S0002-9939-09-10183-1.  Google Scholar

[22]

J. J. Manfredi, J. D. Rossi and S. Somersille, An obstacle problem for tug-of-war games,, preprint., ().   Google Scholar

[23]

Y. Peres, G. Pete and S. Somersille, Biased tug-of-war, the biased infinity Laplacian, and comparison with exponential cones,, \emph{Calc. Var. Partial Differential Equations}, 38 (2010), 541.  doi: 10.1007/s00526-009-0298-2.  Google Scholar

[24]

Y. Peres, O. Schramm, S. Sheffield and D. B. Wilson, Tug-of-war and the infinity Laplacian,, \emph{J. Amer. Math. Soc.}, 22 (2009), 167.  doi: 10.1090/S0894-0347-08-00606-1.  Google Scholar

[25]

Y. Peres and S. Sheffield, Tug-of-war with noise: a game-theoretic view of the p-Laplacian,, \emph{Duke Math. J.}, 145 (2008), 91.  doi: 10.1215/00127094-2008-048.  Google Scholar

[26]

M. B. Rudd and H. A. Van Dyke, Median values, 1-harmonic functions, and functions of least gradient,, \emph{Commun. Pure Appl. Anal.}, 12 (2013), 711.  doi: 10.3934/cpaa.2013.12.711.  Google Scholar

show all references

References:
[1]

T. Antunović, Y. Peres, S. Sheffield and S. Somersille, Tug-of-war and infinity Laplace equation with vanishing Neumann boundary condition,, \emph{Comm. Partial Differential Equations}, 37 (2012), 1839.  doi: 10.1080/03605302.2011.642450.  Google Scholar

[2]

S. N. Armstrong and C. K. Smart, An easy proof of Jensen's theorem on the uniqueness of infinity harmonic functions,, \emph{Calc. Var. Partial Differential Equations}, 37 (2010), 381.  doi: 10.1007/s00526-009-0267-9.  Google Scholar

[3]

S. N. Armstrong and C. K. Smart, A finite difference approach to the infinity Laplace equation and tug-of-war games,, \emph{Trans. Amer. Math. Soc.}, 364 (2012), 595.  doi: 10.1090/S0002-9947-2011-05289-X.  Google Scholar

[4]

S. N. Armstrong, C. K. Smart and S. J. Somersille, An infinity Laplace equation with gradient term and mixed boundary conditions,, \emph{Proc. Amer. Math. Soc.}, 139 (2011), 1763.  doi: 10.1090/S0002-9939-2010-10666-4.  Google Scholar

[5]

M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations,, Systems & Control: Foundations & Applications, (1997).  doi: 10.1007/978-0-8176-4755-1.  Google Scholar

[6]

G. Barles and P. E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations,, \emph{Asymptotic Anal.}, 4 (1991), 271.   Google Scholar

[7]

F. Charro, J. García Azorero and J. D. Rossi, A mixed problem for the infinity Laplacian via tug-of-war games,, \emph{Calc. Var. Partial Differential Equations}, 34 (2009), 307.  doi: 10.1007/s00526-008-0185-2.  Google Scholar

[8]

M. G. Crandall, H. Ishii and P.-L. Lions, User's guide to viscosity solutions of second order partial differential equations,, \emph{Bull. Amer. Math. Soc. (N.S.)}, 27 (1992), 1.  doi: 10.1090/S0273-0979-1992-00266-5.  Google Scholar

[9]

Y. Giga and Q. Liu, A billiard-based game interpretation of the Neumann problem for the curve shortening equation,, \emph{Adv. Differential Equations}, 14 (2009), 201.   Google Scholar

[10]

H. Ishii, Perron's method for Hamilton-Jacobi equations,, \emph{Duke Math. J.}, 55 (1987), 369.  doi: 10.1215/S0012-7094-87-05521-9.  Google Scholar

[11]

H. Ishii, A simple, direct proof of uniqueness for solutions of the Hamilton-Jacobi equations of eikonal type,, \emph{Proc. Amer. Math. Soc.}, 100 (1987), 247.  doi: 10.2307/2045953.  Google Scholar

[12]

R. V. Kohn and S. Serfaty, A deterministic-control-based approach to motion by curvature,, \emph{Comm. Pure Appl. Math.}, 59 (2006), 344.  doi: 10.1002/cpa.20101.  Google Scholar

[13]

R. V. Kohn and S. Serfaty, A deterministic-control-based approach to fully nonlinear parabolic and elliptic equations,, \emph{Comm. Pure Appl. Math.}, 63 (2010), 1298.  doi: 10.1002/cpa.20336.  Google Scholar

[14]

S. Koike, A Beginner's Guide to the Theory of Viscosity Solutions,, vol. 13 of MSJ Memoirs, (2004).   Google Scholar

[15]

E. Le Gruyer and J. C. Archer, Harmonious extensions,, \emph{SIAM J. Math. Anal.}, 29 (1998), 279.  doi: 10.1137/S0036141095294067.  Google Scholar

[16]

Q. Liu, Waiting time effect for motion by positive second derivatives and applications,, \emph{Nonlinear Differential Equations Appl.}, 21 (2014), 589.  doi: 10.1007/s00030-013-0259-5.  Google Scholar

[17]

Q. Liu, Fattening and comparison principle for level-set equations of mean curvature type,, \emph{SIAM J. Control Optim.}, 49 (2011), 2518.  doi: 10.1137/100814330.  Google Scholar

[18]

Q. Liu and A. Schikorra, A game-tree approach to discrete infinity Laplacian with running costs,, preprint., ().   Google Scholar

[19]

H. Luiro, M. Parviainen and E. Saksman, On the existence and uniqueness of p-harmonious functions,, \emph{Differential and Integral Equations}, 27 (2014), 201.   Google Scholar

[20]

J. J. Manfredi, M. Parviainen and J. D. Rossi, An asymptotic mean value characterization for a class of nonlinear parabolic equations related to tug-of-war games,, \emph{SIAM J. Math. Anal.}, 42 (2010), 2058.  doi: 10.1137/100782073.  Google Scholar

[21]

J. J. Manfredi, M. Parviainen and J. D. Rossi, An asymptotic mean value characterization for p-harmonic functions,, \emph{Proc. Amer. Math. Soc.}, 138 (2010), 881.  doi: 10.1090/S0002-9939-09-10183-1.  Google Scholar

[22]

J. J. Manfredi, J. D. Rossi and S. Somersille, An obstacle problem for tug-of-war games,, preprint., ().   Google Scholar

[23]

Y. Peres, G. Pete and S. Somersille, Biased tug-of-war, the biased infinity Laplacian, and comparison with exponential cones,, \emph{Calc. Var. Partial Differential Equations}, 38 (2010), 541.  doi: 10.1007/s00526-009-0298-2.  Google Scholar

[24]

Y. Peres, O. Schramm, S. Sheffield and D. B. Wilson, Tug-of-war and the infinity Laplacian,, \emph{J. Amer. Math. Soc.}, 22 (2009), 167.  doi: 10.1090/S0894-0347-08-00606-1.  Google Scholar

[25]

Y. Peres and S. Sheffield, Tug-of-war with noise: a game-theoretic view of the p-Laplacian,, \emph{Duke Math. J.}, 145 (2008), 91.  doi: 10.1215/00127094-2008-048.  Google Scholar

[26]

M. B. Rudd and H. A. Van Dyke, Median values, 1-harmonic functions, and functions of least gradient,, \emph{Commun. Pure Appl. Anal.}, 12 (2013), 711.  doi: 10.3934/cpaa.2013.12.711.  Google Scholar

[1]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213

[2]

Nhu N. Nguyen, George Yin. Stochastic partial differential equation models for spatially dependent predator-prey equations. Discrete & Continuous Dynamical Systems - B, 2020, 25 (1) : 117-139. doi: 10.3934/dcdsb.2019175

[3]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027

[4]

Jaume Llibre, Luci Any Roberto. On the periodic solutions of a class of Duffing differential equations. Discrete & Continuous Dynamical Systems - A, 2013, 33 (1) : 277-282. doi: 10.3934/dcds.2013.33.277

[5]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203

[6]

Changpin Li, Zhiqiang Li. Asymptotic behaviors of solution to partial differential equation with Caputo–Hadamard derivative and fractional Laplacian: Hyperbolic case. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021023

[7]

Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192

[8]

Gheorghe Craciun, Abhishek Deshpande, Hyejin Jenny Yeon. Quasi-toric differential inclusions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2343-2359. doi: 10.3934/dcdsb.2020181

[9]

Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409

[10]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008

[11]

Zengyun Wang, Jinde Cao, Zuowei Cai, Lihong Huang. Finite-time stability of impulsive differential inclusion: Applications to discontinuous impulsive neural networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2677-2692. doi: 10.3934/dcdsb.2020200

[12]

V. Vijayakumar, R. Udhayakumar, K. Kavitha. On the approximate controllability of neutral integro-differential inclusions of Sobolev-type with infinite delay. Evolution Equations & Control Theory, 2021, 10 (2) : 271-296. doi: 10.3934/eect.2020066

[13]

Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1693-1716. doi: 10.3934/dcdss.2020450

[14]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185

[15]

Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825

[16]

Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006

[17]

Marco Cirant, Diogo A. Gomes, Edgard A. Pimentel, Héctor Sánchez-Morgado. On some singular mean-field games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021006

[18]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[19]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[20]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

2019 Impact Factor: 1.105

Metrics

  • PDF downloads (166)
  • HTML views (0)
  • Cited by (10)

Other articles
by authors

[Back to Top]