EUVIMEDEUVIMED entdecken
Crossref

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

Ruirui Huang, Longfei Wang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →