min-max-min规划的凝聚同伦方法及其在数据挖掘中的应用

《min-max-min规划的凝聚同伦方法及其在数据挖掘中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、大连理工大学博士学位论文min-max-min规划的凝聚同伦方法及其在数据挖掘中的应用姓名：熊慧娟申请学位级别：博士专业：计算数学指导教师：于波20090901大连理工大学博士学位论文摘要min．max-min规划是一类重要的非光滑非凸优化问题，在工程优化设计、电子线路设计、数据挖掘等领域有着重要应用．本文的工作在已有的凝聚同伦算法的基础上进行．第一章主要介绍min-max-min规划模型及其应用背景，并回顾一些相关理论与算法．第二章提出了数值跟踪凝聚同伦的一个基于截断策略的高效率算法．在算法的每步迭代，只用至Umax-min函数的组成函数中的一小部分的凝聚函数，这一部分组成函数对应的下

2、标集合在每步迭代过程中随着截断精度控制准则自适应调整．以尽可能地减少函数的梯度及海赛阵的计算量．我们给出保持校正算法的二次收敛性和预估步的有效性的截断凝聚精度控制准则，该精度控制准则不涉及梯度和海赛阵的计算。只与max-rain函数的组成函数的函数值有关．基于该精度控制准则，我们证明了截断凝聚同伦算法的收敛性及每步校正的局部二次收敛性．第三章基于二次凝聚函数，对min-max-min规划构造了一种动约束函数，使得原问题的可行集可以由一个凸球约束连续形变过去，进而给出了一类新的凝聚形变同伦方法．新算法不要求可行集满足弱法锥条件，并且不要求初始点是内点．第四章基于离散化相容逼近的策略，将半无

3、限rain-max-rainl'石]题转化为有限min—Iila。xomin规划问题，再用截断凝聚同伦方法求解．可以证明：当离散点充分稠密时，离散化子问题的稳定点是原问题的e一次稳定点．第五章将半无限min．max-min问题写成一个双层规划问题．在底层问题严格凸的假设下，建立了原问题的一阶最优性条件，并构造凝聚同伦方法求解该问题．在一定条件下．可以证明通向原问题的广义KKT点的光滑同伦路径的存在性和收敛性．第六章考虑了截断凝聚同伦算法在数据挖掘的支持向量机模型求解中的一些应用．首先考虑了半监督分类问题．将已有的求解半监督分类问题的一个支持向量机模型加以变形，得到一个由max型以及max

4、-min型的非光滑函数组合得到的无约束非光滑非凸优化问题，并构造了截断凝聚同伦算法求解该模型．其次考虑了多示例分类问题．该问题是线性min．max-min规划问题。即组成函数均为线性函数．我们证明该问题满足弱法锥条件，因此可以用截断凝聚同伦方法求解该问题．文中所有的算法．都用Matlab编程实现，并通过数值实验与已有的一些算法相比较。结果表明本文给出的算法是有效的．关键词：min—max-min规划；凝聚函数；同伦方法；非光滑半无限规划；支持向量机min，max-rain规划的凝聚同伦方法及其在数据挖掘中的应用AggregateHomotowMethodsforMin—max-rainP

5、rogrammingwithApplicationsinDataMiningAbstractMin—max-rainprogrammingisakindofimportantnonsmoothproblemthatappearsinvariousfieldssuchasengineeringoptimizationdesign：circuitdesignanddatamining．Thethesisisbasedontheexistingaggregatehomotopymethod，itconsistsofthefollowingsections：InChapter1．min-max-

6、minprogrammingproblemwithitsapplicationgroundist01’一mulated，andsomeresultsonrelatedtheoryandalgorithmsarerecalled．InChapter2，bygivingatruncatedaggregatestrategy,allefficienttruncateaggregatemethodfornumericallytracingaggregatehomotopypathisintroduced．Atevery．iteration，onlyapartofcomponentfunction

7、sareusedtomakeaggregatesmoothingapproximation．whoseindexsetisupdatedadaptivelywithatruncatedaggregatecriterion．Thecrite-rionconcernsonlywithcomputationofcomponentfunctionsvalue，nottheirgradientsorHessian．Basedonthecrit