KMS Of Academy of mathematics and systems sciences, CAS
| L-p-NORM REGULARIZATION ALGORITHMS FOR OPTIMIZATION OVER PERMUTATION MATRICES | |
Jiang, Bo1; Liu, Ya-Feng2 ; Wen, Zaiwen3
| |
| 2016 | |
| Source Publication | SIAM JOURNAL ON OPTIMIZATION
 |
| ISSN | 1052-6234 |
| Volume | 26Issue:4Pages:2284-2313 |
| Abstract | Optimization problems over permutation matrices appear widely in facility layout, chip design, scheduling, pattern recognition, computer vision, graph matching, etc. Since this problem is NP-hard due to the combinatorial nature of permutation matrices, we relax the variable to be the more tractable doubly stochastic matrices and add an L-p-norm (0 < p < 1) regularization term to the objective function. The optimal solutions of the L-p-regularized problem are the same as the original problem if the regularization parameter is sufficiently large. A lower bound estimation of the nonzero entries of the stationary points and some connections between the local minimizers and the permutation matrices are further established. Then we propose an L-p regularization algorithm with local refinements. The algorithm approximately solves a sequence of L-p regularization subproblems by the projected gradient method using a nonmonotone line search with the Barzilai-Borwein step sizes. Its performance can be further improved if it is combined with certain local search methods, the cutting plane techniques as well as a new negative proximal point scheme. Extensive numerical results on QAPLIB and the bandwidth minimization problem show that our proposed algorithms can often find reasonably high quality solutions within a competitive amount of time. |
| Keyword | permutation matrix doubly stochastic matrix quadratic assignment problem Lp regularization cutting plane negative proximal p oint Barzilai-Borwein method |
| DOI | 10.1137/15M1048021 |
| Language | 英语 |
| Funding Project | NSFC[11501298] ; NSFC[11301516] ; NSFC[11331012] ; NSFC[11571221] ; NSFC[11322109] ; NSFC[11421101] ; NSF of Jiangsu Province[BK20150965] ; Priority Academic Program Development of Jiangsu Higher Education Institutions ; National Basic Research Project[2015CB856002] |
| WOS Research Area | Mathematics |
| WOS Subject | Mathematics, Applied |
| WOS ID | WOS:000391853600013 |
| Publisher | SIAM PUBLICATIONS |
| Citation statistics | |
| Document Type | 期刊论文 |
| Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/24556 |
| Collection | 计算数学与科学工程计算研究所 |
| Corresponding Author | Jiang, Bo |
| Affiliation | 1.Nanjing Normal Univ, Key Lab NSLSCS Jiangsu Prov, Sch Math Sci, Nanjing 210023, Jiangsu, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Inst Computat Math & Sci Engn Comp, State Key Lab Sci & Engn Comp, Beijing 100190, Peoples R China 3.Peking Univ, Beijing Int Ctr Math Res, Beijing 100871, Peoples R China |
| Recommended Citation GB/T 7714 | Jiang, Bo,Liu, Ya-Feng,Wen, Zaiwen. L-p-NORM REGULARIZATION ALGORITHMS FOR OPTIMIZATION OVER PERMUTATION MATRICES[J]. SIAM JOURNAL ON OPTIMIZATION,2016,26(4):2284-2313. |
| APA | Jiang, Bo,Liu, Ya-Feng,&Wen, Zaiwen.(2016).L-p-NORM REGULARIZATION ALGORITHMS FOR OPTIMIZATION OVER PERMUTATION MATRICES.SIAM JOURNAL ON OPTIMIZATION,26(4),2284-2313. |
| MLA | Jiang, Bo,et al."L-p-NORM REGULARIZATION ALGORITHMS FOR OPTIMIZATION OVER PERMUTATION MATRICES".SIAM JOURNAL ON OPTIMIZATION 26.4(2016):2284-2313. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment