复合迫近束方法及其对偶问题的研究

摘要

非光滑优化一词是由Bailinski和Wolfe在1975年首次提出的，该类问题源于众多应用领域[4]，例如，经济学，力学，工程学和最优控制学方面.束方法在当前被认为是解决该类问题中最有效且最有前景的方法之一，它提出的初衷是为了解决某一类极值问题.对束方法的研究涉及了凸分析、线性、非线性规划以及非光滑分析等相关方面的知识领域. 对于非光滑优化问题，我们有很多种不同解法.实际上非光滑优化问题的解决方法可以分成两大主要类型，即次梯度方法和束方法.这两种方法都是基于目标函数值是唯一的且在每一点处的次梯度值都存在的假设.次梯度方法是以次梯度为基础求解非光滑问题的方法，该方法简单易行，但是却可能会导致在其收敛性、最优检测和次梯度近似方面的失败.切平面方法是束方法的思想基础，它充分地利用了黑盒子得到的信息构造了原始问题中目标函数的分段仿射模型.在切平面方法的基础上，产生了一般束方法.该方法目前被广泛使用，能够将前面迭代所产生的迭代点和次梯度等相关信息保留，建立一个信息束，即bundle.因此，就可以在当前迭代步处使用之前所建立起来的信息，用来产生下一个迭代点.但是，随着迭代次数的增加，信息束就会越来越膨胀，带来庞大的计算量和存储问题.为解决这个问题，出现了束方法中特殊的集成压缩技术. 本文主要研究目标函数为复合形式的复合迫近束方法.全文结构如下: 第一章，首先介绍了非光滑优化问题的历史背景与研究现状.非光滑函数的出现为优化问题的求解带来很多困难，为了克服计算上以及理论分析上的困难，许多方法应运而生.接下来本文分别介绍了切平面方法和一般束方法的基本思想，为第二章和第三章中问题的深入研究奠定理论基础. 第二章，首先介绍了非光滑复合束方法的基本思想，引进了问题函数的概念性模型，概念性模型的切平面模型的构建不同于一般束方法中构建目标函数的切平面模型.本章中，主要通过一般束方法的惩罚思想，将目标函数为正齐次凸函数与光滑映射复合函数的原始问题转化成一系列二次规划问题的求解.针对这一稳定子问题，采用对偶空间思想，对惩罚子问题展开研究，在其对偶空间里展开相关性质的探讨与证明，刻画了原问题与对偶问题之间的关系.进一步，我们定义了合成线性化，并且总结出合成线性化的一些性质.同时，详细介绍了相应算法的基本框架. 第三章，构建了一种特殊的复合目标函数，该类函数的外层函数是正齐次凸函数，内层函数是线性函数.进而得到了复合目标函数的特殊切平面模型，利用这种特殊的切平面模型构建了原始问题对应的稳定惩罚子问题.同样采用对偶空间的思想，找到了该惩罚子问题的对偶问题，并在对偶空间里展开了多种性质的研究.与此同时，介绍了算法的基本步骤，详细展开了算法的收敛性分析与证明.在收敛性分析这一节，主要分两种情形进行讨论:当算法产生最后一个下降步，之后全部都是零步时，在参数μk是递增序列且有上下界时，候选点序列是收敛的，并且收敛到原目标函数的极小值点;当算法产生无限多下降步时，通过引进了极小化序列这一概念，也得到了相应的收敛结果.

目录

声明

摘要

1 引言

1．1 预备知识

1．2 切平面方法简介

1．3 一般束方法简介

2 正齐次凸函数与光滑映射复合函数的迫近束方法

2．1 非光滑复合束方法的基本思想

2．2 带有惩罚思想的一般束方法子问题

2．3 复合迫近束方法思想及算法框架

2．4 束方法子问题对偶问题的研究

3 正齐次凸函数与线性函数复合函数的迫近束方法

3．1 问题模型及算法思想简介

3．2 算法框架及对偶问题的研究

3．3 算法收敛性分析

结论

参考文献

攻读硕士学位期间发表学术论文情况

致谢