2024-11-24 Sunday Sign in CN

Activities
A new KKT based branch and bound algorithm for a separable singly constrained quadratic program subject to upper and lower bounds
Home - Activities
Reporter:
Jinyu Dai, Lecturer, Beijing University of Posts and Telecommunications
Inviter:
Yuhong Dai, Professor
Subject:
A new KKT based branch and bound algorithm for a separable singly constrained quadratic program subject to upper and lower bounds
Time and place:
9:00-10:00 March 27(Sunday), Classroom 702, South Building, School of Mathematics
Abstract:

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).