%A O. L. Mangasarian
%T Minimum-Support Solutions of Polyhedral Concave Programs
%D April 1997
%R 97-05
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X
Motivated by the successful application of mathematical programming
techniques to difficult machine learning problems, we seek solutions
of concave minimization problems over polyhedral sets with a minimum
number of nonzero components. We prove that if such problems
have a solution, they have a vertex solution with a minimal number
of zeros. This includes linear programs and general linear
complementarity problems. A smooth concave exponential
approximation to a step function solves the
minimum-support problem exactly for a finite value of the
smoothing parameter. A fast finite linear-programming-based
iterative method terminates at a stationary point, which for many
important real world problems provides very useful answers.
Utilizing the complementarity property of linear programs
and linear complementarity problems,
an upper bound on the number of nonzeros can be obtained by
solving a single convex minimization problem on a polyhedral set.