Relaxations of KKT Conditions do not Strengthen Finite RLT and SDP-RLT Bounds for Nonconvex Quadratic Programs

E. Alper Yıldırım · 2025

Read Relaxations of KKT Conditions do not Strengthen Finite RLT and SDP-RLT Bounds for Nonconvex Quadratic Programs by E. Alper Yıldırım (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-2506-09892.txt.

Introduction

E Alper Yildirim wrote a 2025 mathematics paper testing whether adding optimality conditions can tighten the bounds used to solve hard quadratic programs. Such programs resist exact solution, so solvers lean on relaxations: easier problems whose answers bound the true one. A common reformulation adds the first-order conditions as extra constraints, which might in principle sharpen the bound.

Yildirim proves that, when the base relaxation has a finite best value, the bounds from the enriched and plain forms agree exactly for the two main relaxation families. Adding the conditions therefore buys nothing in that regime. The paper also gives families of cases where the relaxations run off to infinity, showing different behaviour there.

Catalog record

CREATORE. Alper Yıldırım
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-09892

Browse the full library · About the Tower of Babel

Full text

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

Relaxations of KKT Conditions do not Strengthen Finite RLT and SDP-RLT Bounds for Nonconvex Quadratic Programs E. Alper Yıldırım Abstract We consider linear and semidefinite programming relaxations of nonconvex quadratic programs given by the reformulation-linearization technique (RLT relaxation), and the Shor relaxation combined with the RLT relaxation (SDP-RLT relaxation). By incorporating the first-order optimality conditions, a quadratic program can be formulated as an optimization problem with complementarity constraints. We investigate the effect of incorporating optimality conditions on the strength of the RLT and SDP-RLT relaxations. Under the assumption that the original relaxations have a finite optimal value, we establish that the RLT and SDP-RLT bounds arising from the complementarity formulation agree with their counterparts. We present several classes of instances of quadratic programs with unbounded RLT and SDP-RLT relaxations to illustrate the different behavior of the relaxations of the complementarity formulation. In particular, our examples reveal that relaxations of optimality conditions may even yield misleading information on certain families of instances. Keywords: Quadratic programming; Reformulation linearization technique; RLT relaxation; Semidefinite relaxation; Optimality conditions Mathematics Subject Classification (2020): 90C20, 90C26, 90C05, 90C22, 90C46 1 Introduction In this paper, we consider the problem of minimizing a (possibly nonconvex) quadratic function over a polyhedron: \quad\nu^{*}=\min\limits_{x\in\mathbb{R}^{n}}\left\{\mathsf{q}(x):x\in\mathsf{F}\right\}, where \mathsf{q}:\mathbb{R}^{n}\to\mathbb{R} and \mathsf{F}\subseteq\mathbb{R}^{n} are given by \displaystyle\mathsf{q}(x) \displaystyle=\textstyle\frac{1}{2}x^{\top}Qx+c^{\top}x, (1) \displaystyle\mathsf{F} \displaystyle=\left\{x\in\mathbb{R}^{n}:G^{\top}x\leq g,\quad H^{\top}x=h\right\}. (2) ( 1 ) is a quadratic program defined by the parameters Q\in\mathbb{R}^{n\times n} , c\in\mathbb{R}^{n} , G\in\mathbb{R}^{n\times m} , H\in\mathbb{R}^{n\times p} , g\in\mathbb{R}^{m} , and h\in\mathbb{R}^{p} . Without loss of generality, we assume that Q is a symmetric matrix. We denote the optimal value of ( 1 ) by \nu^{*}\in\mathbb{R}\cup\{-\infty\}\cup\{+\infty\} , with the usual conventions for infeasible and unbounded problems. Quadratic programs play a central role in optimization due to numerous applications (see, e.g., [ 12 ] ). Unless \mathsf{q}(x) is a convex function, ( 1 ) is an NP-hard problem (see, e.g., [ 24 , 19 ] ). Global solution algorithms for ( 1 ) are typically based on branch-and-bound methods, which recursively partition the feasible region into smaller subregions and generate upper and lower bounds on the objective function value in each subregion (see, e.g., [ 17 ] ). Lower bounds are usually given by solving convex relaxations of ( 1 ). Strong relaxations provide tighter lower bounds, which can potentially improve the solution time by closing the gap earlier. In this paper, we consider two convex relaxations of ( 1 ). The first one, referred to as the RLT relaxation, is a linear programming relaxation given by the reformulation-linearization technique (see, e.g., [ 25 ] ). The RLT relaxation is obtained by generating implied quadratic constraints for \mathsf{F} and then replacing each quadratic term with a new variable. The second relaxation, referred to as the SDP-RLT relaxation, is a semidefinite programming relaxation obtained by combining the RLT relaxation with the Shor relaxation [ 27 ] , further tightening the relationship between the original variables and the new variables representing quadratic terms. By incorporating the first-order optimality conditions, ( 1 ) can be formulated as an optimization problem with complementarity constraints (see, e.g., [ 13 ] ). Unless ( 1 ) is unbounded, the two formulations are equivalent. On the other hand, it is well-known that convex relaxations arising from equivalent formulations may not, in general, be equivalent (see, e.g., [ 22 , Example 3] ). Motivated by this observation, we investigate the effect of incorporating the first-order optimality conditions on the strength of RLT and SDP-RLT relaxations of ( 1 ). Our contributions are as follows: 1. If the RLT relaxation of ( 1 ) has a finite optimal value, we show that incorporating optimality conditions does not improve the strength of the RLT relaxation (see Theorem 1 ). 2. Unless p=0 , we show that the Slater condition fails for the SDP-RLT relaxation (see Lemma 3 ). 3. Using facial reduction techniques, we present an equivalent formulation of the SDP-RLT relaxation as a conic optimization problem that satisfies the Slater condition (see Proposition 1 ). 4. By relying on the equivalence between the two formulations, we establish necessary and sufficient optimality conditions for the original SDP-RLT relaxation (see Proposition 2 ). 5. We establish that incorporating optimality conditions does not improve the strength of the SDP-RLT relaxation if its optimal value is attained (see Theorem 2 ). 6. We present several classes of instances of ( 1 ) with unbounded RLT and SDP-RLT relaxations to illustrate the different behavior of the relaxations arising from the complementarity formulation. In particular, our examples reveal that the information from the relaxations of optimality conditions should be treated with some caveat. We briefly motivate our choice of \mathsf{F} in the general form given by ( 2 ). RLT and SDP-RLT relaxations are, in general, highly dependent on the particular representation of \mathsf{F} . For instance, if one replaces each equality constraint with two inequality constraints, then the resulting RLT relaxation is, in general, weaker than the original one (see, e.g., the discussion at the end of Section 6 in [ 22 ] ). Furthermore, converting \mathsf{F} into a more convenient form may increase the dimension of the problem, which may adversely affect the computational cost of the relaxations. Therefore, throughout this manuscript, we will assume the general form given by ( 2 ). This paper is organized as follows. We review the literature in Section 1.1 and define our notation in Section 1.2 . We present the first-order optimality conditions and incorporate these conditions to obtain a reformulation of ( 1 ) as an optimization problem with complementarity constraints in Section 2 . Section 3 is devoted to the comparison of the RLT relaxations arising from the original formulation and the complementarity formulation. We compare the corresponding SDP-RLT relaxations in Section 4 . Section 5 concludes the paper. 1.1 Literature Review In addition to playing a central role in guiding algorithmic methods and their termination criteria, optimality conditions can be taken into consideration prior to solving an optimization problem. For instance, by directly incorporating the first-order optimality conditions, ( 1 ) can be reformulated as a linear programming problem with complementarity constraints [ 13 ] . Such reformulations can then be utilized to develop solution methods based on mixed integer linear programming approaches (see, e.g., [ 16 , 31 , 14 ] ). Optimality conditions can also be employed to develop branching strategies in a branch-and-bound framework. For box-constrained quadratic programs, Hansen et al. [ 15 ] propose a finite branch-and-bound algorithm by employing first-order optimality conditions to subdivide the feasible region (see also Audet et al. [ 1 ] for a similar method for disjoint bilinear programming), and Vandenbussche and Nemhauser [ 29 ] utilize the optimality conditions from [ 15 ] to generate valid inequalities for a linear programming relaxation and develop a finite branch-and-bound algorithm using a similar branching rule [ 28 ] . By using semidefinite programming relaxations, Burer and Vandenbussche propose a similar finite branch-and-bound method for box-constrained quadratic programs [ 8 ] and general quadratic programs with bounded feasible regions [ 7 ] (see also [ 9 ] for a copositive relaxation-based approach). In addition to the first-order optimality conditions, Burer and Chen [ 6 ] propose

Read the complete text