大规模非凸优化问题的分裂算法及应用

With the development of information technology and internet industry, the total amount of data in the world has exploded. The number of decision-making variables and constraints of the optimization problem becomes more and more large, and the research of optimization problems gradually enters the large-scale era. For large-scale optimization problems, the classical optimization algorithms such as the Newton method can not be directly applied due to the huge amount of computation at each step. As the computational complexity of each step is relatively small and can take full advantage of the structure of the problem, the splitting algorithm is favored by the majority of optimization scholars. This project intends to: (1) Focus on the design and application of the splitting algorithm for large-scale non-convex optimization problems, so that the algorithm can make full use of the structure of the problem to quickly obtain the solution of the problem, and analyze the convergence and stability of the algorithm. KL inequality convergence speed. 2) By using the structure of complementary cone, the algorithm is applied to solve QPEC and MPEC problems, and the convergence and convergence rate are analyzed. 3) Numerical experiments are carried out on the above algorithms and applied to securities investment portfolio, electric vehicle charging and other issues, and the preparation of effective optimization software package. The implementation of this project can not only provide new algorithms and theories for solving large-scale non-convex optimization problems, but also provide some support for the cross-integration of data science, management science and optimization theory.

随着信息技术和互联网行业的发展，全世界的数据总量呈爆发式增长，最优化问题的决策变量与约束条件的数目变得愈加庞大，优化问题的研究逐渐进入大规模时代。对于大规模优化问题, Newton法等经典的优化算法由于每一步计算量巨大，无法被直接应用。分裂算法由于每一步的计算量相对较小且能充分利用问题的结构，受到广大优化学者的青睐。本项目拟：1）重点研究大规模非凸优化问题的分裂算法设计及应用，使算法能够充分的利用问题的结构快速获得问题的解，并分析算法的收敛性、稳定性, 利用K-L不等式估计收敛速度。2）利用互补锥的结构，将算法应用于求解QPEC和MPEC问题，分析收敛性与收敛速度。3）对上述算法进行数值实验并将其应用在证券投资组合、电动汽车充电等问题中，并编制有效的优化软件包。该项目的实施不仅能为求解大规模非凸优化问题提供新的算法与理论，也可为数据科学、管理科学、最优化理论的交叉融合提供一定的支持。

随着人类进入数智化时代，决策问题的复杂性和规模大幅增加，优化研究进入大规模时代。本项目旨在研究大规模非凸优化分裂算法的理论与应用，取得了一系列研究成果：1）针对典型的线性等式约束非凸优化问题，建立了交替方向乘子法的新收敛结果，并且在收敛性条件不满足时，提出其收敛变形；2）对于一般的MPEC和QPEC问题，分别提出了嵌入块坐标下降类和交替方向乘子类算法的增广拉格朗日乘子方法，算法能收敛到M稳定点，如进一步假设MPEC-MFCQ条件和算法参数的某些条件，解序列收敛到S稳定点；3）算法应用于稀疏投资组合、产品需求估计、正则化MDP和鲁棒机器学习模型中，提高决策精度。应用产生鲁棒机器学习算软件包1项，公开发表在Github。.项目组共发表国内外知名期刊或会议论文10篇，包括1篇优化领域顶级期刊SIAM Journal on Optimization, 3篇人工智能顶级期刊或会议IEEE Trans. Neural Netw. Learn. Syst.、CVPR2020和NeruIPS2020，成果得到了包括德国国家科学院院士、ACM会士Bernhard Scholkopf教授的引用，先后获得2019年江苏省社科优青、2019年南京大学青年五四奖章、2020年江苏省工业与应用数学学会青年奖等奖励。项目执行期内，2人获批国家自然科学基金优秀青年项目，1人职称晋升为教授，1人晋升为副教授，已培养或正在培养博士生4人，已培养或正在培养硕士生25人。项目有效的推进了大规模非凸优化的算法研究，培养了大量的相关人才。