【作者】 宇振盛；

【导师】 王长钰；

【作者基本信息】 大连理工大学 ， 运筹学与控制论， 2004， 博士

【摘要】 信赖域方法是求解非线性最优化问题的一类重要数值计算方法，由于它具有较好的可靠性和很强的收敛性，因而在近三十年来受到了最优化研究界的重视。特别是近几年来，一直是最优化领域的一个研究重点。目前，信赖域方法已经和传统的线搜索方法并列为非线性规划的两类主要数值方法。在变分不等式与互补问题及平衡约束优化问题中也有信赖域算法可见，在最近兴起的filter方法中，信赖域方法也起着重要的作用。 本文主要研究非线性优化中的信赖域方法。其中包括信赖域子问题的构造、求解以及在约束优化及半定互补问题中的应用。全文共分六章。 第一章：简单介绍信赖域方法的起源及发展现状。 第二章：给出了带记忆的信赖域子问题模型。该模型不仅包含当前点的信息而且包含着过去迭代点的信息，从而使我们可以从更全局的角度来求得信赖域试探步，避免了传统信赖域方法中试探步的求取完全依赖于当前点的信息而过于局部化的困难。将此模型应用到凸约束优化及等式约束优化问题，在几种不同的非单调信赖域技术下，获得了方法的全局收敛性。 第三章：利用谱投影梯度方法与一个新的非单调线搜索技术给出了求解信赖域子问题的一个方法，在一般的假设条件下获得了方法的全局收敛性。 第四章：分析了求解一般非线性方程组的有效集信赖域-CG方法的全局收敛性。将一般非线性方程组问题转化为带非负约束的极小化问题，并利用有效集信赖域对其进行求解，其中信赖域子问题是利用截断共轭梯度方法求解的。在不需要聚点存在的条件下获得了算法的全局收敛性。 第五章：将Nocedal与Yuan的组合信赖域与线搜索技术应用到等式约束优化问题。通过求解某一信赖域子问题及对罚因子的矫正，证明了信赖域步为价值函数提供了一个下降方向。为允许负曲率方向及克服Maratos效应，我们在信赖域试探步中加入二阶校正步，线搜索时采用非单调技术。在一般信赖域方法的假摘要设条件下，我们证明了该方法的全局收敛性及局部收敛速度.数值试验表明了该方法的有效性. 第六章:给出了求解非线性半定互补间题的一个新的光滑效益函数，在不需要单调及LIPschitz连续的条件下，证明了效益函数的水平集有界且稳定点即为全局极小点.进一步地，给出了求解带半定约束极小化间题的信赖域算法，其中信赖域子问题是利用截断共扼梯度法近似求解的.更多还原

【Abstract】 Trust region method is a class of important numerical method for nonlinear optimization problems. Because of its remarkable numerical reliability in conjunction with a sound and complete convergence theory, researchers in nonlinear optimization area have paid great attention to it since 80’s, especially during 90’s. At present, trust region method and line search method are two mainly types numerical algorithms for nonlinear programming. For variational inequality problems and complementarity problems, one can also design the corresponding trust region algorithms. Moreover, it also play an important role in a recently developed filter method.The aim of this thesis is to study the trust region method in nonlinear optimization, which including the forming and the solving of the trust region subproblem and applications for constrained optimization and semidefmite complementarity problems. This thesis includes six chapters.Chapter 1: Introduction.Chapter 2: A trust region subproblem model with memory is proposed. The model includes memory of the past iteration, which makes the algorithm more farsighted in the sense that its behavior is not completely dominated by the local nature of the objective function, but rather by a more global view. We apply this model to convex constrained and equality constrained optimization problems and establish the global convergence with the help of nonmonotone techniques.Chapter 3: Using spectral projected gradient method and a new nonmonotone line search technique, we propose a algorithm for solving the trust region subproblem. Under weak conditions, the global convergence is established.Chapter 4: We analyze an active set trust region-CG method for the solution of nonlinear system with equalities and inequalities. By reformulating the system into a nonlinear minimization problem with non-negative constraint, we proposed an active set trust region algorithm with which the subproblem is solved bythe truncated conjugate gradient method. The global convergence is established without requiring the existence of an accumulation point.Chapter 5: We apply the combining trust region and line search algorithm to solve equality constrained optimization. By using L1 exact penalty function as the merit function and solving a trust region subproblem, we prove that the trust region trial step provide a descent direction for the merit function. To allow the negative curvature direction and avoid the Maratos effect, we add second correction step to trust region trial step and employ nonmonotone technique in line search. The global convergence and local superlinear rate are obtained under certain conditions. Some numerical tests are also presented.Chapter 6: In this chapter, we present a new merit function for the semi-definite complementarity problem (SDCP) by extending the bounded smooth reformulation for variational inequality problems. We prove that the merit function has a bounded level set and any stationary point of it is a global minimizer without the assumption of monotonicity. Moreover, we present a trust region algorithm for solving the minimization problem with semidefinite constraints. The trust region subproblem is solved by the truncated conjugate gradient method and the global convergence is established even without requiring the existence of an accumulation point of the generated sequence.更多还原