RiNNAL+: a Riemannian ALM Solver for SDP-RLT Relaxations of Mixed-Binary Quadratic Programs
- Doubly nonnegative (DNN) relaxation usually provides a tight lower bound for a
mixed-binary quadratic program (MBQP). However, solving DNN problems is chal-
lenging because: (1) the problem size is � ((n + l)2) for an MBQP with n variables
and l inequality constraints, and (2) the rank of optimal solutions cannot be estimated
a priori due to the absence of theoretical bounds. In this work, we propose RiNNAL+,
a Riemannian augmented Lagrangian method (ALM) for solving DNN problems. We
prove that the DNN relaxation of an MBQP, with matrix dimension (n + l + 1), is
equivalent to the SDP-RLT relaxation (based on the reformulation-linearization tech-
nique) with a smaller matrix dimension (n + 1). In addition, we develop a hybrid
method that alternates between two phases to solve the ALM subproblems. In phase
one, we apply low-rank matrix factorization and random perturbation to transform the
feasible region into a lower-dimensional manifold so that we can use the Riemannian
gradient descent method. In phase two, we apply a single projected gradient step to
update the rank of the underlying variable and escape from spurious local minima
arising in the first phase if necessary. To reduce the computation cost of the projected
gradient step, we develop pre-processing and warm-start techniques for acceleration.
Unlike traditional rank-adaptive methods that require extensive parameter tuning, our
hybrid method requires minimal tuning. Extensive experiments confirm the efficiency
and robustness of RiNNAL+ in solving various classes of large-scale DNN problems