An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions

被引：0
作者：
Xuewen Mu
Wenlong Liu
机构：
[1] Xidian University,School of Mathematics and Statistics
[2] Dalian University of Technology,School of Information and Communication Engineering
来源：
Optimization Letters | 2016年 / 10卷
关键词：
Binary quadratic programming; Augmented Lagrangian method; Max-cut; Barzilai–Borwein type method; Continuous functions;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this paper, an augmented Lagrangian method is proposed for binary quadratic programming (BQP) problems based on a class of continuous functions. The binary constraints are converted into a class of continuous functions. The approach reformulates the BQP problem as an equivalent augmented Lagrangian function, and then seeks its minimizer via an augmented Lagrangian method, in which the subproblem is solved by Barzilai–Borwein type method. Numerical results are reported for max-cut problem. The results indicate that the augmented Lagrangian approach is promising for large scale binary quadratic programming by the quality of the near optimal values and the low computational time.
引用
收藏
页码：485 / 497
页数：12
相关论文
共 47 条
[1]  
Goeman MX(1995)Improved approximation algorithms for maximum cut and satisfiably problem using semidefinite programming J. ACM 42 1115-1145
[2]  
Williamson DP(1998)An application of combinatorial optimization to statiscal optimization and circuit layout design Oper. Res. 36 493-513
[3]  
Barahon F(2001)The application of semidefinite programming for detection in CDMA IEEE Select. Commun. 19 1442-1449
[4]  
Grotschel M(2004)Speed and accuracy comparation of techniques to solve a binary programming problem with application to syschronous CDMA IEEE Trans. Commun. 52 2775-2780
[5]  
Peng HT(2003)Binary partitioning, perceptual grouping, and restoration with semidefinite programming IEEE Trans. Pattern Anal. Mach. Intell. 25 1364-1379
[6]  
Rasmussen LK(2008)Improved spectral relaxation methods for binary quadratic optimization problems Comput. Vis. Image Understand. 112 3-13
[7]  
Hasegawa F(1998)Design and performance of parallel and distributed approximation algorithms for max-cut J. Parallel Distrib. Comput. 9 141-160
[8]  
Luo J(2001)A projected gradient algorithm for solving the max-cut relaxation Optim. Methods Softw. 15 175-200
[9]  
Pattipati K(2001)Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs SIAM J. Optim. 12 503-521
[10]  
Willett P(2004)Feasible direction algorithm for solving SDP relaxation of the quadratic Optim. Methods Softw. 19 125-136
12345