Study On Numerical Methods For Several Optimization Problems

In this thesis, we study on numerical methods for several related optimization prob-lems, which are the nonlinear complementarity problems with Po-function (P0-NCP), the split feasibility problem (SFP), and the stochastic split feasibility problem (SSFP).In the first chapter, we introduce several optimization problems concerned in this thesis, their relations, and some basic notations.In chapter 2,we investigate the nonlinear complementarity problems with Po-function (P0-NCP).Nonlinear complementarity problem is the interdisciplinary research areas of operations research and computational science,and has various important ap-plications in many fields,such as mechanics,engineering,economics, transportation, and so on.In its general form, the nonlinear complementarity problem is formally de-fined below:Let F:Rn→Rn be a continuous differentiabie function.The nonlinear complementarity problem (NCP) is to find a vector x∈Rn such that x≥0, F(x)≥0, xTF(x)=0.In this chapter, we present a new non-interior path-following methods for nonlin-ear complementarity problems with Po-function (P0-NCP).Instead of using the standard central path,we use a scaled central path.Based on this new central path, we give a one-step smoothing Newton method for solving nonlinear complementarity problems with Po-function. Our smoothing Newton method solves only one linear system of equations and performs only one line search at each iteration.It is proved that our proposed al-gorithm has superlinear convergence in absence of strict complementarity assumption at the P0-NCP solution. Under suitable conditions, the modified algorithm has global convergence and local quadratic convergence.Finally, we perform some numerical ex-periments, which preliminarily show the behaviors of the algorithms proposed, and we made comparison of the new method with the method which using the standard central path.In chapter 3,we propose several solution methods for the split feasibility problem (SFP).The split feasibility problem (SFP) is to find x∈C, such that Ax∈Q, where C and Q are nonempty closed convex sets in RN and RM,respectively, and A is an M by N real matrix. Such problems arise in signal processing, especially in phase retrieval and other image restoration problems.Recently the split feasibility problem has been proposed application in intensity modulated radiation therapy. Meanwhile, the SFP is closely related to the convex feasibility problem (CFP),i.e.,to find a point in the nonempty intersection of finitely many closed and convex sets.The latter is a fundamental problem in many disciplines, such as mathematics and physical science, and so on.So it is of great meaning to study on how to solve the split feasibility problem.The so-called CQ algorithm is a brief method for solving the SFP. In this thesis, we first give an inexact relaxed scheme of the CQ algorithm, which is more practicable than the CQ algorithm when orthogonal projections PC and PQ are not easy to get. Then we discuss about the variable stepsize CQ algorithm and demonstrate that the CQ algorithm with fixed stepsize and variable stepsize CQ algorithm are both a specific realization of gradient projection algorithm.The variable stepsize, comparing with a fixed one, can accelerate the convergence of algorithm.In the end,we offer an inexact scheme of variable stepsize CQ algorithm and its relaxed version.Chapter 4 deals with stochastic split feasibility problem(SSFP) and apply the SAA method to solve it. The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation.In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. The process is repeated with different samples to obtain candidate solutions along with statistical estimates of their optimality gaps.In this chapter, we present a definition for the stochastic split feasibility problem (SSFP) and apply the SAA method to solve it. We investigate the existence and conver-gence of a solution to the sample average approximated SSFP. Under some moderate conditions, we show that the sample average approximated SSFP has a solution with probability one and with probability approaching one exponentially fast with the in-crease of sample size,the solution converges to its true counterpart.