基于自协调指数核函数的原始—对偶内点算法

【摘要】线性锥规划是目前优化领域中最热门的研究课题之一.Nemirovskii在2006年国际数学家大会一小时报告[72]中指出,锥规划是近20年凸优化研究工作中的一项重大突破性进展,主要包括线性规划,二阶锥规划和半正定锥规划这三类常见的对称锥规划.这三类规划可以转化成统一的线性锥规划模型.线性锥规划不仅具有良好的结构特征和对偶理论，而且具备很强的数学表达能力和实用性.许多应用领域中的实际问题都可以描述成线性锥规划的模型,诸如工程管理,金融优化,图像处理和信号处理中的许多优化问题都可以借助于线性锥规划问题的模型来求解.此外,线性锥规划存在多项式时间内点算法,原始–对偶内点算法是其中很重要的一类.原始–对偶内点算法是求解线性规划,二阶锥规划和半正定规划的强有力工具,它可以快速有效的求解大规模锥优化问题.目前已有许多实用的优化软件是基于原始–对偶内点算法开发的.因此,针对线性锥规划研究有效的原始–对偶内点算法具有十分重要的理论意义和实际应用价值.构造一个合适的障碍函数对原始–对偶内点算法的设计和分析起着非常重要的作用.障碍函数不仅可以确定搜索方向,而且还可以简化算法的复杂性分析,改进迭代界.在基于核函数的原始–对偶内点算法中,障碍函数可以通过一个给定的一元核函数来确定.本博士学位论文首次提出了一类新的完全由指数函数构造的自协调指数核函数.作为核函数,本文所提出的自协调指数核函数并不完全满足在基于核函数的原始–对偶内点算法中对核函数要求的‘Eligible’性质.通过进一步研究此函数及其各阶导数之间的性质,证明自协调指数核函数的二阶导数和三阶导数之间满足自协调性质.基于此类自协调指数核函数,分别针对线性规划,二阶锥规划和半正定规划设计原始–对偶内点算法,并对算法进行复杂性分析,得到大步校正内点算法的迭代界.本文主要工作包括:1.针对线性规划问题,基于自协调指数核函数设计了原始–对偶内点算法.利用由自协调指数核函数定义的障碍函数来确定搜索方向,并利用相应的障碍函数作度量函数来估计迭代点与中心路径之间的距离.在算法的复杂性分析中,利用牛顿法极小化目标函数为自协调函数的无约束优化问题得到了算法内迭代中障碍函数的下降量,并得到了更新μ-乘子之后障碍函数的上界,最终得到了大步校正内点算法的迭代界.最后我们给出线性规划的数值算例验证了算法的实际计算效果.2.针对二阶锥规划问题,基于自协调指数核函数设计了原始–对偶内点算法.首先利用向量的谱分解给出了二阶锥上的向量值函数,并根据向量值函数来确定相应的障碍函数.进一步地,我们利用障碍函数来确定搜索方向并作度量函数来估计迭代点与中心路径之间的距离.在若当代数结构下,分析了二阶锥规划的中心路径.在算法的复杂性分析中,基于二阶锥上内积的定义,我们首先利用牛顿法极小化目标函数为自协调函数的无约束优化问题得到了算法内迭代中障碍函数的下降量.其次根据向量值函数的性质,通过计算得到了更新μ-乘子之后障碍函数的上界,最后得到了大步校正内点算法的迭代界.我们通过一些数值算例验证了算法的实际计算效果.3.针对半正定规划问题,设计了基于自协调指数核函数的原始–对偶内点算法.首先引入矩阵函数来确定相应的障碍函数,使用障碍函数来确定搜索方向并作度量函数来估计迭代点与中心路径之间的距离.在算法的复杂性分析中,根据矩阵函数的性质,利用牛顿法极小化目标函数为自协调函数的无约束优化问题得到了算法内迭代中障碍函数的下降量,并得到了更新μ-乘子之后障碍函数的上界,最终得到了大步校正内点算法的迭代界.最后我们给出半正定规划的数值算例来验证算法的实际计算效果.
【作者】张景；
【导师】白延琴；
【作者基本信息】上海大学，运筹学与控制论，2014，博士
【关键词】线性规划；二阶锥规划；半正定规划；内点算法；自协调函数；核函数；障碍函数；复杂性分析；

