Generalized Newton-type methods and their applications

Abstract

The main purposes of this thesis are to solve the semi-infinite programming (SIP) problems, the option price interpolation problems and the L2 spectral estimation problems by using some generalized Newton methods. Our proposed methods have the following three features: (1) At each iteration, only a system of linear equations needs to be solved; (2) These methods have Global convergence; (3) These methods are shown to be locally supperlinearly convergent. We also present a smoothing implicit programming method to solve the generalized semi-infinite programming (GSIP) problem with uncertainty. The main contributions of this thesis are as follows. We introduce a class of integral functions which arises from many applications such as nonsmooth equation reformulations of the option price problems, the SIP problems and the L2 spectral estimation problems. We investigate the differentiability, semi-smoothness and smoothing approximation properties of this class of integral functions. This content is mainly based on the papers 1, 3 and 4 in Underlying Papers. We introduce four kinds of algorithms for solving SIP problems. First, we present a smoothing sequential quadratic programming (SQP) algorithm. At each iteration of this algorithm, we only need to solve a quadratic program which is always feasible and solvable. The global convergence of the smoothing SQP algorithm is established under some mild conditions. Further, we present a smoothing projected Newton-type algorithm and prove its global and local superlinear convergence property. However, the accumulation point of an iterative sequence generated by these algorithms above may not be a stationary point of the original SIP problem. So, we propose the third method, say, smoothing Newton-type algorithm. For this algorithm, we not only prove its global and local superlinear convergence under some mild conditions, but also show that any accumulation point of an iterative sequence generated by it is a stationary point of the original SIP problem. Finally, based on the smoothing projected Newton-type algorithm, we develop a truncated projected Newton-type algorithm which can solve large scale SIP problems with 2000 decision variables. The feasibility for all algorithms is ensured by an integral function. For all these algorithms, numerical experiments are also given. These contents are mainly based on the papers 3-6 in Underlying Papers. We discuss a generalized semi-infinite programming problem with uncertainty. We propose a reformulation of the considered problem by using the first order optimality conditions of the second stage optimization problem and present a smoothing implicit programming method to solve the problem with finite discrete distribution. Global convergence results are obtained. This content is mainly based on the paper 2 in Underlying Papers. For option price interpolation problem, Wang, Yin and Qi (2004) presented a generalized Newton method for solving it and established its superlinear convergence rate. We show that the proposed method has at least 4/3-order convergence rate, and then give conditions under which this method has 3/2 order and quadratic convergence rate. And finally, we give a damped version of the generalized Newton method and show that it is globally convergent and the convergence order is at least 4/3. This content is mainly based on the paper 1 in Underlying Papers. A Newton method for solving power spectrum estimation problems is proposed in Chapter 7, and it is proved that the method is at least 1+1/2m-order convergent rate. We also produce a globalized Newton-type method for solving the problem, which has at least 1+1/2m-order convergence rate. This content is mainly based on the paper 7 in Underlying Papers.