Equivalence of Minimal L0 and Lp Norm Solutions of Linear Equalities, Inequalities and Linear Programs for Sufficiently Small p
MetadataShow full item record
For a bounded system of linear equalities and inequalities we show that the NP-hard ?0 norm minimization problem min ||x||0 subject to Ax = a, Bx ? b and ||x||? ? 1, is completely equivalent to the concave minimization min ||x||p subject to Ax = a, Bx ? b and ||x||? ? 1, for a sufficiently small p. A local solution to the latter problem can be easily obtained by solving a provably finite number of linear programs. Computational results frequently leading to a global solution of the ?0 minimization problem and often producing sparser solutions than the corresponding ?1 solution are given. A similar approach applies to finding minimal ?0 solutions of linear programs.
Showing items related by title, author, creator and subject.
Mangasarian, Olvi (University of Wisconsin-Madison Department of Computer Sciences, 1976)It is shown that the linear complementarity problem of finding an n-by-1 vector x such that Mx + q > 0, x > 0, and xT(Mx+q) = 0, where M is a given n-by-n real matrix and q is a given n-by-l vector, is solvable if and ...
Bennett, Kristin P; Mangasarian, Olvi L (University of Wisconsin-Madison Department of Computer Sciences, 1991)
Error Bounds for Strongly Convex Programs and (Super) Linearly Convergent Iterative Schemes for the Least 2- Norm Solution of Linear Programs Mangasarian, Olvi L; DeLeone, Renato (University of Wisconsin-Madison Department of Computer Sciences, 1986)