Quadratic Optimization Through the Lens of Adjustable Robust Optimization

1. Introduction

Various practical problems in different domains, including financial mathematics (Markowitz 1952), machine learning (Cevikalp and Polikar 2008), resource allocation (Ibaraki and Katoh 1988), computer vision (Bhanja et al. 2016), game theory (Bomze 2002b), robotic systems (Khadivar et al. 2023), graph theory (Gibbons et al. 1997), and image processing (Bulo et al. 2011), to mention few, can be formulated as quadratic optimization problems. Thus, developing efficient techniques to solve general quadratic optimization problems is of great importance.

Let us consider a quadratic optimization (QO) problem of the form:

where $\mathcal{X}\subseteq {\mathbb{R}}^{n_x}$ is a nonempty convex set, $Q\in {\mathbb{R}}^{n_x\times n_x}$ is a real matrix, and $c\in {\mathbb{R}}^{n_x}$ is a real vector. Without loss of generality, we assume that Q is a symmetric matrix. If Q is a positive semidefinite matrix, we have a convex QO, which is solvable in polynomial time (Kozlov et al. 1980, Renegar 2001). In contrast, even when Q has only one negative eigenvalue, (QO) is NP-hard (Pardalos and Vavasis 1991). Besides, identifying local minimizers of (QO) over a polyhedron is not simpler than finding global minimizers from a complexity perspective (Ahmadi and Zhang 2022).

Because of the NP-hardness of indefinite QO problems, there has been a lot of research on constructing upper bounds via finding “good” solutions (Bentobache et al. 2022, Cuong et al. 2024) and lower bounds to identify the quality of a candidate solution, which are mainly based on linear or conic approximations (Mitchell et al. 2014, Rostami et al. 2023, Zamani 2023). A customary way to approximate a QO problem is by relaxing it into linear optimization problems, which is achieved through reformulation-linearization techniques (RLTs) (Sherali and Tuncbilek 1995, Anstreicher 2009). For an overview of RLTs, we refer the reader to the chapter by Sherali and Liberti (2009) and the references therein.

Among the conic relaxations, copositive relaxations have been considered the most powerful as it was shown that they result in tight bounds (Burer 2009, Bomze 2015). In such relaxations, the primary computational challenge shifts to deal with the copositive cone using tractable inner and outer approximations (Bundfuss and Dur 2009, Gouveia et al. 2020, Kim et al. 2020), or use a Karush-Kuhn-Tucker (KKT)-based branch-and-bound method (Chen and Burer 2012).

Another important conic relaxation for QO problems is the positive semidefinite relaxations. In the last thirty years, the field of semidefinite optimization (SDO) has undergone significant and swift advancement (Wolkowicz et al. 2012). Because of their efficiency, the SDO framework has led to many semidefinite relaxations; these relaxations are reviewed and compared in Bao et al. (2011), Wang and Kılınç-Karzan (2022), and Zheng et al. (2011). Moreover, Burer and Vandenbussche (2008, 2009) develop branch-and-bound approaches based on semidefinite relaxations to solve a QO problem.

In addition to directly approximating QO problems, a research direction is to reformulate them into other well-studied problems. Hu et al. (2012) and Xia et al. (2020) show how a QO problem is reformulated as a mixed-integer linear optimization (MILO) problem. Furthermore, it is possible to transform an indefinite QO problem with quadratic constraints into a bilinear problem with additional variables and constraints (Hansen and Jaumard 1992). Moreover, because any quadratic function can be written as the difference between two convex quadratic functions, a QO can be reformulated as a difference-of-convex (DC) optimization problem (Anstreicher and Burer 2005, Fampa et al. 2017). For a review of DC optimization, we refer the reader to Horst and Thoai (1999) and Lipp and Boyd (2016).

Next to methods developed for general QO problems, there are techniques to solve or approximate special classes. One class is when the matrix Q has a few negative eigenvalues. In Cen and Xia (2021), the authors propose a solution scheme that involves solving a series of convex QO problems over the original feasible region. Additionally, Luo et al. (2019) introduce an alternative direction-based method to solve QO problems in this class.

Another class is standard QO problems, where the feasible region is the unit simplex. For more details on lower bound approximations for this class of QO problems, we refer the reader to Bomze and De Klerk (2002), Bomze et al. (2008), Bonami et al. (2019), Gökmen and Yıldırım (2022), Gondzio and Yıldırım (2021), and Selvi et al. (2023).

In this paper, we focus on the relation between QO problems and adjustable robust optimization problems. The adjustable robust optimization (ARO) framework, initially introduced in Ben-Tal et al. (2004), has gained significant attention among researchers due to its ability to handle decision-making problems in the presence of uncertain parameters. This approach involves adaptive decision making by considering two types of decision variables: static and adjustable decisions. Static (or “here-and-now”) decisions are made based on available information, whereas adjustable (or “wait-and-see”) decisions are made in response to the actual values of uncertain parameters. In recent years, the ARO framework has been successfully applied to tackle complex optimization problems such as convex maximization, bilinear optimization, and convex-nonconvex quadratic optimization (Bomze and Gabl 2021, Selvi et al. 2022, Zhen et al. 2022).

There are algorithms and approaches developed in the literature to solve an ARO problem exactly. Fourier-Motzkin elimination (FME) is such an approach that can be used in ARO problems with fixed recourse (Zhen et al. 2018). If all adjustable decision variables are eliminated, a static solution can be obtained by solving the robust counterpart. Even if not all adjustable decision variables can be eliminated, the resulting exact reformulation is likely to lead to stronger bounds after applying approximation techniques. Furthermore, there are iterative approaches to solve such problems exactly either by partitioning the uncertainty set (Bertsimas and Dunning 2016, Postek and Hertog 2016) or applying piece-wise decision rules (Thomä et al. 2024).

To obtain an approximate solution for an ARO problem, various techniques, such as the finite scenario approach (Hadjiyiannis et al. 2011), finite adaptability approach (Bertsimas and Caramanis 2010), and decision rules (El Housni and Goyal 2021) can be employed, particularly in the case of linear ARO problems. Using these methods, one can estimate the optimal value or obtain an approximated solution for the original problem. For more information on ARO, we refer to the tutorial by Delage and Iancu (2015) and the survey paper by Yanıkoğlu et al. (2019).

Although there has been a lot of research in approximating linear ARO problems, the literature sparsely covers nonlinear ARO problems due to their inherent complexity. De Ruiter et al. (2023) show a class of nonlinear ARO problems featuring a polyhedral uncertainty set that can be transformed into an equivalent linear ARO problem, thereby enabling the application of the existing approximations techniques for linear cases. In a recent study, Khademi et al. (2024) employed Fenchel’s duality to convert a nonlinear ARO problem into its dual formulation and introduce a cutting-plane algorithm to find locally robust solutions.

In this paper, we make a four-fold contribution to the literature to connect the two fields of quadratic optimization and adjustable robust optimization. First, we show that any QO problem can be reformulated as a disjoint biconvex quadratic optimization problem. Using this new reformulation, we further show that any QO problem can be reformulated as an ARO problem, where the objective functions and constraints are convex quadratic in the decision variables. This structure allows us to employ customary techniques to relax the ARO reformulation, thereby enabling us to derive a near-optimal solution to the original problem.

Second, we show how one can interpret an approximation of the ARO reformulation on the original QO problem. More specifically, we prove that applying a structured affine decision rule to approximate the ARO formulation is equivalent to applying an RLT to approximate the original problem.

Third, we design an algorithm to construct a bound on the optimal value of (QO). More specifically, we apply a decision rule approximation to obtain a lower bound. Then, based on the solution and the structure of the ARO problem, we construct “good” feasible solutions. In the final step, we apply the mountain climbing procedure to improve the quality of the solution.

Finally, we conduct an extensive numerical experiment to illustrate the efficiency of our algorithm in obtaining near-optimal solutions. Based on the numerical results, we see that the solution obtained from the algorithm is close to optimum and, in most cases, has an optimality gap of 1% for concave QO problems (the optimality gap is measured as the percentage relative gap between lower and upper bounds on the optimal value). Regarding speed, our algorithm is computationally efficient and significantly outperforms the available off-the-shelf solvers and state-of-the-art approaches for large-sized instances.

The rest of the paper is structured as follows. In Section 1.1, we define the notation used throughout the paper. Section 2 introduces the reformulation of a QO problem as a biconvex optimization problem and outlines its equivalent ARO problem. In Section 3, we approximate this problem using available techniques and prove the equivalence to an RLT for the original QO problem. Subsequently, in Section 4, we design an algorithm that provides a near-optimal solution for a QO problem using the ARO reformulation. Section 5 presents numerical results, demonstrating the efficiency of our ARO-based algorithm, particularly for large-sized instances. Finally, in Section 6, we summarize our findings and present our conclusions.

1.1. Notation

In this section, we introduce notations used in the paper. For a symmetric matrix B, we use $B⪰0$ ($B\succ 0$) to show B is positive semidefinite (positive definite); that is, it has nonnegative (positive) eigenvalues. The smallest and largest eigenvalues of a symmetric matrix B are denoted by ${\lambda }_{\mathit{\text{min}}}(B)$ and ${\lambda }_{\mathit{\text{max}}}(B)$, respectively. For a given matrix B, and indices i and j, we denote by $B_i$, $B^j$, and $B_{ij}$, the ith row, the jth column, and the ijth entry of B, respectively. For a matrix B, $\text{vec}(B)$ denotes the vector formed by concatenating all the rows of matrix B. For a square matrix B, $\text{diag}(B)$ is a vector containing the main diagonal elements of matrix B. For vector v, $\text{Diag}(v)$ is a matrix with the elements of vector v placed on its main diagonal and zeros elsewhere. The notation $B\ge 0$ for matrix B indicates that all its elements are nonnegative. We use ${\mathcal{S}}^n$ to refer to the space of $n\times n$ symmetric matrices. We use ${(·)}^{\top }$ to refer to the transpose operator for both matrices and vectors. We denote the $n\times n$ identity matrix by $I_n$, the vector of all ones by e, and the ith unit vector by $e_i$. To avoid overcomplicating notation, we do not specify the dimensions of e and $e_i$ but make sure they are always evident from the context. We misuse the notation and denote the real number zero, the vector of all zeroes, and the matrix of all zeroes by zero.

