Robust SOS-convex polynomial optimization problems: exact SDP relaxations

Abstract

This paper studies robust solutions and semidefinite linear programming (SDP) relaxations of a class of convex polynomial optimization problems in the face of data uncertainty. The class of convex optimization problems, called robust SOS-convex polynomial optimization problems, includes robust quadratically constrained convex optimization problems and robust separable convex polynomial optimization problems. It establishes sums-of-squares polynomial representations characterizing robust solutions and exact SDP-relaxations of robust SOS-convex polynomial optimization problems under various commonly used uncertainty sets. In particular, the results show that the polytopic and ellipsoidal uncertainty sets, that allow second-order cone re-formulations of robust quadratically constrained optimization problems, continue to permit exact SDP-relaxations for a broad class of robust SOS-convex polynomial optimization problems.

1 Introduction

Consider the convex polynomial optimization problem

$$\begin{aligned} \begin{array}{c@{\quad }rl} (P_0) &{} \inf &{} f(x) \\ &{} s.t. &{} g_i(x)\le 0,\ i=1,\ldots ,m, \end{array} \end{aligned}$$

where $f$ and $g_i$’s are convex polynomials. The model problem $(P_0)$ admits a hierarchy of semidefinite programming (SDP) relaxations, known as the Lasserre hierarchy of SDP-relaxations. More generally, the Lasserre hierarchy of SDP relaxations is often used to solve nonconvex polynomial optimization problems with compact feasible sets [20, 22], and it has finite convergence generically as shown recently in [26].

In particular, if $f$ and $g_i, i=1,2,\ldots , m$ are SOS-convex polynomials (see Definition 2.2), then $(P_0)$ enjoys an exact SDP-relaxation in the sense that the optimal values of $(P_0)$ and its relaxation problem are equal and the relaxation problem attains its optimum under the Slater constraint qualification ([22, Theorem 3.4]). The class of SOS-convex polynomials is a numerically tractable subclass of convex polynomials and it contains convex quadratic functions and convex separable polynomials [1, 15]. The SOS-convexity of a polynomial can be numerically checked by solving a semidefinite programming problem.

The exact SDP-relaxation of a convex optimization problem is a highly desirable feature because SDP problems can be efficiently solved [2, 11]. However, the data of real-world convex optimization problems are often uncertain (that is, they are not known exactly at the time of the decision) due to estimation errors, prediction errors or lack of information. Recently, robust optimization approach has emerged as a powerful approach to treat optimization under data uncertainty. It is known that a robust convex quadratic optimization problem under ellipsoidal data uncertainty enjoys exact SDP relaxation as it can be equivalently reformulated as a semi-definite programming problem (see [7]). In the same vein, Goldfarb and Iyengar [14] have shown that a robust convex quadratic optimization problems under restricted ellipsoidal data uncertainty can be equivalently reformulated as a second-order cone programming problem.

Unfortunately, an exact SDP relaxation may fail for a robust convex (not necessarily quadratic) polynomial optimization problem under restricted ellipsoidal data uncertainty (see Example 3.1). This raises the fundamental question: do some classes of robust convex (not necessarily quadratic) polynomial optimization problems posses exact SDP relaxation? This question has motivated us to study SOS-convex polynomial optimization problems under uncertainty.

In this paper, we study the SOS-convex polynomial optimization problem $(P_0)$ in the face of data uncertainty. This model problem under data uncertainty in the constraints can be captured by the model problem

$$\begin{aligned} \begin{array}{c@{\quad }rl} (UP_0) &{} \inf &{} f(x) \\ &{} s.t. &{} g_i(x,v_i)\le 0,\ i=1,\ldots ,m, \end{array} \end{aligned}$$

where $v_i$ is an uncertain parameter and $v_i \in \mathcal {V}_i$ for some compact uncertainty set $\mathcal {V}_i \in \mathbb {R}^{q_i}$, $q_i \in \mathbb {N}$, $f:\mathbb {R}^n\rightarrow \mathbb {R}$ is a SOS-convex polynomial and $g_i:\mathbb {R}^n\times \mathbb {R}^{q_i}\rightarrow \mathbb {R}$, $i=1,\ldots ,m$, are functions such that for each $v_i\in \mathbb {R}^{q_i}$, $g_i(\cdot ,v_i)$ is a SOS-convex polynomial. As solutions to convex optimization problems are generally sensitive to data uncertainty, even a small uncertainty in the data can affect the quality of the optimal solution of a convex optimization problem. This has clearly been demonstrated in [6] by solving 90 linear programming problems from the well-known NETLIB collection.

Consequently, how to find robust optimal solutions, that are immunized against data uncertainty, has become an important question in convex optimization and has recently been extensively studied in the literature (see [7–10, 16–18] and the references therein).

Following the robust optimization approach, the robust counterpart of $(UP_0)$, which finds a robust solution of $(UP_0)$ that is immunized against all the possible uncertain scenarios, is given by

$$\begin{aligned} \begin{array}{crl} (P) &{} \inf &{} f(x) \\ &{} s.t. &{} g_i(x,v_i)\le 0,\quad \ \forall v_i\in \mathcal {V}_i,i=1,\ldots ,m, \end{array} \end{aligned}$$

and is called a robust SOS-convex polynomial optimization problem or called simply, robust SOSCP. In the robust counterpart, the uncertain inequality constraints are enforced for all realizations of the uncertainties $v_i\in \mathcal {V}_i, \ i=1,\ldots ,m$. A sum of squares (SOS) relaxation problem of $(P)$ with degree $k$ is the model problem

$$\begin{aligned} \begin{array}{cr} (D_k) &{} \sup \limits _{\mu \in \mathbb {R}, v_i\in \mathcal {V}_i, \lambda _i\ge 0} \left\{ \mu \ :\ f(\cdot ) +\sum \limits _{i=1}^{m}\lambda _i g_i(\cdot ,v_i)-\mu \in \Sigma ^2_k \right\} \\ \end{array} \end{aligned}$$

where $\Sigma ^2_k$ denotes the set of all sum of squares polynomials with degree no larger than $k$. The model $(D_k)$ is, in fact, the sum of squares relaxation of the robust Lagrangian dual, examined recently in [3, 12, 16–18].

The following contributions are made in this paper to robust convex optimization.

I. We first derive a complete characterization of the solution of a robust SOS-convex polynomial optimization problem $(P)$ in terms of sums of squares polynomials under a normal cone constraint qualification that is shown to be the weakest condition for the characterization (see Theorem 2.2). We show that the sum of squares characterization can be numerically checked for some classes of uncertainty sets by solving a semidefinite programming problem.

II. We establish that the value of a robust SOS-convex optimization problem (P) can be found by solving a sum-of-squares programming problem (see Theorem 2.3). This is done by proving an exact sum-of-squares relaxation of the robust SOS-convex optimization problem $(P)$.

III. Although the sum of squares relaxation problem $(D_k)$ is, in general, a computationally hard problem for general classes of uncertainty sets (see Remark 2.1), we prove that, for the classes of polytopic and ellipsoidal uncertainty sets, the relaxation problem can equivalently be re-formulated as a semidefinite programming problem (see Theorems 3.1 and 3.2). This shows that these uncertainty sets, which allow second-order cone re-formulations of robust quadratically constrained optimization problems [14], permit exact SDP relaxations for a broad class of robust SOS-convex optimization problems. The relaxation problem provides an alternative formulation of an exact second-order cone relaxation for the robust quadratically constrained optimization problem, studied in [14].

The outline of the paper is as follows. Section 2 presents necessary and sufficient conditions for robust optimality and derives SOS-relaxation for robust SOS-convex optimization problems. Section 3 provides numerically tractable classes of robust convex optimization problems by presenting exact SDP-relaxations.

2 Solutions of robust SOSCPs

We begin with some definitions and preliminaries on polynomials. We say that a real polynomial $f$ is sum-of-squares [23] if there exist real polynomials $f_j$, $j=1,\ldots ,r$, such that $f=\sum _{j=1}^rf_j^2$. The set consisting of all sum of squares real polynomial is denoted by $\Sigma ^2$. Moreover, the set consisting of all sum of squares real polynomial with degree at most $d$ is denoted by $\Sigma ^2_d$. The space of all real polynomials on $\mathbb {R}^n$ is denoted by $\mathbb {R}[x]$ and the set of all $n\times r$ matrix polynomials is denoted by $\mathbb {R}[x]^{n \times r}$.

Definition 2.1

(SOS matrix polynomial) We say a matrix polynomial $F \in \mathbb {R}[x]^{n \times n}$ is a SOS matrix polynomial if $F(x)=H(x)H(x)^T$ where $H(x) \in \mathbb {R}[x]^{n \times r}$ is a matrix polynomial for some $r \in \mathbb {N}$.

