非凸优化问题的Barzilai-Borwein类算法的理论与应用研究

Barzilai-Borwein (BB)-like methods enjoy properties such as low-memory cost, high efficiency, and nonmonotone reduction. For nonconvex problems, the BB-like stepsize will possibly become negative which may significantly deteriorate the performance of the algorithm. For large-scale problems, the nonmonotone iterations may increase the cost of the algorithm. Currently, most of the existing works on the convergence of the BB-like methods focus on convex problems. The available BB-like methods for nonconvex problems are only guaranteed to be global convergent without any analysis on the convergence rate. Based on the existing results, this project attempts to develop fast BB-like methods for nonconvex optimization problems. The convergence theories as well as applications in some practical problems will also be studied. The proposed methods should avoid the deterioration caused by negative stepsizes and decrease the unnecessary nonmonotone iterations as many as possible. It is expected that, by implementing this project, we have new gains in the theory and applications on BB-like methods for nonconvex optimization problems.

Barzilai-Borwein（BB）类算法具有内存占用少、计算效率高以及非单调性等特点。对于非凸优化问题，BB类步长容易出现负值，这会对算法的计算效率产生很大的负面影响。当问题规模较大时，非单调的迭代步可能会增加算法的整体开销。目前文献中大部分BB类算法的收敛性分析都是针对凸优化问题，现有的非凸优化问题的BB类算法仅有全局收敛结果，缺少收敛速度的相关结论。本项目旨在已有成果的基础上，研究求解非凸优化问题的高效BB类算法，分析其收敛性理论，并探讨其在实际问题中的应用。所提算法应避免步长出现负值对效率的影响，减少不必要的非单调迭代步。我们希望通过本项目的研究，能够进一步改善BB类算法求解非凸优化问题的能力，在BB类算法的理论和应用方面取得新的进展。

Barzilai-Borwein（BB）算法是求解大规模无约束优化问题的一种重要方法，现已广泛应用于机器学习、无线通信和图像处理等领域。本项目在已有成果的基础上，重点研究BB类算法及其应用，取得了如下成果：1、提出一簇以两个经典BB步长的凸组合构成的新步长，并发展出一簇新的BB类算法；从谱性质和二维二次终止性质的角度研究BB类算法的加速技术，开发了多个无约束优化问题的BB类算法，将所提算法推广用于求解盒子约束优化问题，分析了其收敛性理论。2、针对机器学习中的经验风险极小化问题，基于目标函数是多个函数求和的结构，结合信赖域策略，提出了两种方差下降的随机BB类算法，并建立其收敛性理论。3、针对非负矩阵分解和一类正交约束优化问题，根据其结构特点，分别提出了自适应单调投影BB算法和交替梯度法。此外，我们还针对一类多商品设施选址问题和热油输运问题，分别提出基于线性松弛解的启发式方法和基于凸松弛的分支定界算法。数值测试和对比表明，我们提出的算法在迭代次数和CPU时间方面具有优势。