离散HJB方程及离散HJB障碍问题的快速迭代算法研究

Discrete HJB equations and discrete HJB obstacle problems result from fully implicit discretisations of an HJB equation and a special case of an HJBI equation, respectively. Because of the high nonlinearity and nonsmooth- ness of the discrete problems， many existing algorithms for nonlinear equations can not be used. It is of important practical significance and theoretical value to develop fast iterative algorithms for solving these problems. Based on the principles of simplicity, high efficiency and practicality for an algorithm, this project shall study fast iterative algorithms to solve discrete HJB equations and discrete HJB obstacle problems. The detailed research progresses are: 1) we present a damped semismooth Newton method for solving discrete HJB obstacle problems and study the monotone convergence of the method; 2) combining semismooth Newton method and fixed point iteration, we propose semismooth Newton-iterative method for the solution of discrete HJB equations and diecrete HJB obstacle problems; 3) we also propose Schwarz methods to solve these two kinds of discrete problems and study the convergence of the methods, espesially the convergence rate of independence on mesh-size.

离散HJB方程和离散HJB障碍问题分别来源于HJB方程和一类特殊的HJBI方程的全隐式离散。由于离散问题高度的非线性性和非光滑性，许多求解非线性方程组的迭代算法已不能运用。发展快速迭代算法来解这些问题具有重要的实际意义和理论价值。本项目从算法应该简单、高效、实用的角度出发，研究离散HJB方程和离散HJB障碍问题的快速迭代算法。具体研究工作为：1) 提出阻尼半光滑牛顿法求解离散HJB障碍问题并研究算法的单调收敛性；2）结合半光滑牛顿法和不动点迭代，提出半光滑牛顿-迭代法解离散HJB方程及离散HJB障碍问题；3) 提出Schwarz算法求解这两类离散问题，研究算法的收敛性，尤其是网格步长无关的收敛率。

现实生活中许许多多的问题(如：自由液面水动力学问题、美式期权定价问题和L_1正则化问题等等)可以通过Hamilton-Jacobi-Bellman(HJB)方程或HJB障碍问题来描述。项目组研究了快速迭代算法来求解几类离散HJB方程和离散HJB障碍问题，具体研究内容如下：. 第一、研究了阻尼半光滑牛顿法来求解两类离散HJB障碍问题和相应的罚方程，在一定条件下证明了算法具有单调收敛性以及有限步终止性，最后通过数值实验验证了收敛性结论；. 第二、研究了Schwarz算法来求解两类离散HJB方程(即线性互补问题和半线性互补问题)，给出了算法的收敛率估计，数值结果表明算法具有与网格步长无关的收敛性质；. 第三、研究了求解线性互补问题和混合线性互补问题的幂罚方法的收敛性，在此基础上，提出了迭代算法来解罚方程并且分析了算法的收敛性，最后通过求解美式期权定价模型验证了理论结果的正确性以及迭代算法的有效性；. 第四、研究得到L_1正则化问题的最优解满足一个HJB障碍问题，在此基础上，提出梯度型算法求解该问题，在一定条件下证明了算法具有全局收敛性，最后通过数值实验验证了算法的有效性。此外，提出了数值算法解L_{1/2}正则化问题，研究了的收敛性和计算复杂度。