We use ${\mathbb{R}}^n$ to refer to the n-dimensional real-valued Euclidean space, where $\Vert ·{\Vert }_2$ is the Euclidean norm. The standard or unit simplex in ${\mathbb{R}}^n$, given by $\{x\in {\mathbb{R}}^n: e^{\top }x=1, x\ge 0\}$, is denoted by $\mathrm{\Delta }$.

2. New Reformulations for Quadratic Optimization Problems

This section proposes two reformulations for a quadratic optimization problem (QO). We first show how we can reformulate (QO) as a disjoint biconvex quadratic optimization problem. Using this reformulation, we further provide an equivalent adjustable robust optimization problem. Therefore, we start with the following theorem.

Theorem 1.

Let $Q^{+},-Q^{-}⪰0$, and $\mathcal{X}\subseteq {\mathbb{R}}^{n_x}$ be an arbitrary set. Then,

$$\underset{x\in \mathcal{X}}{\min } x^{\top }(Q^{+}+Q^{-})x+c^{\top }x$$(1)

is equivalent to

$$\underset{x,y\in {\mathbb{R}}^{n_x}}{\min }\left\{\frac{1}{2}{x}^{\top }{Q}^{+}x+\frac{1}{2}{y}^{\top }{Q}^{+}y+x^{\top }{Q}^{-}y+\frac{1}{2}{c}^{\top }x+\frac{1}{2}{c}^{\top }y: x,y\in \mathcal{X}\right\}.$$(Bi-QO)

Proof.

It is clear that

$$\begin{array}{ll}\underset{x\in \mathcal{X}}{\min } x^{\top }(Q^{+}+Q^{-})x+c^{\top }x\hfill & \hfill \\ =\underset{x,y\in {\mathbb{R}}^{n_x}}{\min }\left\{\frac{1}{2}{x}^{\top }{Q}^{+}x+\frac{1}{2}{y}^{\top }{Q}^{+}y+x^{\top }{Q}^{-}y+\frac{1}{2}{c}^{\top }x+\frac{1}{2}{c}^{\top }y: x=y, x,y\in \mathcal{X}\right\}\hfill & \hfill \\ \ge \underset{x,y\in {\mathbb{R}}^{n_x}}{\min }\left\{\frac{1}{2}{x}^{\top }{Q}^{+}x+\frac{1}{2}{y}^{\top }{Q}^{+}y+x^{\top }{Q}^{-}y+\frac{1}{2}{c}^{\top }x+\frac{1}{2}{c}^{\top }y: x,y\in \mathcal{X}\right\},\hfill & \hfill \end{array}$$

where the inequality is because the feasible region of the last optimization problem is contained in the feasible region of the middle optimization problem.

To show “$\le$,” we use the negative semidefiniteness of $Q^{-}$. For any given x and y in ${\mathbb{R}}^{n_x}$, because $Q^{-}⪯0$, we have ${(x-y)}^{\top }{Q}^{-}(x-y)\le 0$. Hence, $x^{\top }{Q}^{-}x+y^{\top }{Q}^{-}y\le 2x^{\top }{Q}^{-}y$. This implies that for any $x,y\in {\mathbb{R}}^{n_x}$,

$$x^{\top }(Q^{+}+Q^{-})x+y^{\top }(Q^{+}+Q^{-})y\le x^{\top }{Q}^{+}x+y^{\top }{Q}^{+}y+2x^{\top }{Q}^{-}y.$$

Therefore,

$$x^{\top }(Q^{+}+Q^{-})x+y^{\top }(Q^{+}+Q^{-})y+c^{\top }x+c^{\top }y\le x^{\top }{Q}^{+}x+y^{\top }{Q}^{+}y+2x^{\top }{Q}^{-}y+c^{\top }x+c^{\top }y.$$

Now, by taking the minimum over $x,y\in \mathcal{X}$, we have

$$\begin{array}{ll}\underset{x\in \mathcal{X}}{\min }\left\{x^{\top }(Q^{+}+Q^{-})x+c^{\top }x\right\}+\underset{y\in \mathcal{X}}{\min }\left\{y^{\top }(Q^{+}+Q^{-})y+c^{\top }y\right\}\hfill & \hfill \\ \le \underset{x,y\in \mathcal{X}}{\min }\left\{x^{\top }{Q}^{+}x+y^{\top }{Q}^{+}y+2x^{\top }{Q}^{-}y+c^{\top }x+c^{\top }y\right\}.\hfill & \hfill \end{array}$$

The fact that

$$\underset{x\in \mathcal{X}}{\min }\left\{x^{\top }(Q^{+}+Q^{-})x+c^{\top }x\right\}=\underset{y\in \mathcal{X}}{\min }\left\{y^{\top }(Q^{+}+Q^{-})y+c^{\top }y\right\},$$

completes the proof. □

It is worth noting that the proof of Theorem 1 does not rely on the specific structure of the feasible set $\mathcal{X}$. If $\mathcal{X}$ is convex, then the theorem asserts that any indefinite QO can be reformulated as a disjoint biconvex quadratic optimization problem, where the variables x and y are linked only in the objective function. Furthermore, it can be demonstrated that if $x^{*}$ is an optimal solution for (QO), then the pair $(x^{*},x^{*})$ is an optimal solution for (Bi-QO). Conversely, when $Q^{+}⪰0$ and $-Q^{-}\succ 0$, if $(\widehat{x},\widehat{y})$ is an optimal pair for (Bi-QO), then both $\widehat{x}$ and $\widehat{y}$ are optimal solutions for (QO), and we have $\widehat{x}=\widehat{y}$. For more details, see Online Supplement A.

From now on, let us restrict the feasible region of (QO) to polytopes, that is, $\mathcal{X}=\{x\in {\mathbb{R}}^{n_x}: Ax=b, x\ge 0\}$ for some $A\in {\mathbb{R}}^{m_x\times n_x}$ and $b\in {\mathbb{R}}^{m_x}$, so that $\mathcal{X}$ is compact. In the next theorem, we show that we can reformulate the (QO) problem to an adjustable robust optimization problem.

Theorem 2.

Let $Q=Q^{+}+Q^{-}$, where $Q\in {\mathbb{R}}^{n_x\times n_x}$, and $Q^{+},-Q^{-}⪰0$. Assume that $\mathcal{X}=\{x\in {\mathbb{R}}^{n_x}: Ax=b, x\ge 0\}$ is nonempty compact. Then, the optimal value of (QO) is equal to the optimal value of the following problem:

$$\begin{array}{cc}\underset{\tau \in \mathbb{R}}{\max }& \tau \\ \text{s}.\text{t}.& \forall x\in \mathcal{X}, \exists (u_x,w_x):\{\begin{array}{l}\frac{1}{2}{x}^{\top }{Q}^{+}x+\frac{1}{2}{c}^{\top }x-\frac{1}{2}{u}_x^{\top }{Q}^{+}{u}_x+b^{\top }{w}_x\ge \tau ,\hfill \\ A^{\top }{w}_x-Q^{+}{u}_x\le Q^{-}x+\frac{1}{2}c.\hfill \end{array}\end{array}$$(ARO-QO)

Proof.

Based on the assumption, we have that (QO) is equivalent to

$$\underset{x\in \mathcal{X}}{\min }{x}^{\top }(Q^{+}+Q^{-})x+c^{\top }x,$$

which is, using Theorem 1, equivalent to

$$\underset{x,y\in {\mathbb{R}}^{n_x}}{\min }\left\{\frac{1}{2}{x}^{\top }{Q}^{+}x+\frac{1}{2}{y}^{\top }{Q}^{+}y+x^{\top }{Q}^{-}y+\frac{1}{2}{c}^{\top }x+\frac{1}{2}{c}^{\top }y: x,y\in \mathcal{X}\right\}.$$(2)

We can write (2) as

$$\underset{x\in \mathcal{X}}{\min }\{\frac{1}{2}{x}^{\top }{Q}^{+}x+\frac{1}{2}{c}^{\top }x+\underset{y\in \mathcal{X}}{\min }\frac{1}{2}{y}^{\top }{Q}^{+}y+x^{\top }{Q}^{-}y+\frac{1}{2}{c}^{\top }y\}.$$(3)

We consider the inner minimization problem over y for a given $x\in \mathcal{X}$. Because $\mathcal{X}$ is nonempty compact, we can apply Dorn duality (Dorn 1960) and rewrite (3) as follows:

$$\begin{array}{l}\underset{x\in \mathcal{X}}{\min }\frac{1}{2}{x}^{\top }{Q}^{+}x+\frac{1}{2}{c}^{\top }x+\underset{u_x,w_x}{\max }-\frac{1}{2}{u}_x^{\top }{Q}^{+}{u}_x+b^{\top }{w}_x\\ \text{s}.\text{t}. A^{\top }{w}_x-Q^{+}{u}_x\le Q^{-}x+\frac{1}{2}c.\end{array}$$(4)

Let $x\in \mathcal{X}$. If the inner maximization is infeasible, its optimal value is $-\infty$, implying that (4) is unbounded. Therefore, in this case, (QO) is unbounded, which contradicts the compactness of $\mathcal{X}$. Therefore, for any $x\in \mathcal{X}$, there is a feasible $(u_x,w_x)$ for the inner maximization. Thus, using the epigraph reformulation of the objective function, we can rewrite (4) as

$$\underset{\tau }{\max }\left\{\tau \hspace{0.17em}|\begin{array}{l}\forall x\in \mathcal{X}, \exists (u_x,w_x):\begin{array}{ll}\hfill & \frac{1}{2}{x}^{\top }{Q}^{+}x+\frac{1}{2}{c}^{\top }x-\frac{1}{2}{u}_x^{\top }{Q}^{+}{u}_x+b^{\top }{w}_x\ge \tau ,\hfill \\ \hfill & A^{\top }{w}_x-Q^{+}{u}_x\le Q^{-}x+\frac{1}{2}c.\hfill \end{array}\hfill \end{array}\right\},$$(5)

which completes the proof. □

Problem (ARO-QO) is a quadratic ARO problem with fixed recourse and right-hand side uncertainty. In this problem, $\tau$ is the static variable, $x\in \mathcal{X}$ is the uncertain parameter, and $(u_x,w_x)$ is the adjustable variable. The adjustable variables can be seen as functions of x and are known as decision policies (Yanıkoğlu et al. 2019, Khademi et al. 2024).

It is important to note that a concave QO problem, that is, when dealing with a negative semidefinite matrix Q, is NP-hard (Sahni 1974). This complexity primarily arises from the crucial relationship between achieving optimality and enumerating the extreme points within the feasible region (Pardalos and Schnitger 1988). Predominant strategies for addressing concave QO problems typically involve cutting plane methods, branch-and-bound approaches, or iterative computational techniques (Phillips and Rosen 1988, Audet et al. 2005, Chinchuluun et al. 2005, Andrianova et al. 2016). Furthermore, recent studies in this area have focused on establishing bounds from a robust optimization perspective (Selvi et al. 2022), and some have adopted approaches that begin with convex optimization techniques to find starting points and then proceed to gradient descent principles (Ben-Tal and Roos 2022); the application of these techniques has been instrumental in deriving high-quality bounds for the optimal solution. In the subsequent corollary, we present the ARO reformulation for a concave QO problem.

Corollary 1.

Let Q be a negative semidefinite matrix. Assume that $\mathcal{X}=\{x\in {\mathbb{R}}^{n_x}: Ax=b, x\ge 0\}$ is nonempty compact. Then, the optimal value of (QO) is equal to the optimal value of the following problem:

$$\begin{array}{l}\underset{\tau \in \mathbb{R}}{\max } \tau \hfill \\ \text{s}.\text{t}. & \forall x\in \mathcal{X}, \exists w_x:\{\begin{array}{c}\frac{1}{2}{c}^{\top }x+b^{\top }{w}_x\ge \tau ,\\ A^{\top }{w}_x\le Qx+\frac{1}{2}c.\end{array}\end{array}$$(6)

Proof.

From Theorem 2 by setting $Q^{+}≔0$ and $Q^{-}≔Q$. □

Note that (6) is a linear adjustable robust optimization problem and all techniques in the literature can be used to solve or approximate it.

Remark 1.

In Table 6 of Online Supplement C, we present the equivalent ARO formulations if the polytope $\mathcal{X}$ is formulated in another form than canonical.

To approximate (ARO-QO), we can use customary techniques to deal with adjustable variables, such as eliminating the adjustable variables via FME or using decision rules to approximate the adjustable variables. In the next section, we focus on such approximation methods.

3. ARO-Based Approximations

In this section, we recap some of the available customary approaches to approximate our (ARO-QO) problem from the literature and discuss their interpretations concerning (QO).

3.1. Decision Rules

In the (ARO-QO) problem, the adjustable variables $u_x$ and $w_x$ are, in essence, functions of the uncertain parameter x. One of the popular methods to approximate an ARO problem is by restricting the adjustable variables to belong to a specific class of functions. For example, we can restrict them to be constants, resulting in a static formulation, or to be affine, known as affine decision rule (ADR), which is a good approximation for linear ARO problems (Bertsimas and Bidkhori 2015; Bertsimas et al. 2015, 2010).

Because (ARO-QO) contains a nonlinear convex term $u_x^{\top }{Q}^{+}{u}_x$, using ADR to approximate $u_x$ results in an intractable approximation. Therefore, we apply a hybrid decision rule to have a tractable approximation. More specifically, we restrict $u_x$ to be constant and $w_x$ to be affine:

where $u\in {\mathbb{R}}^{n_x}$, $z\in {\mathbb{R}}^{m_x}$, and $Z\in {\mathbb{R}}^{m_x\times n_x}$ are static variables. Using this decision rule in (ARO-QO) leads to the following static robust counterpart, which gives a lower bound on the optimal value of (QO):where u, z, and Z are simultaneously optimized together with the static decision variable $\tau$.

In the previous section, we demonstrated that the (QO) problem is equivalent to both the (Bi-QO) and (ARO-QO) problems. In the rest of this section, we explore the relationship between the reformulation-linearization technique (RLT) and the hybrid decision rule.

The RLT was originally proposed by Sherali and Alameddine (1992) and was further developed in Sherali and Tuncbilek (1995). RLT works in two steps: reformulation and linearization. The reformulation step creates additional constraints by multiplying the existing ones. The linearization step then replaces each unique product of variables with a new continuous variable. By applying RLT to approximate the problem with a convex problem, we can find a lower bound on the solution of the original nonconvex minimization problem.

The following theorem demonstrates that (7) is equivalent to applying RLT to the nonconvex part of the objective function in (QO) when representing Q as $Q^{+}+Q^{-}$, and linearizing $x^{\top }{Q}^{-}x$.

Theorem 3.

Let $Q=Q^{+}+Q^{-}$ where $Q\in {\mathbb{R}}^{n_x\times n_x}$, and $Q^{+},-Q^{-}⪰0$. Assume that $\mathcal{X}=\{x\in {\mathbb{R}}^{n_x}: Ax=b, x\ge 0\}$ is nonempty compact. Then, the optimal value of (7) is equal to the optimal value

$$\begin{array}{ll}\underset{\stackrel{x\in {\mathbb{R}}^{n_x}}{\gamma \in {\mathcal{S}}^{n_x}}}{\min }\hfill & x^{\top }{Q}^{+}x+c^{\top }x+{\displaystyle \sum _{i,j=1}^{n_x}{Q}_{ij}^{-}}{\gamma }_{ij}\hfill \\ \text{s}.\text{t}. \hfill & Ax=b,\hfill \\ \hfill & A\gamma =b{x}^{\top },\hfill \\ \hfill & x\ge 0, \gamma \ge 0.\hfill \end{array}$$(8)

Proof.

We can rewrite (7) as

$$\underset{u,z,Z,\tau }{\max }\{\tau \left|\begin{array}{cc}\underset{x\in \mathcal{X}}{\min }\left\{\frac{1}{2}{x}^{\top }{Q}^{+}x+(\frac{1}{2}{c}^{\top }+b^{\top }Z)x\right\}+b^{\top }z-\frac{1}{2}{u}^{\top }{Q}^{+}u\ge \tau ,& \\ \underset{x\in \mathcal{X}}{\min }\left\{{(-A^{\top }Z+Q^{-})}_{i}x\right\}+{(\frac{1}{2}c+Q^{+}u-A^{\top }z)}_i\ge 0,& i=1,\dots ,n_x\end{array}\right\}.$$(9)

Because $\mathcal{X}$ is a polytope, the inner minimizations are convex optimization problems. Because $\mathcal{X}$ is nonempty and compact, strong duality holds (Dorn 1960, Boyd and Vandenberghe 2004). Therefore, (9) is equivalent to

$$\begin{array}{cc}\underset{u,z,Z,\tau }{\max }& \hspace{1em}\tau \\ \text{s}.\text{t}.& \hspace{1em}\underset{\alpha ,\beta }{\max }\left\{b^{\top }\beta -\frac{1}{2}{\alpha }^{\top }{Q}^{+}\alpha : \hspace{0.17em}{A}^{\top }\beta -Q^{+}\alpha \le {(b^{\top }Z)}^{\top }+\frac{1}{2}c\right\}+b^{\top }z-\frac{1}{2}{u}^{\top }{Q}^{+}u\ge \tau ,\\ & \hspace{1em}\underset{{\theta }^i}{\max }\left\{b^{\top }{\theta }^i: A^{\top }{\theta }^i\le {({(-A^{\top }Z+Q^{-})}_i)}^{\top }\right\}+{\left(\frac{1}{2}c+Q^{+}u-A^{\top }z\right)}_i\ge 0,\hspace{1em}i=1,\dots ,n_x.\end{array}$$(10)

We can omit the inner maximization operator in the above constraints since the maximizations are bounded. Thus, we have

$$\begin{array}{lll}\underset{u,z,Z,\alpha ,\beta ,\theta }{\max }\hfill & b^{\top }\beta -\frac{1}{2}{\alpha }^{\top }{Q}^{+}\alpha +b^{\top }z-\frac{1}{2}{u}^{\top }{Q}^{+}u\hfill & \hfill \\ \text{s}.\text{t}. \hfill & A^{\top }\beta -Q^{+}\alpha \le {(b^{\top }Z)}^{\top }+\frac{1}{2}c,\hfill & \hfill \\ \hfill & b^{\top }{\theta }^i+{\left(\frac{1}{2}c+Q^{+}u-A^{\top }z\right)}_i\ge 0,\hfill & i=1,\dots ,n_x,\hfill \\ \hfill & A^{\top }{\theta }^i\le {({(-A^{\top }Z+Q^{-})}_i)}^{\top },\hfill & i=1,\dots ,n_x.\hfill \end{array}$$(11)

Now, consider the following RLT reformulation of the (Bi-QO) problem:

$$\begin{array}{ll}\underset{\gamma ,x,y}{\min }\hfill & \frac{1}{2}\left(x^{\top }{Q}^{+}x+y^{\top }{Q}^{+}y+c^{\top }x+c^{\top }y\right)+{\displaystyle \sum _{i,j=1}^{n_x}{Q}_{ij}^{-}}{\gamma }_{ij}\hfill \\ \text{s}.\text{t}. \hfill & Ax=b,\hfill \\ \hfill & Ay=b,\hfill \\ \hfill & A\gamma =b{y}^{\top },\hfill \\ \hfill & A{\gamma }^{\top }=b{x}^{\top },\hfill \\ \hfill & x\ge 0, y\ge 0, \gamma \ge 0.\hfill \end{array}$$(12)

We first show that if $(\widehat{x},\widehat{y},\widehat{\gamma })$ is an optimal solution to (12), and then $\left(\frac{\widehat{x}+\widehat{y}}{2},\frac{\widehat{x}+\widehat{y}}{2},\frac{\widehat{\gamma }+{\widehat{\gamma }}^{\top }}{2}\right)$ is also an optimal solution. Because of the optimality of $(\widehat{x},\widehat{y},\widehat{\gamma })$, it is clear that $(\widehat{y},\widehat{x},{\widehat{\gamma }}^{\top })$ is also an optimal solution. Therefore, the feasibility of $\left(\frac{\widehat{x}+\widehat{y}}{2},\frac{\widehat{x}+\widehat{y}}{2},\frac{\widehat{\gamma }+{\widehat{\gamma }}^{\top }}{2}\right)$ is evident. Setting $\mathrm{\Phi }(x,y,\gamma )≔\frac{1}{2}\left(x^{\top }{Q}^{+}x+y^{\top }{Q}^{+}y+c^{\top }x+c^{\top }y\right)+{\sum }_{i,j=1}^{n_x}{Q}_{ij}^{-}{\gamma }_{ij}$, we know the optimal value of (12) is $\mathrm{\Phi }(\widehat{x},\widehat{y},\widehat{\gamma })=\mathrm{\Phi }(\widehat{y},\widehat{x},{\widehat{\gamma }}^{\top })$. Furthermore, the convexity of $x^{\top }{Q}^{+}x$ in x implies that

$$2\mathrm{\Phi }\left(\frac{\widehat{x}+\widehat{y}}{2},\frac{\widehat{x}+\widehat{y}}{2},\frac{\widehat{\gamma }+{\widehat{\gamma }}^{\top }}{2}\right)\le \mathrm{\Phi }(\widehat{x},\widehat{y},\widehat{\gamma })+\mathrm{\Phi }(\widehat{y},\widehat{x},{\widehat{\gamma }}^{\top })=2\mathrm{\Phi }(\widehat{x},\widehat{y},\widehat{\gamma }).$$

Therefore, $\left(\frac{\widehat{x}+\widehat{y}}{2},\frac{\widehat{x}+\widehat{y}}{2},\frac{\widehat{\gamma }+{\widehat{\gamma }}^{\top }}{2}\right)$ is an optimal solution to (12).

We have thus shown that there exists an optimal solution to (12) with the structure $x=y$ and $\gamma ={\gamma }^{\top }$. We now show that (12) and (8) are equivalent. To demonstrate this, it suffices to show that any optimal solution to (12) corresponds to an optimal solution to (8) with the same objective value. Suppose that $(\widehat{x},\widehat{y},\widehat{\gamma })$ is optimal for (12). Then $\left(\overline{x}=\frac{\widehat{x}+\widehat{y}}{2},\overline{x}=\frac{\widehat{x}+\widehat{y}}{2},\overline{\gamma }=\frac{\widehat{\gamma }+{\widehat{\gamma }}^{\top }}{2}\right)$ is also optimal for (12). We claim that $(\overline{x},\overline{\gamma })$ is an optimal solution to (8). If the claim is not true, then there exists a feasible solution $(\tilde{x},\tilde{\gamma })$ such that

$${\tilde{x}}^{\top }{Q}^{+}\tilde{x}+c^{\top }\tilde{x}+{\displaystyle \sum _{i,j=1}^{n_x}{Q}_{ij}^{-}}{\tilde{\gamma }}_{ij}<{\overline{x}}^{\top }{Q}^{+}\overline{x}+c^{\top }\overline{x}+{\displaystyle \sum _{i,j=1}^{n_x}{Q}_{ij}^{-}}{\overline{\gamma }}_{ij}.$$

This implies that $(\tilde{x},\tilde{x},\tilde{\gamma })$ is feasible for (12) and achieves a better objective value than $(\widehat{x},\widehat{y},\widehat{\gamma })$, which is a contradiction.

Now, we show that (11) is the Dorn dual problem of (12) (which is equivalent to (8)). To do this, we first write (12) in the matrix form:

$$\begin{array}{ll}\underset{\text{vec}(\gamma ),x,y}{\min } \hfill & \frac{1}{2}{\left(\begin{array}{c}x\\ y\\ \text{vec}(\gamma )\end{array}\right)}^{\top }\left(\begin{array}{ccc}{Q}^{+}& 0& 0\\ 0& Q^{+}& 0\\ 0& 0& 0\end{array}\right)\left(\begin{array}{c}x\\ y\\ \text{vec}(\gamma )\end{array}\right)+{\left(\begin{array}{c}\frac{c}{2}\\ \frac{c}{2}\\ \text{vec}(Q^{-})\end{array}\right)}^{\top }\left(\begin{array}{c}x\\ y\\ \text{vec}(\gamma )\end{array}\right)\hfill \\ \text{s}.\text{t}. \hfill & \left(\begin{array}{ccc}A& 0& 0\\ 0& A& 0\\ 0& B& C\\ B& 0& D\end{array}\right)\left(\begin{array}{c}x\\ y\\ \text{vec}(\gamma )\end{array}\right)=\left(\begin{array}{c}b\\ b\\ 0\\ 0\end{array}\right),\hfill \\ \hfill & \left(\begin{array}{c}x\\ y\\ \text{vec}(\gamma )\end{array}\right)\ge 0,\hfill \end{array}$$(13)

where $B≔-\left(\begin{array}{c}{b}_1{I}_{n_x}\\ b_2{I}_{n_x}\\ ⋮\\ b_{m_x}{I}_{n_x}\end{array}\right)$, $C≔\left(\begin{array}{cccc}{A}_{11}{I}_{n_x}& A_{12}{I}_{n_x}& \cdots & A_{1n_n}{I}_{n_x}\\ ⋮& ⋮& \ddots & ⋮\\ A_{m_{x}1}{I}_{n_x}& A_{m_{x}2}{I}_{n_x}& \cdots & A_{m_x{n}_x}{I}_{n_x}\end{array}\right)$, and $D≔\left(\begin{array}{ccc}{A}_1& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & A_1\\ ⋮& & ⋮\\ A_{m_x}& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & A_{m_x}\end{array}\right)$. The dual of (13) is

$$\begin{array}{ll}\underset{Y,W}{\max }\hfill & -\frac{1}{2}{Y}^{\top }\left(\begin{array}{ccc}{Q}^{+}& 0& 0\\ 0& Q^{+}& 0\\ 0& 0& 0\end{array}\right)Y+{\left(\begin{array}{c}b\\ b\\ 0\\ 0\end{array}\right)}^{\top }W\hfill \\ \text{s}.\text{t}.\hfill & -\left(\begin{array}{ccc}{Q}^{+}& 0& 0\\ 0& Q^{+}& 0\\ 0& 0& 0\end{array}\right)Y+{\left(\begin{array}{ccc}A& 0& 0\\ 0& A& 0\\ 0& B& C\\ B& 0& D\end{array}\right)}^{\top }W\le \left(\begin{array}{c}\frac{c}{2}\\ \frac{c}{2}\\ \text{vec}(Q^{-})\end{array}\right).\hfill \end{array}$$(14)

Setting

$$\begin{array}{l}Y\equiv \left(\begin{array}{c}\alpha \\ u\\ Y^3\end{array}\right),\hspace{1em}W\equiv \left(\begin{array}{c}\beta \\ z\\ \text{vec}(\theta )\\ \text{vec}(Z)\end{array}\right),\hfill \end{array}$$

(14) is the matrix form of (11). Hence, (12) is the dual of the deterministic reformulation of (7). Observe that, because of the property of Dorn duality at the optimal solution, we have $Y^{*}=\left(\begin{array}{c}{x}^{*}\\ y^{*}\\ \text{vec}({\gamma }^{*})\end{array}\right)$, i.e., $x^{*}={\alpha }^{*}$ and $y^{*}=u^{*}$. □

Theorem 3 establishes that a convex relaxation of the original QO through an RLT is equivalent to approximating its ARO reformulation via hybrid decision rules.

The literature has also considered RLTs to approximate an ARO problem. More specifically, it is shown in Ardestani-Jaafari and Delage (2021) that a linear ARO problem can be reformulated as a bilinear optimization problem using duality techniques. The authors then show that using an RLT to approximate the bilinear optimization reformulation is equivalent to applying ADR to the original problem. In Zhen et al. (2022), the same results are shown for disjoint bilinear problems with convex feasible regions.

Theorem 3 bridges the gap between existing analytical results for approximating ARO problems and those for approximating (QO). This allows us to extend the analytical techniques from one domain to the other. For example, Bertsimas and Bidkhori (2015) provide us with analytical bounds on the quality of the ADR approximation of a linear ARO problem, which can directly be translated to analytical bounds on the quality of (8) to approximate a concave QO problem.

In (QO), we can assume, without loss of generality, that the matrix Q is symmetric; otherwise, we can replace the objective function with $x^{\top }(\frac{Q^{\top }+Q}{2})x+c^{\top }x$. Now, for a symmetric matrix Q, we know that the eigenvalues are real (O’Nan 1971). Therefore, for an indefinite matrix Q, we can construct the matrices in Theorem 1 in many ways, including the following representations.

Representation 1:

Representation 2:

Representation 3:

where $V\in {\mathbb{R}}^{n_x\times n_x}$ is an orthonormal matrix of eigenvectors of Q, ${\mathrm{\Lambda }}^{+}=\text{Diag}(d_1^{+},\dots ,d_{n_x}^{+})$, ${\mathrm{\Lambda }}^{-}=\text{Diag}(d_1^{-},\dots ,d_{n_x}^{-})$, with $d_i^{+}=\max \{{\lambda }_i+ϵ,ϵ\}$, $d_i^{-}=\min \{{\lambda }_i-ϵ,-ϵ\}$, and ${\lambda }_i$ being the ith eigenvalue of Q, $i=1,\dots ,n_x$. In all representations, a small positive constant $ϵ$ is chosen to ensure that $Q^{+},-Q^{-}\succ 0$.

The representations above offer a natural method to decompose arbitrary indefinite symmetric matrices by expressing them as the sum of one positive and one negative semidefinite matrix, as also discussed in Bomze (2002a, section 5.2).

Considering Representation 1, we see that $Q^{-}$ is a diagonal matrix, but $Q^{+}$ has a similar density as Q. Therefore, in (ARO-QO), all entries of $u_x$ are linked together via $Q^{+}{u}_x$. However, in Representation 2, $Q^{+}$ is a diagonal matrix, implying that the entries of $u_x$ are only linked together via $u_x^{\top }{Q}^{+}{u}_x$ and are not linked in the constraints. In the numerical result section, we will use Representation 2 and Representation 3, showcasing their effectiveness in practical scenarios and their impact on computational efficiency and solution accuracy.

In the rest of this section, we apply the hybrid decision rules to approximate standard quadratic optimization problems.

Example 1.

Let us consider a standard quadratic optimization problem:

$$\underset{x\in \mathrm{\Delta }}{\min } x^{\top }\tilde{Q}x+c^{\top }x.$$

We remark that the quadratic function $x^{\top }\tilde{Q}x+c^{\top }x$ over the unit simplex set can be described as a homogeneous quadratic function $x^{\top }Qx,$ where $Q≔\tilde{Q}+\frac{1}{2}e{c}^{\top }+\frac{1}{2}c{e}^{\top }$. Hence, without loss of generality, the standard QO problem can be represented as follows:

$$\underset{x\in \mathrm{\Delta }}{\min } x^{\top }Qx.$$(StQO)

For an indefinite symmetric matrix $Q\in {\mathbb{R}}^{n_x\times n_x}$, Problem (StQO) is NP-hard in general (Bomze and De Klerk 2002). Using Theorem 2, (StQO) is equivalent to

$$\begin{array}{c}\underset{\tau \in \mathbb{R}}{\max }\tau \\ \text{s}.\text{t}.& \forall x\in \mathrm{\Delta }, \exists (u_x\in {\mathbb{R}}^{n_x},w_x\in \mathbb{R}):\{\begin{array}{l}\frac{1}{2}{x}^{\top }{Q}^{+}x-\frac{1}{2}{u}_x^{\top }{Q}^{+}{u}_x+w_x\ge \tau ,\hfill \\ -Q^{+}{u}_x+e{w}_x\le Q^{-}x,\hfill \end{array}\end{array}$$(ARO-StQO)

where $\tau$ is the static variable, $x\in \mathrm{\Delta }$ is the uncertain parameter, and $(u_x,w_x)\in {\mathbb{R}}^{n_x}\times \mathbb{R}$ is the adjustable variable. According to Theorem 3, applying a hybrid decision rule (i.e., $u_x=u$ and $w_x=z+Zx$) to (ARO-StQO) is equivalent to approximating (StQO) with the following problem:

$$\begin{array}{ll}\underset{\stackrel{x\in {\mathbb{R}}^{n_x}}{\gamma \in {\mathcal{S}}^{n_x}}}{\min }\hfill & x^{\top }{Q}^{+}x+{\displaystyle \sum _{i,j=1}^{n_x}{Q}_{ij}^{-}}{\gamma }_{ij}\hfill \\ \text{s}.\text{t}. \hfill & e^{\top }x=1,\hfill \\ \hfill & e^{\top }\gamma =x^{\top },\hfill \\ \hfill & x\ge 0, \gamma \ge 0.\hfill \end{array}$$(15)

Selvi et al. (2023) show that any optimal solution $(x^{*},{\gamma }^{*})$ of (15) satisfies the sparsity pattern ${\gamma }^{*}=\text{Diag}(x^{*})$. Consequently, the number of decision variables in (15) can be reduced. Moreover, they show that adding a semidefinite constraint $\gamma ⪰x{x}^{\top }$ offers no advantage over the relaxed problem (15). Therefore, the lower bound obtained from the hybrid decision rule on (ARO-StQO) is equivalent to

$$\begin{array}{ll}\underset{x\in {\mathbb{R}}^{n_x}}{\min }\hfill & x^{\top }{Q}^{+}x+\text{diag}{(Q^{-})}^{\top }x\hfill \\ \text{s}.\text{t}. \hfill & e^{\top }x=1,\hfill \\ \hfill & x\ge 0.\hfill \end{array}$$(16)

3.2. FME

In linear ARO problems with fixed recourse, an adjustable variable may be eliminated by employing FME. This approach effectively handles problems involving a limited number of adjustable variables (Zhen et al. 2018).

Note that for a given $x\in \mathcal{X}$, in (ARO-QO), we have the ability to eliminate the adjustable variable $w_x\in {\mathbb{R}}^{m_x}$. We assume without loss of generality that $b\ge 0$. Let $k\in \{1,\dots ,m_x\}$. To eliminate $w_{x_k}$, the kth component of the vector $w_x$, we first isolate it in the constraints:

Because $\mathcal{X}=\{x\in {\mathbb{R}}^{n_x}: Ax=b, x\ge 0\}$ is nonempty, we cannot have $b_k>0$ and $A_{ki}\le 0$ for any $i=1,\dots ,m_x$.

If $A_{ki}\ne 0$ and $b_k>0$, then both sides of their respective constraints can be divided by $A_{ki}$ and $b_k$. This yields an equivalent representation of the feasible region, involving the following constraints:

After the adjustable variable $w_{x_k}$ is eliminated, the feasible set becomes

By continuing the process of FME, the adjustable variable $w_x$ (or some part of it) is eliminated, resulting in a problem with fewer adjustable variables but potentially many more constraints. If the number of constraints in (QO) is limited, then it is computationally efficient to eliminate $w_x$.

In the case of (StQO), applying FME results in a more compact formulation. More explicitly, by applying FME and eliminating the adjustable variable $w_x$, we derive the following equivalent reformulation of (StQO):

The next proposition establishes a connection between approximating the above ARO reformulation and the standard reformulation-linearization technique applied to (StQO).

Proposition 1.

In the (FME-StQO) problem, applying the decision rule $u_x=x$ is equivalent to applying standard reformulation-linearization technique relaxation to (StQO), that is,

$$\begin{array}{ll}\underset{\gamma ,x}{\min }\hfill & {\displaystyle \sum _{i,j=1}^{n_x}{Q}_{ij}}{\gamma }_{ij}\hfill \\ \text{s}.\text{t}. \hfill & e^{\top }x=1,\hfill \\ \hfill & e^{\top }\gamma =x^{\top },\hfill \\ \hfill & x\ge 0, \gamma \ge 0,\hfill \end{array}$$(RLT-StQO)

with the optimal value of ${\min }_{1\le i,j\le n_x}{Q}_{ij}$.

Proof.

Applying the decision rule $u_x=x$ results in

$$\begin{array}{ll}\hfill & \underset{\tau \in \mathbb{R}}{\max } \tau \hfill \\ \hfill & \hspace{0.17em} \text{s}.\text{t}.\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{Q}_{i}x\ge \tau ,\hspace{1em}\forall x\in \mathrm{\Delta },\hspace{1em}i=1,\dots ,n_x,\hfill \end{array}$$(18)

which is equivalent to

$$\begin{array}{ll}\hfill & \underset{\tau \in \mathbb{R}}{\max } \tau \hfill \\ \hfill & \text{s}.\text{t}.\hspace{1em}\underset{x\in \mathrm{\Delta }}{\min }{Q}_{i}x\ge \tau ,\hspace{1em}i=1,\dots ,n_x.\hfill \end{array}$$(L1-StQO)

The extreme points of the unit simplex $\mathrm{\Delta }$ are represented by ${\{e_j\}}_{j=1}^{n_x}$. Because the optimal values are among the extreme point, (L1-StQO) is equivalent to ${\min }_{1\le i,j\le n_x}{Q}_{ij}$. Note that the optimal value of (RLT-StQO) is also ${\min }_{1\le i,j\le n_x}{Q}_{ij}$, because

$${\displaystyle \sum _{i,j=1}^{n_x}{Q}_{ij}}{\gamma }_{ij}\ge {\displaystyle \sum _{i,j=1}^{n_x}\left(\underset{1\le i,j\le n_x}{\min }{Q}_{ij}\right)}{\gamma }_{ij}=\left(\underset{1\le i,j\le n_x}{\min }{Q}_{ij}\right){\displaystyle \sum _{i,j=1}^{n_x}{\gamma }_{ij}}=\underset{1\le i,j\le n_x}{\min }{Q}_{ij},$$

where the first inequality holds because each $Q_{ij}$ is at least as large as ${\min }_{1\le i,j\le n_x}{Q}_{ij}$, the second equality holds because ${\min }_{1\le i,j\le n_x}{Q}_{ij}$ is a constant factor, and the last equality holds due to the constraints $e^{\top }\gamma =x^{\top }$ and $e^{\top }x=1$, which together enforce that the sum of all entries of $\gamma$ must equal one. Thus, ${\min }_{1\le i,j\le n_x}{Q}_{ij}$ is a lower bound on the optimal value of (RLT-StQO). Let $Q_{rs}≔{\min }_{1\le i,j\le n_x}{Q}_{ij}$. Clearly, the solution $(\overline{\gamma },\overline{x})$, where

$${\overline{\gamma }}_{ij}≔\{\begin{array}{ll}1,\hfill & \text{if} i=r \text{and} j=s\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array} \text{and} \overline{x}≔e_r,$$

is feasible for (RLT-StQO) with the objective value of $Q_{rs}$; hence, (RLT-StQO) has the optimal value of ${\min }_{1\le i,j\le n_x}{Q}_{ij}$, which is the same applying the decision rule $u_x=x$ to (FME-StQO). □

In Proposition 1, we see that applying the special linear decision rule $u_x=x$ yields a simple lower bound ($\text{LB}={\min }_{1\le i,j\le n_x}{Q}_{ij}$) to the optimal value of the (StQO) problem. This simple lower bound can be tight if and only if the minimum entry of Q is located on the diagonal; otherwise, the approximation is not tight.

4. Solution Method

In the previous section, we explained how to obtain a lower bound using the techniques from ARO literature. This section first provides an algorithm to obtain a feasible solution and construct an upper bound for a general (QO) and then focuses on (StQO).

4.1. General Quadratic Optimization

After solving the approximated problem (7), we use the obtained solution to extract worst-case scenarios from each constraint of the robust counterpart problem (7). Among these scenarios, we select the one that yields the best objective value for the original (QO) problem. After identifying the most favorable scenario, our attention is redirected to the biconvex reformulation of (QO) problem. Given the selected scenario, we employ the mounting claiming (algorithm Algorithm 1) for (Bi-QO) to improve the quality of the solution. This process ultimately leads us to an upper bound for (QO) problem. The mountain climbing procedure was initially introduced by Konno (1976) for bilinear optimization problems, but can easily be extended to biconvex problems, wherein the variable is partitioned into disjoint sets. For further information regarding the convergence theory of the mountain climbing procedure, we refer to Gorski et al. (2007) and Grippo and Sciandrone (2000).

Algorithm 1

(Mountain Climbing Procedure)

Input: Matrix Q and starting point $x^0$.

Initialization: Decompose $Q=Q^{+}+Q^{-}$ such that $Q^{+},-Q^{-}⪰0$.

Repeat: Execute the following steps:

$$x^{(k+1)}\leftarrow \underset{x\in {\mathbb{R}}^{n_x}}{\text{arg}\hspace{0.17em}\text{min}}\left\{\frac{1}{2}{x}^{\top }{Q}^{+}x+x^{\top }{Q}^{-}{x}^{(k)}+\frac{1}{2}{c}^{\top }x: x\in \mathcal{X}\right\}.$$

 Until: No further improvement is possible.

Output: Solution candidate $x^{(\mathit{\text{end}})}$.

By employing the ARO reformulation, biconvex reformulation, and mounting claiming method, we can efficiently explore and improve the solution space, thereby obtaining an upper bound that closely approaches the optimal value. This approach allows us to make significant progress in refining the solution quality while mitigating computational challenges often associated with large-scale optimization problems. Algorithm 2 presents the pseudo-code of the approach discussed above.

Algorithm 2

(ARO-Based Algorithm to Obtain an Upper Bound for QO)

Input: Matrix Q, vector c, matrix A, and vector b.

Initialization: Decompose $Q=Q^{+}+Q^{-}$ such that $Q^{+},-Q^{-}⪰0$.

(Step 1) Lower Bound: Compute the lower bound for the approximated problem based on the ARO formulation of the QO and hybrid decision rule (see Section 3).

(Step 2) Generation of Worst-Case Scenarios: Generate a finite set of worst-case scenarios by substituting the optimal decision rule into (7).

(Step 3) Set Initial Point: Select from these scenarios the one that yields the best objective value for the original QO problem. Denote this point by $x^{(0)}$.

(Step 4) Improve the Initial Solution: Execute the mountain climbing algorithm starting with the initial solution $x^{(0)}$:

$$x^{(k+1)}\leftarrow \underset{x\in {\mathbb{R}}^{n_x}}{\text{arg}\hspace{0.17em}\text{min}}\left\{\frac{1}{2}{x}^{\top }{Q}^{+}x+x^{\top }{Q}^{-}{x}^{(k)}+\frac{1}{2}{c}^{\top }x: x\in \mathcal{X}\right\}.$$

(Step 5) Termination: Continue (Step 4) until no further improvement is observed.

Output: Final solution candidate $x^{*}≔x^{(\mathit{\text{end}})}$, and the corresponding upper bound value $\text{UB}≔{(x^{*})}^{\top }Q{x}^{*}+c^{\top }{x}^{*}$.

4.2. Standard Quadratic Optimization

Based on our findings in Section 3, we tackle the (StQO) problem using Algorithm 2, generating a finite set of worst-case scenarios in Step 2 based on two lower-bound approximations for (StQO).

4.2.1. Scenario Based on (L1-StQO).

To select scenarios, we can use the following optimization problems:

However, we do not need to solve linear optimization problems in (19) to find ${\{{\overline{x}}^i\}}_{i=1}^{n_x}$ because we only need to consider the extreme points of the unit simplex set, that is, ${\{e_i\}}_{i=1}^{n_x}$. These points provide the natural upper bound (i.e., $e_i{}^{\top }Q{e}_i=Q_{ii}$), which exists in the literature (Gondzio and Yıldırım 2021, lemma 2.1).

To collect additional worst-case scenarios beyond the extreme points of the unit simplex, we also use (FME-StQO), where applying a constant decision rule on $u_x$ (i.e., $u_x=u$) results in

4.2.2. Scenario Based on (L2-StQO).

Using this approximation, we can use the following problem to generate scenarios:

We denote by $x^{(0)}$ the scenario with the lowest objective value from all scenarios, that is,

After choosing $x^{(0)}$ from either of the approaches above, we move to Step 4 of Algorithm 2. In this step by using this initial point, we can improve this initial solution, to get the candidate solution, with its corresponding objective value serving as an upper bound.

5. Numerical Experiments

In this section, we conduct a comprehensive numerical experiment to evaluate the efficacy of Algorithm 2, which we call the ARO-QO algorithm. The efficiency of a particular bound on the optimal value of a mathematical optimization problem is influenced by two key aspects: the precision of the generated bound and the required computational time.

We implement the numerical experiments using MATLAB 2022a. The computations are executed on a laptop equipped with an Intel(R) Core(TM) i5-3210M CPU at 2.50 GHz and 8 GB of RAM. We use YALMIP to pass optimization problems to suitable solvers (Löfberg 2004).

We emphasize that the computational times reported in our experiments exclude the time required by YALMIP to build the model and pass it to solvers, and we merely consider the time consumed by the solvers themselves. In what follows, we present the numerical experiments, specifically focusing on concave quadratic minimization, standard quadratic optimization, and general indefinite quadratic optimization. All the instances and the code are available in the repository Khademi and Marandi (2025).

We use off-the-shelf global solvers to solve the QO problems, namely Gurobi (Gurobi Optimization 2023, version 10.0) and CPLEX (IBM 2019, version 12.9). We specifically use CPLEX version 12.9, as Zhen et al. (2022) reported a bug in the solver of newer versions for solving nonconvex QO problems. It is crucial to highlight that these solvers aim to achieve global solutions. Moreover, MOSEK (MOSEK ApS 2023, version 10.1.15) is used to solve second-order cone optimization problems.

5.1. Concave Quadratic Minimization

Let us consider a concave quadratic minimization over a polyhedron

where $Q\in {\mathbb{R}}^{n_x\times n_x}$, and $-Q⪰0$, $c\in {\mathbb{R}}^{n_x}$, $A\in {\mathbb{R}}^{m_x\times n_x}$, and $b\in {\mathbb{R}}^{m_x}$ are given. From Corollary 1 and Table 6 in Online Supplement C, we have the following linear ARO reformulation of (22):where $\mathcal{X}=\{x\in {\mathbb{R}}^{n_x}: Ax\ge b, x\ge 0\}$. To obtain a lower bound, we consider the following decision rule:where for a given $r\in \{1,2,\dots ,m_x\}$, $z\in {\mathbb{R}}^r$, $Z\in {\mathbb{R}}^{r\times n_x}$, and $w\in {\mathbb{R}}^{(m_x-r)}$ are static variables. It is important to note that for $r=m_x$, we obtain a full affine decision rule, whereas for $r=0$, we have a static decision rule. For other values, we have a partial affine decision rule. Each decision rule type has its own advantages and disadvantages, which we will address later in this section.

In Selvi et al. (2022), the authors propose an approximation solution approach for solving a concave minimization problem via ARO by providing upper and lower bounds, where the lower bound is formulated as a second-order cone optimization problem. Furthermore, the solution method proposed by Ben-Tal and Roos (2022) finds near-optimal solutions to concave minimization problems. This method consists of two main phases. In the initial phase, the method employs several approaches to approximate the original problem with a tractable convex optimization problem. Subsequently, in the second phase, the method employs conditional gradient descent and iterates through various starting points generated in the initial phase, thereby enhancing the quality of the final solution. It is worth mentioning that this method only provides an upper bound on the problem. In this section, we compare the quality of the solution obtained by the ARO-QO algorithm with Gurobi, CPLEX, Selvi et al. (2022), and Ben-Tal and Roos (2022). In all of our numerical experiments, we set a maximum time limit of 3,000 seconds.

We analyze the performance of the upper and lower bound in terms of the optimality gap, which is measured as follows:

where LB is the lower bound and UB is the upper bound for a given instance. Adding the small constant ${10}^{-4}$ in the denominator ensures the prevention of division by zero. Additionally, we analyze the performance of the upper bounds in terms of the solution gap, measured aswhere UB is the objective value of the solution obtained by the specific approach, and ${\text{UB}}^{(\mathit{\text{best}})}$ is the minimum of these bounds over all approaches. Therefore, SGap shows how far a solution from an approach is compared with the best-found solution.

5.1.1. Problem Instances.

First, we consider the seven test instances from section 4.3 of Selvi et al. (2022). We undertake a detailed comparison of three versions of the ARO-QO algorithm (static, partial, and fully affine), Selvi et al. (2022), Ben-Tal and Roos (2022), and global solvers Gurobi and CPLEX. In the lower bound approximation of the ARO-QO algorithm, applying fully static, partially affine (restricting the first $r=\left[\frac{m_x}{7}\right]+1$ of $w_x$ to be affine and the remaining $m_x-r$ to be constant), and fully affine decision rules has distinct effects on the optimality gaps.

Table 1 demonstrates a clear correlation between the type of decision rules and the tightness of optimality gaps within our proposed ARO-QO algorithm. The fully affine ARO-QO algorithm consistently achieves the smallest optimality gaps among its variants, providing the tightest bounds for problems it can solve within the time limit. However, this precision comes at the cost of significantly longer solver times, particularly for larger problems. For instance, Problem 5 required 900.48 seconds, whereas Problems 6 and 7 exceeded the 3,000-second time limit. In contrast, the static and partial ARO-QO algorithms offer a balance between solution quality and speed, achieving competitive optimality gaps within reasonable time frames, especially for larger problems like Problem 7. Global solvers Gurobi and CPLEX demonstrate acceptable performance on smaller instances (Problems 1–6), consistently achieving optimality. However, they struggle with the largest problem (Problem 7), where both solvers reach time limits.

Table 1. Solution and Optimality Gaps for Concave Quadratic Minimization Instances from Selvi et al. (2022)

Although the method of Ben-Tal and Roos (2022) offers a notable balance between solution quality and speed across all problem sizes, by consistently achieving reasonable solution gaps with competitive computation times, the fully static version of our algorithm outperforms their method in all instances. The method of Selvi et al. (2022), although providing relatively quick solutions, typically leads to larger optimality gaps compared with the ARO-QO algorithm due to its less tight lower bounds (see Table 10 in Online Supplement D for more details). Moreover, the solver times for the Selvi et al. (2022) method are generally longer than those of the static ARO-QO algorithm. The results of our analysis indicate that the static ARO-QO algorithm demonstrates superior performance compared with the method proposed by Selvi et al. (2022) when considering both optimality gap and computational efficiency.

Even though the static ARO-QO algorithm yields the highest optimality gap among other decision rules, it stands out for its minimal computation time required to derive both lower and upper bounds. In the static ARO-QO algorithm, based on the structure of Problem (23), the upper bound can be calculated by directly identifying worst-case scenarios and then improving the best one using the mountain climbing procedure to reach a candidate solution. Furthermore, we incorporate the worst-case scenario corresponding to each constraint in (23), resulting in a linear optimization problem that yields the lower bound. Remarkably, in all seven instances, the calculated upper bound is obtained computationally efficiently with good solution quality. Compared with alternative approaches—such as partial or full affine ARO-QO algorithms, or using the methods of Selvi et al. (2022) and Ben-Tal and Roos (2022)—the static ARO-QO algorithm demonstrates a faster computation process in reaching a candidate solution.

After considering the seven test instances of Selvi et al. (2022), we randomly generate large-size instances. For a meaningful comparison of the mentioned approaches, we evaluate the quality of the bounds on the objective value of Problem (22) using 15 groups of random instances, with the dimension $n_x$ taking value in $\{50,100,\dots ,600,700\}$ with the number of constraints $m_x=n_x+50$ and $m_x=n_x+100$. Each group contains five instances of the same size, which are generated similarly to those created in Selvi et al. (2022).

Table 2 presents a comparison of various methods for 15 groups of increasing size. For each group, the table lists the mean optimality gap, solution gap, and solver time, with standard deviations shown in brackets (see Table 7 in Online Supplement D for more details). Boldface numbers highlight the best solution gap, and underlined numbers highlight the best optimality gap in each group.

Table 2. Statistic of Solution and Optimality Gaps and Solver Times for Randomly Generated Concave Minimization Instances

Our proposed (static) ARO-QO algorithm demonstrates remarkable consistency, maintaining strong performance across all problem dimensions. It achieves the best optimality gaps for larger problems (Groups 6–15), with the average optimality gap being less than 2% for all groups, and solves all instances within the time limit with very low solution gaps. Notably, the ARO-QO algorithm exhibits the lowest computation time compared with other methods in each group, underscoring its efficiency in balancing time and gap management across these instances. The method by Selvi et al. (2022) displays more consistent optimality gaps across all problem groups, despite being significantly higher than those of Gurobi and CPLEX for the smaller instances. The method of Ben-Tal and Roos (2022) consistently achieves the best average solution gap, which is always below 0.05%, with a maximum standard deviation of 0.12% across all problem sizes, although it cannot provide optimality gaps.

Global solvers Gurobi and CPLEX perform exceptionally well for smaller problems (Groups 1–3), with Gurobi achieving very low optimality gaps. However, they begin to struggle with larger problems from Group 4 onward. Gurobi and CPLEX have acceptable solution gaps up to Group 7, but Gurobi could not find feasible solutions for instances in Groups 14 and 15, whereas CPLEX failed to find feasible solutions for instances in Groups 8–15, all within the given 3,000-second time limit. This highlights the challenges these solvers face with large-scale instances.

5.2. Standard Quadratic Optimization

Let us consider a standard quadratic optimization problem

where $Q\in {\mathbb{R}}^{n_x\times n_x}$ is an indefinite symmetric matrix.

In Proposition 1, we see that applying the special linear decision rule $u_x=x$ after eliminating an adjustable variable yields a lower bound approximation problem (RLT-StQO) to the optimal value of the (StQO) problem. Adding the additional semidefinite constraint $\gamma ⪰x{x}^{\top }$ in (RLT-StQO) results in a progressively tighter bound. However, this comes at the expense of significant computational demands (Selvi et al. 2023). For large-sized problems, this bound frequently encounters “out-of-memory” errors during the solving process, making it generally inapplicable.

Gondzio and Yıldırım (2021) propose an exact mixed-integer linear optimization (MILO) reformulation for (StQO):

where nonnegative parameter $M\in {\mathbb{R}}^{n_x}$ depends on a lower bound of the optimal value of (StQO), ensuring that the optimal value of (MILO-StQO) is equivalent to the optimal value of (StQO).

We will explore how to enhance the solution quality of the (MILO-StQO) formulation by integrating the ARO-QO algorithm.

5.2.1. Problem Instances.

It is of paramount importance to note that, with a high probability, global solutions of randomly generated (StQO) instances are located either at vertices or edges of the standard simplex (Bomze et al. 2018). In order to make a fair comparison, we do not generate naive random instances in our study because our upper bound methodology would be optimal in these cases. Instead, we concentrate on using instances from well-known data sets or employing their patterns to generate new instances, as outlined by Liuzzi et al. (2019).

5.2.2. Detailed Results.

We consider 15 groups each of which contains five instances with the dimension $n_x$ taking values in $\{500,600,700,800,900\}$. These test problems were generated using the pattern described in Liuzzi et al. (2019) and Scozzari and Tardella (2008). Another important factor affecting the performance of different solution methods is the density of matrix Q. We examine three density values for each dimension: 50%, 75%, and 90%. For further details, we refer the reader to Scozzari and Tardella (2008).

In the initial comparison, we evaluate the quality of the ARO-based upper bound approximation against CPLEX local search. Setting cplex.optimalitytarget option to 2 allows CPLEX to solve indefinite quadratic optimization problems locally. This configuration guarantees solutions that satisfy first-order optimality conditions but not necessarily global optimality. Analysis of these bounds, obtained through local solution methods, provides insights into the problem’s computational complexity.

Table 3 provides statistics on the solution gap and the time it takes for ARO-QO and CPLEX to obtain a solution. As one can see, the ARO-QO algorithm demonstrates frequently better performance compared with CPLEX local search in terms of upper bound quality and computational efficiency. More specifically, the ARO-QO algorithm outperforms CPLEX local search in 46 of 75 instances, whereas CPLEX local search produces better upper bounds in only 28 instances, with 1 instance resulting in equal performance (see Table 8 in Online Supplement D). This comparison highlights the ARO-QO algorithm’s consistent ability to generate good upper bounds for most test instances. Overall, across all instances, the average solution gaps are 4.15% and 5.75% (with the maximum value of 14.53% and 19.73%), respectively, for ARO-QO and CPLEX. From a solution time perspective, the ARO-QO algorithm also exhibits better performance. It consistently solves instances more quickly. In Table 3, we see that ARO-QO Algorithm outperforms CPLEX local in solution quality for 11 of 15 problem groups, particularly excelling in larger instances.

Table 3. Comparison of Solution Gaps and Solver Times for Standard Quadratic Optimization Instances Between ARO-QO Algorithm and CPLEX Local Search

Given that our approach obtained a good solution, we use it to improve the performance of (MILO-StQO) reformulation. Specifically, because the objective function of (MILO-StQO) is linear, we can restrict the objective function to only get values between the valid lower and upper bounds, that is, $\text{LB}\le \alpha \le \text{UB}$, potentially accelerating convergence and improving solution quality by guiding the solver toward more promising areas of the search space. It is worth mentioning that Gondzio and Yıldırım (2021) used $\text{UB}≔{\min }_{1\le i\le n_x}{Q}_{ii}$ as a natural upper bound, which corresponds to the best objective value achievable for (StQO) when restricted to the vertices of the unit simplex. For the lower bound, they used a tight SDO-based bound. However, in our instances, because of out-of-memory errors, this type of bound is not applicable, so we use (L1-StQO) as a valid lower bound. We remark that there exist other lower bounds in the literature (Bomze et al. 2008, Liuzzi et al. 2019).

Based on the upper bound UB obtained from the ARO-QO algorithm, we first generate a feasible solution $(\overline{x},\overline{y},\overline{z},\overline{\alpha })$ for (MILO-StQO) such that $\overline{\alpha }\le \text{UB}$. To do so, we use CPLEX, because it has fast heuristic algorithms to find a feasible solution for MILOs. We then use this solution as a warm starting point for (MILO-StQO) and add the extra objective cut LB$\le \alpha$.

In this part of the numerical results, we compare the following approaches to solve (StQO): the original (MILO-StQO); its variant with the additional LB and UB cuts (MILO-L-U), where UB is the natural upper bound (as in Gondzio and Yıldırım (2021)); and its variant with LB cut and ARO-based warm start (ARO-QO-MILO). Additionally, we compare these with global solvers Gurobi and CPLEX. All (MILO-StQO) versions are solved using Gurobi as the MILO solver.

Table 4 shows the statistics of the results. In this table, the first column represents the group of instances, including the number of variables ($n_x$) and the density (d). The subsequent columns are organized into five different solution methods. For each method, three performance metrics are reported: optimality gap, solution gap, and solver time in seconds. Each cell contains the mean value and standard deviation in brackets. Bold numbers indicate the best (lowest) solution gap, whereas underlined numbers show the best (lowest) optimality gap for each group. An asterisk in the time column indicates that the method is terminated due to the time restriction.

Table 4. Statistic of Solution and Optimality Gaps and Solver Times for Standard Quadratic Optimization Instances

For small instances ($n_x=500$), all MILO variants perform well, often with zero gaps. MILO-L-U and ARO-QO-MILO are typically faster. As problem size increases, all methods reach the time limit, and performance differences become clearer. ARO-QO-MILO significantly improves solution quality, consistently achieving the best optimality and solution gaps, even for larger problems. Detailed results are in Table 8 of Online Supplement D.

The ARO-QO-MILO’s benefits are evident in its consistent outperformance of MILO-L-U, especially regarding solution quality. In contrast, both Gurobi and CPLEX struggle with larger instances, consistently producing higher optimality and solution gaps compared with the MILO variants. CPLEX, in particular, shows extremely large optimality gaps for all problem sizes. These results suggest that ARO-QO-MILO is promising for enhancing the performance of MILO reformulations for quadratic optimization problems. This method is particularly valuable for larger instances where global solvers may struggle.

5.3. General Quadratic Optimization

In our final experiment, we consider a general quadratic optimization problem:

where $Q\in {\mathbb{R}}^{n_x\times n_x}$ is an indefinite matrix, and $c\in {\mathbb{R}}^{n_x}$, $A\in {\mathbb{R}}^{m_x\times n_x}$, and $b\in {\mathbb{R}}^{m_x}$ are given.

From Theorem 2, we know that the above problem can be rewritten as

We examine three distinct versions of the ARO-QO algorithm, denoted as static ARO-QO, linear ARO-QO, and affine ARO-QO, each employing different decision policies. Static ARO-QO uses a static decision rule with $u_x=u$ and $w_x=w$, linear ARO-QO employs a decision rule with $u_x=x$ and $w_x=w$, and affine ARO-QO utilizes a special affine decision rule with $u_x=x$ and $w_x=Zx+z$, where $u\in {\mathbb{R}}^{n_x}$, $w\in {\mathbb{R}}^{m_x}$, $Z\in {\mathbb{R}}^{m_x\times n_x}$, and $z\in {\mathbb{R}}^{m_x}$ are static variables. To implement the ARO-QO algorithm and its variants, we use MOSEK as a convex optimization solver.

In Xia et al. (2020), the authors propose an exact MILO reformulation of Problem (24)

This reformulation is based on the KKT conditions. The authors introduce binary variables z and big-M parameters (U and V) to linearize the nonconvex complementarity constraints in the KKT conditions. The parameters $U\in {\mathbb{R}}^{n_x}$ and $V\in {\mathbb{R}}^{n_x}$ are determined by solving a series of linear optimization problems. For a more detailed explanation of this reformulation technique, see Xia et al. (2020). In the remainder of this section, we consider (MILO-QO) as a benchmark approach and utilize Gurobi to solve it.

5.3.1. Problem Instances.

We generate a square matrix Q using the formula $Q=P\mathrm{\Lambda }{P}^{\top }$, where P is an orthogonal matrix obtained from the QR decomposition of a random matrix, and $\mathrm{\Lambda }$ is a diagonal matrix with components sampled uniformly from the interval $[-5,5]$. We know that (QO) is NP-hard even when Q has only one negative eigenvalue (Pardalos and Vavasis 1991). To explore the problem’s behavior across different scenarios, we generate Q in three cases based on its convexity rank (which we define as the number of positive eigenvalues). We consider low, medium, and high convexity ranks, corresponding to 10%, 50%, and 90% of the eigenvalues being positive, respectively. We also generate the matrix A and the vector c with components from the interval $[-5,5]$ uniformly. To ensure the feasible region is bounded and feasible, we add a row of ones to the matrix A and set $b≔A(\frac{1}{2}e)$.

5.3.2. Detailed Results.

We consider 15 groups, each of which contains five instances, with the dimension $n_x$ taking values in $\{20,50,100,200,1,000\}$. To ensure a large feasible set, we set the number of constraints $m_x$ to $\frac{n_x}{5}$. These test problems were generated using the mentioned pattern with the same convexity rank in each group.

The statistics of the results of solution gaps, optimality gaps, and solver times are presented in Table 5, where the first column in each represents the group of instances with the number of variables ($n_x$), number of constraints ($m_x$), and convexity rank of the matrix Q (p), respectively.

Table 5. Statistics of Solution and Optimality Gaps and Solver Times for General Quadratic Optimization Instances

Static ARO-QO variants consistently outperform the CPLEX local search in terms of solution quality. Static ARO-QO with Representation 2 and Representation 3 achieve average solution gaps of 2.80% and 2.08%, respectively, compared with 11.15% for CPLEX local search across all instances. The superiority of static ARO-QO is further emphasized by the maximum solution gaps observed: 34.26% for Representation 2, 28.66% for Representation 3, and a substantial 92.53% for the CPLEX local search.

For smaller instances (Groups 1–6), all methods perform well, with MILO-QO, Gurobi, and CPLEX often achieving optimal solutions. The ARO methods show progressive improvement as their complexity increases from static to linear and then affine variants, specifically lower bound for low convexity rank groups.

For medium-sized instances (Groups 7–12), a significant performance shift becomes apparent. MILO-QO struggles, often failing to find solutions within the time limit. Although Gurobi and CPLEX do find solutions, they generally exhibit higher optimality gaps than the ARO-QO family. However, on larger problems, Gurobi and CPLEX outperform MILO-QO, frequently finding solutions where MILO-QO fails. The ARO-QO family consistently achieves lower optimality gaps more rapidly. For example, in Group 7, the ARO-QO family consistently outperforms all others in terms of both optimality and solution gaps while maintaining reasonable computation times. Specifically, affine ARO-QO achieves the best optimality gap, and linear ARO-QO achieves the best solution gap. In contrast, MILO-QO, Gurobi, and CPLEX struggle to find good solutions within the given time limit, demonstrating the superiority of the ARO-QO family for this group of instances.

The ARO-QO algorithm variants begin to outperform the MILO-QO reformulation and the global solvers Gurobi and CPLEX for medium-sized instances. This trend becomes even more evident for large instances (Groups 13–15), where only static ARO-QO and linear ARO-QO consistently provide solutions and lower bounds within acceptable solver times, whereas MILO-QO, Gurobi, and CPLEX fail to provide any solutions for these instances.

The impact of convexity rank is evident across all problem sizes. With increasing p, the function approaches convexity, making it easier to obtain a good solution, as shown in Table 5. In contrast, nonconvex QO problems with a lower convexity rank (i.e., a higher number of negative eigenvalues in Q) are generally more challenging to solve due to their complex landscape and the potential presence of multiple local optima, which complicates the search for the global optimum. However, a small value of p in ARO-QO often yields the best solutions as well. According to Section 5.1, we know that for $p=0$, ARO outperforms to finding near-optimal solutions and acceptable optimality gaps. The results demonstrate that for $p=0.1$, the optimality gap achieved by the ARO approaches remains small across all instances. As the problem size increases, and with lower p values, ARO methods maintain their effectiveness while other methods struggle or fail to provide viable solutions. This highlights the robustness of ARO approaches, especially in challenging scenarios where global solvers and MILO-QO reformulation falter. The consistent ability of ARO methods to deliver high-quality solutions with reasonable computational effort across diverse problem characteristics underscores their value in addressing complex quadratic optimization challenges.

6. Conclusions

We introduce a novel reformulation technique that enables the QO problem to be recast as an ARO problem. This process begins by demonstrating that any QO problem can be transformed into a disjoint biconvex QO problem. Following this, we propose an equivalent ARO reformulation. Specifically, we illustrate that employing a so-called decision rule technique to approximate the ARO reformulation equates to using a reformulation-linearization technique on original QO problem. The ARO reformulation offers a new approach to solving nonconvex QO problems by transferring the complexity from the original problem to its equivalent ARO counterpart. Specifically, in the concave QO problem, our ARO model transforms into a linear ARO, whereas in the indefinite QO problem, it becomes a nonlinear ARO. Moreover, we develop an algorithm capable of identifying near-optimal solutions using our novel reformulations. We demonstrate the effectiveness of our ARO-based method in solving a class of quadratic optimization problems through numerical experiments, showing that it can yield high-quality solutions with reasonable computational costs. This established connection between QO and ARO provides a new perspective on addressing the challenges of nonconvex QO problems and opens up new possibilities for further research in the field of mathematical optimization.