【参考文献】
[1]马恋.彩虹障碍期权的定价问题[D].华中师范大学,应用数学,2013,硕士.
[2]赵杰.珠江口盆地东部中新统珠江组碳酸盐岩结构与成岩作用[D].成都理工大学,地质学,2013,硕士.
[3]王淑鸿.电力营销决策支持系统的研究与建立[D].华北电力大学（北京）,2003.
[4]杨彪.基于普通数字影像的近景摄影测量技术研究与应用[D].河海大学,摄影测量与遥感,2004,硕士.
[5]李斌.Teradata数据仓库在中国邮政的应用前景研究[J].邮政研究,2005,05:20-22.
[6]刘应国.四川县域优势产业发展的对策研究[D].西南交通大学,区域经济学,2014,硕士.
[7]燕鹏.从晚清重臣到民国政要—孙宝琦研究[D].苏州大学,中国近现代史,2014,硕士.
[8]吴婷芳.金坛于氏家族文化研究[D].安庆师范学院,中国古代文学,2013,硕士.
[9]苗文青.崔炳元钢琴作品的演奏技术探析[D].西安音乐学院,钢琴演奏,2014,硕士.
[10]姚从潮,王新民,黄耀,谢蓉.再入飞行器反推力器配置性能评价方法[J].控制与决策,2014,08:1465-1470.
[11]温树勇.提高客户价值的可拓策略生成系统研究[D].广东工业大学,计算机应用技术,2013,硕士.
[12]胡昊.或有可转换债券的定价与数值分析[D].浙江财经学院,金融学,2013,硕士.
[13]吴丹.企业社会资本对小额贷款公司影响的社会学分析[D].吉林大学,社会学,2013,硕士.
[14]陈洁.政府网络新闻发言人研究[D].苏州大学,新闻与传播（专业学位）,2014,硕士.
[15]刘文明.论公司法人人格否认制度在我国的适用[D].西南政法大学,民商法（专业学位）,2012,硕士.
[16]肖文栋,王克明,张森.连铸过程结晶器液面控制的模糊控制方法[J].控制与决策,2002,02:167-170+174.
[17]曹秋良.参与努力与捐赠额度对善因营销的作用效果及影响机制研究[D].华中科技大学,企业管理,2012,硕士.
[18]王顺萍.中职学生自我管理能力培养的研究[D].鲁东大学,教育管理（专业学位）,2013,硕士.
[19]张文韬.安今益用于绝经后妇女的激素补充治疗[D].兰州大学,妇产科学（专业学位）,2013,硕士.
[20]冯蕾,严雪芳.基于模糊语言学的第二语言教学[J].湖北社会科学,2015,02:177-180.
[21]赵晶晶.基于Qt的多电飞机电源监测系统研究及实现[D].南京航空航天大学,交通信息工程及控制,2013,硕士.
[22]杜聪慧.面向互联网数据的新词发现平台的设计与实现[D].哈尔滨工业大学,软件工程,2013,硕士.
[23]刘议隆.《伤寒杂病论》对精神疾病的辨治规律研究[D].南京中医药大学,中医临床基础,2014,博士.
[24]蔡邑鹏.治理理论视域下石狮市社区管理改革探析[D].华侨大学,公共管理（专业学位）,2013,硕士.
[25]刘祥田.佩珀生态社会主义理论及当代价值研究[D].山东大学,马克思主义中国化研究,2013,硕士.
[26]王玉红.论我国基金会制度的完善[D].河北大学,民商法学,2014,硕士.
[27]王丽娜.Web日志挖掘的智能化站点技术[J].河南科技,2004,04:26-27.
[28]张羽阳.伊恩·麦克尤恩的《赎罪》中塔利斯姐妹的心理分析[D].河北师范大学,英语语言文学,2013,硕士.
[29]李悦.明代火器的谱系[D].东北师范大学,中国古代史,2012,硕士.
[30]柯小清.疏肝解郁活血法联合激光治疗肝郁血滞型视网膜静脉阻塞的临床观察[D].福建中医药大学,中医五官科学（专业学位）,2013,硕士.
[31]曾灏.二次相关法自动静校正[J].石油地球物理勘探,1981,04:37-43.
[32]卜新春.城市轨道交通换乘车站客流预测及分析[D].长安大学,交通工程,2014,硕士.
[33]宋彩霞.3，4-二氯苯胺降解菌S1的降解特性及功能定位[D].西南大学,农药学,2014,硕士.
[34]何玉龙.当代甘南藏族题材工笔人物画创作探析[D].湖南师范大学,美术学,2014,硕士.
[35]赵夏爽.河南省金融结构调整与产业结构升级关系研究[D].郑州大学,金融学,2013,硕士.
[36]张洪涛,李隆球,张广玉,王武义.基于单目视觉的微型空中机器人自主悬停控制[J].控制与决策,2014,08:1501-1504.
[37]刘景.基于多面体模型的预测控制方法研究[D].江南大学,控制理论与控制工程,2012,硕士.
[38]李芳.我国电信业的民间资本准入法律制度研究[D].西南大学,民商法学,2014,硕士.
[39]黄星.共混改性制备抗菌性耐污染聚醚砜超滤膜的研究[D].中国海洋大学,海洋化学,2014,硕士.
[40]涂健.无烟煤用作锂离子电池负极材料的可行性研究[D].湖南大学,材料学,2003,硕士.
[41]郭丽峰.轻钢密立柱墙体的抗剪性能研究[D].西安建筑科技大学,结构工程,2004,硕士.
[42]秦昊.Cr_7C_3在磁场作用下取向行为[D].沈阳工业大学,材料加工工程,2013,硕士.
[43]赵冬冬.基于FPGA的1024点FFT算法实现[D].苏州大学,微电子学与固体电子学,2014,硕士.
[44]王彦芳.游梁式抽油机及其横梁支撑轴承载荷的力学特性研究[D].兰州理工大学,机械制造及其自动化,2013,硕士.
[45]陈超.卢梭现代性批判思想研究[D].中共中央党校,外国哲学,2013,硕士.
[46]卡萨克（Antoine）.蜂窝网络中多输入多输出信道的设计和性能分析[D].北京交通大学,2014.
[47]王路平.成渝经济区投资环境评估研究[D].重庆工商大学,区域经济学,2014,硕士.
[48]高晓光.基于LON网络技术的应用研究[D].西北工业大学,控制理论与控制工程,2004,硕士.
[49]余大新.蒙古中南部地区与青藏高原东北缘地震面波层析成像[D].中国地震局地球物理研究所,固体地球物理学,2014,博士.
[50]郑巍.基于网络的企业经营管理决策支持系统研究与应用[D].重庆大学,2004.