RiNNAL+: a Riemannian ALM Solver for SDP-RLT Relaxations of Mixed-Binary Quadratic Programs

Di Hou, Tianyun Tang, Kim-Chuan Toh · 2025

Read RiNNAL+: a Riemannian ALM Solver for SDP-RLT Relaxations of Mixed-Binary Quadratic Programs by Di Hou, Tianyun Tang, Kim-Chuan Toh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13776.txt.

Introduction

Di Hou, Tianyun Tang, and Kim-Chuan Toh present a 2025 paper on a faster solver for hard planning problems that mix yes-no choices with continuous amounts. Such problems appear in scheduling and design. A strong relaxation gives good lower bounds on the best answer, but solving that relaxation is itself heavy, and the right rank for the answer is unknown ahead of time.

Their solver works on curved spaces of low-rank matrices and alternates two phases: one glides downhill on the curved space, and the other nudges the rank up to escape false resting spots. They also prove their relaxation equals a smaller known one. Wide tests showed the solver is fast and robust.

Catalog record

CREATORDi Hou, Tianyun Tang, Kim-Chuan Toh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE132 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-13776

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

RiNNAL+: a Riemannian ALM Solver for SDP-RLT Relaxations of Mixed-Binary Quadratic Programs Di Hou, Tianyun Tang, Kim-Chuan Toh Abstract Doubly nonnegative (DNN) relaxation usually provides a tight lower bound for a mixed-binary quadratic program (MBQP). However, solving DNN problems is challenging because: (1) the problem size is Ω ⁡ ( ( n + l ) 2 ) \Omega((n+l)^{2}) for an MBQP with n n variables and l 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 ) (n+l+1) , is equivalent to the SDP-RLT relaxation (based on the reformulation-linearization technique) with a smaller matrix dimension ( n + 1 ) (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. 1 Introduction 1.1 Mixed-binary nonconvex quadratic program In this paper, we consider the following mixed-binary quadratic program: v^{P_{1}}:=\min\left\{x^{\top}Qx+2c^{\top}x:Ax=b,\ Gx\leq d,\ x_{i}\in\{0,1\},\ \forall i\in B,\ x\in\mathbb{R}^{n}_{+}\right\}, (MBQP) where Q\in\mathbb{S}^{n},\,c\in\mathbb{R}^{n},\,A\in\mathbb{R}^{m\times n},\,G\in\mathbb{R}^{l\times n},\,b\in\mathbb{R}^{m},\,d\in\mathbb{R}^{l} , B\subseteq[n] is the index set of p binary variables. Without loss of generality, we assume that A has full row rank and b\geq 0. Problem ( MBQP ) is general because it includes both binary and continuous nonnegative variables, as well as equality and inequality constraints. The objective function features both quadratic and linear terms, allowing it to model a broad range of optimization problems. This formulation encompasses key problems such as 0-1 mixed-integer programming (MIP), non-convex quadratic programming (QP), binary integer nonconvex quadratic programming (BIQ), and more. Since ( MBQP ) is generally nonconvex and NP-hard, solving it to global optimality is computationally intractable in most cases. As a result, numerous convex relaxations have been developed to approximately solve it efficiently [ 13 , 16 ] . Among these, semidefinite programming (SDP) relaxations have been particularly effective due to their ability to provide tight lower bounds and, in some cases, exact solutions under specific conditions [ 26 , 60 , 19 , 3 ] . Beyond stand-alone approximations, convex relaxations also play a crucial role in global optimization frameworks, such as branch-and-bound and branch-and-cut methods [ 36 , 39 ] . In these frameworks, relaxations are used to derive valid bounds that help prune the search space, significantly improving computational efficiency. The strength of the relaxation directly impacts the overall performance of such global approaches, making SDP relaxations a key ingredient in state-of-the-art exact algorithms for nonconvex quadratic optimization [ 15 , 28 , 34 ] . In the next subsection, we introduce several widely used SDP relaxations, with a particular emphasis on the SDP-RLT relaxation. We discuss their formulations, the quality of their respective bounds, and numerical challenges associated with their implementation in deriving tight lower bounds for ( MBQP ). Remark 1 . The algorithm we propose in this paper is not limited to just solving the DNN relaxation of ( MBQP ). It can also handle the relaxations of QCQP problems with additional general quadratic constraints: \displaystyle x^{\top}A_{i}x+b_{i}^{\top}x+c_{i} \displaystyle\leq 0,\quad i=1,\dots,m_{1}, (1) \displaystyle x^{\top}A_{j}x+b_{j}^{\top}x+c_{j} \displaystyle=0,\quad j=m_{1}+1,\dots,m_{2}, where A_{i}\not=0_{n\times n} for all i\in[m_{2}] . By introducing the new variable X\in\mathbb{S}^{n}_{+} to represent xx^{\top} , we obtain the following convex relaxation of ( 1 ): \displaystyle\langle A_{i},X\rangle+b_{i}^{\top}x+c_{i} \displaystyle\leq 0,\quad i=1,\dots,m_{1}, (2) \displaystyle\langle A_{j},X\rangle+b_{j}^{\top}x+c_{j} \displaystyle=0,\quad j=m_{1}+1,\dots,m_{2}. (3) For instance, complementarity constraints are a special class of quadratic constraints defined by x_{i}x_{j}=0 for (i,j)\in E , where E\subseteq\{(i,j)\mid 1\leq i<j\leq n\} represents the set of complementary index pairs. By lifting these constraints using ( 3 ), we obtain X_{ij}=0,\,\forall(i,j)\in E . By incorporating ( 2 ) and ( 3 ) into the set \mathcal{I} and \mathcal{E} defined in the subsequent subsection, respectively, our results for ( MBQP ) extend naturally to general QCQP problems. For simplicity, we exclude additional quadratic constraints of the form ( 1 ) in ( MBQP ) throughout this paper. 1.2 SDP-RLT relaxations of ( MBQP ) Shor relaxation. A commonly used convex relaxation of general QCQP problems is the Shor relaxation [ 53 ] , which is obtained by replacing the quadratic term xx^{\top} with a matrix X and introducing a positive semidefinite constraint X-xx^{\top}\succeq 0 . The explicit formulation of the Shor relaxation ( SHOR ) of ( MBQP ) is given in Subsection 2.1 . While the Shor relaxation can be exact under certain conditions [ 60 , 19 ] , it often yields weak lower bounds for most instances of ( MBQP ). In some cases, the bound can even be unbounded below. Therefore, additional constraints are necessary to strengthen the relaxation and improve bound quality. DNN relaxation. To address this limitation, researchers have explored the doubly nonnegative (DNN) relaxation, which extends the Shor relaxation by incorporating nonnegativity constraints on X . Initially proposed by Burer [ 17 , 18 ] and further analyzed in [ 33 , 11 , 30 ] , the DNN relaxation generally provides a significantly tighter relaxation than the Shor relaxation. The explicit formulation of the DNN relaxation ( DNN ) of ( MBQP ) is given in Subsection 2.1 . However, deriving ( DNN ) requires converting all inequality constraints into equality constraints via the introduction of slack variables. This transformation can substantially increase both the matrix dimension and the number of constraints in the resulting relaxation. For instance, if the number of inequality constraints l equals the variable dimension n , the matrix dimension of the DNN relaxation increases to 2n , significantly increasing computational complexity. SDP-RLT relaxation. To address the high dimensionality of ( DNN ) while maintaining its bound quality, we consider the SDP-RLT relaxation of ( MBQP ). Unlike ( DNN ), which increases the problem size by introducing additional slack variables, the SDP-RLT relaxation preserves the original problem dimension by deriving quadratic constraints from the linear constraints of ( MBQP ). Specifically, it integrates the reformulation-linearization technique (RLT) [ 51 , 48 ] with the Shor relaxation ( SHOR ), yielding a tighter bound than ( SHOR ). In fact, we will further show that it achieves the same bound as ( DNN ). To systematically construct the SDP-RLT relaxation of ( MBQP ), we first apply the RLT technique to obtain the quadratic constraints. These constraints are derived by multiplying pairs of linear inequalities, including x\geq 0 , and by multiplying each equality constraint with a decision variable. Next, we replace the

Read the complete text