Global Minimization of a Bi-Quadratic Function with a Linear Term

Abstract

This paper studies the minimization of a bi-quadratic function with a linear term. As both a quartic programming problem and a generalized convex multiplicative programming problem, it poses significant challenges for standard convex optimization methods. We propose an adaptive branch-and-bound algorithmic framework based on explicit relaxation bounds. Theoretically, the proposed framework guarantees a global ϵ-approximate solution within O(1/ϵ) worst-case iterations. Numerically, we apply it to compute the Legendre–Fenchel conjugate of the product of two positive definite quadratic forms, demonstrating its advantages over the compared methods.