Scholarlink

<p>Many applications involve nonsmooth optimization problems that often exhibit a low-dimensional structure in their optimal solutions. The projection gradient method (PG), the alternating direction method of multipliers (ADMM), and the accelerated projection gradient method (APG) are particularly effective for solving nonconvex composite programming problems and are known to determine the optimal sparsity pattern after a finite number of iterations. However, the exact number of iterations required to identify the final sparsity pattern remains an open problem. In this work, we develop a novel analytical framework to characterize the complexity of determining the active manifold and provide a rigorous proof. Using this framework, we show that PG, ADMM, and APG satisfy the necessary assumptions, enabling us to characterize the complexity of identifying the final active manifold for composite programs with nonsmooth, nonconvex regularizers, such as the <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(L_0\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>L</mi> <mn>0</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(L_p\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>L</mi> <mi>p</mi> </msub> </math></EquationSource> </InlineEquation> norms, without requiring nondegeneracy conditions. Finally, we present numerical validation for the derived theoretical complexity bound.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Complexity Analysis Framework for Active Manifold Identification with Applications to \(L_0\) and \(L_p\) Regularization Models

  • 期刊论文

  • 发表日期：

    2026年3月10日

查看全文
  • Min Tao,
  • Xiao-Ping Zhang

摘要

Many applications involve nonsmooth optimization problems that often exhibit a low-dimensional structure in their optimal solutions. The projection gradient method (PG), the alternating direction method of multipliers (ADMM), and the accelerated projection gradient method (APG) are particularly effective for solving nonconvex composite programming problems and are known to determine the optimal sparsity pattern after a finite number of iterations. However, the exact number of iterations required to identify the final sparsity pattern remains an open problem. In this work, we develop a novel analytical framework to characterize the complexity of determining the active manifold and provide a rigorous proof. Using this framework, we show that PG, ADMM, and APG satisfy the necessary assumptions, enabling us to characterize the complexity of identifying the final active manifold for composite programs with nonsmooth, nonconvex regularizers, such as the \(L_0\) L 0 and \(L_p\) L p norms, without requiring nondegeneracy conditions. Finally, we present numerical validation for the derived theoretical complexity bound.