非对称锥优化理论与内点算法及其应用研究

Nonsymmetric conic optimization problems are an important class of optimization problems in which the decision variables belong to the intersection of a non-self-dual cone and an affine space while the objective function is linear of form. Nonsymmetric conic optimization is a powerful tool for modeling nonconvex quadratic problems and combinatorial NP-hard problems. It also has wide applications for sloving real-world problems, such as modeling and computing in data mining and image processing. Although nonsymmetric conic programming problems share the same form as the symmetric conic optimization problems, there exists fundamental difference in the underlying cone structure. For nonsymmetric conic optimization, the challenge and difficulty are encountered by the structure of non-self-dual cone. It is well known that deciding an element belongs a copositive cone or not is NP-complete problem. This project aims to study the theory and methods for nonsymmetric conic optimization and to establish the framework for developing interior-point methods. We first analyze the structure for several non-self-dual cones, such as the p-th order cone, copositive cone and completely positive cone. Then we will identify those computable cones to approximate or represent a nonsymmetric cone. A corresponding algebraic system and marix inequalities are developed to represent and study the analytical properties of non-self-dual cones. Moreover, we will construct a self-concordant barrier function (SCBF) for the nonsymmetric cones. Furthermore, based on SCBF, we will establish a framework of primal-dual interior-point methods and analyze related convergence and efficiency. Finally, we will apply the theory and algorithms of nonsymmetric conic optimization to data mining and image peocessing. In particular, we will focus on modeling of machine learning and sparse representation problems of image proceesing. The goal of our project is to overcome the comuting difficulty of non-self-dual cones. The output of our research will enrich and broaden the theory and applications of nonsymmetric conic optimization.

非对称锥优化是决策变量取自非自对偶凸锥与仿射集的交，而目标是线性函数的一类优化模型。这类优化模型是表示非凸二次规划和组合优化难问题的有力工具。被广泛应用于数据挖掘和图像处理等实际问题。非对称锥优化形式上保存了对称锥优化的特点，但本质上，由于约束锥的非自对偶性，直接导致了理论研究和算法设计的难度。本项目旨在系统研究非对称锥优化的理论与内点算法及其应用。针对几类非对称锥，分析其结构，利用已知对称性和结构的凸锥来逼近或表示它们；建立代数系统来刻画锥所诱导的矩阵不等式；建立定义在锥内部的自协调障碍函数，估计障碍参数与维数的关系；设计基于自协调障碍函数的原始或对偶障碍内点算法；分析算法的收敛性和有效性。应用上，将非对称锥优化应用于数据挖掘和图像处理的建模与算法中，特别为分类问题提供可计算的锥优化模型和最佳分类机。本项目的研究目标是突破约束锥在非自对偶的情形下带来的困难，丰富和发展锥优化理论与方法。

本项目主要探索和研究非对称锥优化的理论与内点算法及其应用。众所周知，非对称锥优化是决策变量取自不自对偶的凸锥与仿射空间的交集和目标函数是线性函数的一类优化模型。这类优化模型是表示非凸二次规划和组合优化NP难问题的有力工具，被广泛应用于数据挖掘、机器学习中的分类模型、图像处理、稀疏优化等实际问题。本项目系统与具体开展了五个方面的研究内容:1.关于非对称旋转锥优化模型与内点算法。2. 锥优化模型与有效算法在机器学习中分类问题的应用。3.高次非齐次多项式和复数多项式优化问题的近似算法。4.稀疏约束和半连续约束优化问题的分裂拉格朗日方法。5.关于带有敏感参数的投资组合问题的模型与算法及其应用。在五个研究方向中，项目分别做出一系列具有一定创新性和先进性的研究工作，取得了丰富的研究结果。比如发展了非对称协正锥、非对称旋转锥的代数表达理论和自协调函数理论，设计了非对称旋转锥的具有多项式时间的内点算法；分别为机器学习中分类问题和回归问题构建锥优化模型；并设计一阶与内点算法等快速算法求解实际的分类问题和回归问题；分析了四阶张量锥性质及希尔伯特恒等式分解；推广了张量Tucker分解最优核选择及其应用；设计了求解稀疏约束和半连续约束优化问题的分裂拉格朗日方法，在图像处理高维数据的应用中具有显著的效果。在应用方面，对于实际疾病分类问题，选取了国际通用数据库(UCI Repository) 的实际算例进行了数值试验. 数值结果分别表明，研究工作提供的优化模型与算法具有好的分类和聚类效果。.本项目五个研究方向的先进性、研究内容的创新性以及研究结果的前沿性与丰富性，项目的研究工作产生的影响力体现在丰富和发展了锥优化的理论与算法。项目的研究成果以论文的形式体现，总共发表了28篇期刊论文，其中4篇文章发表在最优化领域顶级期刊Mathematics of Operations Research；计算数学的顶级期刊Foundations of Computational Mathematics和Mathematics of Computation和国际信号处理顶级期刊IEEE Transactions on Automatic Control.在项目的支持下，培养了运筹学与控制论专业的8名博士研究生和9名硕士研究生。