二次锥规划的算法研究

来源 :西安电子科技大学 | 被引量 : 20次 | 上传用户:jeans
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
二次锥规划是一类十分重要的非光滑凸规划问题.它是在有限个二次锥的笛卡儿乘积的仿射子空间的交集上极小化或极大化一个线性函数.许多数学问题都可转化成二次锥规划求解,如线性规划和凸二次规划等.由于其在工程、控制、金融等领域的广泛应用,近年来二次锥规划问题备受关注. 本文主要研究了二次锥规划的一些不可行内点算法和光滑方法,并探讨了二次锥互补函数的几种光滑函数及其性质.具体内容如下: 1.为了克服内点算法中要求初始点严格可行这一缺点,提出二次锥规划的三种不可行内点算法一原对偶不可行内点算法、基于价值函数的不可行内点法和预估校正不可行内点算法.不可行内点算法不要求初始点及其迭代点的可行性,只要它们位于中心路径的某个不可行邻域内即可.通过恰当选取步长,证明了不可行内点算法是全局收敛的多项式时间算法. 2.将线性规划中求解搜索方向的非精确技巧引入到二次锥规划,给出求解二次锥规划的三种非精确不可行内点算法.算法允许运用非精确搜索方向,且不要求初始点和迭代点位于严格可行解集内.非精确搜索方向在计算时可以有适度的误差,特别当求解大规模二次锥规划问题时可节省计算时间和内存.同时证明了这三种算法的全局收敛性. 3.给出Chen-Harker-Kanzow-Smale(CHKS)光滑函数和光滑Fischer-Burmeister函数的一些性质;提出两种新的向量值函数,讨论其利普希茨连续、强半光滑和可微性质,给出其雅可比公式,并证明它们分别是最小值函数的光滑函数和Fischer-Burmeister函数的光滑函数.上述工作将在二次锥规划光滑方法的设计及收敛性分析中起到重要作用. 4.提出二次锥规划的五种带光滑参数的光滑牛顿法.基于最小值函数或Fischer-Burmeister函数,将二次锥规划问题转化为一个非线性方程组.用牛顿法求解该方程组的扰动,且在迭代过程中恰当选取光滑参数,从而得到二次锥规划问题的最优解.算法对初始点的选取没有任何限制且是全局收敛的. 5.给出二次锥规划的五种带光滑变量的光滑牛顿法并证明了其全局收敛性.基于二次锥互补函数的光滑函数构造一个等价于最优性条件的非线性方程组,该方程组不含任何显式的不等式约束,如x∈K, s∈K或x∈K0,s∈K0.然后用牛顿法求解这一非线性方程组,得到二次锥规划问题的最优解.这五种算法都将光滑函数中的参数视作变量,因而每一步迭代只需求解一个线性方程组,并进行一次线性搜索.算法对初始点的选取都没有任何限制,且其收敛性分析不依赖一致非奇异假设.
其他文献
在现实世界中,许多问题需要考虑系统的层次性,如资源分配、价格问题、工程设计、甚至于兵力部署等。这类问题有个共同特点,即系统中不只有一个决策者,各决策者间具有层次关系,并且
著名的Shannon样本定理表明了任意一个信号函数f∈BΩ,2都可以通过其可列个点上的样本值完全重构。但在实际应用中,由于信号可能是非有限带宽的,以及测量仪器的属性和精度的限
19世纪末至20世纪初,Poincaré等人从经典力学和微分方程定性理论的研究中,提出了动力系统的概念.随后在1927年,Birkhoff出版了名著《Dynamical Systems》,之后动力系统作为一门系
随着计算机和网络通信技术的发展,口令与数字签名技术应运而生。口令是最广泛使用的一种验证用户身份合法性的方法.授权的用户都拥有一个区别于系统中其他用户的标识符ID和秘
为了避免不锈钢生产线酸洗机组火灾事故的发生,在冷轧酸洗生产线投入消防灭火控制系统。新增的消防灭火控制系统通过发现控制、确认控制、火灾处置、日常处置等手段,做到事故
函数空间在经典数学和现代数学中都起着非常重要的作用。在调和分析领域,我们经常碰到Lebesgue空间Lp,Hardy空间Hp,Lipschitz空间以及BMO空间,在这些空间的原始定义中,看不出它们
本文旨在对农村小学读写教学现状进行分析,并以鲁迅人物主题单元为例,通过感悟写话技巧、创设合理情节、拓展习作思维等策略,培养学生阅读能力,提升写作水平.
反问题的研究起源于二十世纪六十年代Tikhonov的基础性论文.反问题广泛存在于自然科学和实际工程技术各个领域,它具有很广阔的应用前景,如地下勘探、无损探伤、医学CT、地震、声
求解稀疏线性方程组是科学计算里的一个重要的课题。随着并行和分布式处理器的出现与流行,使得寻求适合高性能计算机的可并行化预条件子变得越来越重要。稀疏近似逆方法(SAI)因
由于其广泛的应用背景,半定规划己成为数学规划领域中一个较为活跃的研究方向。近几年来半定规划的理论和算法取得了很大的进展。基于非线性Lagrangian方法的成熟,这种方法被尝