Definition 2.2

(SOS-Convex polynomial [15]) A real polynomial $f$ on $\mathbb {R}^n$ is called SOS-convex if the Hessian matrix function $F:x\mapsto \nabla ^2 f(x)$ is a SOS matrix polynomial.

Clearly, a SOS-convex polynomial is convex. However, the converse is not true, that is, there exists a convex polynomial which is not SOS-convex [1]. It is known that any convex quadratic function and any convex separable polynomial is a SOS-convex polynomial. Moreover, a SOS-convex polynomial can be non-quadratic and non-separable. For instance, $f(x)=x_1^8+x_1^2+x_1x_2+x_2^2$ is a SOS-convex polynomial (see [15]) which is non-quadratic and non-separable.

Lemma 2.1

(SOS-Convexity & sum-of-squares[15, Lemma 8]) Let $f$ be a SOS-convex polynomial on $\mathbb {R}^n$. If $f(u)=0$ and $\nabla f(u)=0$ for some $u\in \mathbb {R}^n$, then $f$ is a sum-of-squares polynomial.

The following existence result for solutions of a convex polynomial optimization problem will also be useful for our later analysis.

Lemma 2.2

(Solutions of convex polynomial optimization [4, Theorem 3]) Let $f_0,f_1,\ldots ,f_m$ be convex polynomials on $\mathbb {R}^n$ and let $C:=\big \{x \in \mathbb {R}^n : f_i(x) \le 0, i=1,\ldots ,m\big \}$. If $\inf \limits _{x\in C}f_0(x)>-\infty$ then $\mathop {\mathrm{argmin}}\nolimits _{x\in C}f_0(x) \ne \emptyset$.

We note that it is possible to reduce a convex polynomial optimization problem to a quadratic optimization problem by introducing new variables. For example, $\min _{x \in \mathbb {R}}\{x^2:x^4 \le 1\}$ can be converted to a quadratic optimization problem $\min _{(x,t) \in \mathbb {R}^2}\{x^2:x^2 \le 1, t=x^2\}$. However, introducing new variables will result in a problem which may not satisfy the required convexity.

Recall that for a convex set $A\subset \mathbb {R}^{m}$, the normal cone of $A$ at $x\in A$ is given by $N_A(x):=\left\{ v\in \mathbb {R}^n : v^T(y-x)\le 0,\,\forall y\in A\right\} .$ Let $F:=\left\{ x : g_i(x,v_i)\le 0\ \forall v_i\in \right.$ $\left. \mathcal {V}_i,i=1,\ldots ,m\right\} \ne \emptyset$. We say that the normal cone condition holds for $F$ at $x\in F$ provided that

$$\begin{aligned} N_F(x) = \left\{ \sum _{i=1}^{m} \lambda _i \nabla _x g_i(x,v_i) : \lambda _i\ge 0, v_i\in \mathcal {V}_i, \lambda _i g_i(x,v_i)=0\right\} , \end{aligned}$$

where $\nabla _x$ denotes the gradient with respect to the variable $x$.

It is known from [16] that the normal cone condition is guaranteed by the following robust Slater condition, $\left\{ x\in \mathbb {R}^n : g_i(x,v_i)< 0, \ \forall v_i\in \mathcal {V}_i, i=1,\ldots ,m\right\} \ne \emptyset .$ On the other hand, the normal cone condition is, in general, weaker than the robust Slater condition.

In the following theorem we first prove that the normal cone condition guarantees a robust solution characterization involving sums-of-squares representations for robust SOSCPs.

Theorem 2.1

(Sum-of-squares characterization of solutions) Let $f:\mathbb {R}^n\rightarrow \mathbb {R}$ be a SOS-convex polynomial and let $g_i:\mathbb {R}^n\times \mathbb {R}^{q_i}\rightarrow \mathbb {R}$, $i=1,\ldots ,m$, be functions such that for each $v_i\in \mathbb {R}^{q_i}$, $g_i(\cdot ,v_i)$ is a SOS-convex polynomial with degree at most $d_i$. Let $\mathcal {V}_i\subset \mathbb {R}^{q_i}$ be compact and $F:=\left\{ x\in \mathbb {R}^n : g_i(x,v_i)\le 0\ \forall v_i\in \mathcal {V}_i, i=1,\ldots ,m\right\} \ne \emptyset$. Suppose that $\mathrm{argmin}_{x\in F}f(x)\ne \emptyset$ and the normal cone condition holds at $x^*\in F$. Then, $x^*$ is a minimizer of $\min _{x \in F}f(x)$ if and only if $(\exists \ \bar{v}_i\in \mathcal {V}_i, \, \lambda _i \in \mathbb {R}_+, i=1,\ldots ,m, \, \sigma _0\in \Sigma ^2_{k_0})$ $(\forall \, x \in \mathbb {R}^n)$

$$\begin{aligned} f(x)-f(x^*)+\sum _{i=1}^{m}\lambda _i g_i\left( x,\bar{v}_i\right) = \sigma _0(x), \end{aligned}$$

(2.1)

where $k_0$ is the smallest even number such that $k_0 \ge \max \left\{ \deg f, \max _{1 \le i \le m}d_i\right\}$.

Proof

[(if part)] It easily follows from the fact that $f(x)-f(x^*)=\sigma _0(x)-\sum _{i=1}^{m}\lambda _i g_i\left( x,\bar{v}_i\right) \ge 0$ for all $x\in F$ as $\sigma _0(x) \ge 0$ and $\lambda _i \ge 0$. [(only if part)] If $f(x^*) = \min _{x\in F}f(x)$, then, by the optimality condition of convex optimization, $-\nabla f(x^*) \in N_F(x^*)$. By the normal cone condition, there exist $\bar{v}_i\in \mathcal {V}_i$, $\lambda _i\ge 0$, $i=1,\ldots ,m$, with $\lambda _i g_i(x^*,\bar{v}_i) = 0$, such that $-\nabla f(x^*) = \sum _{i=1}^{m} \lambda _i \nabla g_i(x^*,\bar{v}_i)$. Let $L(x):=f(x)-f(x^*)+\sum _{i=1}^{m}{\lambda _i g_i(x,\bar{v}_i)}$, for $x\in \mathbb {R}^n$. Observe that $L(x^*)=0$ and $\nabla L(x^*)=0$. Clearly, $L$ is SOS-convex since $f$ and $g(\cdot ,\bar{v}_i)$ are all SOS-convex. So, Lemma 2.1 guarantees that $L$ is a sum of squares polynomial. Moreover, the degree of $L$ is not larger than $k_0$. So, there exists $\sigma _0 \in \Sigma ^2_{k_0}$ such that $f(x)-f(x^*)+\sum _{i=1}^{m}{\lambda _i g_i\left( x,\bar{v}_i\right) } = \sigma _0(x) \quad \forall x\in \mathbb {R}^n.$ Thus, the conclusion follows. $\square$

Next, we show that the normal cone condition is indeed the weakest condition for the robust solution characterization in the sense that if the normal cone condition fails at some feasible point then there exists a SOS-convex real polynomial $f$ such that the robust solution characterization fails.

Theorem 2.2

(Weakest qualification for solution characterization) Let $g_i:\mathbb {R}^n\times \mathbb {R}^{q_i}\rightarrow \mathbb {R}$, $i=1,\ldots ,m$, be functions such that for each $v_i\in \mathbb {R}^{q_i}$, $g_i(\cdot ,v_i)$ is a SOS-convex polynomial with degree at most $d_i$. Let $F:=\{x\in \mathbb {R}^n : g_i(x,v_i)\le 0\ \forall v_i\in \mathcal {V}_i,$ $i=1,\ldots ,m\} \ne \emptyset$ and let $\mathcal {V}_i\subset \mathbb {R}^{q_i}$ be compact. Then, the following statements are equivalent:

• (i) For each SOS-convex real polynomial $f$ on $\mathbb {R}^n$ with $\mathrm{argmin}_{x\in F}f(x)\ne \emptyset$, $f(x^*) = \min \limits _{x\in F}f(x)\ \Leftrightarrow \ \left[ \exists \,\bar{v}_i\in \mathcal {V}_i, \lambda _i\ge 0 : f(\cdot )-f(x^*)+\sum _{i=1}^{m}\lambda _i g_i\left( \cdot ,\bar{v}_i\right) \in \Sigma ^2_{k_0} \right]$ where $k_0$ is the smallest even number such that $k_0 \ge \max \left\{ \deg f, \max _{1 \le i \le m}d_i\right\}$.

• (ii) $N_F(x) = \left\{ \sum _{i=1}^{m} \lambda _i \nabla _x g_i(x,v_i) : \lambda _i\ge 0, v_i\in \mathcal {V}_i, \lambda _i g_i(x,v_i)=0\right\}$, for all $x \!\in \! F$.

