非线性约束优化问题的仿射投影既约Hessian修正梯度路径内点方法

论文摘要

最优化技术在国民经济的许多领域,如国防、工农业生产、交通运输、金融、贸易、管理、科学研究中有广泛的应用。非线性规划是最一般的优化问题,当变量受到一些条件的限制时,寻求目标函数的最优解称为约束最优化,反之,当变量不受任何约束的限制时,寻求最优解称为无约束最优化。在本文中,我们研究的是一个带等式约束和有界变量约束的非线性规划问题。最优性条件是指最优化问题的最优解(局部的或全局的)所必须满足的条件,常见并常用的有一阶必要条件和二阶必要条件。由于最优性条件不仅对于最优化理论的研究具有重要意义,而且对最优化算法的设计和终止条件的确定起重要作用,所以本文中我们首先从最优性条件出发,通过构建一个目标函数的二次近似模型来提出一种基于仿射投影既约Hesse阵的修正梯度路径内点算法。Coleman 和Li 在[5] 中提出了一种信赖域内点算法,称为“双信赖域法”。其中一个很有启发性的想法是构建了一个仿射尺度矩阵,在“双信赖域法”中,利用仿射内点变换,在取合理的信赖域半径时迭代所得的方向均落在严格可行区域内,使解信赖域子问题时不用考虑有界约束。在本文中,对于有界变量约束这一难点,我们根据最优性条件,也构造了一个相应的仿射尺度矩阵。对于仿射空间中的等式约束,我们采用了既约Hesse 矩阵算法。既约Hesse矩阵算法是目前较流行的解决非线性等式约束优化问题的有效方法之一,朱德通在[20]中利用信赖域投影Hesse 阵算法成功解决了线性约束最优化问题。利用等式约束系数矩阵的QR 分解的既约Hesse 阵思想将原问题分解成值空间和零空间中的两个通常的信赖域子问题,更易于数值求解和实现。线搜索技术和信赖域策略是解非线性优化问题的两种基本逼近方法,这两种技术都能用来保证算法的整体收敛性。无论对于无约束最优化还是约束最优化,信赖域方法都是一种行之有效,常用的方法。信赖域方法是首先定义当前迭代点的某个邻域,假定在此邻域(称为“信赖域”)内,二次模型是目标函数的一个合适的近似,则在这个邻域内极小化二次模型,得到一个近似极小点。信赖域方法不仅能保证算法的整体收敛性,而且不要求目标函数的Hesse 矩阵(或其近似)是正定的。信赖域方法也可以通过构造适当的路径,在路径上搜索满足信赖域约束的二次模型最小值。弧线路径方法有很多,如折线路径、最优路径、共轭梯度路径、修正梯度路径等(见[4],[15] 和[18])。本文是在近似二次模型的基础上,采用修正梯度路径代替信赖域方法获得迭代方向。修正梯度路径可以通过用Hesse 阵的特征值和特征向量表示(见Bulteau 和Vial [4])。对于传统的信赖域方法,要获得可接受的迭代步可能要通过重复计算多次信赖域子问题才能获得,因此每完成一次迭代的整个计算会比较大。Nocedal 和Yuan[13] 提出了信赖域和线搜索两种技术相结合的方法,称为回代法(backtracking)。当由信赖域子问题求得的搜索方向不被接受时,利用线搜索技术得到接受步长,定义新的有足够下降量的迭代点。在[18] 中,朱

论文目录

• 致谢
• 中文摘要
• 英文摘要
• 序言
• 第一章 最优化问题的概念、性质和主要方法
• 1.1 最优化问题简介
• 1.2 最优性条件
• 1.3 最优化方法概述
• 1.4 最优化方法的收敛性
• 1.5 线搜索技术与信赖域方法
• 1.5.1 线搜索技术
• 1.5.2 信赖域方法
• 第二章 非线性约束优化问题的仿射投影既约Hessian修正梯度路径内点算法
• 2.1 非线性约束最优化问题的引入
• 2.2 近似二次模型的建立
• 2.3 仿射既约Hessian修正梯度路径
• 2.3.1 仿射既约Hessian修正梯度路径的构成
• 2.3.2 仿射既约Hessian修正梯度路径的性质
• 2.4 仿射投影既约Hessian 修正梯度路径内点算法
• 第三章 算法的收敛性
• 3.1 整体弱收敛性
• 3.2 整体强收敛性和局部收敛速率
• 第四章 算法的数值结果
• 第五章 小结
• 参考文献
• 攻读硕士学位期间的研究成果
• 论文独创性声明
• 论文使用授权声明