Optimization Online


Exact penalty decomposition method for zero-norm minimization based on MPEC formulation

Shujun Bi(bishj***at***scut.edu.cn)
Xiaolan Liu(liuxl***at***scut.edu.cn)
Shaohua Pan(shhpan***at***scut.edu.cn)

Abstract: 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. 19852001] by solving a finite number of weighted l1-norm minimization problems. To handle the weighted l1-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 l1-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. 24482478], the iterative support detection method [Y. L. Wang and W. T. Yin, SIAM J. Sci. Comput., 3 (2010), pp. 462491], and the state-of-the-art code FPC AS [Z. W. Wen et al., SIAM J. Sci. Comput., 32 (2010), pp. 18321857]. Numerical comparisons indicate that the proposed method is very efficient in terms of the recoverability and the required computing time.

Keywords: zero-norm minimization, MPECs, exact penalty, decomposition method

Category 1: Applications -- OR and Management Sciences

Citation: SIAM J. SCI. COMPUT., Vol. 36, No. 4, pp. A1451A1477

Download: [PDF]

Entry Submitted: 05/21/2017
Entry Accepted: 05/21/2017
Entry Last Modified: 05/21/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society