Abstract
In this paper, we deal with exact semidefinite programming (SDP) reformulations for a class of adjustable robust quadratic optimization problems with affine decision rules. By virtue of a special semidefinite representation of the non-negativity of separable non-convex quadratic functions on box uncertain sets, we establish an exact SDP reformulation for this adjustable robust quadratic optimization problem on spectrahedral uncertain sets. Note that the spectrahedral uncertain set contains commonly used uncertain sets, such as ellipsoids, polytopes, and boxes. As special cases, we also establish exact SDP reformulations for this adjustable robust quadratic optimization problems when the uncertain sets are ellipsoids, polytopes, and boxes, respectively. As applications, we establish the corresponding results for fractionally adjustable robust quadratic optimization problems.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
As a special class of nonlinear optimization problems, quadratic optimization has received extensive attention by many researchers and used in a wide range of fields, such as game theory, signal processing, and portfolio optimization. In recent years, there have been various excellent works on the investigation of quadratic optimization problems from different perspectives, see [1, 2, 15, 16, 23, 33, 34, 36] and the references therein.
Recently, quadratic optimization problems with uncertain data have attracted extensive interest of many researchers due to their applications in different fields of mathematics, engineering, and economics. Robust optimization approach [4, 6, 17] is a powerful methodology for dealing with quadratic optimization problems with uncertain data. For example, by using the robust optimization methodology, second-order cone programming reformulation problems for convex quadratic optimization problems on different kinds of uncertain sets are obtained in [26]. Exact second-order cone programming relaxations are established in [19] for non-convex minimax separable quadratic optimization problems with multiple separable quadratic constraints. In [24], exact copositive optimization reformulations are obtained for robust quadratic optimization problems with uncertain parameters containing both continuous and integer components. In [13], a deterministic approach is given to examine robust optimality conditions and find robust efficient solutions of convex quadratic multiobjective optimization problems with uncertain data. By virtue of a new robust type characteristic cone constraint qualification, second-order conic programming dual of robust convex quadratic optimization problems on polytopic and norm uncertain sets is considered in [37].
Note that all of the above papers are concentrated on the investigation of static (single-stage) robust optimization models, containing only “here and now” decisions variables. This means that before obtaining complete information about uncertain parameters, we must now determine their values [9, 10, 21, 27,28,29, 31]. However, many dynamic decision models contain not only “here-and-now” (first-stage) decision variables, but also “wait-and-see” (second-stage) decision variables which are assigned numerical values after some of the uncertain parameters are known. Adjustable robust optimization, introduced in [3], is an important deterministic methodology to deal with optimization problems involving both “here-and-now” and “wait-and-see” decision variables. Although there are few papers in the literature devoted to adjustable robust quadratic optimization problems, see, for example, [7, 8, 11, 12, 32, 35], adjustable robust quadratic optimization problems have received far less attention than others. This is a main motivation for the investigation of adjustable robust quadratic optimization problems in this paper.
Motivated by the works reported in [7, 12], this paper will establish exact SDP reformulations for a class of adjustable robust quadratic optimization problems with affine decision rules on spectrahedral uncertain sets [25, 30]. More precisely, by using a special semidefinite representation of the non-negativity of separable non-convex quadratic functions on box uncertain sets, we show that this adjustable robust quadratic optimization problem admits an exact SDP reformulation problem in the sense that they share the same optimal values and their optimal solutions are one-to-one correspondence. The result obtained provides us with a way to investigate adjustable robust quadratic optimization problems by considering the corresponding SDP reformulation problems. For ellipsoidal, polytopic, and box uncertain sets, we also establish exact SDP reformulations for adjustable robust quadratic optimization problems. We show that our results cover as special cases of some optimization problems considered in the recent literature [12, 32]. Furthermore, as an application, the proposed approach is applied to investigate exact SDP reformulations for fractionally adjustable robust quadratic optimization problems on spectrahedral uncertain sets.
The rest of the paper is organized as follows. In Section 2, we recall some basic notions and introduce an adjustable robust quadratic optimization problem. In Section 3, we establish exact SDP reformulations for adjustable robust quadratic optimization problems on spectrahedral uncertain sets. In Section 4, we consider exact SDP reformulations for fractionally adjustable robust quadratic optimization problems.
2 Preliminaries and Auxiliary Results
Unless otherwise specified, \(\mathbb {R}^{n}\) signifies the n-dimensional Euclidean space equipped with the usual Euclidean norm \(\Vert \cdot \Vert \). The inner product in \(\mathbb {R}^n\) is defined by \(\langle x,y\rangle :=x^{\top }y\), for all \(x,y\in \mathbb {R}^n\). The zero vector of \(\mathbb {R}^n\) is denoted by \(0_n\). The non-negative orthant of \(\mathbb {R}^{n}\) is denoted by \(\mathbb {R}^n_+:=\left\{ (x_1,\dots ,x_n)\in \mathbb {R}^n~|~x_i\ge 0,i=1,\dots ,n\right\} \). The space of all symmetric \(n\times n\) matrices is denoted by \(\mathbb {S}^{n}\). \(M\in \mathbb {S}^{n}\) is said to be a positive semidefinite matrix, denoted by \(M\succeq 0,\) iff \(x^{\top }Mx\ge 0,\) \( \forall x\in \mathbb {R}^n.\) Moreover, \(M\in \mathbb {S}^{n}\) is said to be a positive definite matrix, denoted by \(M\succ 0,\) iff \(x^{\top }Mx>0,\) \(\forall x\in \mathbb {R}^n\setminus \{0_n\}.\) The symbol \(I_n\) stands for the \(n\times n\) identity matrix, and the symbol \(\text{ O}_{n \times n}\in \mathbb {R}^{n\times n}\) stands for the \(n\times n\) matrix of all zeros. The matrix \(D:= \text{ diag }(r_1,\dots ,r_n)\in \mathbb {R}^{n\times n}\) stands for the diagonal matrix with \(r_i\in \mathbb {R},\) \(i=1,\dots ,n.\)
In what follows, let \(Q_0\in \mathbb {S}^{n},\) \(q_0\in \mathbb {R}^n\), \(\xi _0\in \mathbb {R},\) \(Q_i:=diag (a_1^i,\dots ,a_n^i)\in \mathbb {R}^{n\times n} \), \(q_i:=(q^1_i,\dots ,q^n_i)\in \mathbb {R}^n \), \(q^i_k:=(q_{k}^{i1},\dots ,q_{k}^{in})\in \mathbb {R}^n,\) \(\xi _i\in \mathbb {R}\) and \(\xi ^i_k\in \mathbb {R},\) \(k=1,\dots ,p,\) \(i=1,\dots ,l.\) In this paper, we consider the following uncertain quadratic optimization problem
where \(f_0(x):=x^{\top }Q_0x+q_0^{\top }x+\xi _0\) and \(f_i(x,u^i):=x^{\top }Q_ix+q_i^{\top }x+\xi _i+\sum _{k=1}^p u^i_k\left( (q^i_k)^{\top }x+\xi ^i_k\right) ,\) \(i=1,\dots ,l\). \(u^i:=(u_1^i,\dots ,u_p^i)\in \mathbb {R}^p\), \(i=1,\dots ,l\), are uncertain parameters, belonging to the following spectrahedral uncertain sets [25, 30]
where \(A^i\) and \(A^i_k,\) \(i=1,\dots ,l,\) are symmetric matrices. Note that the spectrahedral uncertain sets in (1) are closed convex sets covering the most commonly used uncertain sets often encountered in robust optimization problems, such as ellipsoids, polytopes, and boxes [14, 29].
The problem \(\text{(UP) }\) with adjustable decision variables can be captured by
where \(g_i(y(z)):=(y(z))^{\top }B_iy(z)+b_i^{\top }y(z)+t_i\), \(i=0,1,\dots ,l,\) with \(B_i:=diag (\theta _1^i,\dots ,\theta _m^i)\in \mathbb {R}^{m\times m},\) \(b_i:=(b^1_i,\dots ,b^m_i)\in \mathbb {R}^m\) and \(t_i\in \mathbb {R}\). Here, \(x:=(x_1,\dots ,x_n)\in \mathbb {R}^n\) is the first-stage (here-and-now) decision variable and \(y(\cdot )\in \mathbb {R}^m\) is the second-stage (wait-and-see) decision variable, which is an adjustable decision variable that depends on the uncertain parameter \(z:=(z_1,\dots ,z_m)\in \mathbb {R}^m\) in a box uncertain set
In what follows, we assume that \(y(\cdot )\) is an affinely adjustable variable in the sense that it satisfies the affine decision rule [5] given by
where \(\rho :=(\rho _1,\dots ,\rho _m)\in \mathbb {R}^m\) and \(W:=diag (\omega _1,\dots ,\omega _m)\in \mathbb {R}^{m\times m}\) are non-adjustable variables.
For (UTP) with the affine decision rule (2), it is usually associated with the robust (worst-case) counterpart given below:
To present the exact SDP reformulation of (RTP), we recall the following results, which play a key role in the sequel.
Lemma 2.1
[12] Let \(\alpha \in \mathbb {R},\) \(v:=(v_1,\dots ,v_m)\in \mathbb {R}^m\) and \(W:=diag (\omega _1,\dots ,\omega _m)\), where \(\omega _j\in \mathbb {R},\) \(j=1,\dots ,m.\) Then, the following statements are equivalent:
(i) The following implication holds
where \(\beta _j,\gamma _j\in \mathbb {R}\) with \(\beta _j\le \gamma _j,\) \(j=1,\dots ,m.\)
(ii) There exist \(\alpha _j\in \mathbb {R},\) \(j=1,\dots ,m,\) such that \(\sum _{j=1}^m \alpha _j\le \alpha \) and
where \(\Sigma _4^2[z_j]\) denotes the set consisting of all the sum of squares polynomials with variable \(z_j\) and degree at most 4, \(h_j^1(z_j):=(1+z_j^2)^2,\) \(h_j^2(z_j):=(\beta _j+\gamma _jz_j^2)(1+z_j^2)\) and \(h_j^3(z_j):=(\beta _j+\gamma _jz_j^2)^2\) for \(z_j\in \mathbb {R}.\)
(iii) There exist \(\alpha _j\in \mathbb {R}\) and \( X^j:= \left( \begin{array}{lll} X_{11}^j ~X_{12}^j ~X_{13}^j\\ X_{12}^j ~X_{22}^j ~X_{23}^j\\ X_{13}^j ~X_{23}^j ~X_{33}^j \end{array}\right) \succeq 0,\) \(j=1,\dots ,m, \) such that \(\sum _{j=1}^m\alpha _j\le \alpha \) and
3 Exact SDP Reformulations for (RTP)
In this section, we establish an exact SDP reformulation for (RTP) in terms of a special semidefinite representation of the non-negativity of separable non-convex quadratic functions on box uncertain sets. For convenience, let \(u:=(u^1,\dots ,u^l)\in \mathbb {R}^{pl}\) with \(u^i:=(u_1^i,\dots ,u_p^i)\in \mathbb {R}^{p},\) \(\delta :=(\delta _1,\dots ,\delta _l)\in \mathbb {R}^{lm}\) with \(\delta _i:=(\delta ^1_i,\dots ,\delta ^m_i)\in \mathbb {R}^{m},\) \(\sigma :=(\sigma _1,\dots ,\sigma _m)\in \mathbb {R}^m,\) \(X:=(X^{11},\dots ,X^{1m},\dots ,X^{l1},\dots ,X^{lm})\in \mathbb {R}^{3\times 3lm}\) with \(X^{ij}\in \mathbb {S}^3,\) \(Y:=(Y^1,\dots ,Y^m)\in \mathbb {R}^{3\times 3m}\) with \(Y^j\in \mathbb {S}^3,\) \(i=1,\dots ,l,\) \(j=1,\dots ,m.\)
Now, we propose a SDP reformulation for the problem (RTP) as follows:
The following theorem describes an exact SDP reformulation for (RTP) in the sense that (RTP) and (SDP) share the same optimal values and their optimal solutions are one-to-one correspondence.
Theorem 3.1
Consider the problem \(\mathrm {(RTP)}\) with \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) given by (1) and its reformulation problem \(\mathrm {(SDP)}\). Then,
Moreover, \((x,\rho ,W)\) is an optimal solution of the problem \(\mathrm {(RTP)}\) if and only if there exist \(\tau \in \mathbb {R},\) \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl},\) \(X \in \mathbb {R}^{3\times 3lm},\) \(\sigma \in \mathbb {R}^m\) and \(Y \in \mathbb {R}^{3\times 3\,m}\) such that \((x,\rho ,W,\tau ,\delta ,u,X,\sigma ,Y)\) is an optimal solution of the problem \(\mathrm {(SDP)}\).
Proof
Obviously, \(\mathrm {(RTP)}\) is equivalent to
Note that \(\tau \) is an auxiliary variable and adding it does not cause the optimal value to change. Therefore, it is sufficient to show that the feasible sets between \(\mathrm {(RTP_0)}\) and \(\mathrm {(SDP)}\) are equivalent.
Now, let \((x,\rho ,W,\tau ,u )\) be a feasible solution of \(\mathrm {(RTP_0)}\). This means that
and
From Lemma 2.1 and (6), there exist \(\delta _i^j\in \mathbb {R}\) and \( X^{ij}:= \left( \begin{array}{lll} X_{11}^{ij} ~X_{12}^{ij} ~X_{13}^{ij}\\ X_{12}^{ij} ~X_{22}^{ij} ~X_{23}^{ij}\\ X_{13}^{ij} ~X_{23}^{ij} ~X_{33}^{ij} \end{array}\right) \succeq 0, ~i=1,\dots ,l, ~j=1,\dots ,m, \) such that
and
Moreover, (4) and (5) amount to
Similarly, from Lemma 2.1 and (9), there exist \(\sigma _j\in \mathbb {R}\) and \( Y^{j}:= \left( \begin{array}{lll} Y_{11}^{j} ~Y_{12}^{j} ~Y_{13}^{j}\\ Y_{12}^{j} ~Y_{22}^{j} ~Y_{23}^{j}\\ Y_{13}^{j} ~Y_{23}^{j} ~Y_{33}^{j} \end{array}\right) \succeq 0, ~j=1,\dots ,m, \) such that
and
Together with (7), (8), (10) and (11), it follows that the problems \(\mathrm {(RTP)}\) and \(\mathrm {(SDP)}\) are equivalent in the sense that
Moreover, \((x,\rho ,W)\) is a feasible solution of the problem \(\mathrm {(RTP)}\) if and only if there exist \(\tau \in \mathbb {R},\) \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl},\) \(X \in \mathbb {R}^{3\times 3lm},\) \(\sigma \in \mathbb {R}^m\) and \(Y \in \mathbb {R}^{3\times 3\,m}\) such that \((x,\rho ,W,\tau ,\delta ,u,X,\sigma ,Y)\) is an optimal solution of the problem \(\mathrm {(SDP)}\). The proof is complete.
Remark 3.1
Note that similar results for exact SDP reformulations of adjustable robust linear optimization problems have been investigated in [12, Theorem 3.1]. However, Theorem 3.1 extends these results from linear optimization models to quadratic optimization models.
The following example illustrates how to obtain robust optimal solutions and the corresponding optimal value of (RTP) on spectrahedral uncertain sets by Theorem 3.1.
Example 3.1
For problem (UTP). Let \(n=p=m:=2\) and \(l:=4.\) The uncertain sets \(\mathcal {U}^i,\) \(i=1,\dots ,4\), are defined by
Obviously, by (1), we have
Let \(f_0(x):=x_1+x_2\), \(g_0(y(z)):=0,\) \(f_1(x,u^1):=x_1^2-3x_1-x_2+u^1_1\), \(g_1(y(z)):=\left( 0,-1\right) ^{\top }y(z)-3,\) \(f_2(x,u^2):=-2x_2\), \(g_2(y(z)):=2,\) \(f_3(x,u^3):= -3x_1 \), \(g_3(y(z)):= 3,\) \(f_4(x,u^4):=x_2^2-x_1-u^4_2\), and \(g_4(y(z)):=\left( 1,0\right) ^{\top }y(z).\) Let the affine decision rule \(y(\cdot )\) be given by \( y(z):=\rho +W z, \) where \(\rho :=(\rho _1,\rho _2)\in \mathbb {R}^2,\) \(W:=diag (\omega _1,\omega _2)\in \mathbb {R}^{2\times 2}\) and \(z:=(z_1,z_2)\in \mathcal {U}_{box}:=[-1,1]\times [0,2]\). In this setting, (RTP) becomes
It is easy to show that the problem (RTP) admits an optimal solution \(( {x}, {\rho }, {W})\) with \( {x}=(1,1),\) \( {\rho }=(-151,151)\) and \( {W}=\text{ O}_{2\times 2}.\) Moreover, \(\min \mathrm {(RTP)}=2.\)
Now, we apply Theorem 3.1 to show that \(( {x}, {\rho }, {W})\) is an optimal solution of (RTP). Clearly, the SDP reformulation of (RTP) becomes
Using the Matlab toolbox CVX [18], we solve (SDP). The solver returns \(\min \mathrm {(RTP)}=2\) and an optimal solution of (SDP) as \((x,\rho ,W,\delta ,u,X)\), where \(x=(1.0000,1.0000),\) \(\rho =(-151.0951, 151.4487),\) \(W=\left( \begin{array}{lll} 0.1148 &{} ~0.0000 \\ 0.0000 &{} -0.1148 \end{array}\right) ,\) \(\delta =(50.1210,50.0255,4.9909\times 10^{-10},1.4983\times 10^{-9},2.2255\times 10^{-9},2.2255\times 10^{-9},49.9106,50.1210)\), \(u=(u^1,u^2,u^3,u^4)\) with \(u^i=(-1.9376\times 10^{-20},-2.7868\times 10^{-20}),\) \(i=1,\dots ,4,\) and \(X:=(X^{11},X^{12},X^{21},X^{22},X^{31},X^{32},X^{41},X^{42})\) with \( X^{11}=\left( \begin{array}{lll} 50.1210 &{}~0.000 &{}~10.0608\\ 0.0000 &{}~80.1204 &{}~0.0000\\ 10.0608 &{}~0.0000 &{}~50.1210 \end{array}\right) ,\) \( X^{12}=\left( \begin{array}{lll} 50.0255 &{}~0.000 &{}~9.9271 \\ 0.0000 &{}~79.9670 &{}~0.0000\\ 9.9271 &{}~0.0000 &{}~49.7958 \end{array}\right) ,~~~~~\) Thus, by Theorem 3.1, \(( {x}, {\rho }, {W})\) is an optimal solution of (RTP).
Now, let us consider special cases of (RTP). In the special case when \(B_0=\text{ O}_{m\times m},\) \(b_0=0_m\) and \(t_0=0\), (RTP) collapses to
and its SDP reformulation becomes
By virtue of Theorem 3.1, we can easily obtain the following result.
Corollary 3.1
Consider the problem \(\mathrm {(RTP_1)}\) with \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) given by (1) and its reformulation problem \(\mathrm {(SDP_1)}\). Then,
Moreover, \((x,\rho ,W)\) is an optimal solution of \(\mathrm {(RTP_1)}\) if and only if there exist \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl}\) and \(X \in \mathbb {R}^{3\times 3lm}\) such that \(\left( x,\rho ,W,\delta ,u,X \right) \) is an optimal solution of the problem \(\mathrm {(SDP_1)}\).
In the special case when (RTP) with \(t_0=0\) and \(Q_i=B_i=\text{ O}_{m\times m},\) \(i = 0,1,\dots ,l,\) (RTP) collapses to the following adjustable robust linear optimization
and its SDP reformulation becomes
Corollary 3.2
Consider the problem \(\mathrm {(RTP_2)}\) with \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) given by (1) and its reformulation problem \(\mathrm {(SDP_2)}\). Then,
Moreover, \((x,\rho ,W)\) is an optimal solution of the problem \(\mathrm {(RTP_2)}\) if and only if there exist \(\tau \in \mathbb {R},\) \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl},\) \(X \in \mathbb {R}^{3\times 3lm},\) \(\sigma \in \mathbb {R}^m\) and \(Y \in \mathbb {R}^{3\times 3\,m}\) such that \((x,\rho ,W,\tau ,\delta ,u,X,\sigma ,Y)\) is an optimal solution of the problem \(\mathrm {(SDP_2)}\).
Remark 3.2
Corollary 3.2 improves upon the results obtained in [32, Theorem 2.3], where no adjustable variables are involved in the objective function of the adjustable robust linear optimization problem.
At the end of this section, we examine the category of uncertain sets such that (RTP) enjoys the SDP reformulation. We first consider the case when \(\mathcal {U}^i\), \(i=1,\dots ,l,\) are ellipsoidal uncertain sets, that is, \(\mathcal {{U}}^i\) is given by
Here, \(E^i\in \mathbb {S}^p\) and \(E^i\succ 0,\) \(i=1,\dots ,l.\)
In this case, its SDP reformulation becomes
Corollary 3.3
Consider the problem \(\mathrm {(RTP)}\) with \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) given by (12) and its reformulation problem \(\mathrm {(SDP)}\). Then,
Moreover, \((x,\rho ,W)\) is an optimal solution of the problem \(\mathrm {(RTP)}\) if and only if there exist \(\tau \in \mathbb {R},\) \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl},\) \(X \in \mathbb {R}^{3\times 3lm},\) \(\sigma \in \mathbb {R}^m\) and \(Y \in \mathbb {R}^{3\times 3\,m}\) such that \((x,\rho ,W,\tau ,\delta ,u,X,\sigma ,Y)\) is an optimal solution of the problem \(\mathrm {(SDP)}\).
Proof
Following similar arguments to those used in [14, Corollary 2.1], we can show that
Then, the desired result is obtained.
Remark 3.3
Note that related results for SDP reformulations of static robust quadratic optimization problems on ellipsoidal uncertain sets have been investigated in [26, Lemma 2]. However, Corollary 3.3 extends these results from static to the adjustable setting.
We now consider the case where \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) are cross-polytopes defined by
where \(\lambda _i>0,\) \(i=1,\dots ,l.\)
In this case, the SDP reformulation of \(\mathrm {(RTP)}\) becomes
Corollary 3.4
Consider the problem \(\mathrm {(RTP)}\) with \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) given by (14) and its reformulation problem \(\mathrm {(SDP)}\). Then,
Moreover, \((x,\rho ,W )\) is an optimal solution of the problem \(\mathrm {(RTP)}\) if and only if there exist \(\tau \in \mathbb {R},\) \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl},\) \(X \in \mathbb {R}^{3\times 3lm},\) \(\sigma \in \mathbb {R}^m\) and \(Y \in \mathbb {R}^{3\times 3\,m}\) such that \((x,\rho ,W,\tau ,\delta ,u,X,\sigma ,Y)\) is an optimal solution of the problem \(\mathrm {(SDP)}\).
Proof
Following similar arguments to those used in [14, Corollary 2.2], we can show that
Then, the desired result is obtained.
Remark 3.4
Note that related results for SDP reformulations of robust optimization problems on polytopic uncertain sets have been investigated in [26, Lemma 1] and [7, Theorem 1]. However, Corollary 3.4 extends the results obtained in [26, Lemma 1] from static to the adjustable setting. Furthermore, Corollary 3.4 also extends the results obtained in [7, Theorem 1] from linear optimization models to quadratic optimization models.
Let us now consider the case when \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) are boxes defined by
where \(\lambda _i>0,\) \(i=1,\dots ,l.\)
In this setting, the SDP reformulation of (RTP) becomes
Corollary 3.5
Consider the problem \(\mathrm {(RTP)}\) with \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) given by (16) and its reformulation problem \(\mathrm {(SDP)}\). Then,
Moreover, \((x,\rho ,W )\) is an optimal solution of the problem \(\mathrm {(RTP)}\) if and only if there exist \(\tau \in \mathbb {R},\) \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl},\) \(X \in \mathbb {R}^{3\times 3lm},\) \(\sigma \in \mathbb {R}^m\) and \(Y \in \mathbb {R}^{3\times 3\,m}\) such that \((x,\rho ,W,\tau ,\delta ,u,X,\sigma ,Y)\) is an optimal solution of the problem \(\mathrm {(SDP)}\).
Proof
Using similar arguments to those used in [14, Corollary 2.2], we can show that
Then, we obtain the desired result.
4 Applications
In this section, we apply the results obtained in the previous sections to fractionally adjustable robust optimization problems.
In what follows, suppose that \(g_0,\) \(f_i\), \(g_i,\) \(y(\cdot )\), \(\mathcal {U}^i\) and \(\mathcal {U}_{box}\) are considered as before. Let \(Q_0\), \(\widetilde{Q}_0 \in \mathbb {S}^{n},\) \(q_0\), \(\widetilde{q}_0\in \mathbb {R}^n\), and \(\xi _0\), \(\widetilde{\xi }_0\in \mathbb {R}.\) We consider the following fractionally adjustable robust quadratic optimization
where \(\widetilde{g}_0(y(z)):=(y(z))^{\top }\widetilde{B}_0y(z)+\widetilde{b}_0^{\top }y(z)+\widetilde{t_0}\) with \(\widetilde{B}_0:=diag (\widetilde{\theta }_1^0,\dots ,\widetilde{\theta }_m^0)\in \mathbb {R}^{m\times m},\) \(\widetilde{b}_0:=(\widetilde{b}_0^1,\dots ,\widetilde{b}_0^m)\in \mathbb {R}^m\) and \(\widetilde{t}_0\in \mathbb {R}.\) Moreover, we assume that \(x^{\top }\widetilde{Q}_0x+\widetilde{q}_0^{\top }x+\widetilde{\xi }_0>0\) and \(\widetilde{g}_0(y(z))>0\) are in the feasible set of (FTP).
The SDP reformulation of (FTP) is given as follows:
Now, we give the following theorem which describes an exact SDP reformulation for (FTP).
Theorem 4.1
Consider the problem \(\mathrm {(FTP)}\) with \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) given by (1) and its reformulation problem \(\mathrm {(FSDP)}\). Then,
Moreover, \((x,\rho ,W)\) is an optimal solution of the problem \(\mathrm {(FTP)}\) if and only if there exist \(\tau \in \mathbb {R},\) \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl},\) \(X \in \mathbb {R}^{3\times 3lm},\) \(\sigma \in \mathbb {R}^m\) and \(Y \in \mathbb {R}^{3\times 3\,m}\) such that \((x,\rho ,W,\tau ,\delta ,u,X,\sigma ,Y)\) is an optimal solution of the problem \(\mathrm {(FSDP) }\).
Proof
Obviously, (FTP) is equivalent to
The problem (18) is equivalent to
which can be written as:
Now, using similar arguments as in the proof of Theorem 3.1, it is easy to show that Theorem 4.1 holds.
Remark 4.1
Note that related results for SDP reformulations of fractional optimization problems have been investigated in [22, Theorem 3.2] and [20, Theorem 3.5]. However, Theorem 4.1 extends [22, Theorem 3.2] from deterministic models to the uncertain setting. Theorem 4.1 also extends the results obtained in [20, Theorem 3.5] from static to the adjustable setting.
In the special case that \(B_0=\text{ O}_{m\times m},\) \(b_0=0_m\) and \(t_0=0\), (FTP) collapses to
and (FSDP) becomes
By virtue of Theorem 4.1, we can easily obtain the following result.
Corollary 4.1
Consider the problem \(\mathrm {(FTP_0)}\) with \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) given by (1) and its reformulation problem \(\mathrm {(FSDP_0)}\). Then,
Moreover, \((x,\rho ,W )\) is an optimal solution of the problem \(\mathrm {(FTP_0)}\) if and only if there exist \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl}\) and \(X \in \mathbb {R}^{3\times 3lm}\) such that \((x,\rho ,W, \delta ,u,X)\) is an optimal solution of the problem \(\mathrm {(FSDP_0)}\).
In the special case when (FTP) with \(t_0=\widetilde{t}_0=0\) and \(Q_i=\widetilde{Q}_0=B_i=\widetilde{B}_0=\text{ O}_{m\times m},\) \(i=0,1,\dots ,l,\) (FTP) collapses to the following fractionally adjustable robust linear optimization
and (FSDP) becomes
Corollary 4.2
Consider the problem \(\mathrm {(FTP_1)}\) with \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) given by (1) and its reformulation problem \(\mathrm {(FSDP_1)}\). Then,
Moreover, \((x,\rho ,W )\) is an optimal solution of the problem \(\mathrm {(FTP_1)}\) if and only if there exist \(\tau \in \mathbb {R},\) \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl},\) \(X \in \mathbb {R}^{3\times 3lm},\) \(\sigma \in \mathbb {R}^m\) and \(Y \in \mathbb {R}^{3\times 3\,m}\) such that \((x,\rho ,W,\tau ,\delta ,u,X,\sigma ,Y)\) is an optimal solution of the problem \(\mathrm {(FSDP_1)}\).
At the end of this section, we examine the category of uncertain sets such that (FTP) has the exact SDP reformulation. We first consider the case when \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) are ellipsoids in (12). In this case, its SDP reformulation becomes
Corollary 4.3
Consider the problem \(\mathrm {(FTP)}\) with \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) given by (12) and its reformulation problem \(\mathrm {(FSDP)}\). Then,
Moreover, \((x,\rho ,W)\) is an optimal solution of the problem \(\mathrm {(FTP)}\) if and only if there exist \(\tau \in \mathbb {R},\) \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl},\) \(X \in \mathbb {R}^{3\times 3lm},\) \(\sigma \in \mathbb {R}^m\) and \(Y \in \mathbb {R}^{3\times 3\,m}\) such that \((x,\rho ,W,\tau ,\delta ,u,X,\sigma ,Y)\) is an optimal solution of the problem \(\mathrm {(FSDP)}\).
Proof
Together with (13) and Theorem 4.1, we can easily get the desired result.
We now consider the case where \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) are cross-polytopes in (14). In this case, the SDP reformulation of (FTP) becomes
Corollary 4.4
Consider the problem \(\mathrm {(FTP)}\) with \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) given by (14) and its reformulation problem \(\mathrm {(FSDP)}\). Then,
Moreover, \((x,\rho ,W)\) is an optimal solution of the problem \(\mathrm {(FTP)}\) if and only if there exist \(\tau \in \mathbb {R},\) \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl},\) \(X \in \mathbb {R}^{3\times 3lm},\) \(\sigma \in \mathbb {R}^m\) and \(Y \in \mathbb {R}^{3\times 3\,m}\) such that \((x,\rho ,W,\tau ,\delta ,u,X,\sigma ,Y)\) is an optimal solution of the problem \(\mathrm {(FSDP)}\).
Proof
From (15) and Theorem 4.1, it is easy to show the validity of the corollary.
Let us now consider the case when \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) are boxes in (16). In this setting, the SDP reformulation of (FSDP) becomes
Corollary 4.5
Consider the problem \(\mathrm {(FTP)}\) with \(\mathcal {U}^i,\) \(i=1,\dots ,l,\) given by (16) and its reformulation problem \(\mathrm {(FSDP)}\). Then,
Moreover, \((x,\rho ,W)\) is an optimal solution of the problem \(\mathrm {(FTP)}\) if and only if there exist \(\tau \in \mathbb {R},\) \(\delta \in \mathbb {R}^{lm},\) \(u \in \mathbb {R}^{pl},\) \(X \in \mathbb {R}^{3\times 3lm},\) \(\sigma \in \mathbb {R}^m\) and \(Y \in \mathbb {R}^{3\times 3\,m}\) such that \((x,\rho ,W,\tau ,\delta ,u,X,\sigma ,Y)\) is an optimal solution of the problem \(\mathrm {(FSDP)}\).
Proof
By (17) and Theorem 4.1, it is easy to obtain the desired result.
5 Conclusions
In this paper, under the framework of adjustable robust optimization approach, a class of adjustable robust quadratic optimization problems, where both objective and constraint functions involve uncertain data, is considered. We first obtain exact SDP reformulations for adjustable robust quadratic optimization problems with an affine decision rule on spectrahedral uncertain sets. For applications, we also establish exact SDP reformulations for fractionally adjustable robust quadratic optimization problems on spectrahedral uncertain sets.
In the future, further studies on SDP problems and optimality conditions for adjustable robust quadratic optimization problems are still needed. For example, similar to [11], can we obtain some SDP dual results for adjustable robust quadratic optimization problems with an affine decision rule. On the other hand, it is important to consider how the proposed approach can be extended to handle adjustable robust nonlinear optimization problems.
References
Akbay, M.A., Kalayci, C.B., Polat, O.: A parallel variable neighborhood search algorithm with quadratic programming for cardinality constrained portfolio optimization. Knowl. Based Syst. 198, 105944 (2020)
Al-Sultan, K.S., Murty, K.G.: Exterior point algorithms for nearest points and convex quadratic programs. Math. Program. 57, 145–161 (1992)
Ben-Tal, A., Nemirovski, A.: Robust solutions of uncertain linear programs. Oper. Res. 25, 1–13 (1999)
Ben-Tal, A., Nemirovski, A.: Robust optimization-methodology and applications. Math. Program. 92, 453–480 (2002)
Ben-Tal, A., Goryashko, A., Guslitzer, E., Nemirovski, A.: Adjustable robust solutions of uncertain linear programs. Math. Program. 99, 351–376 (2004)
Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)
Bertsimas, D., de Ruiter, F.J.: Duality in two-stage adaptive linear optimization: faster computation and stronger bounds. Inf. J. Comput. 28, 500–511 (2016)
Chen, X., Zhang, Y.: Uncertain linear programs: extended affinely adjustable robust counterparts. Oper. Res. 57, 1469–1482 (2009)
Chen, J.W., Köbis, E., Yao, J.C.: Optimality conditions and duality for robust nonsmooth multiobjective optimization problems with constraints. J. Optim. Theory Appl. 181, 411–436 (2019)
Chen, J.W., Li, J., Li, X.B., Lv, Y.B., Yao, J.C.: Radius of robust feasibility of system of convex inequalities with uncertain data. J. Optim. Theory Appl. 184, 384–399 (2020)
Chuong, T.D., Jeyakumar, V.: Generalized Farkas lemma with adjustable variables and two-stage robust linear programs. J. Optim. Theory Appl. 187, 488–519 (2020)
Chuong, T.D., Jeyakumar, V., Li, G., Woolnough, D.: Exact SDP reformulations of adjustable robust linear programs with box uncertainties under separable quadratic decision rules via SOS representations of non-negativity. J. Global Optim. 81, 1095–1117 (2021)
Chuong, T.D., Mak-Hau, V.H., Yearwood, J., Dazeley, R., Nguyen, M.T., Cao, T.: Robust Pareto solutions for convex quadratic multiobjective optimization problems under data uncertainty. Ann. Oper. Res. 319, 1533–1564 (2022)
Chuong, T.D., Jeyakumar, V., Li, G., Woolnough, D.: Exact dual semi-definite programs for affinely adjustable robust SOS-convex polynomial optimization problems. Optimization 71, 3539–3569 (2022)
Fang, S., Tsao, H.S.J.: An unconstrained convex programming approach to solving convex quadratic programming problems. Optimization 27, 235–243 (1993)
Friedlander, M.P., Orban, D.: A primal-dual regularized interior-point method for convex quadratic programming. Math. Program. Comput. 4, 71–107 (2012)
Gabrel, V., Murat, C., Thiele, A.: Recent advances in robust optimization: an overview. Eur. J. Oper. Res. 235, 471–483 (2014)
Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx (2014)
Jeyakumar, V., Li, G.: Exact second-order cone programming relaxations for some nonconvex minimax quadratic optimization problems. SIAM J. Optim. 28, 760–787 (2018)
Jiao, L., Lee, J.H.: Fractional optimization problems with support functions: exact SDP relaxations. Linear Nonlinear Anal. 5, 255–268 (2019)
Köbis, E.: On robust optimization: relations between scalar robust optimization and unconstrained multicriteria optimization. J. Optim. Theory Appl. 167, 969–984 (2015)
Lee, J.H., Jiao, L.: Solving fractional multicriteria optimization problems with sum of squares convex polynomial data. J. Optim. Theory Appl. 176, 428–455 (2018)
Liu, P., Fattahi, S., Gómez, A., Küçükyavuz, S.: A graph-based decomposition method for convex quadratic optimization with indicators. Math. Program. 200, 669–701 (2023)
Mittal, A., Gokalp, C., Hanasusanto, G.A.: Robust quadratic programming with mixed-integer uncertainty. Inf. J. Comput. 32, 201–218 (2020)
Ramana, M., Goldman, A.J.: Some geometric results in semidefinite programming. J. Global Optim. 7, 33–50 (1995)
Robust convex quadratically constrained programs: Goldfarb, D., Iyengar. G. Math. Program. 97, 495–515 (2003)
Sun, X.K., Teo, K.L., Zeng, J., Guo, X.L.: On approximate solutions and saddle point theorems for robust convex optimization. Optim. Lett. 14, 1711–1730 (2020)
Sun, X.K., Teo, K.L., Long, X.J.: Some characterizations of approximate solutions for robust semiinfinite optimization problems. J. Optim. Theory Appl. 191, 281–310 (2021)
Sun, X.K., Tan, W., Teo, K.L.: Characterizing a class of robust vector polynomial optimization via sum of squares conditions. J. Optim. Theory Appl. 197, 737–764 (2023)
Vinzant, C.: What is a spectrahedron? Notices Am. Math. Soc. 61, 492–494 (2014)
Wei, H.Z., Chen, C.R., Li, S.J.: Characterizations for optimality conditions of general robust optimization problems. J. Optim. Theory Appl. 177, 835–856 (2018)
Woolnough, D., Jeyakumar, V., Li, G.: Exact conic programming reformulations of two-stage adjustable robust linear programs with new quadratic decision rules. Optim. Lett. 15, 25–44 (2021)
Xia, Y.S., Feng, G.: An improved neural network for convex quadratic optimization with application to real-time beamforming. Neurocomputing 64, 359–374 (2005)
Yang, Y.: A polynomial arc-search interior-point algorithm for convex quadratic programming. Eur. J. Oper. Res. 215, 25–38 (2011)
Yanikoglu, I., Gorissen, B.L., den Hertog, D.: A survey of adjustable robust optimization. Eur. J. Oper. Res. 277, 799–813 (2019)
Zhang, S., Huang, Y.: Complex quadratic optimization and semidefinite programming. SIAM J. Optim. 16, 871–890 (2006)
Zhang, H., Sun, X.K., Li, G.H.: On second-order conic programming duals for robust convex quadratic optimization problems. J. Ind. Manag. Optim. 19, 8114–8128 (2023)
Funding
This research is supported by the Science and Technology Research Program of Chongqing Municipal Education Commission (KJZDK202100803), the Team Building Project for Graduate Tutors in Chongqing (yds223010) and the Innovation Project of CTBU (yjscxx2023-211-72).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Jen-Chih Yao.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Zhang, H., Sun, X. & Teo, K.L. Exact SDP Reformulations for Adjustable Robust Quadratic Optimization with Affine Decision Rules. J Optim Theory Appl (2024). https://doi.org/10.1007/s10957-023-02371-5
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10957-023-02371-5
Keywords
- Adjustable robust optimization
- Quadratic optimization
- Semidefinite programming reformulation
- Spectrahedral uncertain sets