Bounds on linear PDEs via semidefinite optimization. (English) Zbl 1099.90063

Summary: Using recent progress on moment problems, and their connections with semidefinite optimization, we present in this paper a new methodology based on semidefinite optimization, to obtain a hierarchy of upper and lower bounds on linear functionals defined on solutions of linear partial differential equations. We apply the proposed method to examples of PDEs in one and two dimensions, with very encouraging results. We pay particular attention to a PDE with oblique derivative conditions, commonly arising in queueing theory. We also provide computational evidence that the semidefinite constraints are critically important in improving the quality of the bounds, that is, without them the bounds are weak.


90C34 Semi-infinite programming
35F99 General first-order partial differential equations and systems of first-order partial differential equations


Full Text: DOI Link


[1] Akhiezer, N.: The classical moment problem, Eng. Ed., Oliver and Boyd, London 1965 · Zbl 0135.33803
[2] Bertsimas, D.: The achievable region method in the optimal control of queueing systems; formulations, bounds and policies. Queueing Systems and Applications 21 (3–4), 337–389 (1995) · Zbl 0857.60093
[3] Bertsimas, D., Paschalidis, I., Tsitsiklis, J.: Optimization of multiclass queueing networks: polyhedral and nonlinear characterizations of achievable performance. Ann. Appl. Prob. 4 (2), 43–75 (1994) · Zbl 0797.60079
[4] Bertsimas, D., Popescu, I.: Optimal inequalities in probability theory: a convex optimization approach. SIAM Journal of Optimization 15, 780–804 (2005) · Zbl 1077.60020
[5] Bertsimas, D., Popescu, I.: On the relation between option and stock prices: a convex optimization approach. Operations Research 50 (2), 358–374 (2002) · Zbl 1163.91382
[6] Bochnak, J., Coste, M., Roy, M.: Real algebraic geometry, Springer–Verlag, Berlin Heidelberg, 1998 · Zbl 0912.14023
[7] Brezzi, F., Fortin, M.: Mixed and hybrid finite element methods. Springer–Verlag, New York, 1991 · Zbl 0788.73002
[8] Fujisawa, K., Kojima, M., Nakata, K.: SDPA (Semidefinite Programming Algorithm) User’s Manual, Version 4.10, Research Report on Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo, Japan, 1998
[9] Haviland, E.K.: On the momentum problem for distribution functions in more than one dimension II. Amer. J. Math. 58, 164–168 (1936) · Zbl 0015.10901
[10] Harrison, J.M.: The diffusion approximation for tandem queues in heavy traffic. Adv. Appl. Prob. 10, 886–905 (1978) · Zbl 0387.60090
[11] Harrison, J.M., Landau, H.J., Shepp, L.A.: The stationary distribution of reflected Brownian motion in a planar region. Ann. Prob. 13, 744–757 (1985) · Zbl 0573.60071
[12] Kumar, S., Kumar, P.R.: Performance bounds for queueing networks and scheduling policies. IEEE Trans. on Aut. Control 39, 1600–1611 (1994) · Zbl 0812.90049
[13] Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001) · Zbl 1010.90061
[14] Lasserre, J.B.: Bounds on measures satisfying moment conditions. Annals Appl. Prob. 12, 1114–1137 (2002) · Zbl 1073.90534
[15] Paraschivoiu, M., Patera, A.: A Hierarchical Duality Approach to Bounds for the Outputs of Partial Differential Equations. Comput. Methods Appl. Eng. 158, 389–407 (1998) · Zbl 0953.76054
[16] Paraschivoiu, M., Peraire, J., Patera, A.: A Posteriori Finite Element Bounds for Linear–Functional Outputs of Elliptic Partial Differential Equations. Comput. Meth. Appl. Mech. Eng. 150, 289–312 (1997) · Zbl 0907.65102
[17] Parrilo, P.: Semidefinite programming relaxations for semi-algebraic problems. Math. Programming Ser. B 96, 293–320 (2003) · Zbl 1043.14018
[18] Peraire, J., Patera, A.: Bounds for linear-functional outputs of coercive partial differential equations: Local indicators and adaptive refinement. New Advances in Adaptive Computational Methods in Mechanics, available at http://raphael.mit.edu/peraire/, 1997
[19] Quarteroni, A., Valli, A.: Numerical Approximation of Partial Differential Equations, Springer–Verlag, Berlin, 1997 · Zbl 1151.65339
[20] Reznick, B.: Some concrete aspects of Hilbert’s 17th problem. In: Delzell, C.N., Madden, J.J. (eds.), Real Algebraic Geometry and Ordered Structures. Cont. Math. 2000, p 253 · Zbl 0972.11021
[21] Schwerer, E.: A Linear Programming Approach to the Steady–State Analysis of Markov Processes. Palo Alto, CA: Ph.D. Thesis, Stanford University, 1996 · Zbl 0982.62071
[22] Schmüdgen, K.: The K–moment problem for compact semi–algebraic sets. Math. Ann. 289, 203–206 (1991) · Zbl 0744.44008
[23] Strang, G., Fix, G.: An Analysis of the Finite Element Method, Prentice–Hall, Englewood Cliffs, NJ, 1973 · Zbl 0356.65096
[24] Sturm, J.: SeDuMi Semidefinite Software, http://www/unimaas.nl/sturm
[25] Trefethen, L.N., Williams, R.J.: Conformal mapping solution of Laplace’s equation on a polygon with oblique derivative boundary conditions.” J. Comp. and App. Math. 14, 227–249 (1986) · Zbl 0596.30014
[26] Vandenberghe, L., Boyd, S.: Semidefinite Programming. SIAM Review 38, 49–95 (1996) · Zbl 0845.65023
[27] Varadhan, S.R.S., Williams, R.J.: Brownian motion in a wedge with oblique reflection. Comm. Pure. Appl. Math. 38, 405–443 (1985) · Zbl 0579.60082
[28] Watson, G.N.: A Treatise on the Theory of Bessel Functions, 2nd Edition, The Macmillan Company, Cambridge, 1994
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.