SERIES B: Operations Research B-442 Solving partial differential equations via sparse SDP relaxations

Abstract. To solve a partial differential equation (PDE) numerically, we formulate it as a polynomial optimization problem (POP) by discretizing it via a finite difference approximation. The resulting POP satisfies a structured sparsity, which we can exploit to apply the sparse SDP relaxation of Waki, Kim, Kojima and Muramatsu [20] to the POP to obtain a roughly approximate solution of the PDE. To compute a more accurate solution, we incorporate a grid-refining method with repeated applications of the sparse SDP relaxation or Newton’s method. The main features of this approach are: (a) we can choose an appropriate objective function, and (b) we can add inequality constraints on the unknown variables and their derivatives. These features make it possible for us to compute a specific solution when the PDE has multiple solutions. Some numerical results on the proposed method applied to ordinary differential equations, PDEs, differential algebraic equations and an optimal control problem are reported. Key words. Partial differential equation, ordinary differential equation, differential algebraic equation, polynomial optimization