• Login
    View Item 
    •   MINDS@UW Home
    • MINDS@UW Madison
    • College of Letters and Science, University of Wisconsin–Madison
    • Department of Computer Sciences, UW-Madison
    • DMI Technical Reports
    • View Item
    •   MINDS@UW Home
    • MINDS@UW Madison
    • College of Letters and Science, University of Wisconsin–Madison
    • Department of Computer Sciences, UW-Madison
    • DMI Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Equivalence of Minimal L0 and Lp Norm Solutions of Linear Equalities, Inequalities and Linear Programs for Sufficiently Small p

    Thumbnail
    File(s)
    Equivalence of Minimal ℓ0 and ℓp Norm Solutions of Linear Equalities, Inequalities and Linear Programs for Sufficiently Small p (68.27Kb)
    Date
    2011
    Author
    Mangasarian, Olvi
    Fung, Glenn
    Metadata
    Show full item record
    Abstract
    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.
    Subject
    linear programming
    linear inequalities
    linear equations
    l0 minimization
    Permanent Link
    http://digital.library.wisc.edu/1793/64358
    Citation
    11-02
    Part of
    • DMI Technical Reports

    Related items

    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)

    Contact Us | Send Feedback
     

     

    Browse

    All of MINDS@UWCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Contact Us | Send Feedback