提出无需子问题求解的高效优化方法，解决带正交约束的非光滑非凸问题。
Primal-Dual Methods for Nonsmooth Nonconvex Optimization with Orthogonality Constraints
- 采用无回缩的原-对偶框架，线性化平滑增广拉格朗日法避免复杂子问题。
- 迭代复杂度达O(ε⁻³)，可找到ε-卡鲁什-库恩-塔克点，性能领先现有方法。
- 适合大规模、非光滑且需保持正交性的优化任务，如矩阵分解与特征学习。
数据科学的发展使正交约束优化问题愈发重要。由于Stiefel流形具有优越的计算与分析性质，黎曼方法成为主流。然而，非光滑性与正交约束的结合给现有黎曼方法带来巨大挑战，包括扩展性差、难以并行、子问题复杂及累积数值误差导致不可行。本文提出一种无回缩的原-对偶方法，设计了一种针对非光滑非凸正交约束优化的线性化平滑增广拉格朗日算法。该方法为单循环结构，无需求解子问题。我们建立了其寻找ε-KKT点的迭代复杂度为O(ε⁻³)，与黎曼优化领域最佳结果一致。进一步在标准Kurdyka-Lojasiewicz (KL) 性质下证明了算法的渐近序列收敛性。在光滑与非光滑正交约束问题上的数值实验表明，该方法在计算效率与可扩展性上显著优于当前最优算法。
原文摘要 · Abstract (English)
Recent advancements in data science have significantly elevated the importance of orthogonally constrained optimization problems. The Riemannian approach has become a popular technique for addressing these problems due to the advantageous computational and analytical properties of the Stiefel manifold. Nonetheless, the interplay of nonsmoothness alongside orthogonality constraints introduces substantial challenges to current Riemannian methods, including scalability, parallelizability, complicated subproblems, and cumulative numerical errors that threaten feasibility. In this paper, we take a retraction-free primal-dual approach and propose a linearized smoothing augmented Lagrangian method specifically designed for nonsmooth and nonconvex optimization with orthogonality constraints. Our proposed method is single-loop and free of subproblem solving. We establish its iteration complexity of $O(ε^{-3})$ for finding $ε$-KKT points, matching the best-known results in the Riemannian optimization literature. Additionally, by invoking the standard Kurdyka-Lojasiewicz (KL) property, we demonstrate asymptotic sequential convergence of the proposed algorithm. Numerical experiments on both smooth and nonsmooth orthogonal constrained problems demonstrate the superior computational efficiency and scalability of the proposed method compared with state-of-the-art algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。