Strong formulations for quadratic optimization with M-matrices and indicator variables |
| |
Authors: | Alper Atamtürk " target="_blank">Andrés Gómez |
| |
Institution: | 1.Department of Industrial and Systems Engineering,Chuo University,Tokyo,Japan;2.Department of Mathematical Analysis and Statistical Inference,The Institute of Statistical Mathematics,Tokyo,Japan;3.RIKEN Center for Advanced Intelligence Project,Tokyo,Japan;4.Data Science Research Laboratories,NEC Corporation,Kanagawa,Japan |
| |
Abstract: | We propose a DC (Difference of two Convex functions) formulation approach for sparse optimization problems having a cardinality or rank constraint. With the largest-k norm, an exact DC representation of the cardinality constraint is provided. We then transform the cardinality-constrained problem into a penalty function form and derive exact penalty parameter values for some optimization problems, especially for quadratic minimization problems which often appear in practice. A DC Algorithm (DCA) is presented, where the dual step at each iteration can be efficiently carried out due to the accessible subgradient of the largest-k norm. Furthermore, we can solve each DCA subproblem in linear time via a soft thresholding operation if there are no additional constraints. The framework is extended to the rank-constrained problem as well as the cardinality- and the rank-minimization problems. Numerical experiments demonstrate the efficiency of the proposed DCA in comparison with existing methods which have other penalty terms. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|