  


Exact penalty decomposition method for zeronorm minimization based on MPEC formulation
Shujun Bi(bishjscut.edu.cn) Abstract: We reformulate the zeronorm 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 zeronorm 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 l1norm minimization problems. To handle the weighted l1norm subproblems, we develop a partial proximal point algorithm where the subproblems may be solved approximately with the limited memory BFGS (LBFGS) or the semismooth NewtonCG. Finally, we apply the exact penalty decomposition method with the weighted l1norm subproblems solved by combining the LBFGS with the semismooth NewtonCG 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 stateoftheart 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. Keywords: zeronorm minimization, MPECs, exact penalty, decomposition method Category 1: Applications  OR and Management Sciences Citation: SIAM J. SCI. COMPUT., Vol. 36, No. 4, pp. A1451–A1477 Download: [PDF] Entry Submitted: 05/21/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  