L-p-NORM REGULARIZATION ALGORITHMS FOR OPTIMIZATION OVER PERMUTATION MATRICES

doi:10.1137/15M1048021

	L-p-NORM REGULARIZATION ALGORITHMS FOR OPTIMIZATION OVER PERMUTATION MATRICES
	Jiang, Bo 1; Liu, Ya-Feng2 ; Wen, Zaiwen 3
	2016
发表期刊	SIAM JOURNAL ON OPTIMIZATION
ISSN	1052-6234
卷号	26 期号:4 页码:2284-2313
摘要	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.
关键词	permutation matrix doubly stochastic matrix quadratic assignment problem Lp regularization cutting plane negative proximal p oint Barzilai-Borwein method
DOI	10.1137/15M1048021
语种	英语
资助项目	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研究方向	Mathematics
WOS类目	Mathematics, Applied
WOS记录号	WOS:000391853600013
出版者	SIAM PUBLICATIONS
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/24556
专题	计算数学与科学工程计算研究所
通讯作者	Jiang, Bo
作者单位	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
推荐引用方式 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.