解可分离结构型变分不等式的LQP交替方向法

摘要

变分不等式有着广泛的应用背景，它是最优化领域一类非常重要的研究工具。图像恢复、信号处理、管理科学、统计计算、矩阵完整化、机器学习等信息技术领域中存在的大量凸优化问题，均可以转换成变分不等式问题来求解。在变分不等式这一统一框架下研究凸优化问题的求解方法，常常会带来很大的方便。
　　可分离结构型变分不等式是变分不等式的特殊形式，而LQP交替方向法是求解该类变分不等式的有效算法，该方法是原始交替方向法的一种改进算法，它不仅充分利用原问题的可分离性，将原问题分裂为两个较低维子问题，而且通过引入LQP正则项，将子问题转化为两个更容易求解的非线性方程组，打破了原始交替方向法中必须求解两个单调变分子问题的瓶颈。
　　本文对LQP交替方向法及其改进算法做了进一步的探索。主要成果有以下两个方面：
　　①构造一个新的下降方向，从而提出一种新的下降型LQP交替方向法。在算法分析的过程中给出了最优步长的选取方式，并在较弱的假设条件下证明了算法全局收敛性。最后数值实验结果显示新算法是可行的。
　　②结合广义交替方向法提出了一种非精确型LQP广义交替方向法，其迭代格式只需要求解两个子问题的近似解而非精确解。在选取适当非精确准则的条件下证明了算法的全局收敛性，最后给出了新算法在遍历意义下和非遍历意义下O(1/t)的收敛率分析，从而说明算法的有效性。

目录

封面

中文摘要

英文摘要

目录

1 绪 论

1.1 变分不等式的概述

1.2 求解变分不等式问题的两种经典算法

1.3 解结构型单调变分不等式的交替方向法概述

1.4 本文的主要工作

2 预备知识

3 新的下降型LQP交替方向法

3.1 引言

3.2 算法及全局收敛性

3.3 算法比较

3.4 数值实验

3.5 本章小结

4 一种非精确型LQP广义交替方向法

4.1 引言

4.2 算法及全局收敛性

4.3 算法的收敛率分析

4.3.1 遍历意义下算法的收敛率分析

4.3.2 非遍历意义下算法的收敛率分析

4.4 本章小结

5 总结与展望

致谢

参考文献

附录

A. 作者在攻读硕士学位期间发表的论文目录