The sparsest solution of the union of finite polytopes via its nonconvex relaxation

Guowei You (), Zheng-Hai Huang () and Yong Wang ()
Additional contact information
Guowei You: Henan University of Science and Technology
Zheng-Hai Huang: Tianjin University
Yong Wang: Tianjin University

Mathematical Methods of Operations Research, 2019, vol. 89, issue 3, No 6, 485-507

Abstract: Abstract Sparse optimization problems have gained much attention since 2004. Many approaches have been developed, where nonconvex relaxation methods have been a hot topic in recent years. In this paper, we study a partially sparse optimization problem, which finds a partially sparsest solution of a union of finite polytopes. We discuss the relationship between its solution set and the solution set of its nonconvex relaxation. In details, by using geometrical properties of polytopes and properties of a family of well-defined nonconvex functions, we show that there exists a positive constant $$p^*\in (0,1]$$ p ∗ ∈ ( 0 , 1 ] such that for every $$p\in [0,p^*)$$ p ∈ [ 0 , p ∗ ) , all optimal solutions to the nonconvex relaxation with the parameter p are also optimal solutions to the original sparse optimization problem. This provides a theoretical basis for solving the underlying problem via its nonconvex relaxation. Moreover, we show that the problem we concerned covers a wide range of problems so that several important sparse optimization problems are its subclasses. Finally, by an example we illustrate our theoretical findings.

Keywords: Nonconvex relaxation; Sparse optimization; Sparse solution; 90C25; 93C41; 65K05 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00186-019-00660-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:89:y:2019:i:3:d:10.1007_s00186-019-00660-2

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-019-00660-2

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().