Proof

It suffices to show that (i) $\Rightarrow$ (ii) since the converse statement has been already shown in Theorem 2.1. In fact, we just need to show $N_F(x) \subset \{\sum _{i=1}^{m} \lambda _i \nabla _x g_i(x,v_i) : \lambda _i\ge 0, v_i\in \mathcal {V}_i, \lambda _i g_i(x,v_i)=0\},$ for any $x\in F$, since the converse inclusion always holds. Let $x^*\in F$ be arbitrary. If $w\in N_F(x^*)$ then $-w^T(x-x^*)\ge 0$ for all $x\in F$. Let $f(x):=-w^T(x-x^*)$. Then, $\min _{x\in F}f(x) = f(x^*) = 0$. Since any affine function is SOS-convex, applying (i), there exist $\bar{v}_i\in \mathcal {V}_i$, $\lambda _i\ge 0$, for $i=1,\ldots ,m$, and $\sigma _0\in \Sigma ^2_{k_0}$ such that, for all $x\in \mathbb {R}^n$,

$$\begin{aligned} -w^T(x-x^*) + \sum _{i=1}^{m}\lambda _i g_i\left( x,\bar{v}_i\right) = \sigma _0(x) \ge 0. \end{aligned}$$

(2.2)

Letting $x=x^*$, we see that $\sum _{i=1}^{m}\lambda _i g_i\left( x^*,\bar{v}_i\right) \ge 0$. This together with $x\in F$ implies $\lambda _i g_i\left( x^*,\bar{v}_i\right) = 0$, $i=1,\ldots ,m$. So, (2.2) implies that $\sigma _0(x^*)=0$ and $0=\nabla \sigma _0(x^*) = -w+\sum _{i=1}^{m}\lambda _i g_i\left( x^*,\bar{v}_i\right)$. Then, $w\in \{ \sum _{i=1}^{m} \lambda _i \nabla _x g_i(x^*,v_i) : \lambda _i\ge 0, v_i\in \mathcal {V}_i, \lambda _i g_i(x^*,v_i)=0 \}.$ Thus, the conclusion follows. $\square$

It is worth noting that the sum-of-squares condition characterizing the solution of a robust SOSCP can be numerically verified by solving semi-definite programming problems for some uncertainty sets. We illustrate this with two simple examples: (1) SOS-convex constraints with finite uncertainty sets; (2) quadratic constraints with spectral norm data uncertainty sets. The numerical tractability of more general classes of robust SOS-convex optimization problems under sophisticated classes of uncertainty sets will be discussed later on in Sect. 3.

2.1 SOS-convex constraints and finite uncertainty sets

Suppose that $\mathcal {V}_i=\left\{ v_i^1,\ldots ,v_i^{s_i}\right\}$ for any $i\in \left\{ 1,\ldots ,m\right\}$. Then, the robust SOS-convex polynomial optimization problem takes the form

$$\begin{aligned} (P_1) \ \ \ \min _{x \in \mathbb {R}^n} \{f(x): g_i(x,v_i^j)\le 0,\ \forall j=1,\ldots ,s_i,\ \forall i=1,\ldots ,m\}, \end{aligned}$$

and the minimum is attained in virtue of Lemma 2.2. Let $x^*$ be a feasible solution of $(P_1)$ and suppose that the normal cone condition is satisfied at $x^*$.

Let $k_0=\max _{1 \le i \le m, 1 \le j \le s_i}\{\mathrm{deg}f,\mathrm{deg}g_i(\cdot ,v_i^j)\}$. In this case, (2.1) in Theorem 2.1 is equivalent to the condition that there exist ${\lambda }_i^j \ge 0$, $i=1,\ldots ,m, j=1,\ldots ,s_i$, and $\sigma _0\in \Sigma _k^2$ such that

$$\begin{aligned} f(x)-f(x^*)+\sum _{1 \le i \le m, 1 \le j \le s_i}{\lambda }_i^j g_i\left( x, {v}_i^j\right) = \sigma _0(x)\quad \text{ for } \text{ all } \quad x\in \mathbb {R}^n. \end{aligned}$$

(2.3)

Indeed, it is easy to see that (2.1) in Theorem 2.1 implies (2.3). On the other hand, (2.3) immediately gives us that $x^*$ is a solution of $(P_1)$ which implies (2.1). Therefore, a solution of a SOS-convex polynomial optimization problem under finite uncertainty sets can be efficiently verified by solving a semidefinite programming problem.

2.2 Quadratic constraints under spectral norm uncertainty

Consider the following SOS-convex polynomial optimization problem with quadratic constraints under spectral norm uncertainty:

$$\begin{aligned} \min _{x \in \mathbb {R}^n} \{f(x) :x^TB_ix + 2b_i^T x + \beta _i \le 0,\ i=1,\ldots ,m\}, \end{aligned}$$

where, $b_i \in \mathbb {R}^n$ and $\beta _i \in \mathbb {R}$, the data $(B_i,b_i,\beta _i) \in S^n \times \mathbb {R}^n \times \mathbb {R}$, $i=1,\ldots ,m$, are uncertain and belong to the spectral norm uncertainty set

$$\begin{aligned} \mathcal {V}_i=\{(B_i,b_i,\beta _i) \in S^n \times \mathbb {R}^n \times \mathbb {R} : \left\| \left( \begin{array}{c@{\quad }c} B_i &{} b_i\\ b_i^T &{} \beta _i \end{array} \right) -\left( \begin{array}{c@{\quad }c} \overline{B}_i &{} \overline{b}_i\\ \overline{b}_i^T &{} \overline{\beta }_i \end{array} \right) \right\| _\mathrm{spec} \le \varepsilon _i\}, \end{aligned}$$

for some $\varepsilon _i \ge 0$, $\overline{B}_i \succeq 0$, $\overline{b}_i \in \mathbb {R}^n$ and $\overline{\beta }_i \in \mathbb {R}$. Here, $S^{n}$ denotes the space of symmetric $n\times n$ matrices and $\Vert \cdot \Vert _\mathrm{spec}$ denotes the spectral norm defined by $\Vert M\Vert _\mathrm{spec}=\sqrt{\lambda _{\max }(M^TM)}$ where $\lambda _{\max }(C)$ is the maximum eigenvalue of the matrix $C$. The corresponding robust counterpart of the above problem is

$$\begin{aligned} \begin{array}{crl} (P_2) &{} \min &{} f(x) \\ &{} s.t. &{} x^TB_ix + 2b_i^T x + \beta _i \le 0, \ \forall \, (B_i,b_i,\beta _i) \in \mathcal {V}_i, \ i=1,\ldots ,m, \end{array} \end{aligned}$$

Let $k=\max \{\mathrm{deg} f,2\}$. In this case, (2.1) in Theorem 2.1 becomes $(\exists \,B_i\in \mathcal {V}_i,\,\lambda \in \mathbb {R}^m_+,\,\sigma _0\in \Sigma _k^2)$ $(\forall x \in \mathbb {R}^n)$ $f(x)-f(x^*)+\sum _{i=1}^{m}\lambda _i (x^TB_ix + 2b_i^T x + \beta _i ) = \sigma _0(x)$. This, in turn, is equivalent to the condition that there exist $\lambda _i \ge 0$, $i=1,\ldots ,m$, and $\sigma _0\in \Sigma _k^2$ such that

$$\begin{aligned} f(x)-f(x^*)+\sum _{i=1}^{m}\lambda _i (x^T(\overline{B}_i+\varepsilon _i I_n) x + 2\overline{b}_i^T x + \overline{\beta }_i+\varepsilon _i ) = \sigma _0(x)\quad \text{ for } \text{ all } \quad x\in \mathbb {R}^n. \end{aligned}$$

(2.4)

In fact, (2.4) implies (2.1) as $(\overline{B}_i+\varepsilon _i I_n,\overline{b}_i,\overline{\beta }_i+\varepsilon _i) \in \mathcal {V}_i$. On the other hand, note that, for all $(B_i,b_i,\beta _i) \in \mathcal {V}_i$, $\small \left( \begin{array}{c@{\quad }c} \overline{B}_i+\varepsilon _i I_n &{} \overline{b}_i\\ \overline{b}_i^T &{} \beta _i+\varepsilon _i \end{array} \right) -\small \left( \begin{array}{c@{\quad }c} B_i &{} b_i\\ b_i^T &{} \beta _i \end{array} \right)$ is a positive semidefinite matrix, and hence, for each $i=1,\ldots ,m$,

