基于有效集识别和多维滤子技术的优化算法研究

摘要

本文主要研究求解无约束和界约束优化问题的有效集方法和多维滤子信赖域方法.论文共分为六部分.首先,在第一章我们回顾了几种求解界约束优化问题的有效集识别策略以及滤子技术的发展和研究现状,并对现有算法加以分析,从而引出进一步需要解决的问题以及本文的主要工作.
　　 本文的第二章,我们根据界约束优化问题KKT条件的特殊性,推导出乘子的每一个元素或者等于0,或者等于梯度或负梯度相应的元素.为了比较建立在乘子函数和乘子基础上的有效集识别函数的不同,构建了有效集拟牛顿算法框架。算法全局收敛,并且在严格互补松弛条件成立的情况下局部超线性收敛.最终数值结果表明在问题规模很大时,基于乘子函数的有效集识别策略因为要额外的求解两个n×n的线性系统,整个求解过程所需的CPU计算时间要多于后者.
　　 第三章,提出了求解界约束优化问题的精确有效集牛顿算法,成功地将Facchinei,Fischer和Kanzow提出的精确有效集识别函数应用到界约束优化问题.新算法的每步迭代,借助于KKT条件,将工作集进一步划分为三部分,巧妙的保证了算法的全局收敛性.与文献[2,3,6]不同,本文的有效变量采用负梯度方向或者截断的负梯度方向作为搜索方向.在无严格互补松弛条件的情况下,建立了算法的局部超线性收敛性.最终在同一算法框架下比较了不同有效集识别函数的运行效果.
　　 第四章,同样针对界约束问题,采用第三章分析的精确有效集识别函数,每步迭代在确定搜索方向dk后,利用投影线搜索确定下一步迭代点,实现了界约束优化问题两种有效集识别技术一精确有效集识别函数和投影梯度法的结合.新算法全局收敛.最终通过与投影梯度法的数值比较,说明新算法的有效性.
　　 第五章,针对2005年Gould等人提出的求解无约束优化问题的多维滤子信赖域算法,给出多维滤子技术在牛顿折线法的具体实现,并在此基础上,直接从标准的信赖域算法框架出发,将信赖域子问题中柯西步的求解独立出来,一旦发现二次模型非凸便直接采用柯西点作为下一步迭代点.这一措施避免了原算法针对信赖域子问题非凸时所进行的复杂操作,是一个易于编程实现的多维滤子方法.数值结果表明滤子技术的引入增加了试探点被接收作为新的迭代点的几率,有效的减少了算法的迭代次数.数值试验结果表明了新算法的有效性.
　　 第六章,由第五章求解无约束问题的多维滤子信赖域修正算法出发,将其推广到界约束乃至凸约束的优化问题.此时多维滤子集中的滤子点不再是n维的梯度向量,而是投影剩余梯度.柯西点用于预测有效集.对求解界约束优化问题的信赖域方法而言,成功的近似有效集可以降低信赖域子问题的规模.修正算法对于凸约束优化问题全局收敛,最后我们通过一组数值试验验证了新算法的实际运行效果.

目录

文摘

英文文摘

第一章 绪 论

§1.1引言

§1.2界约束优化问题的应用背景

§1.3几种有效集识别策略

§1.3.1投影梯度法

§1.3.2有效集识别函数

§1.3.3逐次线性规划-等式约束二次规划(SLP-EQP)

§1.4滤子技术

§1.4.1滤子技术

§1.4.2多维滤子技术

§1.5本文主要工作概述

第二章 求解界约束优化问题的近似有效集拟牛顿算法

§2.1引言

§2.2乘子与目标函数梯度的关系

§2.3算法及全局收敛性分析

§2.4数值试验

第三章 求解界约束优化问题的精确有效集牛顿算法

§3.1引言

§3.2精确有效集牛顿算法

§3.2.1搜索方向的确定

§3.2.2算法框架

§3.3算法的全局收敛性

§3.4算法的超线性收敛性

§3.5数值试验

第四章 基于精确有效集识别函数策略的投影梯度法

§4.1 引言

§4.2算法框架

§4.2.1搜索方向的确定

54.2.2投影线搜索

§4.2.3算法框架

§4.3算法的全局收敛性分析

§4.4数值试验

§4.5总结

第五章 求解无约束优化问题的多维滤子信赖域修正算法

§5.1引言

§5.2几个重要定义和多维滤子信赖域算法

§5.3多维滤子牛顿折线法

§5.4多维滤子信赖域修正算法及全局收敛性分析

§5.5数值结论

第六章 求解界约束优化问题的有效集多维滤子拟牛顿信赖域算法

§6.1引言

§6.2基本的拟牛顿信赖域方法

§6.2.1临界尺度

§6.2.2广义柯西点

§6.2.3试探步的确定

§6.3有效集多维滤子信赖域算法及全局收敛性分析

§6.4数值结论

§6.5总结

第七章 总结与展望

§7.1总结

§7.2展望

§7.2.1有效集识别技术与SVM

§7.2.2多维滤子信赖域方法的并行化

参考文献

攻读博士学位期间发表和完成的主要学术论文

致谢