Barzilai-Borwein类方法研究及其应用

The Barzilai-Borwein-like (BB-like) methods are one of the very efficient methods for solving the large scale optimization problems. The study of this project is mainly based on the BB-like methods. The main targets are as follows: (1) We shall investigate the convergence analysis of a new kind of BB-like method for solving symmetric but non-positive definite linear systems. Settling this issue is very difficult and shall help us to understand the efficiency of BB-like methods deeply. (2) We shall study the efficient way to improve the numerical performance of the augmented Lagrangian method or the alternating direction method of multipliers (ADMM) by using the idea of BB-like methods; this will be our key goal. (3) By using the above results, we shall design the efficient algorithms to solve two special but significant optimization problems with orthogonality constraints, namely, the quadratic assignment problem and the nearest low rank correlation matrix problem. Overall, this project will investigate the BB-like methods and ADMM, which are two fundamental algorithms in optimization, in the aspects of theory and algorithm design. This shows that our project will be of great value on theory. Moreover, this project is also important practically by designing efficient and fast algorithms for solving some special optimization problems with realistic background.

Barzilai-Borwein（BB）类方法是求解大规模优化问题十分有效的方法之一。本项目将以BB类方法为出发点开展相关研究。主要研究内容为：（1）我们将着重研究一类新的BB类方法求解对称非正定线性方程组的收敛性问题，解决该问题具有一定的难度且可以进一步加深我们对BB类方法有效性的理解；（2）我们将研究如何有效地结合BB类方法的思想来提高增广Lagrangian方法和交替方向法的数值表现，这部分是项目的重点研究内容；（3）基于以上的研究结果, 我们将设计有效的算法求解两类特殊且十分重要的正交约束优化问题，即二次指派问题以及最优低秩相关系数矩阵问题。本项目在理论和算法方面对BB类方法和交替方向法这两类重要的算法进行研究，因此具有重要的理论价值。此外，本项目还针对具有实际背景的特殊优化问题研制更加快速有效的算法，所以也具有一定的应用价值。

本项目研究了两个问题。第一个是置换矩阵集合上优化问题，该问题在芯片设计、模式识别、计算机视觉、图匹配等领域有着广泛的应用。我们首先提出了与该问题等价的Lp正则化模型，继而提出了Lp正则化方法，其中我们发展了一些新的技巧如负临近点技巧来改进相应算法的表现。相关成果发表在SIAM Journal on Optimization。第二个问题是对于无监督学习的特征选择问题，我们提出了一类新的基于滤子的特征选择方法，相关成果发表在IEEE Transactions on Image Processing。