$$\begin{aligned} h_i(x):= \left( \begin{array}{c} x\\ 1 \end{array} \right) ^T\left( \, \left( \begin{array}{c@{\quad }c} \overline{B}_i+\varepsilon _i I_n &{} \overline{b}_i\\ \overline{b}_i^T &{} \beta _i+\varepsilon _i \end{array} \right) -\left( \begin{array}{c@{\quad }c} B_i &{} b_i\\ b_i^T &{} \beta _i \end{array} \right) \, \right) \left( \begin{array}{c} x\\ 1 \end{array} \right) \end{aligned}$$

is sum-of-squares. So, (2.1) implies that there exist $\lambda _i \ge 0$ and $(B_i,b_i,\beta _i) \in \mathcal {V}_i$, such that

$$\begin{aligned}&f(x)-f(x^*)+\sum _{i=1}^{m}\lambda _i (x^T(\overline{B}_i+\varepsilon _i I_n) x + 2\overline{b}_i^T x + \overline{\beta }_i+\varepsilon _i ) \\&= f(x)-f(x^*)+\sum _{i=1}^{m}\lambda _i (x^TB_ix + 2b_i^T x + \beta _i )+\sum _{i=1}^mh_i(x), \end{aligned}$$

is a sum-of-squares polynomial with degree at most $k$. Therefore, a solution of a quadratic optimization problem under spectral norm data uncertainty can also be efficiently verified by solving a semidefinite programming problem.

Next, we examine how to find the optimal value of a robust SOSCP by solving a sum of squares relaxation problem. In particular, the corresponding sum of squares relaxation problem can often be equivalently reformulated as semi-definite programming problems under various commonly used data uncertainty sets.

Theorem 2.3

(Exact sum of squares relaxation) Let $f:\mathbb {R}^n\rightarrow \mathbb {R}$ be a SOS-convex polynomial. Let $g_i:\mathbb {R}^n\times \mathbb {R}^{q_i}\rightarrow \mathbb {R}$, $i=1,\ldots ,m$, be functions such that for each $x \in \mathbb {R}^n$, $g_i(x,\cdot )$ is concave, $g_i(\cdot ,v_i)$ is a SOS-convex polynomial for each $v_i\in \mathcal V_i$ with degree at most $d_i$, and $\mathcal V_i \subset \mathbb {R}^{q_i}$ are convex compact sets. Let $\left\{ x\in \mathbb {R}^n : g_i(x,v_i) < 0\ \forall v_i\in \mathcal {V}_i, i=1,\ldots ,m\right\} \ne \emptyset$. Then, we have

$$\begin{aligned}&\inf \{f(x): g_i(x,v_i)\le 0\ \forall v_i\in \mathcal {V}_i, i=1,\ldots ,m\}\nonumber \\&\quad = \max _{\lambda _i \ge 0, v_i \in \mathcal {V}_i} \left\{ \mu : f(\cdot )+\sum _{i=1}^{m}{{\lambda }_i g_i\left( \cdot ,{v}_i\right) }-\mu \in \Sigma _{k_0}^2 \right\} ,\end{aligned}$$

where $k_0$ is the smallest even number such that $k_0 \ge \max \left\{ \deg f, \max _{1 \le i \le m}d_i\right\}$.

Proof

Note that, for any $\lambda _i \ge 0$, $v_i \in \mathcal {V}_i$ with $f(\cdot )+\sum _{i=1}^{m}{{\lambda }_i g_i\left( \cdot ,{v}_i\right) }-\mu \in \Sigma _{k_0}^2$ and any point $x \in \mathbb {R}^n$ such that $g_i(x,v_i) \le 0$ for all $v_i\in \mathcal {V}_i$, one has $f(x) \ge f(x)+\sum _{i=1}^{m}{{\lambda }_i g_i\left( x,{v}_i\right) } \ge \mu$. So, we see that $\inf \{f(x): g_i(x,v_i)\le 0\ \forall v_i\in \mathcal {V}_i,\ i=1,\ldots ,m\} \ge \max _{\lambda _i \ge 0, v_i \in \mathcal {V}_i}\{ \mu : f(\cdot )+\sum _{i=1}^{m}{{\lambda }_i g_i\left( \cdot ,{v}_i\right) }-\mu \in \Sigma _{k_0}^2 \}.$

To see the reverse inequality, we may assume without loss of generality that $c:=\inf \{f(x): g_i(x,v_i)\le 0\ \forall v_i\in \mathcal {V}_i,\ i=1,\ldots ,m\} \in \mathbb {R}$. By the usual convex programming duality and the robust Slater condition,

$$\begin{aligned}&\inf \{f(x):g_i(x,v_i) \!\le \! 0, \, \forall \, v_i \!\in \! \mathcal {V}_i\} \!=\! \inf \{f(x): \max _{v_i \in \mathcal {V}_i} g_i(x,v_i) \!\le \! 0, i=1,2,\ldots , m\} \\&\quad = \max \limits _{\begin{array}{c} \lambda _i \ge 0 \end{array}}\,\inf _{x\in \mathbb {R}^n}\left\{ f(x) \!+\! \sum _{i=1}^{m}\lambda _i \max _{v_i \in \mathcal {V}_i}g_i(x,v_i)\right\} \!=\! \max \limits _{\begin{array}{c} \lambda _i\ge 0 \end{array}}\,\inf _{x\in \mathbb {R}^n} \max _{v_i \in \mathcal {V}_i}\left\{ f(x) \!+\! \sum _{i=1}^{m}\lambda _i g_i(x,v_i)\right\} , \end{aligned}$$

where the attainment of the maximum is guaranteed by the robust Slater condition.

Note that $x \mapsto g_i(x,v_i)$ is SOS-convex (and so convex) and $v_i \mapsto g_i(x,v_i)$ is concave. From the convex-concave minimax theorem, we have, for each $\lambda _i \ge 0$,

$$\begin{aligned} \inf _{x\in \mathbb {R}^n} \max _{v_i \in \mathcal {V}_i}\left\{ f(x)+\sum _{i=1}^{m}\lambda _i g_i(x,v_i)\right\} =\max \limits _{v_i\in \mathcal {V}_i} \inf _{x\in \mathbb {R}^n}\left\{ f(x)+\sum _{i=1}^{m}\lambda _i g_i(x,v_i)\right\} . \end{aligned}$$

So, $\inf \{f(x):g_i(x,v_i) \le 0, \, \forall \, v_i \in \mathcal {V}_i\} = \max \nolimits _{v_i\in \mathcal {V}_i, \lambda _i \ge 0} \inf _{x\in \mathbb {R}^n}\left\{ f(x)+\sum _{i=1}^{m}\right.$ $\left. \lambda _i g_i(x,v_i)\right\} .$ Hence, there exist $\bar{v}_i\in \mathcal {V}_i$ and $\bar{\lambda }_i\ge 0$, for $i=1,\ldots ,m$, such that $f(x) + \sum _{i=1}^{m}\bar{\lambda }_i g_i\left( x,\bar{v}_i\right) \ge c$ for all $x\in \mathbb {R}^n.$

Let $h(x):=f(x) + \sum _{i=1}^{m}{\bar{\lambda }_i g_i\left( x,\bar{v}_i\right) } - c$. Then, $h\ge 0$ and it is also a SOS-convex polynomial, as $f(\cdot )$ and $g\left( \cdot ,\bar{v}_i\right)$ are all SOS-convex. So, by Lemma 2.2, we obtain that $\min _{x\in \mathbb {R}^n}h(x) = h(x^*)$ for some $x^*\in \mathbb {R}^n$. The polynomial $L(x):=h(x)-h(x^*)$ is again SOS-convex. Moreover, $L(x^*)=0$ and $\nabla L(x^*)=0$. Then, $L$ is a sum of squares polynomial as a consequence of Lemma 2.1. So we get that $f(x)+\sum _{i=1}^{m}{\bar{\lambda }_i g_i\left( x,\bar{v}_i\right) } - c - h(x^*) = \sigma _1(x) \quad \forall x\in \mathbb {R}^n,$ where $\sigma _1 \in \Sigma ^2_{k_0}$ and $k_0$ is the smallest even number such that $k_0 \ge \max \left\{ \deg f, \max _{1 \le i \le m}d_i\right\}$. Note that a sums-of-squares polynomial must be of even degree. As $h(x^*) \ge 0$, $\sigma _0(\cdot ) := \sigma _1(\cdot ) + h(x^*)$ is also a sum of squares with degree at most $k_0$. Therefore, $\sigma _0 \in \Sigma ^2_{k_0}$ and $f(x)+\sum _{i=1}^{m}{\bar{\lambda }_i g_i\left( x,\bar{v}_i\right) } - c = \sigma _0(x)$ for all $x\in \mathbb {R}^n.$ Hence, $c \le \max _{\lambda _i \ge 0, v_i \in \mathcal {V}_i}\{ \mu : f(\cdot )+\sum _{i=1}^{m}{{\lambda }_i g_i\left( \cdot ,{v}_i\right) }-\mu \in \Sigma _{k_0}^2 \}$ and the conclusion follows. $\square$

