Xiaoling Sun

演讲人

School of Management,Fudan University

Xiaoling Sun ,School of Management,Fudan University.Dr Xiaoling Sun is Professor of Operations Research in the School of Management, Fudan University, Shanghai, China. He got his PhD in Operations Research in 1995 from Shanghai University, China. He worked in the Chinese University of Hong Kong and Edinburgh University as a research fellow from 1997 to 2000. He had been with the Department of Mathematics of Shanghai University from 2000 to 2006 before he joined Fudan University in 2007. His res

Au_61803_54042.jpeg

Continuous and integer 0-1 quadratic programming problems are well-known NP-hard problems in global and discrete optimization. These two classes of problems have many applications in computer science, management and engineering design such as maximum cut, resource allocation, quadratic assignment problem and graph partitioning and densest k-subgraph.Semidefinite programming (SDP) has been a very important tool in approximating NP-hard problems in polynomial time. We discuss in this talk how to improve SDP bounds for a nonconvex quadratic program and a 0-1 quadratic program with linear constraints. For nonconvex quadratic program, we propose a new convex relaxation method using decomposition and linear underestimation. By suitably choosing the decomposition schemes, this convex relaxation method generates lower bound tighter than the strengthened SDP bound, copositive bound and RLT bound. We also investigate improving SDP bound for 0-1 quadratic program with linear constraints using the distance from {-1,1}^n to certain affine subspace and the spectral information. We show that this distance can be computed by the cell enumeration of hyperplane arrangement in discrete geometry.

Improving SDP bounds for continuous and integer nonconvex quadratic programs（一）

Vod_61803.jpeg

CJFZFGB0607144407003.flv

288

350

61803/info.html

error.html

http://gffgaf75067c2e8a043a7h0oq66nufku5v6u09.fbyb.hbpu.cwkeji.cn/adksvod/PublicFolder/Player

http://gffga05319f78c7994b03h0oq66nufku5v6u09.fbyb.hbpu.cwkeji.cn/flvServer.aspx