In a number of applications, such as compressive sensing, it is desirable to obtain sparse solutions. Minimizing the number of nonzeroes of the solution (its l0-norm) is a difficult nonconvex optimization problem, and is often approximated by the convex problem of minimizing the l1-norm. In contrast, we consider an exact formulation as a mathematical program with complementarity constraints. We discuss properties of the exact formulation such as stationarity conditions, and solution procedures for determining local and global optimality. We compare our solutions with those from an l1-norm formulation.