一类非光滑DC优化问题Frank-Wolfe算法的研究

DC optimization problems has important applications in compressed sensing, image joint denoising and polishing, digital communication systems, and network allocation, and has become a hot issue in the field of optimization. Previous DC optimization algorithms need to assume that a proximity operator or projection is easy to calculate, but in some practical cases, it is not easy to satisfy, so this project considers its Non-Projection algorithm--Frank-Wolfe algorithm. Frank-Wolfe method, as a kind of non-projective algorithm, has been extensively studied in convex optimization. The research of Frank-Wolfe algorithm for non-convex optimization problems has just started. So far, only its global convergence has been discussed, and the convergence speed has not been related. Furthermore, the Frank-Wolfe algorithm for non-convex and non-smooth DC optimization problems has not yet begun. This project mainly studies: 1. Designing Frank-Wolfe algorithm for solving non-smooth DC optimization problems, and discussing its global convergence; 2. Discussing the convergence speed of the algorithm; 3. Constructing the Non-Projection algorithm of variational inequalities by using the idea of Frank-Wolfe method.

DC优化问题在压缩感知、图像的联合去噪磨光、数字通信系统、以及网络分配等问题中都有重要的应用，已经成为优化领域的一个热点问题。求解DC优化问题的现有算法基本都基于临近算子或投影算子容易计算的假设，但在有些实际情况中，其并不容易满足，因此本项目考虑其无投影型算法--Frank-Wolfe算法。Frank-Wolfe方法作为一类非投影型算法，在凸优化中得到了广泛的研究，而非凸优化问题的Frank-Wolfe算法研究才刚刚起步，到目前为止，仅讨论了其全局收敛性，收敛速度还没有相关结果。更进一步的，针对非光滑的DC优化问题的Frank-Wolfe算法研究还没有开始。本项目主要研究：1、设计求解非光滑的DC优化问题的Frank-Wolfe算法，并讨论其全局收敛性；2、讨论该算法的收敛速度；3、利用Frank-Wolfe方法的思想，构建变分不等式的非投影型算法。

带约束的非光滑DC优化问题在压缩感知、图像的联合去噪、数字通信系统以及网络分配等问题中有重要的应用价值。而由于其非凸非光滑的特点，直接求解比较困难。本项目首先研究了一类带DC约束的非凸非光滑优化问题，通过定义一类新的广义Linear-optimization Oracles对DC约束和目标函数分别进行线性近似，构建了该类优化问题的FW型算法，并证明了算法的收敛性。其次研究了一类具有光滑约束的DC优化问题，为了保证算法的可行性，通过引入“回撤步”，构建了该类问题的FPA算法（First-order Polyhedral approximation），并通过KL指数分析了该算法的收敛率。最后针对变分不等式，当向可行集投影容易计算时，设计了一类新的次梯度外梯度投影算法，同时首次提出了映射是连续时的加速双投影算法。当向可行集投影不容易计算时，通过利用向球投影来代替直接向可行集投影，得到了针对伪单调变分不等式的松弛投影算法。该算法是可行性算法，并且不需要假设已有松弛投影算法的额外边界条件。经过三年执行期的建设，在国际国内学术期刊上发表论文3篇，培养研究生12名。此外，我们积极开展同国内外同行的合作交流，项目负责人克服新冠疫情影响，于2020年7月赴香港理工大学进行为期1年的学术交流访问，同时项目组成员积极参加国内外相关的学术交流活动。除了受疫情等因素影响的部分研究内容没有获得期待的结果外，我们已完成了既定的研究任务。