Remark 2.1

(Intractability of general SOS-relaxation problems) In general, finding the optimal value of a robust SOSCP using the SOS-relaxation problem can still be an intrinsically hard problem. For example, consider the following robust convex quadratic optimization problem:

$$\begin{aligned} (P_4)&\inf x^TAx + 2a^T x +\alpha \\&s.t. g_i(x,v_i) \le 0, \quad \forall \, v_i^T Q_i^l v_i \le 1, l=1,\ldots ,k, i=1,\ldots ,m, \end{aligned}$$

where

$$\begin{aligned} g_i(x,v_i)=\left\| \left( \overline{B}_i^0\!\!+\!\!\sum _{j=1}^s v_i^j \overline{B}_i^j \right) x\right\| ^2 + 2\left( \overline{b}_i^0\!+\!\sum _{j=1}^s v_i^j \overline{b}_i^j\right) ^Tx \!\!+\!\! \left( \overline{\beta }_i^0\!\!+\!\!\sum _{j=1}^s v_i^j \overline{\beta }_i^j \right) ,\nonumber \\ \end{aligned}$$

(2.5)

$v_i=(v_i^1,\ldots ,v_i^s)$, $Q_i^l \succ 0$, for $l=1,\ldots ,k$, $i=1,\ldots ,m$, and $k \ge 2$. It was shown in [8, Section 3.2.2] that checking the robust feasibility of the problem $(P_4)$, is an NP-hard problem [13] even under the robust Slater condition. By applying Theorem 2.3 with $f(x)=0$, we see that the robust feasibility problem of $(P_4)$ is equivalent to the condition that the optimal value of the following problem is zero:

$$\begin{aligned} \sup \limits _{\mu \in \mathbb {R}, v_i^TQ_i^lv_i \le 1, \lambda _i\ge 0} \left\{ \mu \ :\ \sum _{i=1}^{m}\lambda _i g_i(\cdot ,v_i)-\mu \in \Sigma ^2_2 \right\} . \end{aligned}$$

This, in particular, shows that finding the optimal value of a SOS-relaxation of a robust SOSCP, via Theorem 2.3, is also NP-hard.

Furthermore, observe that for the above intractable case, $v_i \mapsto g_i(x,v_i)$ with $g_i(x,v_i)$ defined in (2.5) is not affine.

A semidefinite programming approximation scheme for solving a robust nonconvex polynomial optimization problem has been given in [21] where it was shown that the optimal value of the robust optimization problem can be approached as close as possible by the optimal value of a sequence of semi-definite programming relaxation problem under mild conditions. In the next section, we show that, in the case of affine data parametrization (that is, $v_i \mapsto g_i(x,v_i)$ is affine), the optimal value of the robust SOS-convex polynomial optimization problem can be found by solving a single semi-definite programming problem under two commonly used data uncertainty sets: polytopic uncertainty and ellipsoidal uncertainty.

3 Exact SDP-relaxations and affine parameterizations

In this section we consider the robust SOSCP under affinely parameterized data uncertainty:

$$\begin{aligned} \begin{array}{crl} (P) &{} \inf &{} f(x) \\ &{} \text{ s.t. } &{} g_i(x,v_i)\le 0,\ \forall v_i\in \mathcal {V}_i,i=1,\ldots ,m, \end{array} \end{aligned}$$

where $f$ is a SOS-convex polynomial and the data is affinely parameterized in the sense that

$$\begin{aligned} g_i(\cdot ,v_i)&= g_i^{(0)}(\cdot ) + \sum _{r=1}^{q_i} v_i^{(r)}g_i^{(r)}(\cdot ), \\ v_i&= (v_i^{(1)},\ldots ,v_i^{(t_i)},v_i^{(t_i+1)},\ldots ,v_i^{(q_i)}) \in \mathcal {V}_i \subseteq \mathbb {R}_{+}^{t_i} \times \mathbb {R}^{q_i-t_i}, \end{aligned}$$

where $g_i^{(r)}$, for $r=1,\ldots ,t_i$, are SOS-convex polynomials, and $g_i^{(r)}$, for $r=t_i+1,\ldots ,q_i$, are affine functions, for all $i=1,\ldots ,m$.

In the following, we show, in the case of two commonly used uncertain sets, that the SOS-relaxation is exact and the relaxation problems can be represented as semi-definite programming (SDP) problems whenever a robust Slater condition is satisfied.

3.1 Polytopic data uncertainty

Consider the robust SOSCP with polytopic uncertainty, that is, $t_i=q_i$ and $\mathcal {V}_i=\bar{\mathcal {V}}_i$, where $\bar{\mathcal {V}}_i$ is given by

$$\begin{aligned} \bar{\mathcal {V}}_i :=\{v_i=(v_i^{(1)},\ldots ,v_i^{(q_i)})\in \mathbb {R}^{q_i}: v_i^{(r)} \ge 0, A_i v_i = b_i\}, \end{aligned}$$

for some matrix $A_i=(A_i^{jr}) \in \mathbb {R}^{l_i \times q_i}$ and $b_i=(b_i^j) \in \mathbb {R}^{l_i}$ such that $\bar{\mathcal {V}}_i$ is compact. This is equivalent to the condition that $A_i\in \mathbb {R}^{l_i \times q_i}$ and $\{x \in \mathbb {R}^{q_i}:A_ix=0\} \cap \mathbb {R}_+^{q_i}=\{0\}$. For instance, the simplex, $\mathcal {V}_i$, defined by $\mathcal {V}_i = \{v_i \in \mathbb {R}^{q_i} : v_i^{(r)} \ge 0, \sum _{r=1}^{q_i}v_i^{(r)}=1\}$, satisfies this assumption.

For the robust SOSCP $(P)$ with polytopic uncertainty sets $\bar{\mathcal {V}}_i$, named $(P^p)$, and each $k \in \mathbb {N}$, the corresponding relaxation problem $(D_k^p)$ can be stated as

$$\begin{aligned} \begin{array}{ccl} (D_k^p) &{} \max \limits _{\mu , w_i^r} &{} \mu \\ &{} s.t. &{} f + \sum \limits _{i=1}^{m} \sum \limits _{r=0}^{q_i} w_i^r g_i^{(r)} - \mu \in \Sigma ^2_{k} \\ &{}&{}\sum \limits _{r=1}^{q_i} A_{i}^{jr} w_i^r = w_i^0 b_i^j, \ \forall j=1,\ldots ,l_i, i=1,\ldots ,m, \\ &{}&{}\mu \in \mathbb {R}, w_i^r \ge 0, \ \forall r=0,1,\ldots ,q_i, i=1,\ldots ,m. \end{array} \end{aligned}$$

(3.1)

Let $k_0$ be the smallest even number such that $k_0 \ge \max _{0 \le r \le q_i, 1 \le i \le m}\{\deg f,\deg g_i^{(r)}\}$. Note that the relaxation problem $(D_k^p)$ can be equivalently rewritten as a semidefinite programming problem.

Theorem 3.1

(Exact SDP-relaxation under polytopic data uncertainty) Consider the uncertain SOS-convex polynomial optimization problem under polytope data uncertainty $(P^p)$ and its relaxation problem $(D_k^p)$. Suppose that

$$\begin{aligned} \left\{ x\in \mathbb {R}^n : g_i^{(0)}(x)+\sum _{r=1}^{q_i}v_i^{(r)}g_i^{(r)}(x)<0\ \forall v_i\in \bar{\mathcal {V}}_i, i=1,\ldots ,m\right\} \ne \emptyset . \end{aligned}$$

Then, the minimum of $(P^p)$ is attained and $\min (P^p)=\max (D_{k_0}^p)$, where $k_0$ is the smallest even number such that $k_0 \ge \max _{0 \le r \le q_i, 1 \le i \le m}\{\deg f,\deg g_i^{(r)}\}$.

Proof

Denote the extreme points of $\bar{\mathcal {V}}_i$ by $v_i^1,\ldots ,v_i^{s_i}$, $i=1,\ldots ,m$. As $v_i \mapsto g_i(x,v_i)$ is affine, $\max _{v_i \in \bar{\mathcal {V}}_i}g_i(x,v_i)=\max _{1 \le j \le s_i}g_i(x,v_i^j)$ for each fixed $x \in \mathbb {R}^n$. So, $\min (P^p)$ can be equivalently rewritten as follows:

$\min \limits _{x\in \mathbb {R}^n}\left\{ f(x) : g_i(x,v_{i}^j)\le 0, \forall j=1,\ldots ,s_i,\,\forall i=1,\ldots ,m\right\}$.

