Vanishing Duality Gap in Large Collaborative Optimization
主 题: Vanishing Duality Gap in Large Collaborative Optimization
报告人: Prof. Mengdi Wang (Princeton University)
时 间: 2015-07-07 15:10-16:10
地 点: 理科一号楼1479（主持人：文再文）
Consider the optimization problem that involves multiple participants driven by self interests and some common goods. We focus on the case where individual preferences are not necessarily convex, making the problem NP-hard. We analyze the nonconvex duality and provide a complete mathematical characterization of the duality gap, which often vanishes to zero as the number of participants goes to infinity. Moreover, we show that there exists an approximate optimum by solving the dual problem and provide a coordinative dual algorithm to achieve the optimum in polynomial time.
