解可分离凸优化问题的线性化交替方向法

摘要

凸优化和变分不等式问题是优化领域很常见的问题，它们的应用也非常广泛，不仅是研究数学、管理科学和工程科学的重要工具，而且在数学规划、交通管理、网络经济以及图像处理等方面也有着重要的应用.因此，设计有效的算法求解这些问题一直是优化领域的熟点。如今，求解凸优化和变分不等式问题有了很多可行的算法，其中带乘子的交替方向法(ADMM)是一种非常有效的算法.因此，针对本文研究的可分离结构的多块凸优化问题，He和Yuan在[26]中提出了一种逐块的交替方向法，此方法在子问题易求解时具有很好的数值效果.另外，线性化近似是一种使交替方向法子问题易求解的重要技巧，这一技巧在很多实际问题中都有重要应用.所以对于子问题不易求解的可分离凸优化问题，我们在[26]的基础上，提出了三种新的线性化近似的交替方向法来求解具有可分离结构的多块凸优化问题，并且将新算法应用到二次规划和图像处理问题。
　　本文提出了三种近似的交替方向法.第一种是对迭代子问题中的二次项进行线性化近似，第二种是对迭代子问题中的可微的目标函数进行线性化近似，第三种是同时对迭代子问题中的二次项和目标函数同时进行线性化近似，并且在较弱的条件下分析了三种算法的收敛性及第一种算法的收敛速度.新算法的主要优势在于可以使子问题拥有显式解，更易求解，这在很多实际问题的应用中有着重要意义。把提出的三种近似交替方向法应用到二次规划问题和图像分解问题，并与其它算法进行比较，验证了算法的可行性和优越性。

目录

声明

摘要

第一章 绪论

§1．1 问题描述

§1．2 应用背景

§1．3 基本知识

§1．4 求解可分离凸优化的交替方向法

§1．5 变分不等式的形式

§1．6 块矩阵的一些性质

§1．7 本文结构

第二章 算法及收敛性分析

§2．1 引言

§2．2 线性化版本A

§2．3 线性化版本B

§2．4 线性化版本C

第三章 数值实验

§3．1 二次规划问题

§3．2 图像分解问题

第四章 结论及展望

参考文献

致谢