提出高效求解非负正交约束优化问题的新算法，计算快且保证解的可行性。
A Support-Set Algorithm for Optimization Problems with Nonnegative and Orthogonal Constraints
- 通过固定支撑集，闭式求解子问题，最多保留n个非零项。
- 算法在ε精度下收敛，迭代复杂度为O(ε⁻²)，实测效率显著提升。
- 适用于非负PCA、聚类、社区发现等实际场景，适合追求高效精确解的研究者。
本文研究具有非负和正交约束的优化问题，其中任意n×p可行矩阵的稀疏结构满足每行至多一个非零元素。分析表明，在固定支撑集的前提下，目标函数近似线性化后的最小化子问题可闭式求解，且解中非零项不超过n个。利用此结构性质，可大幅提高计算效率。基于此，我们提出一种保持迭代解严格可行的支持集算法，核心是设计合理的支撑集更新机制以调整非零元素位置。我们证明该算法收敛至一阶驻点，达到ε-近似一阶驻点所需的迭代复杂度为O(ε⁻²)。数值实验在非负主成分分析（nonnegative PCA）、聚类与社区检测等真实应用中均验证了该算法的优越性。
原文摘要 · Abstract (English)
In this paper, we investigate optimization problems with nonnegative and orthogonal constraints, where any feasible matrix of size $n \times p$ exhibits a sparsity pattern such that each row accommodates at most one nonzero entry. Our analysis demonstrates that, by fixing the support set, the global solution of the minimization subproblem for the proximal linearization of the objective function can be computed in closed form with at most $n$ nonzero entries. Exploiting this structural property offers a powerful avenue for dramatically enhancing computational efficiency. Guided by this insight, we propose a support-set algorithm preserving strictly the feasibility of iterates. A central ingredient is a strategically devised update scheme for support sets that adjusts the placement of nonzero entries. We establish the convergence of the support-set algorithm to a first-order stationary point, and show that its iteration complexity required to reach an $ε$-approximate first-order stationary point is $O (ε^{-2})$. Numerical results are strongly in favor of our algorithm in real-world applications, including nonnegative PCA, clustering, and community detection.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。