Generalized Newton-type Algorithms For Two Kinds Of Discretized Nonsmooth Problems

The obstacle problem and the Hamilton-Jacobi-Bellman equation (denoted by HJB equation) arise from many fields, such as mechanism, engineering, physics, finance, optimal control theory and so on. Their numerical solutions, especially those for the large scale problems, have attracted much attention in engineering and computational mathematics. In the past decades, many fruits have been taken. Taking into account the nonsmoothness of these two kinds of problems, in this thesis, we shall discuss the generalized Newton type methods for solving these two kinds of problems.In Chapter 2, we propose a generalized Newton Schwarz iterative method for the discrete unilateral obstacle problem. The proposed method enjoys some nice properties. First, unlike most smoothing Newton-like methods where at each iteration an exact Newton step have to be obtained, in our method we only need to solve an approximate solution of a lower-dimensional linear system by finitely many additive or multiplicative Schwarz iterations. Consequently, it is desire to save computation cost; Second, the algorithm possesses a monotone convergence property and superlinear convergence property. Moreover, the initial iterate of the method is easy to choose compared with that of other monotonously convergent Schwarz methods.In Chapter 3, we propose a generalized Newton method for the discrete HJB equation and prove that the iterate sequence produced by the method is monoton-ically locally superlinearly convergent. The advantage of the algorithm is that it only needs to solve a system of linear equations at each iteration. In particular, we show that the proposed method contains the iterative sequenceⅡproposed by Lions and Mercier in 1980 as a special case. Hence, the iterative sequenceⅡalso possesses a locally superlinear convegence property. Furthermore, we develop a generalized Newton iterative method for the discrete HJB equation. As we only need to get an approximate solution of the subproblem, the computation cost of the proposed method would be very cheap. Under proper conditions, we prove that the sequence of the iterates converges superlinearly. Numerical results show that the method is efficient.In Chapter 4, we propose a damped generalized Newton method for the dis-crete bilateral obstacle problem. Compared with the discrete unilateral obstacle problem, it is more difficult to solve the discrete bilateral obstacle problem. While the problem solved by the primal active set method (or the augmented Lagrangian active set method), the iterative sequence is not monotonously convergent. In this chapter, we verify that the algorithm is monotonously convergent. Moreover, it terminates at the solution within finitely many iterations if the initial point and the damping factor are chosen appropriately. In particular, as the problem is reduced to a discrete unilateral obstacle problem, the damped generalized Newton method is equivalent to the primal active set method (or the augmented Lagrangian active set method).In Chapter 5, we propose a damped generalized Newton-iterative method for the discrete bilateral obstacle problem. Note that a lower-dimensional linear system needs to be solved at each Newton step for the algorithm from the previous chapter. When the scale of the discrete problem is large, it takes a great deal of computational work to solve the subproblem exactly. In order to save the CPU time, in this chapter we approximate the solution of the subproblem through an iterative method at each Newton step. Under appropriate conditions, we prove that the method converges superlinearly. Numerical results show that the method is efficient.This dissertation is supported by the National Natural Science Foundation of China (10671060,10971058).This dissertation is typeset by software LATEX2ε.