CSpace  > 计算数学与科学工程计算研究所
L-p-NORM REGULARIZATION ALGORITHMS FOR OPTIMIZATION OVER PERMUTATION MATRICES
Jiang, Bo1; Liu, Ya-Feng2; Wen, Zaiwen3
2016
Source PublicationSIAM JOURNAL ON OPTIMIZATION
ISSN1052-6234
Volume26Issue:4Pages:2284-2313
AbstractOptimization 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.
Keywordpermutation matrix doubly stochastic matrix quadratic assignment problem Lp regularization cutting plane negative proximal p oint Barzilai-Borwein method
DOI10.1137/15M1048021
Language英语
Funding ProjectNSFC[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 AreaMathematics
WOS SubjectMathematics, Applied
WOS IDWOS:000391853600013
PublisherSIAM PUBLICATIONS
Citation statistics
Cited Times:10[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/24556
Collection计算数学与科学工程计算研究所
Affiliation1.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.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Jiang, Bo]'s Articles
[Liu, Ya-Feng]'s Articles
[Wen, Zaiwen]'s Articles
Baidu academic
Similar articles in Baidu academic
[Jiang, Bo]'s Articles
[Liu, Ya-Feng]'s Articles
[Wen, Zaiwen]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Jiang, Bo]'s Articles
[Liu, Ya-Feng]'s Articles
[Wen, Zaiwen]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.