大规模稀疏线性规划:基于最优基启发性特征刻划的CRASH算法

摘要

在线性规划模型的求解中,初始基的好坏是至关重要的.普遍相信,好的初始基可以导致迭代次数的减少.在理想的情形,如果初始基恰好是最优基,则无须迭代即可得到最优解.然而,迄今为止的初始基的确定方法(CRASH)均未考虑到这一点.为此,潘平奇教授提出关于最优基的启发性特征刻划(参见[17]),其基本思想是初始基尽量向最优基靠近,从而达到减少总迭代次数的目的.这种方法在稠密问题中虽然已经证实具有很好的效果,但在大规模稀疏问题上还没有人尝试过.该文将首次把最优基的启发刻划应用于大规模稀疏初始基的确定,因而具有更重要的实际意义.研究人员给出了具体的实现方式和算法,采用了适宜的数值结构,进行了大量的数值实验,得到了令人鼓舞的数值结果.

目录

文摘

英文文摘

引言

第一章若干基本结果

第二章基于Gaussian变换的单纯形算法

第一节基本算法过程

2.1.1基本思想

2.1.2形式和解

2.1.3选主元过程

2.1.4带行列交换的Gauss变换及校正

2.1.5主过程

2.1.6一阶段子过程

第二节Harris行主元规则

第三节处理稀疏问题的若干基本过程

3.2.1前推过程

3.2.2后推过程

3.2.3 Bartels-Golub校正方法

第三章大规模稀疏问题的数据结构

第四章最优基的启发性特征刻划和CRASH算法

第一节MINOS 5.3中的CRASH过程

第二节基于最优基的启发性特征刻划思想

第三节基于最优基启发特征刻划的CRASH过程

第四节MARKOWITZ规则的两个变形

第五章数值实验结果

参考文献

致谢