2024年11月10日 星期日 登录 EN

学术活动
A new KKT based branch and bound algorithm for a separable singly constrained quadratic program subject to upper and lower bounds
首页 - 学术活动
报告人:
Jinyu Dai, Lecturer, Beijing University of Posts and Telecommunications
邀请人:
Yuhong Dai, Professor
题目:
A new KKT based branch and bound algorithm for a separable singly constrained quadratic program subject to upper and lower bounds
时间地点:
9:00-10:00 March 27(Sunday), Classroom 702, South Building, School of Mathematics
摘要:

The separable singly constrained quadratic program with upper and lower bounds (SSQP) arises from many applications and receives a lot of attention. In the early 1980s, Pardalos and Kovoor analyzed this problem of convex case, providing a necessary and sufficient condition for a solution to be a KKT point. Furthermore, they presented an algorithm for solving such problem. In this paper, we shall extend the results by Pardalos and Kovoor to the nonconvex case and provide a necessary and sufficient condition that characterizes the KKT points of nonconvex SSQP. Integrating the new KKT condition into the branch and bound framework, we propose a hybrid algorithm for finding the global optimal solutions of SSQP. Numerical experiments show that our new algorithm runs faster than the KKT based algorithm by Burer and Vandenbussche (2008).