A nondeterministic branch-and-bound algorithm for maximizing the sum of a generalized Rayleigh quotient and a quadratic form on the unit sphere
Numerical Algorithms · 2026-11 · 103 (3) · 1711-1731
DOI: 10.1007/s11075-025-02279-3 ↗Kurz gefasst
Fachartikel in der Zeitschrift Numerical Algorithms, online erschienen am 05.12.2025. Verfasst von Ruirui Huang und 1 weiteren Autor:innen. Die Arbeit nennt 35 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
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.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Huang, R., & Wang, L. (2026). A nondeterministic branch-and-bound algorithm for maximizing the sum of a generalized Rayleigh quotient and a quadratic form on the unit sphere. Numerical Algorithms, 103(3), 1711-1731. https://doi.org/10.1007/s11075-025-02279-3
Vancouver
Huang R, Wang L. A nondeterministic branch-and-bound algorithm for maximizing the sum of a generalized Rayleigh quotient and a quadratic form on the unit sphere. Numerical Algorithms. 2026;103(3):1711-1731. doi:10.1007/s11075-025-02279-3
BibTeX
@article{Huang2026,
author = {Huang, Ruirui and Wang, Longfei},
title = {A nondeterministic branch-and-bound algorithm for maximizing the sum of a generalized Rayleigh quotient and a quadratic form on the unit sphere},
journal = {Numerical Algorithms},
year = {2026},
volume = {103},
number = {3},
pages = {1711--1731},
doi = {10.1007/s11075-025-02279-3}
}
EUVIMED