File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Tractable ADMM schemes for computing KKT points and local minimizers for ℓ0-minimization problems

TitleTractable ADMM schemes for computing KKT points and local minimizers for ℓ0-minimization problems
Authors
KeywordsConstraint qualifications and KKT conditions
Convergence analysis
Nonconvex ADMM
Nonconvex sparse recovery
Tractability
Issue Date2021
Citation
Computational Optimization and Applications, 2021, v. 78, n. 1, p. 43-85 How to Cite?
AbstractWe consider an l(0)-minimization problem where f (x) + gamma parallel to x parallel to(0) is minimized over a polyhedral set and the l(0)-norm regularizer implicitly emphasizes the sparsity of the solution. Such a setting captures a range of problems in image processing and statistical learning. Given the nonconvex and discontinuous nature of this norm, convex regularizers as substitutes are often employed and studied, but less is known about directly solving the l(0)-minimization problem. Inspired by Feng et al. (Pac J Optim 14:273-305, 2018), we consider resolving an equivalent formulation of the l(0)-minimization problem as a mathematical program with complementarity constraints (MPCC) and make the following contributions towards the characterization and computation of its KKT points: (i) First, we show that feasible points of this formulation satisfy the relatively weak Guignard constraint qualification. Furthermore, if f is convex, an equivalence is derived between first-order KKT points and local minimizers of the MPCC formulation. (ii) Next, we apply two alternating direction method of multiplier (ADMM) algorithms, named (ADMM(cf)(mu,alpha,p)) and (ADMM(cf)), to exploit the special structure of the MPCC formulation. Both schemes feature tractable subproblems. Specifically, in spite of the overall nonconvexity, it is shown that the first update can be effectively reduced to a closed-form expression by recognizing a hidden convexity property while the second necessitates solving a tractable convex program. In (ADMM(cf)(mu,alpha,p)), subsequential convergence to a perturbed KKT point under mild assumptions is proved. Preliminary numerical experiments suggest that the proposed tractable ADMM schemes are more scalable than their standard counterpart while (ADMM(cf)) compares well with its competitors in solving the l(0) -minimization problem.
Persistent Identifierhttp://hdl.handle.net/10722/309271
ISSN
2023 Impact Factor: 1.6
2023 SCImago Journal Rankings: 1.322
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorXie, Yue-
dc.contributor.authorShanbhag, Uday V.-
dc.date.accessioned2021-12-15T03:59:52Z-
dc.date.available2021-12-15T03:59:52Z-
dc.date.issued2021-
dc.identifier.citationComputational Optimization and Applications, 2021, v. 78, n. 1, p. 43-85-
dc.identifier.issn0926-6003-
dc.identifier.urihttp://hdl.handle.net/10722/309271-
dc.description.abstractWe consider an l(0)-minimization problem where f (x) + gamma parallel to x parallel to(0) is minimized over a polyhedral set and the l(0)-norm regularizer implicitly emphasizes the sparsity of the solution. Such a setting captures a range of problems in image processing and statistical learning. Given the nonconvex and discontinuous nature of this norm, convex regularizers as substitutes are often employed and studied, but less is known about directly solving the l(0)-minimization problem. Inspired by Feng et al. (Pac J Optim 14:273-305, 2018), we consider resolving an equivalent formulation of the l(0)-minimization problem as a mathematical program with complementarity constraints (MPCC) and make the following contributions towards the characterization and computation of its KKT points: (i) First, we show that feasible points of this formulation satisfy the relatively weak Guignard constraint qualification. Furthermore, if f is convex, an equivalence is derived between first-order KKT points and local minimizers of the MPCC formulation. (ii) Next, we apply two alternating direction method of multiplier (ADMM) algorithms, named (ADMM(cf)(mu,alpha,p)) and (ADMM(cf)), to exploit the special structure of the MPCC formulation. Both schemes feature tractable subproblems. Specifically, in spite of the overall nonconvexity, it is shown that the first update can be effectively reduced to a closed-form expression by recognizing a hidden convexity property while the second necessitates solving a tractable convex program. In (ADMM(cf)(mu,alpha,p)), subsequential convergence to a perturbed KKT point under mild assumptions is proved. Preliminary numerical experiments suggest that the proposed tractable ADMM schemes are more scalable than their standard counterpart while (ADMM(cf)) compares well with its competitors in solving the l(0) -minimization problem.-
dc.languageeng-
dc.relation.ispartofComputational Optimization and Applications-
dc.subjectConstraint qualifications and KKT conditions-
dc.subjectConvergence analysis-
dc.subjectNonconvex ADMM-
dc.subjectNonconvex sparse recovery-
dc.subjectTractability-
dc.titleTractable ADMM schemes for computing KKT points and local minimizers for ℓ0-minimization problems-
dc.typeArticle-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/s10589-020-00227-6-
dc.identifier.scopuseid_2-s2.0-85091774007-
dc.identifier.volume78-
dc.identifier.issue1-
dc.identifier.spage43-
dc.identifier.epage85-
dc.identifier.eissn1573-2894-
dc.identifier.isiWOS:000574378800001-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats