A Linear-Time Algorithm for Globally Maximizing the Sum of a Generalized Rayleigh Quotient and a Quadratic Form on the Unit Sphere
Long-Fei Wang, Yong Xia · SIAM Journal on Optimization · 2019
We study the problem, which we refer to as problem (P), of maximizing the sum of a generalized Rayleigh quotient and a quadratic form on the unit sphere. The computational complexity is first analyzed. Then we reformulate (P) as a new univariate optimization problem $({P}_{\alpha})$. Though the objective function has no closed-form expression, with the help of an extended S-lemma, the function value evaluation of $({P}_{\alpha})$ is reduced to minimizing a nonsmooth univariate convex function and hence can be efficiently solved by bisection search. We propose a novel approach for overestimating the objective function of $({P}_{\alpha})$, which leads to a new efficient branch-and-bound algorithm for solving $({P}_{\alpha})$. We show that, with a high probability, the new algorithm can find a global $\epsilon$-approximation solution of $({P}_{\alpha})$ in linear time in terms of the number of nonzero elements of the input matrices. All tested numerical results demonstrate that the new algorithm highly outperforms not only the software BARON but also the recent global optimization algorithm based on Lipschitz bounds.