So, the minimum in the primal problem is attained in virtue of Lemma 2.2.

Now, according to Theorem 2.3, we have

$$\begin{aligned} \min (P^p)&= \min \limits _{x\in \mathbb {R}^n} \left\{ f(x) : g_i^{(0)}(x)+\sum _{r=1}^{q_i} v_i^{(r)}g_i^{(r)}(x) \le 0 \ \forall v_i\in \bar{\mathcal {V}}_i, i=1,\ldots ,m\right\} \nonumber \\&= \max \limits _{\begin{array}{c} \mu \in \mathbb {R}, \lambda _i \ge 0 \\ v_i^{(r)} \ge 0, A_i v_i = b_i \end{array}} \left\{ \mu \ :\ f + \sum \limits _{i=1}^{m} \lambda _i \left( g_i^{(0)}+\sum _{r=1}^{q_i} v_i^{(r)}g_i^{(r)} \right) - \mu \in \Sigma ^2_{k_0} \right\} .\nonumber \\ \end{aligned}$$

(3.2)

Let $w_i^{0}:=\lambda _i$ and $w_i^r:=\lambda _i v_i^{(r)}$ for $r=1,\ldots ,q_i$. Observe that, for each $i=1,\ldots ,m$,

$$\begin{aligned} \lambda _i \ge 0, v_i^{(r)} \ge 0\ \forall r=1,\ldots ,q_i, A_i v_i = b_i \end{aligned}$$

is equivalent to $w_i^r \ge 0 \ \forall r=0,1,\ldots ,q_i, \sum _{r=1}^{q_i} A_{i}^{jr}w_i^r = w_i^0 b_i^j \ \forall j=1,\ldots ,l_i.$ So, the maximization problem in (3.2) collapses to that one in (3.1) with $k=k_0$. Thus, $\min (P^p)=\max (D^p_{k_0})$. $\square$

The above theorem illustrates that, under the robust strict feasibility condition, an exact SDP relaxation holds for robust SOS-convex polynomial optimization problem under polytopic data uncertainty. In the special case of robust convex quadratic optimization problem, such an exact SDP relaxation result was given in [8, 11].

3.2 Restricted ellipsoidal data uncertainty

Consider the robust SOSCP with a restrictive ellipsoidal uncertainty, that is, $\mathcal {V}_i=\hat{\mathcal {V}}_i$ where $\hat{\mathcal {V}}_i$ is given by

$$\begin{aligned} \hat{\mathcal {V}}_i&{:=} \{ v_i \in \mathbb {R}^{q_i} : v_i^{(r)}\ge 0, r=1,\ldots ,t_i, \Vert (v_i^{(1)},\ldots ,v_i^{(t_i)})\Vert \nonumber \\&\le 1, \Vert (v_i^{(t_i+1)},\ldots ,v_i^{(q_i)})\Vert \le 1\}. \end{aligned}$$

(3.3)

In the case where all the SOS-convex polynomials are convex quadratic functions, the above problem collapses to the robust quadratic optimization problem under restrictive ellipsoidal uncertainty set which was examined in [14]. It is worth noting that the restriction of $v_i^{(r)} \ge 0$ is essential. Indeed, as pointed out in [14], if this nonnegative restriction is dropped, the corresponding robust quadratic optimization problem becomes NP-hard. It should also be noted that SOS-convexity of $g_i(\cdot , v)$ may not be preserved if $v_i^{(r)}$ is negative for some $r$ because $g_i(\cdot ,v)=g_i^{(0)}+\sum _{r=1}^{q_i} v_i^{(r)}g_i^{(r)}$ and $g_i^{(r)}$’s are all SOS-convex polynomials.

We begin this case by providing a numerically tractable characterization for a point $x$ to be feasible for the robust SOSCP under the above restricted ellipsoidal data uncertainty.

Lemma 3.1

(Robust feasibility characterization) Let $x \in \mathbb {R}^n$ and let $\hat{\mathcal {V}}_i$ be given in (3.3). Then $x$ is feasible for the robust SOSCP problem (P), that is, $g_i^{(0)}(x)+\sum _{r=1}^{q_i} v_i^{(r)}g_i^{(r)}(x) \le 0$, $\forall v_i\in \hat{\mathcal {V}}_i$, $i=1,2, \ldots , m$, if and only if, for each $i=1,\ldots ,m$, the following second-order cone programming problem has a non-negative optimal value

$$\begin{aligned} \begin{array}{c@{\quad }l} \max \limits _{\mu _1,\mu _2,\lambda _i^{(r)}} &{} -\,\,a_i^{(0)}-\mu _1-\mu _2 \\ s.t. &{} \Vert \big (a_i^{(1)}+\lambda _i^{(1)},\ldots , a_i^{(t_i)}+\lambda _i^{(t_i)}\big )\Vert \le \mu _1, \\ &{} \Vert \big (a_i^{(t_i+1)},\ldots , a_i^{(q_i)}\big )\Vert \le \mu _2, \\ &{} \mu _1, \mu _2 \ge 0, \lambda _i^{(r)}\ge 0, \ \forall r=1,\ldots ,t_i, \end{array} \end{aligned}$$

where $a_i^{(r)}=g_i^{(r)}(x)$, $r=0,1,\ldots ,q_i$.

Proof

Fix $i \in \{1,\ldots ,m\}$. Note that $x$ is feasible for robust SOSCP under the restricted ellipsoidal uncertainty is equivalent to

$$\begin{aligned} \left. \begin{array}{c} \Vert (v_i^{(1)},\ldots ,v_i^{(t_i)})\Vert \le 1, v_i^{(r)} \ge 0, r=1,\ldots ,t_i \\ \Vert (v_i^{(t_i+1)},\ldots ,v_i^{(q_i)})\Vert \le 1 \end{array} \right\} {\Rightarrow } -g_i^{(0)}(x)-\sum _{r=1}^{q_i} v_i^{(r)} g_i^{(r)}(x) \ge 0\!. \end{aligned}$$

Using the standard Lagrangian duality theorem, this can be equivalently rewritten as

$$\begin{aligned} 0 \le \inf \limits _{v_i \in \mathbb {R}^{q_i}} \left\{ -g_i^{(0)}(x)-\sum _{r=1}^{q_i} v_i^{(r)} g_i^{(r)}(x) : \begin{array}{l} \Vert (v_i^{(1)},\ldots ,v_i^{(t_i)})\Vert \le 1, \, v_i^{(r)} \ge 0, \, r=1,\ldots ,t_i \\ \Vert (v_i^{(t_i+1)},\ldots ,v_i^{(q_i)})\Vert \le 1 \end{array} \right\} \end{aligned}$$

$$\begin{aligned} = \max \limits _{\begin{array}{c} \mu _1,\mu _2 \ge 0 \\ \lambda _i \in \mathbb {R}^{t_i}_+ \end{array}} \ \inf \limits _{v_i \in \mathbb {R}^{q_i}} \ \left\{ \begin{array}{c} -g_i^{(0)}(x)-\sum \limits _{r=1}^{q_i} v_i^{(r)} g_i^{(r)}(x) + \mu _1(\Vert (v_i^{(1)},\ldots ,v_i^{(t_i)})\Vert -1) \\ +\,\mu _2(\Vert (v_i^{(t_i+1)},\ldots ,v_i^{(q_i)})\Vert -1)-\sum \limits _{r=1}^{t_i}\lambda _i^{(r)}v_i^{(r)} \ \end{array} \right\} \end{aligned}$$

$$\begin{aligned} = \max \limits _{\begin{array}{c} \mu _1,\mu _2 \ge 0 \\ \lambda _i \in \mathbb {R}^{t_i}_+ \end{array}} \ \left\{ -g_i^{(0)}(x)-\mu _1-\mu _2 : \begin{array}{l} \Vert \big (g_i^{(1)}(x)+\lambda _i^{(1)},\ldots , g_i^{(t_i)}(x)+\lambda _i^{(t_i)}\big )\Vert \le \mu _1, \\ \Vert \big (g_i^{(t_i+1)}(x),\ldots , g_i^{(q_i)}(x)\big )\Vert \le \mu _2. \end{array} \right\} \end{aligned}$$

Hence, the equivalence follows. $\square$

For the robust SOSCP $(P)$ with restricted ellipsoidal uncertainty sets $\hat{\mathcal {V}}_i$, named $(P^e)$, and each $k \in \mathbb {N}$, the corresponding relaxation problem $(D_k^e)$ can be stated as

