| 报告题目 | A conic approximation method for the 0-1 quadratic knapsack problem | ||
| 报告人（单位） | 周晶（清华大学数学系） | ||
| 点评人（单位） | 舒嘉，刘新旺，侯合银，王文平 | 点评人（单位） | |
| 时间地点 | 时间： 2014年4月11日（周五）下午1点 地点：九龙湖经管楼B-201 | ||
| 报告内容摘要 | | ||
| 报告内容： This presentation is about using a conic approximation method for solving the 0-1 quadratic knapsack problem. The problem is a classic and important problem in mathematical programming, which was introduced by Gallo et al. in 1980 and has a wide spectrum of applications. Witzgall formulated a problem occurred in telecommunication industry as a 0-1 quadratic knapsack problem, in which a number of sites for satellite stations are selected such that the global traffic between these stations is maximized and the budget constraint is satisfied. The weighted maximum b-clique problem is also a special case of this problem. This problem is NP-hard, so there is no polynomial-time algorithm to solve it. We propose a nonnegative quadratic function cone program to equivalently represent the problem. Conic programming over cones of nonnegative quadratic functions is an extension of Lagrangian relaxation and semidefinite relaxation. Based on the technique of linear matrix inequality, we present an adaptive approximation scheme to obtain a global optimal solution or a lower bound for the problem by using computable cones. 报告人简介： 周晶，本科毕业于南开大学数学科学学院统计系，后免试推荐到清华大学数学系运筹学方向直博至今，预计7月份毕业，研究方向为最优化理论与算法。 文章： A conic approximation method for the 0-1 quadratic knapsack problem发表在Journal of Industrial and Management Optimization (SCI). Detection of a copositive matrix over a p-th order cone, submitted to Pacific Journal of Optimization (SCI). Conic approximation of quadratic optimization with linear complementarity constraints, submitted to Computational Optimization and Applications (SCI). | |||
