Home » 学术报告 » 美国休斯顿大学彭积明教授 5月22日上午做学术报告

美国休斯顿大学彭积明教授 5月22日上午做学术报告

主讲人: 彭积明教授

邀请人:中科院数学院优化与应用研究中心

时间:2013年12月30日上午10:30-11:30

地点:数学院科南楼二层226会议室

Topic:The Direct Extension of ADMM for Multi-block Convex Minimization Problems is Not Necessarily Convergent

Abstract:

The issue of how to solve generic non-convex QP has been a long standing challenge in optimization. Existing global algorithms usually refer to branch-and-bound or successive relaxation approaches whose running time are typically exponential in term of the number of variables. Moreover, it has been proved that even finding a local optimal solution to LCQP is NP-hard.
In this talk, we introduce a new design paradigm for LCQPs with a few negative eigenvalues that are known to be NP-hard. We first introduce a new class of Lagrangian functions that satisfy the KKT conditions automatically. By using the new Lagrangian function, we present an alternative update scheme to improve the objective function. We then characterize the accumulation point of the sequence. By integrating the new algorithm and other simple optimization techniques such as convex relaxation, line search and partitioning, we present a global algorithm to find the global optimal solution to the underlying LCQP and estimate its complexity. Promising numerical experiments will be reported as well.