Moment-SOS hierarchy and exit location of stochastic processes

Didier Henrion; Mauricio Junca; Mauricio Velasco

doi:10.3934/naco.2024014

Article Contents

2024. Doi: 10.3934/naco.2024014

Previous Article Next Article

Early Access

Early Access articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

Moment-SOS hierarchy and exit location of stochastic processes

1.
CNRS, LAAS, Université de Toulouse, France
2.
Faculty of Electrical Engineering, Czech Technical University in Prague, Czechia
3.
Departamento de Matemáticas, Universidad de los Andes, Bogotá, Colombia
4.
Departamento de Informática, Universidad Católica del Uruguay, Montevideo, Uruguay

^*Corresponding author: Didier Henrion
^*Corresponding author: Didier Henrion

The paper is handled by Jiawang Nie as the guest editor.

Received: November 2023

Revised: March 2024

Early access: April 2024

M. Velasco was partially supported by Proyecto INV-2018-50-1392 (UAndes, Colombia) and Fondo Clemente Estable project FCE-1-2023-1-176172 (ANII, Uruguay). D. Henrion, M. Junca and M. Velasco were partially supported by ColCiencias Colombia-France cooperation Ecos Nord grant "Problemas de momentos en control y optimización" (C19M02).

Abstract / Introduction Full Text(HTML) Figure(4) / Table(2) Related Papers Cited by

Abstract

The moment sum of squares (moment-SOS) hierarchy produces sequences of upper and lower bounds on functionals of the exit time location of a polynomial stochastic differential equation with polynomial constraints, at the price of solving semidefinite optimization problems of increasing size. In this note we use standard results from elliptic partial differential equation analysis to prove convergence of the bounds produced by the hierarchy. We also use elementary convex analysis to describe a super- and sub-solution interpretation dual to a linear formulation on occupation measures. Finally, we introduce a novel Christoffel-Darboux approach for the recovery of the exit location and occupation measures. The practical relevance of these results is illustrated with numerical examples.

Keywords:

Polynomial optimization,
stochastic differential equations.

Mathematics Subject Classification: Primary: 90C23, 60H35; Secondary: 90C22, 65C30.

Citation:

FullText(HTML)

Figure 1. Lower and upper bounds on the functional for increasing relaxation degrees and dimension $ n = 2 $ (left) and $ n = 3 $ (right)

Download: Full-size image PowerPoint slide

Figure 2. Example 5.7: brownian motion

Download: Full-size image PowerPoint slide

Figure 3. Example 5.8: brownian motion with upward drift

Download: Full-size image PowerPoint slide

Figure 4. Example 5.9: square root Bessel process

Download: Full-size image PowerPoint slide

Table 1. Scalar example - bounds for increasing relaxation degrees

relaxation degree	2	4	6	8	10
lower bound	0.65000	0.92157	0.98118	0.99503	0.99827
upper bound	1.00000	1.00000	1.00000	1.00000	1.00000

| Show Table

DownLoad: CSV

Table 2. Computational burden for relaxation degree 8 and increasing dimensions

dimension $ n $	2	3	4	5	6	7	8
number of moments	73	249	705	1749	3927	8151	15873
CPU time (seconds)	0.15	0.59	1.9	5.6	19	51	195

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Barvinok, A Course in Convexity, AMS, 2002. doi: 10.1090/gsm/054.
[2]	A. G. Bhatt and V. S. Borkar, Occupation measures for controlled Markov processes: characterization and optimality, Ann. Proba., 24 (1996), 1531-1562. doi: 10.1214/aop/1065725192.
[3]	R. Buckdahn, D. Goreac and M. Quincampoix, Stochastic optimal control and linear programming approach, Appl. Math. Optim., 63 (2011), 257-276. doi: 10.1007/s00245-010-9120-y.
[4]	M. J. Cho and R. H. Stockbridge, Linear programming formulation for optimal stopping problems, SIAM J. Control Optim., 40 (2002), 1965-1982. doi: 10.1137/S0363012900377663.
[5]	J. Dahl, Semidefinite Optimization using MOSEK, ISMP Berlin, 2012.
[6]	L. C. Evans, Partial Differential Equations, AMS, 1998.
[7]	L. C. Evans, An Introduction to Stochastic Differential Equations, AMS, 2013. doi: 10.1090/mbk/082.
[8]	K. Helmes, S. Röhl and R. H. Stockbridge, Computing moments of the exit time distribution for Markov processes by linear programming, Oper. Res., 49 (2001), 516-530. doi: 10.1287/opre.49.4.516.11221.
[9]	D. Henrion, M. Korda and J. B. Lasserre, The moment-SOS hierarchy, Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs. World Scientific, 2020.
[10]	D. Henrion, J. B. Lasserre and J. Löfberg, GloptiPoly 3: moments, optimization and semidefinite programming, Optim. Meth. Soft., 24 (2009), 761-779. doi: 10.1080/10556780802699201.
[11]	D. Henrion and E. Pauwels, Linear conic optimization for nonlinear optimal control, Chapter 10, in Advances and Trends in Optimization with Engineering Applications (eds. S. Ahmed, M. Anjos and T. Terlaky), SIAM, 2017. doi: 10.1137/1.9781611974683.ch10.
[12]	C. Jiao and R. Kawai, Computable primal and dual bounds for stochastic optimal control, SIAM J. Control. Optim., 58 (2020), 3709-3733. doi: 10.1137/18M1232231.
[13]	K. Kashima and R. Kawai, On weak approximation of stochastic differential equations through hard bounds by mathematical programming, SIAM J. Sci. Comput., 35 (2013), A1-A21. doi: 10.1137/110841497.
[14]	R. Kawai, Explicit hard bounding functions for boundary value problems for elliptic partial differential equations, Comput. Math. Appl., 70 (2015), 2822-2837. doi: 10.1016/j.camwa.2015.09.024.
[15]	A. Kroó and D. S. Lubinsky, Christoffel functions and universality in the bulk for multivariate orthogonal polynomials, Canad. J. Math., 65 (2013), 600-620. doi: 10.4153/CJM-2012-016-x.
[16]	T. G. Kurtz and R. H. Stockbridge, Existence of Markov control and characterization of optimal Markov controls, SIAM J. Control Optim., 36 (1998), 609-653. doi: 10.1137/S0363012995295516.
[17]	J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imperial College Press, 2010.
[18]	J. B. Lasserre, E. Pauwels and M. Putinar, The Christoffel-Darboux Kernel for Data Analysis, Cambridge University Press, 2022. doi: 10.1017/9781108937078.
[19]	J. B. Lasserre and T. Priéto-Rumeau, SDP vs. LP relaxations for the moment approach in some performance evaluation problems, Stoch. Models, 20 (2004), 439-456. doi: 10.1081/STM-200033112.
[20]	J. B. Lasserre, T. Priéto-Rumeau and M. Zervos, Pricing a class of exotic options via moments and SDP relaxations, Math. Finance, 16 (2006), 469-494. doi: 10.1111/j.1467-9965.2006.00279.x.
[21]	B. Øskendal, Stochastic Differential Equations - An Introduction with Applications, $6^{th}$ edition with corrections, Springer, 2013. doi: 10.1007/978-3-642-14394-6.
[22]	M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42 (1993), 969-984. doi: 10.1512/iumj.1993.42.42045.
[23]	J. Urbas, Lectures on second order linear partial differential equations, Proc. Center Math. Appl., Australian Nat. Univ., Workshop on Analysis and Geometry Part 1, 34 (1995), 39-75.