$$\begin{aligned} \begin{array}{ccl} (D_k^e) &{} \max \limits _{\mu , w_i^r} &{} \mu \\ &{} s.t. &{} f + \sum \limits _{i=1}^{m} \sum \limits _{r=0}^{q_i} w_i^r g_i^{(r)} - \mu \in \Sigma ^2_{k} \\ &{}&{} \Vert (w_i^{1},\ldots ,w_i^{t_i})\Vert \le w_i^{0}, \ \forall i=1,\ldots ,m, \\ &{}&{} \Vert (w_i^{t_i+1},\ldots ,w_i^{q_i})\Vert \le w_i^{0}, \ \forall i=1,\ldots ,m, \\ &{}&{} w_i^r \ge 0, \ \forall r=0,1,\ldots ,t_i, \ \forall i=1,\ldots ,m. \\ &{}&{} \mu \in \mathbb {R}, w_i^r \in \mathbb {R}, \ \forall r=t_i+1\ldots ,q_i,\ \forall i=1,\ldots ,m. \end{array} \end{aligned}$$

(3.4)

Let $k_0$ be the smallest even number such that $k_0\ge \max _{0 \le r \le q_i, 1 \le i \le m}\{ \deg f, \deg g_i^{(r)}\}$. As in the polytopic case, the relaxation problem $(D_k^e)$ can be equivalently rewritten as a semidefinite programming problem with additional second-order cone constraints.

Theorem 3.2

(Exact SDP-relaxation under restricted ellipsoidal uncertainty) Consider the uncertain SOS-convex polynomial optimization problem under ellipsoidal data uncertainty $(P^e)$ and its relaxation problem $(D_k^e)$. Suppose that $\{x\in \mathbb {R}^n : g_i^{(0)}(x)+\sum _{r=1}^{q_i} v_i^{(r)} g_i^{(r)}(x)<0 \ \forall v_i\in \hat{\mathcal {V}}_i, i=1,\ldots ,m\} \ne \emptyset .$ Then, $\inf (P^e)=\max (D_{k_0}^e)$.

Proof

Using Theorem 2.3, we obtain that

$$\begin{aligned} \inf (P^e)&= \inf \limits _{x\in \mathbb {R}^n}\left\{ f(x) : g_i^{(0)}(x)+\sum _{r=1}^{q_i} v_i^{(r)}g_i^{(r)}(x) \le 0, \ \forall v_i\in \hat{\mathcal {V}}_i, i=1,\ldots ,m\right\} \nonumber \\&= \max \limits _{\begin{array}{c} \mu \in \mathbb {R}, \lambda _i\ge 0 \\ v_i\in \hat{\mathcal {V}}_i \end{array}} \left\{ \mu : f + \sum \limits _{i=1}^{m}\lambda _i g_i^{(0)} + \sum \limits _{i=1}^{m}\sum _{r=1}^{q_i} \lambda _i v_i^{(r)} g_i^{(r)} -\mu \in \Sigma ^2_{k_0} \right\} . \end{aligned}$$

(3.5)

To see the conclusion, define $w_i^{0}:=\lambda _i$ and $w_i^{r}:=\lambda _i v_i^{(r)}$, $r=1,\ldots ,q_i$. It can be verified that, for each $i=1,\ldots ,m$, $\lambda _i \ge 0,v_i\in \hat{\mathcal {V}}_i$ is equivalent to

$$\begin{aligned} \Vert (w_i^{1},\ldots ,w_i^{t_i})\Vert&\le w_i^{0}, \quad w_i^r \ge 0, \ \forall r=0,1,\ldots ,t_i, \\ \Vert (w_i^{t_i+1},\ldots ,w_i^{q_i})\Vert&\le w_i^{0}, \quad w_i^r \in \mathbb {R}, \ \forall r=t_i+1\ldots ,q_i. \end{aligned}$$

So, the maximization problem in (3.5) collapses to that one in (3.4) with $k=k_0$. Thus, we get $\inf (P^e)=\max (D^e_{k_0})$. $\square$

In the following example, we show that an exact SDP relaxation may fail for a robust convex (but not SOS-convex) polynomial optimization problem with linear constraints under restricted ellipsoidal data uncertainty.

Example 3.1

(Failure of exact SDP relaxation for convex polynomial optimization) Let $f$ be a convex homogeneous polynomial with degree at least $2$ in $\mathbb {R}^n$ which is not a sum-of-squares polynomial (see [5, 19], for the existence of such polynomials). Consider the following robust convex polynomial optimization problem under ellipsoidal data uncertainty:

$$\begin{aligned}&\min _{x \in \mathbb {R}^n} f(x) \\&{ s.t. }&v^Tx -1 \le 0, \, \forall \, v\in \mathcal {V}, \end{aligned}$$

where $\mathcal {V}=\{u\in \mathbb {R}^n : \Vert u\Vert \le 1\}$ is the uncertainty set and $g(x,v)=v^Tx -1$. It is easy to see that the strict feasibility condition is satisfied.

We now show that our SDP relaxation is not exact. To see this, as $f$ is a convex homogeneous polynomial with degree at least $2$ (which is necessarily nonnegative), we first note that $\inf _{x\in \mathbb {R}^n}\{f(x): g(x,v) \le 0, \, \forall \, v\in \mathcal {V}\}=0$. The claim will follow if we show that, for any $(w_1^0,w_1^1,\ldots ,w_1^n) \in \mathbb {R}^{n+1}$ with $\Vert (w_1^1,\ldots ,w_1^n) \Vert \le w_1^0$, $f(x)+(-1)w_1^0+\sum _{i=1}^n w_1^i x_i-0 \notin \Sigma _d^2$. Otherwise, there exists a sum of squares polynomial $\sigma$ with degree at most $d$ such that

$$\begin{aligned} f(x)+(-1)w_1^0+ \sum _{i=1}^n w_1^i x_i=\sigma (x), \ \text{ for } \text{ all } \quad x \in \mathbb {R}^n. \end{aligned}$$

(3.6)

for some $(w_1^0,w_1^1,\ldots ,w_1^n) \in \mathbb {R}^{n+1}$ with $\Vert (w_1^1,\ldots ,w_1^n) \Vert \le w_1^0$. Note that $\sigma$ is a sum-of-squares (and so, is nonnegative) and $w_1^0 \ge 0$. So, $f(x) \ge h(x):=-\sum _{i=1}^n w_1^i x_i$. As $f$ is a convex homogeneous polynomial with degree $m$ and $m \ge 2$, $h \equiv 0$. (Indeed, if there exists $\hat{x}$ such that $h(\hat{x}) \ne 0$, then by replacing $\hat{x}$ with $-\hat{x}$, if necessary, we can assume that $h(\hat{x}) >0$. Now, we have $t^mf(\hat{x})=f(t \hat{x}) \ge 2h(t\hat{x})=2th (\hat{x})$, for all $t > 0$. This shows us that $\frac{f(\hat{x})}{h(\hat{x})} \ge \frac{1}{t^{m-1}}$, for all $t>0$. This is a contradiction as $\frac{1}{t^{m-1}}\rightarrow \infty$ as $t \rightarrow 0$.) Hence, $f=\sigma +w_1^0$ and so $f$ is a sum-of-squares polynomial. This contradicts our construction of $f$. Therefore, our relaxation is not exact.

Corollary 3.1

(Robust SOSCP with a sum of quadratic and separable functions) Consider the uncertain convex polynomial optimization problem under restricted ellipsoidal data uncertainty $(P^e)$ and its relaxation problem $(D_k^e)$, where each $g_i^{(r)}$ is the sum of a separable convex polynomial and a convex quadratic function, i.e., $g_i^{(r)}(x)=\sum _{l=1}^nh_{il}^{(r)}(x_l)+\frac{1}{2}x^TB_i^{(r)}x + \big (b_i^{(r)}\big )^T x + \beta _i^{(r)}$ for some convex univariate polynomial $h_{il}^{(r)}$, $B_i^{(r)} \succeq 0$, $b_i^{(r)} \in \mathbb {R}^n$ and $\beta _i^{(r)} \in \mathbb {R}$. Suppose that $\{x\in \mathbb {R}^n : g_i^{(0)}(x)+\sum _{r=1}^{q_i} v_i^{(r)} g_i^{(r)}(x)<0 \ \forall v_i\in \hat{\mathcal {V}}_i, i=1,\ldots ,m\} \ne \emptyset .$ Then, we have $\inf (P^e)=\max (D_{k_0}^e)$.

Proof

The conclusion follows from the preceding theorem by noting that the sum of a separable convex polynomial and a convex quadratic function is a SOS-convex polynomial. $\square$

Corollary 3.2

