互补锥优化问题的基本理论研究

Cone programming is a new research branch in optimization fields. At present, the research on this topic is mainly focusing on convex cone. It is undoubtedly an important step from convex cone to nonconvex cone. In this project, we will study a special structural nonconvex cone, called complementarity cone, and the associated complementarity cone programming (CCP). (1) CCP is closely related to a series of well-known optimization problems, for instance, sparse optimization, low-rank matrix optimization, bilevel programming, etc. In fact, CCP shows that there is internal and common theoretical basis between these different types of problems. Meanwhile, CCP has a wide range of applications in modern electricity market, transportation network design, etc. (2) The research on CCP belongs to the field of second-order variational analysis, which is a frontier research topic in mathematical programming. Hence the study of CCP is strongly desired due to its applicable value and many challenging difficulties in theoretical analysis. In this project, by employing some advanced optimization theory and tools, such as variational analysis and perturbation analysis, together with the special structure of complementarity cone, we study the CCP from the following aspects: the variational geometry of complementarity cone, first-order and second-order optimality conditions, stability analysis of constraint systems, augmented Lagrangian duality and multiplier methods. The essential extension from convex to nonconvex will produce new theories and methods, expand the research fields of cone programming, enrich the nonconvex and nonsmooth optimization theoretical system, and provide the basis for the real-world applications.

锥优化是最优化学科中一个新的研究分支，研究重心主要集中在凸锥优化。从凸锥到非凸锥无疑是重要的一步。本项目将研究一类具有特殊结构的非凸锥及其优化问题，即互补锥与互补锥优化。(1)它与稀疏优化、低秩矩阵优化、双层规划等问题有着密切联系，揭示出上述不同类型问题之间存在内在相通、彼此关联的理论基础，并在电力市场、交通网络设计等领域有着广泛应用。(2)对互补锥的研究属于二阶变分分析的范畴，具有较大的挑战性。因此对互补锥优化问题的研究兼顾理论难度与应用价值。本项目将利用变分分析、扰动分析等现代分析工具，并结合互补锥的特殊结构，系统研究互补锥优化问题的最优性与对偶理论，具体内容包括：互补锥的几何特征与变分性质、一阶与二阶最优性条件、约束系统的稳定性分析、增广Lagrangian对偶理论与乘子方法等。从凸到非凸必将产生新的理论和方法，拓展锥优化的研究范围，丰富非凸、非光滑优化理论，并为实际应用提供基础支撑。

本项目系统研究了互补锥优化的基本理论，涉及互补锥的变分几何性质、二阶最优性条件、互补系统的稳定性分析、误差界的刻画、近似算法等。由于稀疏优化是一类特殊的互补锥优化，我们还对稀疏优化、0/1损失优化建立了二阶算法。主要结果有：.i) 二阶切集的结构表达式，这是首次对非凸非多面体集建立二阶切集的具体结构表达式。.ii) sigma-term: 对互补锥给出sigma-term的结构式，它反映了互补锥的曲率；利用sigma-term，建立互补锥优化的二阶最优性条件。.iii) 建立方向法锥的结构式，由此建立互补系统具有稳定性、误差界或者度量次正则性质的可验证的充分性条件；引入方向Frechet切锥，证明它是方向法锥的极锥，且二阶切集相对于方向Frechet切锥具有平移不变性。这在研究二阶约束规范中起着重要作用。.iv) 引入hat-sigma-term，我们在度量次正则的条件下，建立了一般非凸集合约束优化的二阶最优性条件。这是从特殊到一般，逐步提升认知的探索过程。.v) 利用Jordan代数，给出互补锥优化问题一类新的等价转化形式。证明S稳定点正好对应新的转化形式的KKT条件；基于新的转化形式，构造光滑逼近算法，讨论逼近问题与原问题在约束规范之间的关系，并对算法进行收敛性分析。.vi) 对稀疏优化、0/1损失优化，结合子空间截取和传统的Newton方法，设计二阶算法。. 上述结果，特别是新的研究工具的引入，进一步丰富了变分分析的理论体系，尤其是二阶变分分析这一新的理论前沿课题。