A nondeterministic branch-and-bound algorithm for maximizing the sum of a generalized Rayleigh quotient and a quadratic form on the unit sphere

Abstract We study the problem of maximizing the sum of a generalized Rayleigh quotient and a quadratic form on the unit sphere (P). First, problem (P) is reformulated into two equivalent problems (EP1) and (EP2) by introducing auxiliary variables. Then, the non-convex part of the objective function in (EP2) is replaced with its linear concave envelope, leading to a relaxation programming (PUBc). Subsequently, a semidefinite relaxation is applied to (PUBc) to obtain an upper bound (PUB2) for (EP2). Further, we adopt a similar approach to derive the upper bound of (EP1). Based on the upper bound (PUB2), a branch-and-bound algorithm is constructed to solve (EP2), where each subproblem is a semidefinite programming. On the one hand, we employ the leading eigenvalue method to recover a feasible solution of (EP2) from the optimal solution of the semidefinite programming (PUB2). On the other hand, by leveraging the Gaussian randomized recovery method, we obtain the theoretical approximation ratio between the homogeneous quadratical constrained quadratic programming relaxation of (PUBc) and its semidefinite relaxation. Moreover, a region reduction technique is established to accelerate the algorithm. Finally, numerical results demonstrate the corresponding advantages in comparison with two existing branch-and-bound algorithms. MSC Classification (2010): 90C22 , 90C26 , 90C32