非对称临近点算法的理论和应用研究

Proximal Point Algorithm (PPA for short) is one of the most classical algorithms for solving problems such as optimization problems, variational inequality problems, or inclusion problems, etc. It attracts a wide range of attention, and has obtained great progress since its appearance. This project aims to extend the PPA by relaxing its proximal term with a nonsymmetric one. The corresponding basic theory, algorithm design and applications to some optimization problems with special structures will be investigated in detail. First, this project will establish the framework of basic theory for the extended algorithm, which includes theoretical proof of the global convergence under reasonable conditions, analysis of the computational complexity and derivation of the convergence rate. Second, based on flexibility of the extended algorithm, some new decomposition algorithms will be customized to solve the optimization problems with special structures, e.g., the separable convex optimization problems with linear constraints arising in practical models. Furthermore, to make the extended algorithm more practical, inexact versions of the algorithms adopting some relaxing and practical accuracy criteria will be introduced, which will not only make the subproblems easy, but also reduce the cost of every iterate. Third, applications of the new designed algorithm to the traffic assignment problem, oligopolistic competition problems and image decomposition will be studied. This project can provide some new ideas for solving the popular problems in mathematical programming such as convex separable optimization problems with more than three blocks, and some new efficient numerical algorithms for some problems in practical applications.

临近点算法是一类非常经典的求解优化问题、变分不等式问题、包含问题的算法，自其出现以来一直受到广泛的重视，已经取得了非常重要的进展。本项目拟将经典临近点算法中的临近点项推广到非对称的形式，研究其基础理论、算法设计以及在特殊结构问题上的应用。首先，从理论上证明非对称临近点算法的全局收敛性，分析其计算复杂性以及收敛速度。其次，利用推广后算法的灵活性，为一些特定结构的优化问题（如带有线性约束的可分凸规划问题等）量身定制一些分解算法。同时，为使算法更加实用，引入宽松、实用的非精确准则，使得子问题容易求解，从而降低每步迭代的计算量。最后，将算法应用到交通规划中的流量分配、寡头竞争和图像处理等问题中。本项目的研究结果将为当前优化领域中的一些热点问题（如多块可分凸规划）的研究提供新的思路，为一些实际应用问题提供更有效的求解方法。

针对大规模稀疏优化中的可以写成多个可分算子的模型，本研究旨在设计一些高效的，子问题求解简单的分解算法和临近算法，并研究其复杂性和收敛速度。.算法设计方面：.利用有限记忆，通过构造新的下降方向，为变分不等式问题设计的新的投影类算法。该算法可以看出是共轭梯度法的一种推广，它每次不仅仅利用当前迭代点梯度信息，还要考虑之前 步的梯度信息。数值实验表明，新的算法较原有的投影梯度法有显著的改善;对三块可分凸优化问题直接推广交替方向法的收敛性进行分析。若没有强凸条件，直接推广的交替方向法不收敛，我们最近给出了交替方向法收敛的一个充分条件，即当函数中有一个是强凸的。这是迄今为止最好的条件;我们又提出一个线性化的块交替方向法，即非精确求解每一个子问题，得到一个预测点，再进行校正，算法能够使子问题非常容易求解，计算效率得到提高;对两块的可分凸优化问题，提出一个新的临近交替方向法，使得子问题容易求解，并能达到O(1/t)计算复杂度;提出一类非线性的PPA算法，这样的邻近点算法中的非线性临近项不要求是一个函数的梯度，使得算法有更好的适应度，可以根据问题的结构选取合适的临近项，我们还提出了一个非精确的版本;向前向后分裂算法中的参数大小直接影响算法的效率，我们增加一个简单的松弛步，使得原来的算法的参数可以扩大一倍，并提出了这个算法的不精确版本，在一定的条件下，算法是线性收敛的。.算法的应用研究：大规模稀疏优化问题在统计，图像处理等方面有很广泛的应用，目前交替方向法是一个非常有效的算法。我们对统计中的Dantzig Selector问题利用交替方向法求解，使子问题求解非常容易，问题求解规模大；并对优化问题中常见的基本问题，点在椭球上的投影，通过引入一个变量，变成一个可分的凸优化问题，用交替方向法求解可以得到线性收敛率。