解凸规划和变分不等式问题的有效数值方法及其应用

摘要

凸规划和变分不等式问题是研究数学、工程科学和管理科学的两大重要工具。随着学科之间的交叉研究，生活中越来越多的问题都可归结为一个凸规划问题，或用一个凸规划问题去逼近，亦或用一个变分不等式问题去刻画；同时，由于信息量的不断增多，问题的规模越来越庞大。因此，设计快速有效的数值算法是刻不容缓的，有着强大的现实意义。
　　本文针对凸规划和变分不等式问题提出了几种有效的数值方法，并成功应用到求解互补问题、图像恢复、广义Nash均衡问题及一类矩阵优化问题上。新方法同样能够轻松地应用于求解目前炙手可热的l1模优化等问题。
　　投影法是求解变分不等式问题中的方法中最简单的一种，尤其是当到可行集上的投影容易计算时，投影法更是简单有效。但是目前已有的投影法中，要么其收敛性条件苛刻；要么每步迭代需要通过线搜索找到一个合适的步长；而且这些方法都需要通过选择一些合适的参数来提高算法的效率。本文第3章首先给出一种改进的自适应投影法，新方法只需要在单调的假设条件下就能保证收敛性，相应的数值结果也表明改进的可行性和有效性。同时，为了克服前面所述的困难，又将BB步长推广到求解一般的变分不等式问题上，在较强的假设条件下证明了算法的收敛性。大量的数值试验表明，带BB步长的投影法有着非常好的数值表现；而且，该方法不需要调节额外的参数来提升计算效率。
　　在求解可分离结构变分不等式问题的所有方法中，交替方向法毫无疑问是最经典的一种。但交替方向法的每步迭代过程中都需要求解两个子变分不等式问题。该方法除了将原来一个大型的变分不等式分解成一系列低维的变分不等式问题逐一进行求解外，其每步迭代过程中仍然无法摆脱求解变分不等式问题的瓶颈。本文第4章首先提出一种混合算子分裂法，新方法用一个强单调的非线性方程组替换掉原交替方向法的一个子变分不等式问题，从而导致新的子问题在大部分情况下要容易求解得多：针对新方法的另外一个子问题是单调的，且只是在固定参数情况下得到其收敛性，又提出一种改进的混合分裂法。改进的方法中，在原来单调的变分不等式子问题上引入一个临近点项，使得变分不等式子问题也具有强单调性；同时，用可变参数矩阵替代原来的固定参数，为设计自适应的混合分裂法提供了理论基础。在比较宽松的条件下，分析了新方法的全局收敛性，而且初步的数值试验进一步说明了新算法的优势。
　　交替方向法是Douglas-Rachford分裂法应用于优化问题的对偶形式得来的，其在统计及图像处理等领域已经得到了很广泛的应用。事实上，交替方向法之所以在这些领域中有着漂亮的数值表现，是因为交替方向法的子问题都有解析解。但是，当这些问题还带有一个简单约束后，交替方向法的子问题并不一定会有显式解。因此，本文第5章针对带线性约束的可分离结构凸规划问题量身定制出了一系列Douglas-Rachford分裂法。这些方法是将最原始的Douglas-Rachford分裂法直接应用于优化问题的原问题上，然后结合问题的可分离结构所设计出的具有并行结构的算子分裂法。在比较宽松的假设条件下，证明了新方法的精确、非精确两种形式的全局收敛性。与传统的交替方向法相比，新方法有三点主要的优势：第一，新方法的子问题在大部分情况下比交替方向法的子问题要容易求解；换句话说，即使在交替方向法无法得到显式解的情况下，文中提出的新方法仍可能很容易得到子问题的解析解；第二，新算法的子问题是相互独立的，可以并行求解，这有利于求解具有可分离结构的大规模问题；第三，新算法可以很容易地推广到求解具有多个可分离结构的问题，而这些都是交替方向法无法拥有的。文中的数值试验进一步说明了新算法的独创性和有效性。

目录

文摘

英文文摘

Contents

表格列表

插图列表

第1章 绪论

1.1 问题描述

1.2 应用实例

1.3 算法简介

1.3.1 投影法

1.3.2 算子分裂法

第2章 预备知识

2.1 投影算子及其性质

2.2 相关定义

2.3 变分不等式的几种特殊情况

2.4 变分不等式的等价形式

第3章 投影法

3.1 引言

3.2 改进的自适应投影法

3.2.1 算法及收敛性

3.2.2 数值试验

3.3 带BB步长的投影法

3.3.1 收敛性分析

3.3.2 数值试验

3.4 小结

第4章 混合分裂法

4.1 引言

4.2 混合分裂法

4.2.1 算法及其主要性质

4.2.2 收敛性分析

4.2.3 数值试验

4.3 改进的混合分裂法

4.3.1 算法及其主要性质

4.3.2 收敛性分析

4.3.3 数值试验

4.4 小结

第5章 定制的Douglas-Rachford分裂法

5.1 引言

5.2 动机

5.3 定制的Douglas-Rachford分裂法

5.3.1 算法

5.3.2 收敛性

5.4 非精确定制的Douglas-Rachford分裂法

5.4.1 算法

5.4.2 收敛性

5.5 数值试验

5.5.1 合成算例

5.5.2 图像恢复

5.6 推广到求解多个可分结构的问题

5.7 小结

第6章 结论与展望

参考文献

攻读博士期间完成论文情况

致谢