We propose a branch-and-bound algorithm for minimizing a bilinear functional of the form f (X, Y) = tr((X ⊗ Y) Q) +tr(AX) +tr(BY), of pairs of Hermitian matrices (X, Y) restricted by joint semidefinite programming constraints. The functional is parametrized by self-adjoint matrices Q, A and B. This problem generalizes that of a bilinear program, where X and Y belong to polyhedra. The algorithm converges to a global optimum and yields upper and lower bounds on its value in every step. Various problems in quantum information theory can be expressed in this form. As an example application, we compute Dobrushin curves of quantum channels, giving upper bounds on classical coding with energy constraints.