(Robust convex quadratic problem) For problem $(P^e)$ and its relaxation problem $(D_2^e)$, let $f(x)= x^TAx + 2a^T x +\alpha$, $g_i^{(r)}(x) =x^TB_i^{(r)}x + 2\big (b_i^{(r)}\big )^T x + \beta _i^{(r)}$, $r=0,1,\ldots ,t_i$, and $g_i^{(r)}(x) =\big (b_i^{(r)}\big )^T x + \beta _i^{(r)}$, $r=t_i+1,\ldots ,q_i$, where $A,B_i^{(r)} \succeq 0$, $a,b_i^{(r)} \in \mathbb {R}^n$ and $\alpha ,\beta _i^{(r)} \in \mathbb {R}$. Suppose that $\{x\in \mathbb {R}^n : g_i^{(0)}(x)+\sum _{r=1}^{q_i} v_i^{(r)} \ g_i^{(r)}(x)<0\ \forall v_i\in \hat{\mathcal {V}}_i, i=1,\ldots ,m\} \ne \emptyset .$ Then, $\inf (P^e)=\max (D_{2}^e)$ and $\max (D_2^e)$ can be written as the following semi-definite programming problem

$$\begin{aligned}&\max \limits _{\mu , w_i^r}\quad \mu \nonumber \\&s.t. \quad \begin{pmatrix} A+\sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{t_i} w_i^{r}B_i^{(r)} &{}\quad a+\sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{q_i} w_i^{r}b_i^{(r)} \\ \left( a+\sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{q_i} w_i^{r}b_i^{(r)}\right) ^T &{}\quad \alpha +\sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{q_i} w_i^{r}\beta _i^{(r)}-\mu \end{pmatrix} \succeq 0\qquad \qquad \\&\Vert (w_i^{1},\ldots ,w_i^{t_i})\Vert \le w_i^{0}, \ \forall i=1,\ldots ,m, \nonumber \\&\Vert (w_i^{t_i+1},\ldots ,w_i^{q_i})\Vert \le w_i^{0}, \ \forall i=1,\ldots ,m, \nonumber \\&w_i^r \ge 0, \ \forall r=0,1,\ldots ,t_i, \ \forall i=1,\ldots ,m, \nonumber \\&\mu \in \mathbb {R}, w_i^r \in \mathbb {R}, \ \forall r=t_i+1\ldots ,q_i,\ \forall i=1,\ldots ,m. \nonumber \end{aligned}$$

(3.7)

Proof

As $f$ and each $g_i^{(r)}$, $r=1,\ldots ,q_i$, are convex quadratic functions, the conclusion follows by applying Theorem 3.2 and noting just that $f + \sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{q_i} w_i^{r} g_i^{(r)} \!\!\!\!-\!{\mu } {\in } {\Sigma ^2_{2}}$ is, in this particular case, equivalent to $\small {\begin{pmatrix} A+\sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{t_i} w_i^{r}B_i^{(r)} &{}\quad a+\sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{q_i} w_i^{r}b_i^{(r)} \\ (a+\sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{q_i} w_i^{r}b_i^{(r)})^T &{}\quad \alpha +\sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{q_i} w_i^{r}\beta _i^{(r)}-\mu \end{pmatrix}} \succeq 0.$ $\square$

We now present a numerical example verifying the exact SDP relaxation for a robust SOS-convex polynomial optimization problem where the objective function is neither a quadratic function nor a separable function.

Example 3.2

(Exact SDP relaxation for a robust non-quadratic SOS-convex problem) Consider the following robust SOSCP

$$\begin{aligned} (P_5)&\min x_1^4+2x_1^2-2x_1x_2+x_2^2 \\&{ s.t. } v_1x_1+v_2x_2 \le 1, \ \forall \ \Vert (v_1,v_2)\Vert \le 1. \end{aligned}$$

It is easy to verify that global solution of $(P_5)$ is $(0,0)$ with optimal value zero, and robust Slater condition is satisfied. The corresponding 4th-order relaxation problem is given by

$$\begin{aligned} \max \limits _{\begin{array}{c} \mu \in \mathbb {R}, \lambda \ge 0 \\ \Vert (v_1,v_2)\Vert \le 1 \end{array}} \{ \mu : x_1^4+2x_1^2-2x_1x_2+x_2^2+\lambda (v_1x_1+v_2x_2-1)-\mu \in \Sigma _4^2\}. \end{aligned}$$

It can be equivalently reformulated as the following semi-definite programming problem:

$$\begin{aligned}&\max \limits _{\mu , w, W}&\mu \\&s.t. W_{11}=-w^0-\mu , 2W_{12}=w^1, 2W_{13}=w^2, 2W_{23}+2W_{14}=-2, \\&2W_{16}+W_{33}=1, 2W_{15}+W_{22}=2, W_{55}=1, \\&W_{ij}=0 \ \,\forall (i,j) \notin \{(2,2),(2,3),(3,2),(3,3),(5,5)\} \cup \{\cup _{j=1}^6 (1,j)\}\\&\cup \{\cup _{j=1}^6 (j,1)\}, \\&\Vert (w^1,w^2)\Vert \le w^0, \mu \in \mathbb {R}, w=(w^0,w^1,w^2)\in \mathbb {R}^3, W=(W_{ij})\in S^6_+. \end{aligned}$$

Let $\mu ^*$ be the optimal value of the above SDP problem associated to a maximizer $(\mu ^*,\hat{w},\hat{W})$. Since $\hat{W} \succeq 0$, then $\hat{W}_{11} \ge 0$ which implies $-\hat{w}^0 - \mu ^* \ge 0$, and so, $\mu ^* \le -\hat{w}^0 \le 0$. On the other hand, define $\overline{W}\in S^6_+$ by $\overline{W}_{33} = \overline{W}_{55} = 1$, $\overline{W}_{22}=2$ and $\overline{W}_{23}=\overline{W}_{32}=-1$ and $\overline{W}_{ij}=0$ otherwise. Let $\overline{w}^0 = \overline{w}^1 = \overline{w}^2 = 0$ and $\overline{\mu }=0$. It is not hard to verify that $\overline{W} \succeq 0$ and $(\overline{\mu },\overline{w}, \overline{W})$ is a feasible point for the above SDP problem. So, $\mu ^* \ge 0$. Thus, $\mu ^*=0$ which shows that the SDP relaxation is exact.

We note that, in the special case of quadratically constrained optimization problem with linear objective function under restrictive ellipsoidal data uncertainty, the linear matrix inequality constraint in (3.7) reduces to

$$\begin{aligned} \left( \begin{array}{c@{\quad }c} \sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{t_i} w_i^{r}(L_i^{(r)})^TL_i^{(r)} &{} a+\sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{q_i} w_i^{r}b_i^{(r)} \\ \left( a+\sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{q_i} w_i^{r}b_i^{(r)}\right) ^T &{} \alpha +\sum \nolimits _{i=1}^{m}\sum \nolimits _{r=0}^{q_i}w_i^{r}\beta _i^{(r)}-\mu \end{array}\right) \succeq 0, \end{aligned}$$

where $L_i^{(r)} \in \mathbb {R}^{n \times s}$, is a matrix such that $B_i^{(r)}=L_i^{(r)}(L_i^{(r)})^T$. It then follows from [24] (see also [25, page 277]) that this linear matrix inequality can be equivalently written as second-order cone constraints. So, for a quadratically constrained optimization problem with linear objective function under restrictive ellipsoidal data uncertainty, the sums-of-squares relaxation problem can be equivalently rewritten as a second order cone programming problem, and hence, exact second-order cone relaxation holds under the robust strict feasibility condition.

A second-order cone reformulation of a robust quadratic optimization problem with linear objective function under restrictive ellipsoidal data uncertainty was first shown in [14]. Our Corollary provides an alternative second-order cone reformulation for this class of problems.

4 Conclusions and further research

In this paper, we studied robust solutions and semidefinite linear programming (SDP) relaxations for SOS-convex polynomial optimization problems in the face of data uncertainty. We established sums-of-squares polynomial representations characterizing robust solutions and exact SDP-relaxations of robust SOS-convex optimization problems under various commonly used uncertainty sets.

Our SDP-relaxation results show that the optimal value of a robust SOS-convex polynomial optimization problem under classes of polytopic and restricted ellipsoidal uncertainty sets can be found by solving a single semi-definite programming problem whenever a suitable regularity condition is satisfied.

On the other hand, how to obtain a minimizer of a robust SOS-convex polynomial optimization problem is also an important and interesting problem, which has not been addressed in this paper. However, it is known that, using the Lasserre hierarchy together with a moment approach [20], one can get a sequence of points converging to a minimizer of a general (possibly nonconvex) polynomial optimization problem under some regularity assumptions. It would be of interest to examine whether the moment approach of [20, 21] together with our exact SDP relaxation results in this paper leads to a sequence of points converging to a minimizer of a given robust SOS-convex polynomial optimization problem under some commonly used uncertainty sets. This would be examined in a forthcoming study.