【作者】 汪仲文；

【导师】 杨庆之；

【作者基本信息】 南开大学 ， 计算数学， 2010， 博士

【摘要】 在这篇论文里,我们研究了几个相互关联的优化问题的数值方法。文中所涉及到的问题分别是互补问题、分裂可行问题和随机分裂可行问题。第一章介绍了本文所研究的几个优化问题,它们之间的关系以及文中要用到的一些记号。在第二章里,我们研究了一类非线性互补问题。互补问题是运筹学与计算科学的一个交叉研究领域,它与非线性规划、极大极小、对策论、不动点理论等分支有紧密联系,在力学、工程、经济、交通等许多实际部门有广泛的应用。互补问题的标准形式是：给定连续可微的向量函数F(x):Rn→Rn求一向量x∈Rn使得x≥0,F(x)≥0,xTF(x)=0当F(x)为线性函数(令F(x)=Mx+q,M Rn×n,q∈Rn)时,称其为线性互补问题,记为LCP (M,q);否则,称其为非线性互补问题,记为NCP(F)互补问题的一个自然的推广就是变分不等式问题(VI),即求解一向量x∈C使得(y-x)TF(x)≥0, (?)y∈C,这里C(?)Rn为一个非空闭凸集.本章针对非线性互补问题(P0-NCP),研究了一类非内点路径跟踪算法。相对于标准中心路径,我们使用了尺度化的中心路径。基于尺度化的中心路径,我们给出了一个求解P0-NCP的一步式非内点连续光滑化牛顿算法。在不需要严格互补性的假设条件下,证明了该算法的全局收敛性,并在适当的假设下,证明了局部二次收敛性。最后,我们通过几个算例与另一类求解P0-NCP的一步式光滑化牛顿法进行了比较。在第三章里,我们研究了求解分裂可行问题的几种投影方法。所谓分裂可行问题(SFP)是：求x∈C,使得Ax∈Q,其中集合C和Q分别是RN和RM中的非空闭凸集,A是M×N阶实矩阵。这类问题产生于信号处理中,特别是在图像重构和其他的图像还原问题中。近年来,分裂可行问题在调强放疗(IMRT)方面也有了重大的应用。同时,分裂可行问题还与凸可行问题密切相关。凸可行问题(CFP)就是要找有限个闭凸集的非空交集中的点,它在数学,物理等许多学科中是一个基本的问题。因此,研究如何求解分裂可行问题具有重要的意义。CQ算法是求解SFP的一种简洁的方法。在本文中,我们首先给出了CQ算法的一个非精确松弛格式,当正交投影PC和PQ不容易求得时,此格式比CQ算法更具实用性。然后我们讨论了变步长的CQ算法,并且说明,不论是带固定步长的CQ算法,还是变步长的CQ算法,都是梯度投影算法的一个具体实现。相对于固定步长,变步长可以提高算法的收敛速度。最后,我们提出了变步长CQ算法的非精确格式以及非精确松弛格式。在第四章里,我们应用样本均值近似(SAA)方法研究了随机分裂可行问题(SSFP)o样本均值近似方法的基本思想是利用Monte Carlo样本技术产生具有独立同分布(iid.)的样本,来模拟随机模型中的随机参数。利用Monte Carlo样本技术,由随机样本产生的样本均值来近似估计随机优化问题的目标函数的数学期望函数,由此产生的样本均值近似问题,可以利用确定性优化技术来求解。用不同的样本重复上述过程,可以用统计方法估计产生的候选解的优化间隙。我们首先定义了随机分裂可行问题(SSFP),然后讨论用样本均值近似(SAA)方法求解该问题。我们研究了样本均值近似的随机分裂可行问题的解的存在性和收敛性。在一定的条件下,我们证明了随着样本点的增加,样本均值近似的随机分裂可行问题依概率1有解,且该解依概率1指数收敛到随机分裂可行问题的解。更多还原

【Abstract】 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.更多还原