arXiv:2511.22613math.OCcs.AI2025-11被引 1

建立低秩矩阵与张量的几何分析框架,揭示优化问题的极值点特性。

Variational analysis of determinantal varieties

  • 提出统一框架,计算低秩集合的一阶与二阶切集。
  • 证明低秩优化的二阶最优性验证是NP难问题。
  • 适用于矩阵、张量、对称阵等场景,适合优化理论研究者。

低秩矩阵与张量构成的行列式流形在低秩优化中日益受到关注。其切锥已被广泛研究,支撑多种几何方法;而二阶几何(包含曲率信息)更为复杂。本文构建统一框架,显式推导出低秩矩阵、张量、对称矩阵及半正定矩阵等各类低秩集合的一阶与二阶切集公式。该框架还可处理低秩集合与其他满足弱假设的集合的交集,从而得到切锥交集规则。基于切集视角,我们建立了非光滑问题与其光滑参数化共享二阶驻点的充要条件。进一步利用切集刻画低秩优化的最优性条件,并证明验证二阶最优性为NP-hard。另通过分析矩阵流形法锥图的变分几何,显式求解了Bouligand切锥、Fréchet与Mordukhovich法锥。这些结果被用于建立低秩双层规划的最优性条件。

原文摘要 · Abstract (English)

Determinantal varieties -- the sets of bounded-rank matrices or tensors -- have attracted growing interest in low-rank optimization. The tangent cone to low-rank sets is widely studied and underpins a range of geometric methods. The second-order geometry, which encodes curvature information, is more intricate. In this work, we develop a unified framework to derive explicit formulas for both first- and second-order tangent sets to various low-rank sets, including low-rank matrices, tensors, symmetric matrices, and positive semidefinite matrices. The framework also accommodates the intersection of a low-rank set and another set satisfying mild assumptions, thereby yielding a tangent intersection rule. Through the lens of tangent sets, we establish a necessary and sufficient condition under which a nonsmooth problem and its smooth parameterization share equivalent second-order stationary points. Moreover, we exploit tangent sets to characterize optimality conditions for low-rank optimization and prove that verifying second-order optimality is NP-hard. In a separate line of analysis, we investigate variational geometry of the graph of the normal cone to matrix varieties, deriving the explicit Bouligand tangent cone, Fréchet and Mordukhovich normal cones to the graph. These results are further applied to develop optimality conditions for low-rank bilevel programs.

低秩优化变分几何切锥NP难

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。