  We reformulate the zero-norm minimization problem as an equivalent
mathematical program with equilibrium constraints and establish that its
penalty problem, induced by adding the complementarity constraint to the
objective, is exact. Then, by the special structure of the exact penalty
problem, we propose a decomposition method that can seek a global optimal
solution of the zero-norm minimization problem under the null space condition
in [M. A. Khajehnejad et al. IEEE Trans. Signal. Process., 59(2011), pp.
1985-2001] by solving a finite number of weighted $l_1$-norm minimization
problems. To handle the weighted $l_1$-norm subproblems, we develop a partial
proximal point algorithm where the subproblems may be solved approximately with
the limited memory BFGS (L-BFGS) or the semismooth Newton-CG. Finally, we apply
the exact penalty decomposition method with the weighted $l_1$-norm subproblems
solved by combining the L-BFGS with the semismooth Newton-CG to several types
of sparse optimization problems, and compare its performance with that of the
penalty decomposition method [Z. Lu and Y. Zhang, SIAM J. Optim., 23(2013), pp.
2448- 2478], the iterative support detection method [Y. L. Wang and W. T. Yin,
SIAM J. Sci. Comput., 3(2010), pp. 462-491] and the state-of-the-art code
FPC_AS [Z. W. Wen et al. SIAM J. Sci. Comput., 32(2010), pp. 1832-1857].
Numerical comparisons indicate that the proposed method is very efficient in
terms of the recoverability and the required computing time.
