图最大化问题的近似算法及其在金融数据挖掘中的应用

图最大化问题是在计算机科学、运筹学、组合优化、网络以及其他离散数学领域里广泛出现的一类NP－hard问题，是关于图的最大化划分问题的简称，这类问题包括：最大割问题、最大二等分问题、最大有向割问题、最大 -割问题（ ）、最大目录分割问题等.本项目将研究用离散填充函数算法和半定规划松弛方法求解一些图的最大化问题及同图的最大化问题密切相关的离散二次非凸优化问题; 研究构造图的最大化问题的有效的离散填充函数和半定规划松弛,设计有效的近似求解算法,分析它们的收敛性,复杂性,近似比等理论性质; 进行广泛的数值试验与比较;应用研究所得成果,结合最大割问题与支持向量机技术,研究海量金融数据的多类分类挖掘技术,并应用于信用风险的控制和信用等级的评估,利用相关金融数据,进行实证分析.

本项目在前一基金项目《大规模最大割问题的连续化近似算法及推广》研究的基础上，继续进一步对图的最大化问题的近似算法及相关算法在金融数据挖掘与金融工程研究中的应用开展研究，截至本报告完成之日，本项目已在国内外期刊杂志上正式发表论文25篇，完成博士论文3篇，硕士论文2篇，其中在国际期刊正式发表论文13篇，全被SCI收录，国际会议报告论文1篇，被EI收录，国内期刊发表论文11篇。项目的主要研究成果可以分为如下两大部分。.一．图最大化与半定规划问题近似求解算法的研究。以前一项目的研究为基础，本项目提出了一个新的不需要对参数调整的求解大规模最大割问题的填充函数法；针对图最大二等分问题，在吸取半定规划松驰和秩二松驰优点的基础上给出了图最大二等分问题的秩二松驰模型，用连续最优化算法求解；对图的最大3-割问题与最大3-等分问题，通过定义问题的K-领域并结合贪婪算法，分别构建了相应的随机搜索启发式算法，算法的性能明显优于0.836算法；对于更一般的图的最大s-t割与最大s-t-v割等图最大化问题，通过引入具有特殊结构的正半定矩阵，给出了结合随机搜索与旋转舍入的近似求解算法。由于图的最大化问题可通过对离散变量的松弛将其松驰成半定规划问题，本项目还开展了对半定规划问题以及同其紧密相关的互补问题近似求解算法的研究，通过引入光滑函数对这两类问题的求解分别给出了不精确光滑牛顿法和信赖域算法，以避免通常牛顿法对方程组需要精确求解的要求；在求解半定规划问题的信赖域算法中，每次迭代信赖域子问题的求解采用共轭梯度法，完全避免了对方程组的求解，并采用了最新的过滤技术以确定新的迭代点；对互补问题的求解主要通过对牛顿方程组的光滑化后，再对方程组序列进行渐近精确的不精确求解，给出了一类不精确光滑牛顿法，而对光滑参数的处理采用了按规则调节与当作变量进行迭代调节的两种技巧，由此给出两种完全不同的不精确光滑牛顿法。. 二．相关算法在金融数据挖掘与金融工程研究中的应用。基于金融历史数据进行预测是金融理论研究与金融实务领域关注的重要对象，本项目在利用数据挖掘技术对金融时间序列趋势的预测，以及对人民币汇率变动趋势的预测分别给出了不等权重支持向量机预测模型和将遗传算法与支持向量机结合的遗传支持向量机预测模型；对金融投资领域的数量化投资，本项目给出了基于优化反问题的投资组合调整模型，以解决市场条件变化后原投资组合是否还是