多凸规划目标罚函数的精确性理论与算法研究

Multi-convex programming is an NP-hard non-convex optimization problem shown itself in the areas of today’s controlling, machine learning, signaling, communication and etc. Current researches mainly cover some special multi-convex programming, so there is a lack of systematic study on solution theories and algorithms of genetic multi-convex programming. Our study takes multi-linear programming, multi-convex quadratic programming and genetic multi-convex programming, as our research objectives, and is to systematically study the theories and algorithms of their penalty functions. In terms of theories, we are to study the sufficient conditions and necessary conditions of the exactness, determination of their optimality, the determination of their penalty function exactness structure, smoothing of non-smooth objective penalty functions and the estimation of error bounds. In terms of algorithms, we are to study approximation algorithm of alternation sub-problems as well as the convergence analysis, and are to conduct corresponding numerical experiments and study the algorithms’ stability of and sensitiveness. In conclusion, our research is to systematically study the theories and algorithms of exact objective penalty functions for multi-convex programming so as to provide practical tools for the multi-convex programming in the real world.

多凸规划是当今在控制、机器学习、信号处理和通信等领域中出现的一类非凸优化NP-hard问题，已有的研究主要是解决一些特殊多凸规划，对于一般多凸规划求解理论与算法缺少系统的研究。本项目以多线性规划、多凸二次规划和一般多凸规划为研究对象，将系统地研究它们的目标罚函数精确性理论与算法，在理论上：研究其精确性充分必要条件、最优性判定、目标罚函数精确结构判定、非光滑目标罚函数进行光滑化与误差界估计等，在算法上：研究交替子问题逼近算法和收敛性分析，并做相应的数值实验、研究算法稳定性和灵敏度分析等问题。本项目将系统地发展多凸规划的目标罚函数精确性理论和算法，为解决实际问题中多凸规划提供理论工具和方法。

本项目从2018年9月开始到2022年12月，共完成学术论文21篇，其中11篇已经在国内外学术期刊及会议上（或在线）发表，10篇论文在评审或投稿中（其中2篇在学术平台arXiv上展示）。项目成果主要包括三个方面的研究：双凸规划与多凸规划的罚函数精确性理论与算法、可转换非凸函数优化理论与算法和罚函数方法在供应链与图像处理算法中应用。.（1）在双凸与多凸规划方面，首次提出双凸与多凸规划的部分KKT条件、部分精确性和部分稳定性等概念，这些概念是刻画双凸（多凸）规划部分最优解之间的关键，并证明了双凸（多凸）规划的精确性等价定理和光滑化部分精确性的误差界估计，这些结果是判定它们部分最优解之间的不可缺少的条件，提出了求解双凸规划的罚函数和目标罚函数算法，数值实验表明算法有效性，以上成果丰富和发展了多凸规划的理论和算法。.（2）在拓宽多凸规划研究途径方面，我们发展了解决非凸非光滑优化新理论和方法，首次提出了一类新的非凸非光滑函数-称之为可转换非凸函数（简称为CN或SCN函数），经过研究获得了许多重要成果，如CN或SCN函数构成优化的最优性条件和对偶理论，提出了增广拉格朗日罚函数算法和分解算法，在使用SCN函数变换研究了稀疏高维特征向量提取模型和稀疏支持向量机发分类模型，分别提出了相应的算法，数值实验结果表明，提出的算法不仅在稀疏性和精度上都要比传统的算法要好。以上研究初步表明CN（SCN）函数构成的优化对于解决非凸非光滑问题和多凸规划具有重要的作用。.（3）在应用方面，将（目标）罚函数算法用于供应链和图象处理等领域中的数学模型求解，如在机器学习模型中的损失函数优化中采用了光滑化罚函数方法解决，数值结果表明了罚函数方法对于提高求解精度，降低求解困难具有重要作用。. 总之，本项目对双凸与多凸规划和CN（SCN）优化理论和算法做了较为深入的研究，特别是在目标罚函数的最优性条件、精确性和稳定性，以及算法方面我们都获得了许多新的成果，为进一步研究非凸非光滑优化和多凸规划提供了新的研究思路和基础。