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.
Characterization of Linear Complementarity Problems as Linear Programs 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 ...
Robust Linear Programming Discrimination of Two Linearly Inseparable Sets 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)