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

发布时间：2018-04-30 20:16

本文选题：变分不等式 + LQP算法　；参考：《重庆大学》2016年硕士论文

【摘要】：变分不等式有着广泛的应用背景,它是最优化领域一类非常重要的研究工具。图像恢复、信号处理、管理科学、统计计算、矩阵完整化、机器学习等信息技术领域中存在的大量凸优化问题,均可以转换成变分不等式问题来求解。在变分不等式这一统一框架下研究凸优化问题的求解方法,常常会带来很大的方便。可分离结构型变分不等式是变分不等式的特殊形式,而LQP交替方向法是求解该类变分不等式的有效算法,该方法是原始交替方向法的一种改进算法,它不仅充分利用原问题的可分离性,将原问题分裂为两个较低维子问题,而且通过引入LQP正则项,将子问题转化为两个更容易求解的非线性方程组,打破了原始交替方向法中必须求解两个单调变分子问题的瓶颈。本文对LQP交替方向法及其改进算法做了进一步的探索。主要成果有以下两个方面:(1)构造一个新的下降方向,从而提出一种新的下降型LQP交替方向法。在算法分析的过程中给出了最优步长的选取方式,并在较弱的假设条件下证明了算法全局收敛性。最后数值实验结果显示新算法是可行的。(2)结合广义交替方向法提出了一种非精确型LQP广义交替方向法,其迭代格式只需要求解两个子问题的近似解而非精确解。在选取适当非精确准则的条件下证明了算法的全局收敛性,最后给出了新算法在遍历意义下和非遍历意义下O(1/t)的收敛率分析,从而说明算法的有效性。
[Abstract]:Variational inequality has a wide application background, it is a very important research tool in the field of optimization. A large number of convex optimization problems in information technology such as image recovery, signal processing, management science, statistical computation, matrix integrity, machine learning and so on, can be transformed into variational inequality problems. It is very convenient to study the solution of convex optimization problems under the unified framework of variational inequalities. The separable structural variational inequality is a special form of variational inequality, and the LQP alternating direction method is an effective algorithm for solving this kind of variational inequality. This method is an improved algorithm of the original alternative direction method. It not only makes full use of the separability of the original problem and splits the original problem into two lower dimensional subproblems, but also transforms the subproblem into two more easily solved nonlinear equations by introducing the LQP regular term. It breaks the bottleneck of two monotonic molecular problems which must be solved in the original alternating direction method. In this paper, the LQP alternating direction method and its improved algorithm are further explored. The main results are as follows: 1) A new descent direction is constructed, and a new descending LQP alternating direction method is proposed. In the process of algorithm analysis, the selection of optimal step size is given, and the global convergence of the algorithm is proved under the condition of weak assumption. Finally, the numerical results show that the new algorithm is feasible. (2) an inexact LQP generalized alternating direction method is proposed in combination with the generalized alternating direction method. The iterative scheme only needs to solve the approximate solution of the two sub-problems rather than the exact solution. The global convergence of the algorithm is proved under the condition of selecting appropriate inexact criteria. Finally, the convergence rate analysis of the new algorithm in the sense of ergodic and non-ergodic is given, which shows the validity of the algorithm.
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O178

【参考文献】