Generalized Farkas’ lemma and gap-free duality for minimax DC optimization with polynomials and robust quadratic optimization

Abstract

Motivated by robust (non-convex) quadratic optimization over convex quadratic constraints, in this paper, we examine minimax difference of convex (dc) optimization over convex polynomial inequalities. By way of generalizing the celebrated Farkas’ lemma to inequality systems involving the maximum of dc functions and convex polynomials, we show that there is no duality gap between a minimax DC polynomial program and its associated conjugate dual problem. We then obtain strong duality under a constraint qualification. Consequently, we present characterizations of robust solutions of uncertain general non-convex quadratic optimization problems with convex quadratic constraints, including uncertain trust-region problems.

1 Introduction

In this paper, we consider the minimax difference of convex optimization problem,

$$\begin{aligned} {\mathrm{(P)}} \qquad \qquad \inf _{x\in {\mathbb {R}} ^{n}}\left\{ \max _{j=1,\ldots ,l}f_{j}(x)-h(x)\ :g_{i}(x)\le 0,\ i=1,\ldots ,m\right\} \end{aligned}$$

where $h:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}}$ is a convex function$,\ f_{j}: {\mathbb {R}}^{n}\rightarrow {\mathbb {R}},\,j=1,\ldots ,l\$ and $g_{i}:{\mathbb {R}} ^{n}\rightarrow {\mathbb {R}},\ i=1,2,\ldots ,m$ are convex polynomials. The minimax model $(\mathrm{P})$ was motivated by robust optimization of uncertain (not necessarily convex) quadratic functions, $\langle x,Ax\rangle +\langle a,x\rangle +\alpha$, over a convex set $K$, where the data $(A,a,\alpha )$ is assumed to be uncertain and it belongs to an uncertainty set $U$. As an illustration, consider the simple case, where the uncertainty set $U$ is given by the convex hull of the set $\{(A_{j},a_{j},\alpha _{j}):\ j=1,2,\ldots ,l\},\,A_{j}$ are $n\times n$ symmetric matrices, $a_{j}\in {\mathbb {R}}^{n}$ and $\alpha _{j}\in {\mathbb {R}}$. The worst-case solution of the uncertain quadratic minimization is obtained by solving the minimax problem

$$\begin{aligned} \min _{x\in K}\max _{j=1,\ldots ,l}\left\{ \langle x,A_{j}x\rangle +\langle a_{j},x\rangle +\alpha _{j}\right\} . \end{aligned}$$

It is a minimax dc-optimization problem of the form ${\mathrm{(P)}}$,

$$\begin{aligned} \min _{x\in K}\max _{j=1,\ldots ,l}\left\{ \langle x,(A_{j}+\rho I_{n})x\rangle +\langle a_{j},x\rangle +\alpha _{j}\right\} -\rho \langle x,x\rangle \end{aligned}$$

where $\rho =\max \{0,\max _{j=1,\ldots ,l}\{-\gamma _{\min }(A_{j})\}\},\,\gamma _{\min }(A_{j})$ is the least eigenvalue of $A_{j},\,A_{j}+\rho I_{n}$ is positive semidefinite, $f_{j}(x):=\langle x,(A_{j}+\rho I_{n})x\rangle +\langle a_{j},x\rangle +\alpha _{j}$, for $j=1,\ldots ,l$ and $h(x)=\rho \langle x,x\rangle$ are convex polynomials.

Minimax optimization of this form arises, for instance, when solving uncertain quadratic minimization problems with convex quadratic constraints, such as uncertain trust-region problems by robust optimization (see Sect. 5). Moreover, the model ${\mathrm{(P)}}$ includes the minimax polynomial optimization problems, examined recently in [13, 15], where $h=0$ and classes of DC-optimization problems which have been extensively studied in the literature (see [4–6, 8, 9, 16] and other references therein).

We make the following key contributions to global non-convex optimization.

• (i) We establish a generalization of the Farkas lemma by obtaining a complete dual characterization of the implication

  $$\begin{aligned} g_{i}(x)\le 0\quad i=1,\ldots ,m\Rightarrow \max _{j=1,\ldots ,l}f_{j}(x)-h(x)\ge 0 \end{aligned}$$

  in terms of conjugate functions without any qualifications. A numerical example is given to show that such a qualification-free generalization may fail when the functions $g_i$’s are not polynomials. Consequently, we also obtain a form of S-procedure [18] for non-convex quadratic systems. For a recent survey of generalizations of the Farkas lemma, see [7] and S-procedure, see [18].

• (ii) As an application of our generalized Farkas’ lemma, we show that there is no duality gap between $(\mathrm{P})$ and its associated conjugate dual problem, which, in particular, establishes that there is no duality gap between a dc polynomial program and its associated standard conjugate dual program. We also obtain strong duality between the problems under a normal cone constraint qualification, instead of the commonly used closed cone epigraph constraint qualification (see [5, 6, 8, 11, 12, 16]). We then derive necessary and sufficient global optimality conditions for classes of problems including fractional programming problems.

• (iii) Finally, we present complete dual characterizations of robust solutions of various classes of non-convex quadratic optimization problems in the face of data uncertainty in the objective as well as constraints. They include uncertain trust-region problems and nonconvex quadratic problems with convex quadratic constraints. For related recent results, see [14, 15], where conditions for robust solutions were given for minimax convex quadratic problems or classes of non-convex problems with no uncertainty in the objective function. The DC approach presented in this work allowed us to treat general non-convex quadratic objective functions.

The outline of the paper is as follows. In Sect. 2, we present basic definition and properties of convex polynomials and conjugate functions. In Sect. 3, we present a generalized Farkas’s lemma and its corresponding results for quadratic systems. In Sect. 4, we present duality results for the minimax DC-optimization problems ${{\mathrm{(P)}}}$ and their applications to fractional programming problems involving convex polynomials. In Sect. 5, we derive robust solution characterizations of various classes of quadratic optimization problems.

2 Preliminaries

We begin this section by fixing notation and preliminaries of convex sets, functions and polynomials. Throughout this paper, ${\mathbb {R}} ^{n}$ denotes the Euclidean space with dimension $n$. The inner product in ${\mathbb {R}}^{n}$ is defined by $\langle x,y\rangle :=x^{T}y$ for all $x,y\in {\mathbb {R}}^{n}$. The nonnegative orthant of ${\mathbb {R}}^{n}$ is denoted by ${\mathbb {R}}_{+}^{n}$ and is defined by ${\mathbb {R}}_{+}^{n}:=\{(x_{1},\ldots ,x_{n})\in {\mathbb {R}}^{n}\ :\ x_{i}\ge 0\}$. We say that the set $A$ is convex whenever $\mu a_{1}+(1-\mu )a_{2}\in A$ for all $\mu \in [0,1],\,a_{1},a_{2}\in A$. The convex hull of the set $A$ is denoted by ${\mathrm{co}}(A)$. A function $f:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}}$ is said to be convex if for all $\mu \in [0,1]$,

$$\begin{aligned} f((1-\mu )x+\mu y)\ \le (1-\mu )f(x)+\mu f(y) \end{aligned}$$

for all $x,y\in {\mathbb {R}}^{n}$. The function $f$ is said to be concave whenever $-f$ is convex. The epigraph of a function $f$, denoted by epi$f$, is defined by $\mathrm{epi}f:=\{(x,\alpha )\in {\mathbb {R}}^{n}\times {\mathbb {R}}\ |\ f(x)\le \alpha \}$.

The conjugate of a convex function $f:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}}$ is defined by, for any $u\in {\mathbb {R}}^{n},\,f^{*}(u)=\sup _{x\in {\mathbb {R}}^{n}}\left\{ u^{T}x-f(x)\right\}$ and, for any $x\in {{\mathbb {R}}} ^{n},\,f^{**}(x)=\sup _{u\in {\mathbb {R}}^{n}}\left\{ u^{T}x-f^{*}(x)\right\}$, respectively. If $f:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}}$ is convex, then $f=f^{**}$. For details, see [17, 19, 21]. The domain of $f^{*}$, denoted by $\mathrm{dom}f^{*}$, is defined by $\mathrm{dom}f^{*}:=\{u\in {\mathbb {R}}^{n}|f^{*}(u)<\infty \}$. The positive semi-definiteness of an $n\times n$ matrix $B$, denoted by $B\succeq 0$, is defined by $\langle x,Bx\rangle \ge 0$, for each $x\in {\mathbb {R}}^{n}$. If $f_{1}$ and $f_{2}:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}}$ are convex functions, then for $u\in {\mathbb {R}}^{n}$,

$$\begin{aligned} (f_{1}+f_{2})^{*}(u)=\min _{v\in {\mathbb {R}}^{n}}\left\{ f_{1}^{*}(v)+f_{2}^{*}(u-v)\right\} . \end{aligned}$$

(1)

For details, see [17, 19, 21].

The following useful result of convex polynomial systems was given in [2] and will play an important role later in the paper.

Lemma 2.1

[2] Let $f_{0},f_{1},\ldots ,f_{m}$ be convex polynomials on ${\mathbb {R}}^{n}$. Let $C:=\{x\in {\mathbb {R}}^{n}:f_{i}(x)\le 0,\ i=1,\ldots ,m\}\ne \emptyset$. Suppose that $\inf _{x\in C}f_{0}(x)>-\infty$. Then, $\arg \min _{x\in C}f_{0}(x)\ne \emptyset$.

The next lemma, given first in [13], follows easily from Lemma 2.1.

Lemma 2.2

Let $f_{0},f_{1},\ldots ,f_{m}$ be convex polynomials on ${\mathbb {R}}^{n}$. Then the set,

$$\begin{aligned} \Omega =\left\{ y\in {\mathbb {R}}^{n+1}:x\in {\mathbb {R}}^{n},\ f_{i}(x)\le y_{i},\ i=0,1,2,\ldots ,m\right\} \end{aligned}$$

is closed and convex.

Proof

Clearly, as $f_{i}$’s are convex functions, $\Omega$ is a convex set. Let $\{y_{0}^{k},y_{1}^{k},\ldots ,y_{m}^{k}\}\subset \Omega$ and $(y_{0}^{k},y_{1}^{k},\ldots ,y_{m}^{k})\rightarrow (y_{0},y_{1},\ldots ,y_{m})$ as $k\rightarrow \infty$. By the definition of $\Omega$, for each $k$, there exists $x^{k}\in {\mathbb {R}}^{n}$ such that $f_{i}(x^{k})\le y_{i}^{k}$. Now, consider the optimization problem

$$\begin{aligned} \begin{array}{lll} (\mathrm{P}_{0}) \qquad \qquad&\min _{x,z_{0},z_{1},\ldots ,z_{m}}&\left\{ \sum \limits _{i=0}^{m}(z_{i}-y_{i})^{2}:f_{i}(x)\le z_{i},\ i=0,1,\ldots ,m\right\} . \end{array} \end{aligned}$$

Then, $(\mathrm{P}_{0})$ is a convex polynomial optimization problem and $0\le \inf (\mathrm{P}_{0})\le \sum _{i=0}^{m}(y_{i}^{k}-y_{i})^{2}\ \ \rightarrow 0$, as $k\rightarrow \infty$. Hence, $\inf (\mathrm{P}_{0})=0$ and by Lemma 2.1, $\inf (\mathrm{P}_{0})$ is attained, and so, there exists $x^{*}\in {\mathbb {R}}^{n}$ such that $f_{i}(x^{*})\le y_{i}$. Thus, $(y_{0},y_{1},\ldots ,y_{m})\in \Omega$ and $\Omega$ is closed.

The following example shows that Lemma 2.2 may fail when all the functions involved in $\Omega$ are not convex polynomials.

Example 2.1

Let $f_{1}(x_{1},x_{2})=\sqrt{ x_{1}^{2}+x_{2}^{2}}-x_{1}$ and $f_{2}(x_{1},x_{2})=1-x_{2}$. Then, $f_{1}$ is not a polynomial. Define the set $C$ by

$$\begin{aligned} C:=\left\{ y\in {\mathbb {R}}^{2}:\ x\in {\mathbb {R}}^{2}, f_{i}(x)\le y_{i}\right\} . \end{aligned}$$

Then, for each integer $k\ge 1,(y_{1}^{k},y_{2}^{k})=(\sqrt{k^{2}+1} -k,0)\in C$ as $(f_{1}(k,1),f_{2}(k,1))\le (\sqrt{k^{2}+1}-k,0)$, and that $(y_{1}^{k},y_{2}^{k})=(\sqrt{k^{2}+1}-k,0)=(\frac{1}{\sqrt{k^{2}+1}+k} ,0)\rightarrow (0,0)$ as $k\rightarrow \infty$. However, $(0,0)\notin C$ because the system

$$\begin{aligned} \left\{ \begin{array}{l} \sqrt{x_{1}^{2}+x_{2}^{2}}-x_{1}\le 0 \\ 1-x_{2}\le 0 \end{array} \right. \end{aligned}$$

has no solution. Therefore, $C$ is not closed. $\square$

3 Generalized Farkas’ lemma

In this section, we present a generalization of Farkas’ lemma and a corresponding result for quadratic inequality systems, called $S$-procedure [18]. The generalized Farkas’ lemma holds without any regularity condition. Note that the simplex in ${\mathbb {R}}^{l}$ is given by $\Delta =\left\{ \delta \in {\mathbb {R}}_{+}^{l}:\sum _{i=1}^{l}\delta _{i}=1\right\}$.

Theorem 3.1

(Generalized Farkas’ lemma) Let $f_{j}:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}},\ j=1,\ldots ,l,\,g_{i}:{\mathbb {R}} ^{n}\rightarrow {\mathbb {R}},\,i=1,2,\ldots ,m$ be convex polynomials and $h: {\mathbb {R}}^{n}\rightarrow {\mathbb {R}}$ be a convex function. Let $K:=\{x\in {\mathbb {R}}^{n}:g_{i}(x)\le 0,\ i=1,\ldots ,m\}$ be non-empty. Then, the following statements are equivalent:

• (i) $g_{i}(x)\le 0\,\ i=1,\ldots ,m\Rightarrow \max _{j=1,\ldots ,l}f_{j}(x) -h(x) \ge 0;$

• (ii) $(\forall u\in \mathrm{\mathrm{dom}}h^{*},\ \epsilon >0)\ \left( \exists \lambda \in {\mathbb {R}}_{+}^{m},\ \mu \in \Delta ,\ v\in {\mathbb {R}}^{n}\right) :$

$$\begin{aligned} h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)+\epsilon \ge 0. \end{aligned}$$

(2)

Proof

$\mathrm{[(ii)]}\,\Rightarrow \mathrm{(i)}$] Note first, by the definition of a conjugate function, that $\mathrm{(ii)}$ is equivalent to the condition that, for any $u\in \mathrm{\mathrm{dom}}h^{*},\ \epsilon >0$, there exist $\lambda \in {\mathbb {R}}_{+}^{m},\ v\in {\mathbb {R}}^{n}$ and $\mu \in \Delta$ such that

$$\begin{aligned} h^{*}(u)+\inf _{x\in {\mathbb {R}}^{n}}\left\{ -\langle v,x\rangle +\sum _{j=1}^{l}\mu _{j}f_{j}(x)\right\} +\inf _{x\in {\mathbb {R}}^{n}}\left\{ -\langle u-v,x\rangle +\sum _{i=1}^{m}\lambda _{i}g_{i}(x)\right\} +\epsilon \ge 0, \end{aligned}$$

which shows that for any $x\in {\mathbb {R}}^{n}$,

$$\begin{aligned} h^{*}(u)-\langle u,x\rangle +\sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)+\epsilon \ge 0. \end{aligned}$$

Let $x\in K$. Then, $h^{*}(u)-\langle u,x\rangle +\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) (x)+\epsilon \ge 0$, as $\sum _{i=1}^{m}\lambda _{i}g_{i}(x) \le 0$. So, for any $u\in \mathrm{\mathrm{dom}}h^{*}$ and $\epsilon >0$, there exists $\mu \in \Delta$ such that for any $x\in K$:

$$\begin{aligned} \sum _{j=1}^{l}\mu _{j}f_{j}(x)+\epsilon \ge \langle u,x\rangle -h^{*}(u). \end{aligned}$$

Moreover, $\max _{j=1,\ldots ,l}f_{j}(x)=\max _{\delta \in \Delta }\delta _{j}f_{j}(x)\ge \sum _{j=1}^{l}\mu _{j}f_{j}(x)$. Hence, for any $u\in \mathrm{\mathrm{dom}}h^{*},\,\epsilon >0,\,\max _{j=1,\ldots ,l}f_{j}(x)+ \epsilon \ge \langle u,x\rangle -h^{*}(u)$ and so, $\max _{j=1,\ldots ,l}f_{j}(x)\ge \sup _{u\in \mathrm{\mathrm{dom}}h^{*}}\left\{ \langle u,x\rangle -h^{*}(u)\right\} =h(x)$. Thus (i) holds.

[$\hbox {(i)}$] $\Rightarrow \mathrm{(ii)}$] Assume that $\mathrm{(i)}$ holds. Let $u\in \mathrm{\mathrm{dom}}h^{*}$. Then, from $\mathrm{(i)}$, for each $x\in K$,

$$\begin{aligned} \max _{j=1,\ldots ,l}f_{j}(x)\ge h(x)\ge \sup _{v\in \mathrm{\mathrm{dom}} h^{*}}\langle v,x\rangle -h^{*}(v)\ge \langle u,x\rangle -h^{*}(u). \end{aligned}$$

So, for each $\epsilon >0,\,\max _{j=1,\ldots ,l}\ \left\{ f_{j}(x)+h^{*}(u)-\langle u,x\rangle \right\} +\epsilon >0$. For $j\in \{1,\ldots ,l\}$, let $\phi _{j}(x)=\ f_{j}(x)+h^{*} (u)-\langle u,x\rangle +\epsilon$, for $x\in {\mathbb {R}}^{n}$. Define a set $C$ by

$$\begin{aligned} C:=\left\{ (y,z)\in {\mathbb {R}}^{l}\times {\mathbb {R}}^{m}:\exists x\in {\mathbb {R}} ^{n}\ \ \text {s.t.}\ \ \phi _{j}(x)\le y_{j},\ \ j=1,\ldots ,l\ ;\ \ g_{i}(x)\le z_{i},\ \ i=1,\ldots ,m\right\} . \end{aligned}$$

Since $\phi _{j},\,j=1,\ldots ,l$ and $g_{i},\,i=1,\ldots ,m$ are convex polynomials, $C$ is a convex set. By Lemma 2.2, $C$ is closed.

Since $\max _{j}\phi _{j}(\cdot )>0$, we have $0\notin C$. By the strong separation theorem ([21, Theorem1.1.5]), there exist $(\gamma _{1},\ldots ,\gamma _{l},v_{1},\ldots ,v_{m})\ne 0,\ \alpha \in {\mathbb {R}},\ \delta _{0}>0$ such that for all $(y,z)\in C$,

$$\begin{aligned}&\left\langle (0,\ldots ,0),\left( \gamma _{1},\ldots ,\gamma _{l},v_{1},\ldots ,v_{m}\right) \right\rangle \le \alpha <\alpha +\delta _{0}\le \langle \left( y_{1},\ldots ,y_{l},z_{1},\ldots ,z_{m}\right) ,\\&\qquad \left( \gamma _{1},\ldots ,\gamma _{l},v_{1},\ldots ,v_{m}\right) \rangle . \end{aligned}$$

Since $C+{\mathbb {R}}_{+}^{m+l}\subset C$, it follows that $\gamma _{j}\ge 0,\ j=1,\ldots ,l$ and $v_{i}\ge 0,\ i=1,\ldots ,m$ and for any $(y,z)\in C$,

$$\begin{aligned} 0\le \alpha <\alpha +\delta _{0}\le \gamma _{1}y_{1}+\ldots \gamma _{l}y_{l}+\sum _{i=1}^{m}v_{i}z_{i}. \end{aligned}$$

As $K\ne \emptyset$, there exists $x_{0}\in {\mathbb {R}}^{n}$ such that $g_{i}(x_{0})\le 0,\ i=1,\ldots ,m$ and so, if $(\gamma _{1},\ldots ,\gamma _{l})=0,$ then $0\le \alpha <0$. This is a contradiction. So, $0\le (\gamma _{1},\ldots \gamma _{l})\ne 0$.

Let $\lambda _{i}=\frac{v_{i}}{\gamma _{1}+\ldots +\gamma _{l}}\ge 0,\ i=1,\ldots ,m$ and $\mu _{i}=\frac{\gamma _{i}}{\gamma _{1}+\ldots +\gamma _{l}} \ge 0,\ i=1,\ldots ,m$. Then, $\sum _{j=1}^{l}\mu _{j}=1$ and $\sum _{j=1}^{l}\mu _{j}\phi _{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)>0$, for any $x\in {\mathbb {R}}^{n}$, because $(\phi _{1}(x),\ldots ,\phi _{l}(x),\ g_{1}(x),\ldots ,g_{m}(x))\in C$ for each $x\in {\mathbb {R}}^{n}$. It shows that

$$\begin{aligned} \sum _{j=1}^{l}\mu _{j}f_{j}(\cdot )+\sum _{i=1}^{m}\lambda _{i}g_{i}(\cdot )+h^{*}(u)-\langle u,\cdot \rangle +\epsilon >0. \end{aligned}$$

(3)

So, for each $u\in \mathrm{dom}h^{*}$ and for each $\epsilon >0$, there exist $\lambda \in {\mathbb {R}}_{+}^{m}$ and $\mu \in \Delta$ such that, for each $x\in {\mathbb {R}}^{n}$,

$$\begin{aligned} h^{*}(u)+\epsilon >\langle u,x\rangle -\left[ \sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)\right] , \end{aligned}$$

which gives us that

$$\begin{aligned} h^{*}(u)+\epsilon \ge \left( \sum _{j=1}^{l}\mu _{j}f_{j}+\sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u). \end{aligned}$$

On the other hand, as $f_{j},\,j=1,\ldots ,l$ and $g_{i},\,i=1,\ldots ,m$ are real-valued convex functions, by (1), for $u\in \mathrm{dom}h^{*}$, there exists $v\in {\mathbb {R}}^{n}$ such that

$$\begin{aligned} \left( \sum _{j=1}^{l}\mu _{j}f_{j}+\sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u)=\sum _{j=1}^{l}\mu _{j}f_{j}^{*}(v)+\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v). \end{aligned}$$

So, we obtain,

$$\begin{aligned} h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)+\epsilon \ge 0. \end{aligned}$$

Hence (ii) holds. $\square$

The following example shows that generalized Farkas’s lemma may not hold for convex constraint systems, $g_{i}(x)\le \,0,i=1,\ldots ,m$, that are not polynomials.

Example 3.1

(Failure of generalized Farkas’s lemma for non-polynomial convex constraint systems) Let $f_{1}(x_1,x_2)=1-x_{2},\, f_{2}(x_1,x_2)=-x_{1},\,h(x_1,x_2)=x_{2}^{2}$ and $g_{1}(x_1,x_2)=\sqrt{x_{1}^{2}+x_{2}^{2}} -x_{1}$. Then,

$$\begin{aligned} h^{*}(u_1,u_2)=\left\{ \begin{array}{ll} \frac{u_{2}^{2}}{4}&{}\quad \text {if}\,\, u_{1}=0 \\ +\infty &{}\quad \text { otherwise.} \end{array} \right. \end{aligned}$$

Moreover, $\{x\in {\mathbb {R}}^{2}:g_{1}(x)\le 0\}={\mathbb {R}}_{+}\times \{0\}$ and so, $\max \{f_{1}(x),f_{2}(x)\}-h(x)\ge 0$ for each $x\in {\mathbb {R}} _{+}\times \{0\};$ thus, the implication

$$\begin{aligned} g_{1}(x)\le 0\Rightarrow \max \{f_{1}(x),f_{2}(x)\}-h(x)\ge 0 \end{aligned}$$

holds. Now, we show that the statement (ii):

$$\begin{aligned}&\forall u\in \mathrm{dom}h^{*},\quad \forall \epsilon >0,\quad \exists \left( \lambda \ge 0,\ v\in {\mathbb {R}}^{2}, \mu \in \Delta \right) ,\quad h^{*}(u)-\left( \sum \limits _{j=1}^{2}\mu _{j}f_{j}\right) ^{*}(v)\\&\quad -(\lambda g_{1})^{*}(u-v)+\epsilon \ge 0, \end{aligned}$$

fails. To see this, let $u=(0,0)\in \mathrm{dom}h^{*}$. Then, $h^{*}(0,0)=0,\, \sum \nolimits _{j=1}^{2}\mu _{j}f_{j}(x)=\mu _{1}(-x_{2})+\mu _{2}(-x_{1})+\mu _{1}$ and $(\sum \nolimits _{j=1}^{2}\mu _{j}f_{j})^{*}(v)=\sup _{x\in {\mathbb {R}}^{2}}\{v_{1}x_{1}+v_{2}x_{2}+\mu _{1}x_{2}+\mu _{2}x_{1}-\mu _{1}\}$. Moreover,

$$\begin{aligned} \left( \sum \limits _{j=1}^{2}\mu _{j}f_{j}\right) ^{*}(v)=\left\{ \begin{array}{ll} -\mu _{1}&{}\quad \text {if}\quad v=(-\mu _{2},-\mu _{1}) \\ +\infty &{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

For $\lambda =0$,

$$\begin{aligned} (\lambda g_{1})^{*}(w)=\left\{ \begin{array}{ll} 0&{}\quad \text {if}\,\, w=(0,0) \\ +\infty &{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

For $\lambda >0,\,(\lambda g_{1})^{*}(\mu _{2},\mu _{1})=\sup _{x\in {\mathbb {R}}^{2}}\{\mu _{2}x_{1}+\mu _{1}x_{2}-\lambda \sqrt{ x_{1}^{2}+x_{2}^{2}}+\lambda x_{1}\}=(\lambda ||x||)^{*}(\mu _{2}+\lambda ,\mu _{1})$. Since $\mu _{2}+\mu _{1}=1$, we get that

$$\begin{aligned} (\lambda ||x||)^{*}(\mu _{2}+\lambda ,\mu _{1})&= \left\{ \begin{array}{ll} 0&{}\quad \text {if}\ \ \frac{\sqrt{(\mu _{2}+\lambda )^{2}+(\mu _{1})^{2}}}{ \lambda }\le 1 \\ +\infty &{}\quad \text { otherwise} \end{array} \right. \\&= +\infty . \end{aligned}$$

Hence, for $u=0$, and $\epsilon >0$, for any $\lambda \ge 0$, we can see that $(\lambda g_{1})^{*}(-v)=+\infty$, whenever $v=(-\mu _{2},-\mu _{1})$, and $(\sum \nolimits _{j=1}^{2}\mu _{j}f_{j})^{*}(v)=+\infty$, whenever $v\ne (-\mu _{2},-\mu _{1})$, and so (ii) of Theorem 3.1 doesn’t hold. $\square$

The following example verifies our generalized Farkas’ lemma, involving convex polynomial constraint systems.

Example 3.2

(Convex polynomial constraint systems and generalized Farkas’ lemma) Let $f_{1}(x)=x_{1}^{8}+x_{1}^{2},\, f_{2}(x)=x_{2}^{2}-1,\,h(x)=\sqrt{x_{1}^{2}+x_{2}^{2}},\, g_{1}(x)=(x_{1}-1)^{2}+x_{2}^{2}-1,\,g_{2}(x)=x_{1}$ and $g_{3}(x)=x_{1}+x_{2}$. Then $f_{1},\ f_{2},\,g_{1},\,g_{2},\ g_{3}$ are convex polynomials, $h$ is convex, but is not a polynomial function. Moreover, $h^{*}(u)=\delta _{B}(u)$, where $\delta _{B}$ is the indicator function of the unit ball $B$ in ${\mathbb {R}}^{2}$.

Let us consider $\mathrm{(i)}$ and $\mathrm{(ii)}$ as in the previous theorem. We can see that $K:=\{x\in {\mathbb {R}}^{2}:g_{i}(x)\le 0,\ i=1,2,3\}=\{(0,0)\}$. Then $\mathrm{(i)}$ holds.

Let $d(x,u,\lambda ):=\mu _{1}f_{1}(x)+\mu _{2}f_{2}(x)+\sum _{i=1}^{3}\lambda _{i}g_{i}(x)+h^{*}(u)-\langle u,x\rangle$. Then,

$$\begin{aligned} d(x,u,\lambda )&= \mu _{1}\left( x_{1}^{8}+x_{1}^{2}\right) +(1-\mu _{1})\left( x_{2}^{2}-1\right) +\lambda _{1}\left( (x_{1}-1)^{2}+x_{2}^{2}-1\right) +\lambda _{2}x_{1}\\&\quad +\,\lambda _{3}(x_{1}+x_{2})-u_{1}x_{1}-u_{2}x_{2}. \end{aligned}$$

Thus, $d(x,u,\lambda )= \mu _{1}x_{1}^{8}+x_{1}^{2}(\mu _{1}+\lambda _{1})+x_{1}(\lambda _{2}+\lambda _{3}-2\lambda _{1}-u_{1})+\left( \lambda _{1}+1-\mu _{1}\right) x_{2}^{2}+(\lambda _{3}-u_{2})x_{2}+\mu _{1}-1$.

For $\lambda _{1}>0$, we get

$$\begin{aligned} \ d(x,u,\lambda )&= \mu _{1}x_{1}^{8}+\left( \sqrt{\mu _{1}+\lambda _{1}} x_{1}+\frac{(\lambda _{2}+\lambda _{3}-2\lambda _{1}-u_{1})}{2\sqrt{\lambda _{1}+\mu _{1}}}\right) ^{2}\\&\quad +\,\left( \sqrt{\lambda _{1}+1-\mu _{1}}x_{2}+\frac{ (\lambda _{3}-u_{2})}{2\sqrt{\lambda _{1}+1-\mu _{1}}}\right) ^{2}-\left( \frac{(\lambda _{2}+\lambda _{3}-2\lambda _{1}-u_{1})}{2\sqrt{\lambda _{1}+\mu _{1}}}\right) ^{2}\\&\quad -\,\left( \frac{(\lambda _{3}-u_{2})}{2\sqrt{ \lambda _{1}+1-\mu _{1}}}\right) ^{2}+\mu _{1}-1. \end{aligned}$$

By the above calculation, for any $u\in {\mathbb {R}}^{2},\epsilon >0$, taking $\mu _{1}=1$ and

$$\begin{aligned} \left\{ \begin{array}{ll} \lambda _{2}=2\lambda _{1}+u_{1},\lambda _{3}=0; &{}\quad \text {if}\,\,(u_1, u_2 )\in B,\quad u_{1}\ge 0,\quad u_{2}=0; \\ \lambda _{3}=2\lambda _{1}=u_{2},\ \lambda _{2}=u_{1}; &{}\quad \text {if}\,\,(u_1, u_2 )\in B,\quad u_{1}\ge 0,\quad u_{2}>0; \\ \lambda _{1}=2(-u_{1}+u_{2}),\ \lambda _{2}=2\lambda _{1}+u_{1}-u_{2},\lambda _{3}=u_{2}; &{}\quad \text {if}\,\,(u_1, u_2 )\in B,\quad u_{1}<0,\quad u_{2}\ge 0; \\ \lambda _{1}=\frac{u_{2}^{2}}{4\epsilon },\ \lambda _{2}=2\lambda _{1}+u_{1},\lambda _{3}=0;\ &{}\quad \text {if}\,\,(u_1, u_2 )\in B, \quad u_{1}\ge 0,\quad u_{2}<0; \\ \lambda _{1}=\frac{4u_{1}^{2}+u_{2}^{2}}{4\epsilon },\ \lambda _{2}=2\lambda _{1}-u_{1},\lambda _{3}=0;\ &{}\quad \text {if}\,\,(u_1, u_2 )\in B,\quad u_{1}<0,\quad u_{2}<0, \end{array} \right. \end{aligned}$$

we get that $-\left( \frac{\lambda _{2}+\lambda _{3}-2\lambda _{1}-u_{1}}{2 \sqrt{\lambda _{1}+\mu _{1}}}\right) ^{2}-\left( \frac{\lambda _{3}-u_{2}}{2 \sqrt{\lambda _{1}+1-\mu _{1}}}\right) ^{2}+\mu _{1}-1\ge -\epsilon$ and hence

$$\begin{aligned} \inf _{x\in {\mathbb {R}}^{2}}\left\{ \sum _{j=1}^{2}\mu _{j}f_{j}(x)+\sum _{i=1}^{3}\lambda _{i}g_{i}(x)+h^{*}(u)-\langle u,x\rangle +\epsilon \right\} \ge 0. \end{aligned}$$

So, we have,

$$\begin{aligned} h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}+\sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u)+\epsilon \ge 0, \end{aligned}$$

which is equivalent to

$$\begin{aligned} h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)+\epsilon \ge 0. \end{aligned}$$

for some $v\in {\mathbb {R}}^{2}$ by (1). It verifies $\mathrm{(ii)}$. $\square$

As a consequence of Theorem 3.1 we derive a form of the S-procedure for a quadratic system without any qualification. The S-procedure is a commonly used technique in stability analysis of nonlinear systems [18] and is a relaxation strategy for solving a quadratic inequality system or a quadratic optimization problem via a linear matrix inequality relaxation. Recall that, for a matrix $C$, the least eigenvalue of $C$ is denoted by $\gamma _{\min }(C)$.

Theorem 3.2

(S-Procedure) Let $B_{1},\ldots ,B_{m}$ be symmetric and positive semidefinite $n\times n$ matrices, $a_{1},\ldots ,a_{l},b_{1},\ldots ,b_{m}\in {\mathbb {R}}^{n}$ and $\alpha _{1},\ldots ,\alpha _{l},\beta _{1},\ldots ,\beta _{m}\in {\mathbb {R}}$. Let $A_{1},\ldots ,A_{l}$ be symmetric $n\times n$ matrices. Assume that $\gamma _{\min }(A_{j})<0$ for some $j\in \{1,\ldots ,l\}$. Let $\rho =\max _{j=1,\ldots ,l}\{-\gamma _{\min }(A_{j})\}$. Then the following statements are equivalent:

• (i) $\langle x,B_{i}x\rangle +\langle b_{i},x\rangle +\beta _{i}\le 0,\ i=1,\ldots ,m\ \Rightarrow \max _{j=1,\ldots ,l}\langle x,A_{j}x\rangle +\langle a_{j},x\rangle +\alpha _{j}\ge 0;\$

• (ii) $(\forall u\in {\mathbb {R}}^{n},\ \epsilon >0)\ \left( \exists \lambda \in {\mathbb {R}}_{+}^{m},\ \mu \in \Delta \right) \ \ \$

$$\begin{aligned} {\left( \begin{array}{l@{\quad }l} 2\left( \sum \nolimits _{j=1}^{l}\mu _{j}A_{j}+\rho I_{n}+\sum \nolimits _{i=1}^{m}\lambda _{i}B_{i}\right) &{} \sum \nolimits _{j=1}^{l}\mu _{j}a_{j}+\sum \nolimits _{i=1}^{m}\lambda _{i}b_{i}-u \\ \left( \sum \nolimits _{j=1}^{l}\mu _{j}a_{j}+\sum \nolimits _{i=1}^{m}\lambda _{i}b_{i}-u\right) ^{T} &{} 2\left( \sum \nolimits _{i=1}^{m}\lambda _{i}\beta _{i}+\frac{||u||^{2}}{4\rho }\ +\sum \nolimits _{j=1}^{l}\mu _{j}\alpha _{j}+\epsilon \right) \end{array} \right) \succeq 0}. \end{aligned}$$

Proof

Note that for any $j=1,\ldots ,l$ we can write [11]

$$\begin{aligned} \langle x,A_{j}x\rangle +\langle a_{j},x\rangle =\langle x,(A_{j}+\rho I_{n})x\rangle +\langle a_{j},x\rangle -\rho ||x||_{2}^{2}. \end{aligned}$$

(4)

Then for any $j\in \{1,\ldots ,l\},\,A_{j}+\rho I_{n}$ is positive semidefinite. Let $f_{j}(x)=\langle x,(A_{j}+\rho I_{n})x\rangle +\langle a_{j},x\rangle +\alpha _{j}$ for $j=1,\ldots ,l$ and $h(x)=\rho ||x||_{2}^{2}$. Thus, $f_{j},~j=1,\ldots ,l$ and $h$ are convex polynomials. We have $h^{*}(u)=\frac{||u||^{2}}{4\rho }$ for any $u\in {\mathbb {R}}^{n}$. Then, the conclusion follows from Theorem 3.1 by noting that

$$\begin{aligned}&\sum \limits _{j=1}^{l}\mu _{j}f_{j}(x)+\left( \sum \limits _{i=1}^{m}\lambda _{i}g_{i}\right) (x)+h^{*}(u)-\langle u,x\rangle +\epsilon \\&\quad =\sum \limits _{j=1}^{l}\mu _{j}\langle x,(A_{j}+\rho I_{n})x\rangle +\sum \limits _{j=1}^{l}\mu _{j}\langle a_{j},x\rangle \ +\sum \limits _{i=1}^{m}\lambda _{i}\left( \langle x,B_{i}x\rangle +\langle b_{i},x\rangle +\beta _{i}\right) \\&\qquad +\frac{||u||^{2}}{4\rho }-\langle u,x\rangle +\sum \limits _{j=1}^{l}\mu _{j}\alpha _{j}+\epsilon \\&\quad \ge 0, \end{aligned}$$

which is equivalent to for any $u\in \mathrm{\mathrm{dom}}h^{*}$ and $\epsilon >0$ there exist $\lambda \in {\mathbb {R}}_{+}^{m}$ and $\mu \in \Delta$ such that

$$\begin{aligned} {\left( \begin{array}{l@{\quad }l} 2\left( \sum \nolimits _{j=1}^{l}\mu _{j}A_{j}+\rho I_{n})+\sum \nolimits _{i=1}^{m}\lambda _{i}B_{i}\right) &{} \sum \nolimits _{j=1}^{l}\mu _{j}a_{j}+\sum \nolimits _{i=1}^{m}\lambda _{i}b_{i}-u \\ \left( \sum \nolimits _{j=1}^{l}\mu _{j}a_{j}+\sum \nolimits _{i=1}^{m}\lambda _{i}b_{i}-u\right) ^{T} &{} 2\left( \sum \nolimits _{i=1}^{m}\lambda _{i}\beta _{i}+\frac{||u||^{2}}{4\rho }\ +\sum \nolimits _{j=1}^{l}\mu _{j}\alpha _{j}+\epsilon \right) \end{array} \right) \succeq 0.} \end{aligned}$$

$\square$

A special case of Theorem 3.1, where $l=1$ is given in the following corollary which gives us a form of Farkas’ lemma for different convex polynomials.

Corollary 3.1

(Qualification-free DC Farkas Lemma) Let $h,\,f,\ g_{i}:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}},\, i=1,2,\ldots ,m$ be convex polynomials. Let $K:=\{x\in {\mathbb {R}} ^{n}:g_{i}(x)\le 0,\ i=1,\ldots ,m\}$ be non-empty. Then the following statements are equivalent:

• (i) $g_{i}(x)\le 0,\ i=1,\ldots ,m\ \Rightarrow \ f(x)\ge h(x);$

• (ii) $(\forall u\in \mathrm{\mathrm{dom}}h^{*},\ \epsilon >0)\ \left( \exists \lambda \in {\mathbb {R}}_{+}^{m},\ v\in {\mathbb {R}}^{n}\right) \ \ \ h^{*}(u)-f^{*}(v)-(\sum _{i=1}^{m}\lambda _{i}g_{i})^{*}(u-v)+\epsilon \ge 0$.

Proof

Applying Theorem 3.1 with $l=1$ and $f_{1}=f$, we see that $\Delta =\{1\}$ and the statement $(ii)$ of Theorem 3.1 collapses to the statement that $(\forall u\in \mathrm{dom}\, h^{*},\ \epsilon >0)\ \left( \exists \lambda \in {\mathbb {R}}_{+}^{m},\ \mu \in \{1\},\ v\in {\mathbb {R}} ^{n}\right) :$

$$\begin{aligned} h^{*}(u)-f^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)+\epsilon \ge 0, \end{aligned}$$

and so the conclusion follows. $\square$

When $h=0$ in Theorem 3.1, we obtain a version of Farkas’s lemma for convex polynomials, given in [15].

Corollary 3.2

[15] Let $f_{j},\ g_{i}:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}},\, j=1,\ldots ,l$ and $i=1,2,\ldots ,m$ be convex polynomials. Let $K:=\{x\in {\mathbb {R}}^{n}:g_{i}(x)\le 0,\ i=1,\ldots ,m\}$ be non-empty. Then the following statements are equivalent:

• (i) $g_{i}(x)\le 0,\ i=1,\ldots ,m\ \Rightarrow \ \max _{j=1,\ldots ,l}f_{j}(x)\ge 0;$

• (ii) $(\forall \epsilon >0)\ \left( \exists \lambda \in {\mathbb {R}} _{+}^{m},\ \mu \in \Delta \right) :\sum _{j=1}^{l}\mu _{j}f_{j}(\cdot )+\sum _{i=1}^{m}\lambda _{i}g_{i}(\cdot )+\epsilon \ge 0$.

Proof

Let $h=0$. Then, $\mathrm{dom}h^{*}=\{0\}$ and Theorem 3.1 gives us that (i) is equivalent to the statement that for each $\epsilon >0$, there exist $\lambda \in {\mathbb {R}}_{+}^{m},\ \mu \in \Delta$ and $v\in {\mathbb {R}}^{n}$ such that

$$\begin{aligned} -\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(-v)+\epsilon \ge 0. \end{aligned}$$

Hence, by the conjugate duality Theorem (see [10]), we obtain that

$$\begin{aligned} 0&\le -\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(-v)+\epsilon \\&\le \max _{w\in {\mathbb {R}}^{n}}\left\{ -\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(w)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(-w)\right\} +\epsilon \\&= \inf _{x\in {\mathbb {R}}^{n}}\left\{ \sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)\right\} +\epsilon . \end{aligned}$$

Hence, if (i) holds then (ii) also holds. The converse implication $\mathrm{(ii)\Rightarrow (i)}$ follows by construction. $\square$

4 Duality and minimax optimization

4.1 Duality

In this subsection, we present duality results for the minimax DC optimization problem

$$\begin{aligned} \begin{array}{lll} {\mathrm{(P)}} &{} \inf _{x\in {\mathbb {R}}^{n}}\max _{j=1,\ldots ,l} &{} f_{j}(x)-h(x)\\ &{} \text {s.t. } &{} g_{i}(x)\le 0,\ i=1,\ldots ,m, \end{array} \end{aligned}$$

where $h:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}}$ is a convex function$,\ f_{j}: {\mathbb {R}}^{n}\rightarrow {\mathbb {R}},\,j=1,\ldots ,l\$ and $g_{i}:{\mathbb {R}} ^{n}\rightarrow {\mathbb {R}},\ i=1,2,\ldots ,m$ are convex polynomials. The conjugate dual problem associated with ${\mathrm{(P)}}$ is given by

$$\begin{aligned} {\mathrm{(D)}}\ \ \ \inf _{u\in \mathrm{dom}h^{*}}\sup _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta ,v\in {\mathbb {R}}^{n}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)\right\} . \end{aligned}$$

We first show that there is no duality gap between problems (P) and (D).

Theorem 4.1

(Zero duality gaps & minimax DC polynomial programs) Let $f_{j}:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}},\ j=1,\ldots ,l$, let $g_{i}: {\mathbb {R}}^{n}\rightarrow {\mathbb {R}},\,i=1,\ldots ,m$ be convex polynomials and $h:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}}$ be a convex function. Let $K=\{x\in {\mathbb {R}}^{n}:g_{i}(x)\le 0,\ i=1,\ldots ,m\}\ne \emptyset$. Then,

$$\begin{aligned} \inf {\mathrm{(P)}}=\inf _{u\in \mathrm{dom}h^{*}}\sup _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta ,v\in {\mathbb {R}}^{n}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)\right\} . \end{aligned}$$

Proof

Let $x\in K$. Then, by the definition of conjugate of $h$,

$$\begin{aligned} \max _{j=1,\ldots ,l}f_{j}(x)-h(x)=\inf _{u\in \mathrm{dom}h^{*}}\max _{\mu \in \Delta }\left\{ \sum _{j=1}^{l}\mu _{j}f_{j}(x)+h^{*}(u)-\langle u,x\rangle \right\} . \end{aligned}$$

(5)

As $x\in K$, for each $\lambda \in {\mathbb {R}}_{+}^{m},\, \sum _{i=1}^{m}\lambda _{i}g_{i}(x)\le 0$ and so, for each $\mu \in \Delta$,

$$\begin{aligned} \sum _{j=1}^{l}\mu _{j}f_{j}(x)+h^{*}(u)-\langle u,x\rangle \ge \sup _{\lambda \in {\mathbb {R}}_{+}^{m}}\inf _{x\in {\mathbb {R}} ^{n}}\left\{ \sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)+h^{*}(u)-\langle u,x\rangle \right\} .\nonumber \\ \end{aligned}$$

(6)

It then follows from (5) and (6) that for $x\in K$,

$$\begin{aligned} \max _{j=1,\ldots ,l}f_{j}(x)-h(x)&= \inf _{u\in \mathrm{dom}h^{*}}\max _{\mu \in \Delta }\left\{ \sum _{j=1}^{l}\mu _{j}f_{j}(x)+h^{*}(u)-\langle u,x\rangle \right\} \\&\ge \inf _{u\in \mathrm{dom}h^{*}}\max _{\mu \in \Delta }\sup _{\lambda \in {\mathbb {R}}_{+}^{m}}\inf _{x\in {\mathbb {R}}^{n}}\left\{ \sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)+h^{*}(u)-\langle u,x\rangle \right\} . \end{aligned}$$

Now, by the definition of a conjugate function, we get that

$$\begin{aligned}&\inf _{u\in \mathrm{dom}h^{*}}\max _{\mu \in \Delta }\sup _{\lambda \in {\mathbb {R}}_{+}^{m}}\inf _{x\in {\mathbb {R}}^{n}}\left\{ \sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)+h^{*}(u)-\langle u,x\rangle \right\} \\&\qquad =\inf _{u\in \mathrm{dom}h^{*}}\max _{\mu \in \Delta }\sup _{\lambda \in {\mathbb {R}}_{+}^{m}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}+\sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}\left( u\right) \right\} \\&\qquad =\inf _{u\in \mathrm{dom}h^{*}}\max _{\mu \in \Delta }\sup _{\lambda \in {\mathbb {R}}_{+}^{m}}\max _{v\in {\mathbb {R}}^{n}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)\right\} . \end{aligned}$$

The last equation is obtained by the sum-conjugate formula (1). Therefore,

$$\begin{aligned} \inf {\mathrm{(P)}}\ge \inf _{u\in \mathrm{dom}h^{*}}\max _{\mu \in \Delta }\sup _{\lambda \in {\mathbb {R}}_{+}^{m}}\max _{v\in {\mathbb {R}} ^{n}}\left\{ \sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)+h^{*}(u)-\langle u,x\rangle \right\} , \end{aligned}$$

which shows that

$$\begin{aligned} \inf {\mathrm{(P)}}\ge \inf _{u\in \mathrm{dom}h^{*}}\sup _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta ,v\in {\mathbb {R}}^{n}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)\right\} . \end{aligned}$$

To see the reverse inequality, we may assume, without loss of generality, that $\inf {\mathrm{(P)}} > -\infty$, otherwise the conclusion follows immediately. Since $K\ne \emptyset$, we have $\overline{t}:=\inf \mathrm{(P)}\in {\mathbb {R}}$. Then, as $\max _{j=1,\ldots ,l}f_{j}(x)-\left( h(x)+ \overline{t}\right) \ge 0$ for all $x\in K$, by Theorem 3.1 we get that for any $\epsilon >0,\,u\in \mathrm{dom}h^{*}$, there exist $\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta ,\ v\in {\mathbb {R}}^{n}$ such that

$$\begin{aligned} h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)\ge \overline{t}-\epsilon . \end{aligned}$$

Consequently

$$\begin{aligned} \inf _{u\in \mathrm{dom}h^{*}}\sup _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta ,v\in {\mathbb {R}}^{n}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)\right\} \ge \overline{t}-\epsilon . \end{aligned}$$

Since the above inequality holds for any $\epsilon >0$, passing to the limit we obtain the desired inequality, which concludes the proof. $\square$

The following example shows that zero duality gap between (P) and (D) may not hold for convex constraints, $g_{i}(x)\le \,0,i=1,\ldots ,m$, that are not polynomials.

Example 4.1

(Non-zero-duality gaps for (P) with non-polynomial convex constraints) Consider the problem

$$\begin{aligned} \begin{array}{lll} \mathrm{(EP}_{1}\mathrm{)}\ &{} \min _{x\in {\mathbb {R}}^{2}}\max &{} \left\{ 1-x_{2},\ -x_{1}\right\} -x_{2}^{2}\ \\ &{} \ \ \text {s.t.}\ \ \ \ &{} \sqrt{x_{1}^{2}+x_{2}^{2}}-x_{1}\le 0, \end{array} \end{aligned}$$

where $f_{1}(x)=1-x_{2},\,f_{2}(x)=-x_{1},\,h(x)=x_{2}^{2}$ and $g_{1}(x)= \sqrt{x_{1}^{2}+x_{2}^{2}}-x_{1}$. Then, clearly, $\inf (\mathrm{EP}_{1})=1$. On the other hand,

$$\begin{aligned}&\inf _{u\in \mathrm{dom}h^{*}}\sup _{\lambda \in {\mathbb {R}}_{+},\mu \in \Delta ,v\in {\mathbb {R}}^{2}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-(\lambda g_{1})^{*}(u-v)\right\} \\&\quad \quad \le \sup _{\lambda \in {\mathbb {R}}_{+},\mu \in \Delta ,v\in {\mathbb {R}} ^{2}}\left\{ h^{*}(0)-\left( \sum _{j=1}^{2}\mu _{j}f_{j}\right) ^{*}(v)-(\lambda g_{1})^{*}(-v)\right\} . \end{aligned}$$

As we saw in Example 3.1, $h^{*}(0,0)=0$ and

$$\begin{aligned} \left( \sum \limits _{j=1}^{2}\mu _{j}f_{j}\right) ^{*}(v)=\left\{ \begin{array}{ll} -\mu _{1}&{}\quad \text {if}\quad v=(-\mu _{2},-\mu _{1}) \\ +\infty &{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

For $\lambda =0$,

$$\begin{aligned} \left( \lambda g_{1}\right) ^{*}(w)=\left\{ \begin{array}{ll} 0&{}\quad \text {if}\quad w=(0,0) \\ +\infty &{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

For $\lambda >0,\,(\lambda g_{1})^{*}(\mu _{2},\mu _{1})=+\infty$. Therefore,

$$\begin{aligned}&\inf _{u\in \mathrm{dom}h^{*}}\sup _{\lambda \in {\mathbb {R}}_{+},\mu \in \Delta ,v\in {\mathbb {R}}^{2}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{2}\mu _{j}f_{j}\right) ^{*}(v)-(\lambda g_{1})^{*}(u-v)\right\} \\&\quad \quad \le \sup _{\lambda \in {\mathbb {R}}_{+},\mu \in \Delta ,v\in {\mathbb {R}} ^{2}}\left\{ h^{*}(0)-\left( \sum _{j=1}^{2}\mu _{j}f_{j}\right) ^{*}(v)-(\lambda g_{1})^{*}(-v)\right\} =-\infty \text {,} \end{aligned}$$

which shows that

$$\begin{aligned} \inf \mathrm{(EP}_{1}\mathrm{)}=1\ne \inf _{u\in \mathrm{dom}h^{*}}\sup _{\lambda \in {\mathbb {R}}_{+},\mu \in \Delta ,v\in {\mathbb {R}} ^{2}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-(\lambda g)^{*}(u-v)\right\} =-\infty . \end{aligned}$$

$\square$

We use the same constraint system as in Example 3.2 to verify that the zero-duality gap property of a minimax DC program.

Example 4.2

(Verifying zero-duality gap for a minimax DC program). Consider the following example

$$\begin{aligned} \begin{array}{lll} \mathrm{(EP}_{2}\mathrm{)}\ &{} \min _{x\in {\mathbb {R}}^{2}}\max &{} \left\{ x_{1}^{8}+x_{1}^{2},\ x_{2}^{2}-1\right\} -\sqrt{x_{1}^{2}+x_{2}^{2}}\ \\ &{} \ \ \text {s.t.}\ \ \ \ &{} (x_{1}-1)^{2}+x_{2}^{2}\le 1\ \ \ \ \ \ \ \ \ \ \ \\ &{} &{} x_{1}\le 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ &{} &{} x_{1}+x_{2}\le 0.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{array} \end{aligned}$$

From Example 3.2, we can see that

$$\begin{aligned} 0&\ge \inf _{||u||_{*}\le 1}\sup _{\lambda \in {\mathbb {R}}_{+}^{3},\mu \in \Delta _{2},t\in {\mathbb {R}}}\left\{ t\in {\mathbb {R}}:\ \sum _{j=1}^{2}\mu _{j}f_{j}(\cdot )+\sum _{i=1}^{3}\lambda _{i}g_{i}(\cdot )+h^{*}(u)-\langle u,\cdot \rangle -t\ge 0\right\} \\&\ge \inf _{||u||_{*}\le 1}\sup _{\lambda \in {\mathbb {R}}_{+}^{3},\mu _{1}\in [0,1]}\left\{ -\left( \frac{(\lambda _{2}+\lambda _{3}\!-\!2\lambda _{1}-u_{1})}{2\sqrt{\lambda _{1}+\mu _{1}}}\right) ^{2}-\left( \frac{(\lambda _{3}-u_{2})}{2\sqrt{\lambda _{1}+1-\mu _{1}}}\right) ^{2}+\mu _{1}\!-\!1\right\} . \end{aligned}$$

Note that $||u||_{*}\le 1$, for $u=(u_{1},u_{2})$. Then, $u_{1},u_{2}\in [-1,1]$. Taking $\mu _{1}=1,\,\lambda _{2}=2\lambda _{1},\,\lambda _{3}=|u_{2}|$ and $\lambda _{1}\rightarrow +\infty$, we get

$$\begin{aligned} \inf ({\mathrm{EP}}_{2})&= \inf _{||u||_{*}\le 1}\sup _{\lambda \in {\mathbb {R}}_{+}^{3},\mu \in \Delta _{2}}\inf _{x\in {\mathbb {R}} ^{2}}\left\{ \sum _{j=1}^{2}\mu _{j}f_{j}(x)+\sum _{i=1}^{3}\lambda _{i}g_{i}(x)+h^{*}(u)-\langle u,x\rangle \right\} =0 \\&= \inf _{||u||_{*}\le 1}\sup _{\lambda \in {\mathbb {R}}_{+}^{3},\mu \in \Delta _{2}}\left\{ h^{*}(u)-\ \left( \sum _{j=1}^{2}\mu _{j}f_{j}+\sum _{i=1}^{3}\lambda _{i}g_{i}\right) ^{*}(u)\right\} . \end{aligned}$$

$\square$

A special case of Theorem 4.1 where $l=1$ shows that there is no duality gap between a difference of convex program and its associated dual program whenever $f,\,h$ and $g_i$’s are convex polynomials.

Corollary 4.1

(Zero duality gaps for DC polynomial programs) Let $h,\,f,\ g_{i}:{\mathbb {R}}^{n}\rightarrow R,\,i=1,2,\ldots ,m$ be convex polynomials. Let $K:=\{x\in {\mathbb {R}}^{n}:g_{i}(x)\le 0,\ i=1,\ldots ,m\}$ be non-empty. Then,

$$\begin{aligned} \inf _{x\in K}\{f(x)-h(x)\}=\inf _{u\in \mathrm{dom}h^{*}}\sup _{\lambda \in {\mathbb {R}}_{+}^{m},v\in {\mathbb {R}}^{n}}\left\{ h^{*}(u)-f^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)\right\} . \end{aligned}$$

Proof

Applying Theorem 4.1 with $l=1$ and $f_{1}=f$, we see that $\Delta =\{1\}$ and then the conclusion easily follows. $\square$

Under the additional assumption that $N_{K}(x)=\bigcup _{\lambda _{i}\ge 0,\lambda _{i}g_{i}(x)=0}\{\sum _{i=1}^{m}\lambda _{i}\nabla g_{i}(x)\}$, we obtain the following strong duality theorem for $({\mathrm{P}})$, where $N_{K}(x)$ is the normal cone in the sense that $N_{K}(x)=\{w\in {\mathbb {R}} ^{n}: \langle w,y-x \rangle \le 0,\ \forall y\in K\}$.

Theorem 4.2

(Strong Duality) Let $f_{j}:{\mathbb {R}} ^{n}\rightarrow {\mathbb {R}},\ j=1,\ldots ,l,\,g_{i}:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}},\,i=1,\ldots ,m$ be convex polynomials and $h:{\mathbb {R}} ^{n}\rightarrow {\mathbb {R}}$ be a convex function. Let $K=\{x\in {\mathbb {R}} ^{n}:g_{i}(x)\le 0,\ i=1,\ldots ,m\}\ne \emptyset$. Assume that $\inf ({ \mathrm{P}})$ is finite, and $N_{K}(x)=\bigcup _{\lambda _{i}\ge 0,\lambda _{i}g_{i}(x)=0}\{\sum _{i=1}^{m}\lambda _{i}\nabla g_{i}(x)\}$, for each $x\in K$. Then

$$\begin{aligned} \inf {\mathrm{(P)}}=\inf _{u\in \mathrm{dom}h^{*}}\max _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta ,v\in {\mathbb {R}}^{n}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)\right\} . \end{aligned}$$

Proof

Let $f:=\max _{j=1,\ldots ,l}f_{j}$. Using the basic properties of conjugate function of $h$, we have

$$\begin{aligned} \inf _{x\in K}\left\{ f(x)-h(x)\right\}&= \inf _{x\in K}\left\{ f(x)-\sup _{u\in \mathrm{dom}h^{*}}\left\{ \langle u,x\rangle -h^{*}(u)\right\} \right\} \\&= \inf _{u\in \mathrm{dom}h^{*}}\inf _{x\in K}\left\{ f(x)+h^{*}(u)-\langle u,x\rangle \right\} \end{aligned}$$

Let $u\in \mathrm{dom} h^{*}$. As $\inf ({\mathrm{P}})$ is finite, $\inf _{x\in K}\left\{ f(x)+h^{*}(u)-\langle u,x\rangle \right\}$ is also finite; thus,

$$\begin{aligned} \inf _{x\in K}\max _{\mu \in \Delta }\left\{ \sum _{j=1}^l\mu _jf_j(x)+h^{*}(u)-\langle u,x\rangle \right\} \end{aligned}$$

is finite, where $\Delta =\left\{ \delta \in {\mathbb {R}}_{+}^{l}:\sum _{j=1}^{l}\delta _{j}=1\right\}$. By the convex-concave minimax Theorem,

$$\begin{aligned} \max _{\mu \in \Delta }\inf _{x\in K}\left\{ \sum _{j=1}^l\mu _jf_j(x)+h^{*}(u)-\langle u,x\rangle \right\} \end{aligned}$$

is finite, and so, there exists $\overline{\mu }\in \Delta$ such that $\inf _{x\in K}\left\{ \sum _{j=1}^l\overline{\mu }_jf_j(x)+h^{*}(u)-\langle u,x\rangle \right\}$ is finite. Now, by Lemma 2.1, $\sum _{j=1}^l\overline{\mu }_jf_j(x)+h^{*}(u)-\langle u,x\rangle$ attains its infimum. Then, there exists $\overline{x} _{u}\in K$ such that $\sum _{j=1}^l\overline{\mu }_jf_j(\overline{x}_{u})+h^{*}(u)-\langle u,\overline{x} _{u}\rangle =\inf _{x\in K}\left\{ \sum _{j=1}^l\overline{\mu }_jf_j(x)\right. \left. +h^{*}(u)-\langle u,x\rangle \right\}$. The standard necessary optimality condition at $\overline{x}_{u}$ gives us that $0\in \sum _{j=1}^{l}\overline{\mu }_{j}\nabla f_{j}(\overline{x}_{u})-u+N_{K}(\overline{x}_{u})$. Employing the assumed normal cone constraint qualification, we can find $\overline{\lambda } _{i}\ge 0,i=1,2,\ldots ,m$ such that

$$\begin{aligned} 0=\sum _{j=1}^{l}\overline{\mu }_{j}\nabla f_{j}(\overline{x} _{u})-u+\sum _{i=1}^{m}\overline{\lambda }_{i}\nabla g_{i}(\overline{x}_{u})\quad \hbox {and}\quad \overline{\lambda }_{i}g_{i}(\overline{x}_{u})=0. \end{aligned}$$

Since $\sum _{j=1}^{l}\overline{\mu }_{j}f_{j}(\cdot )-\langle u,\cdot \rangle +\sum _{i=1}^{m}\overline{\lambda }_{i}g_{i}(\cdot )$ is convex, for all $x\in {\mathbb {R}}^{n}$

$$\begin{aligned}&\sum _{j=1}^{l}\overline{\mu }_{j}f_{j}(x)+h^{*}(u)-\langle u,x\rangle +\sum _{i=1}^{m}\overline{\lambda }_{i}g_{i}(x)\ge \sum _{j=1}^{l}\overline{ \mu }_{j}f_{j}(\overline{x}_{u})+h^{*}(u)-\langle u,\overline{x} _{u}\rangle \\&\quad +\,\sum _{i=1}^{m}\overline{\lambda }_{i}g_{i}(\overline{x}_{u}). \end{aligned}$$

Then,

$$\begin{aligned} \inf _{x\in {\mathbb {R}}^{n}}\left\{ \sum _{j=1}^{l}\overline{\mu }_{j}f_{j}(x)+h^{ *}(u)-\langle u,x\rangle +\sum _{i=1}^{m}\overline{\lambda } _{i}g_{i}(x)\right\} \ge \sum _{j=1}^{l}\overline{\mu }_{j}f_{j}(\overline{x} _{u})+h^{*}(u)-\langle u,\overline{x}_{u}\rangle .\nonumber \\ \end{aligned}$$

(7)

On the other hand, applying Theorem 4.1 by replacing $f_{j}(\cdot )$ by $\widetilde{f_{j}}(\cdot ):=f_{j}(\cdot )+h^{*}(u)-\langle u,\cdot \rangle$ and $h(\cdot )$ by $\widetilde{h}(\cdot )=0$ gives us

$$\begin{aligned} \inf _{x\in K}\max _{j=1,\ldots ,l}\widetilde{f_{j}}(x)&= \inf _{w\in \mathrm{dom} \widetilde{h}^{*}}\sup _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta ,v\in {\mathbb {R}}^{n}} \nonumber \\&\quad \left\{ \widetilde{h}^{*}(w)-\left( \sum _{j=1}^{l}\mu _{j} \widetilde{f}_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(w-v)\right\} \nonumber \\ \inf _{x\in K}\max _{j=1,\ldots ,l}\widetilde{f_{j}}(x)&= \inf _{w\in \{0\}}\sup _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta ,v\in {\mathbb {R}} ^{n}} \nonumber \\&\quad \left\{ \widetilde{h}^{*}(w)-\left( \sum _{j=1}^{l}\mu _{j}\widetilde{f} _{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(w-v)\right\} \nonumber \\&= \sup _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta }\left\{ \sup _{v\in {\mathbb {R}}^{n}}-\left( \sum _{j=1}^{l}\mu _{j}\widetilde{f}_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(-v)\right\} \nonumber \\&= \sup _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta }\left\{ \inf _{x\in {\mathbb {R}}^{n}}\sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)+h^{*}(u)-\langle u,x\rangle \right\} .\nonumber \\ \end{aligned}$$

(8)

Note that the equality in (8) follows by Fenchel’s duality. As $f( \overline{x}_{u})=\sum _{j=1}^{l}\overline{\mu }_{j}f_{j}(\overline{x}_{u})$ and $\inf _{x\in K}\max _{j=1,\ldots ,l}\widetilde{f_{j}}(x)=f(\overline{x} _{u})+h^{*}(u)-\langle u,\overline{x}_{u}\rangle$, it follows from (7) and (8) that

$$\begin{aligned}&\sum _{j=1}^{l}\overline{\mu }_{j}f_{j}(\overline{x}_{u})+h^{*}(u)-\langle u,\overline{x}_{u}\rangle \\&\qquad =\inf _{x\in {\mathbb {R}}^{n}}\left\{ \sum _{j=1}^{l}\overline{\mu } _{j}f_{j}(x)+h^{*}(u)-\langle u,x\rangle +\sum _{i=1}^{m}\overline{ \lambda }_{i}g_{i}(x)\right\} \\&\qquad =\max _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta }\inf _{x\in {\mathbb {R}} ^{n}}\left\{ \sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)+h^{*}(u)-\langle u,x\rangle \right\} . \end{aligned}$$

So, we have

$$\begin{aligned} \min _{x\in K}\{f(x)+h^{*}(u)-\langle u,x\rangle \}=\max _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta }\inf _{x\in {\mathbb {R}}^{n}}\left\{ \sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)+h^{*}(u)-\langle u,x\rangle \right\} . \end{aligned}$$

Hence, by the definition of conjugate function and (1)

$$\begin{aligned}&\min _{x\in K}\{f(x)+h^{*}(u)-\langle u,x\rangle \}=\max _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta }\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}+\sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u)\right\} \\&\qquad =\max _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta ,v\in {\mathbb {R}} ^{n}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)\right\} . \end{aligned}$$

As this is true for each $u\in \mathrm{dom}h^{*}$,

$$\begin{aligned} \inf {\mathrm{(P)}}&= \inf _{u\in \mathrm{dom}h^{*}}\min _{x\in K}\{f(x)+h^{*}(u)-\langle u,x\rangle \} \\&= \inf _{u\in \mathrm{dom}h^{*}}\max _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta ,v\in {\mathbb {R}}^{n}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)\right\} . \end{aligned}$$

$\square$

In the special case of $(P)$ where $l=1$, Theorem 4.2 yields that

$$\begin{aligned} \inf _{x\in K}\{f(x)-h(x)\}=\inf _{u\in \mathrm{dom}h^{*}}\max _{\lambda \in {\mathbb {R}}_{+}^{m},v\in {\mathbb {R}}^{n}}\left\{ h^{*}(u)-f^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)\right\} , \end{aligned}$$

(9)

whenever the normal cone constraint qualification, $N_{K}(x)=\bigcup _{ \lambda _{i}\ge 0,\lambda _{i}g_{i}(x)=0}\{\sum _{i=1}^{m}\lambda _{i}\nabla g_{i}(x)\}$, holds.

Note that the normal cone constraint qualification of Theorem 4.2 is guaranteed by the epigraph constraint qualification that the convex cone, $\bigcup _{\lambda \in {\mathbb {R}}_{+}^{m}}\mathrm{epi} (\sum _{i=1}^{m}\lambda _{i}g_{i})^{*}$, is closed. The epigraph constraint qualification has extensively been used to study convex as well as difference of convex optimization problems. For details, see [5, 6, 8, 11, 12, 16]. Note also that if the so-called Slater condition is satisfied in the sense that there exists $x_{0}\in {\mathbb {R}}^{n}$ such that $g_{i}(x_{0})<0$ for all $i=1,\ldots ,m$, then both the epigraph constraint qualification and the normal cone constraint qualification hold. For details, see [12] and [10, Section 2.2].

We obtain a global optimality characterization directly from Theorem 4.2 under the normal cone constraint qualification.

Corollary 4.2

(Global optimality characterization) Let $f_{j}:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}},\ j=1,\ldots ,l,\,g_{i}:{\mathbb {R}} ^{n}\rightarrow {\mathbb {R}},\,i=1,\ldots ,m$ be convex polynomials and $h: {\mathbb {R}}^{n}\rightarrow {\mathbb {R}}$ be a convex function. Let $K=\{x\in {\mathbb {R}}^{n}:g_{i}(x)\le 0,\ i=1,\ldots ,m\}\ne \emptyset$. Assume that $\inf ({\mathrm{P}})$ is finite, and $N_{K}(x)=\bigcup _{\lambda _{i}\ge 0,\lambda _{i}g_{i}(x)=0}\{\sum _{i=1}^{m}\lambda _{i}\nabla g_{i}(x)\}$ for each $x\in K$. A feasible point $\overline{x}\in K$ is a solution of ${\mathrm{(P)}}$ if and only if, for any $u\in \mathrm{dom}h^{*}$, there exist $\lambda \in {\mathbb {R}}_{+}^{m}$ and $\mu \in \Delta$ such that

$$\begin{aligned} \sum _{j=1}^{l}\mu _{j}f_{j}(\cdot )+\sum _{i=1}^{m}\lambda _{i}g_{i}(\cdot )+h^{*}(u)-\langle u,\cdot \rangle -\left( \max _{j=1,\ldots ,l}f_{j}(\overline{x} )-h(\overline{x})\right) \ge 0. \end{aligned}$$

(10)

Proof

Note first from Theorem 4.2 that

$$\begin{aligned} \inf {\mathrm{(P)}}=\inf _{u\in \mathrm{dom}h^{*}}\max _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta ,v\in {\mathbb {R}}^{n}}\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}\right) ^{*}(v)-\left( \sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u-v)\right\} . \end{aligned}$$

Using (1) and the definition of a conjugate function, we get that

$$\begin{aligned} \inf {\mathrm{(P)}}&= \inf _{u\in \mathrm{dom}h^{*}}\max _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta }\left\{ h^{*}(u)-\left( \sum _{j=1}^{l}\mu _{j}f_{j}+\sum _{i=1}^{m}\lambda _{i}g_{i}\right) ^{*}(u)\right\} \nonumber \\&= \inf _{u\in \mathrm{dom}h^{*}}\max _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta }\inf _{x\in {\mathbb {R}}^{n}}\left\{ h^{*}(u)+\sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)-\langle u,x\rangle \right\} .\nonumber \\ \end{aligned}$$

(11)

[$\Rightarrow$] Assume that $\overline{x}\in K$ is a solution of $\mathrm{(P)}$. As $\max _{j=1,\ldots ,l}f_{j}(\overline{x})-h(\overline{x})=\inf \mathrm{(P)}$, from (11), we have for any $u\in \mathrm{dom}h^{*}$, there exist $\lambda \in {\mathbb {R}}_{+}^{m}$ and $\mu \in \Delta$, such that for all $x\in {\mathbb {R}}^{n}$,

$$\begin{aligned} h^{*}(u)+\sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)-\langle u,x\rangle \ge \max _{j=1,\ldots ,l}f_{j}(\overline{x})-h( \overline{x}), \end{aligned}$$

and so $h^{*}(u)+\sum _{j=1}^{l}\mu _{j}f_{j}(\cdot )+\sum _{i=1}^{m}\lambda _{i}g_{i}(\cdot )-\langle u,\cdot \rangle -(\max _{j=1,\ldots ,l}f_{j}(\overline{x})-h(\overline{x}))\ge 0$. Hence, (10) holds.

[$\Leftarrow$] Conversely, let $\overline{x}\in K$. Assume that for any $u\in \mathrm{dom}h^{*}$, there exist $\lambda \in {\mathbb {R}} _{+}^{m}$ and $\mu \in \Delta$ such that (10) holds. Then, for any $u\in \mathrm{dom}h^{*}$,

$$\begin{aligned} \max _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta }\inf _{x\in {\mathbb {R}} ^{n}}\sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)+h^{*}(u)-\langle u,x\rangle \ge \left( \max _{j=1,\ldots ,l}f_{j}(\overline{x})-h(\overline{x})\right) \end{aligned}$$

By (11),

$$\begin{aligned} \inf {\mathrm{(P)}}&= \inf _{u\in \mathrm{dom}h^{*}}\max _{\lambda \in {\mathbb {R}}_{+}^{m},\mu \in \Delta }\inf _{x\in {\mathbb {R}}^{n}}\left\{ h^{*}(u)+\sum _{j=1}^{l}\mu _{j}f_{j}(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)-\langle u,x\rangle \right\} \\&\ge \max _{j=1,\ldots ,l}f_{j}(\overline{x})-h(\overline{x}), \end{aligned}$$

which shows that $\overline{x}$ is a solution of $\mathrm{(P)}$. $\square$

We now give an example verifying our global optimality characterization.

Example 4.3

Consider the problem

$$\begin{aligned} \begin{array}{lll} (\hbox {EP}_3)\quad \,\, &{} \min _{x\in {\mathbb {R}}^{2}}\max &{} \left\{ x_{1}^{8}+x_{1}x_{2}+x_{1}^{2}+x_{2}^{2}, \ x_{1}^{2}-3\right\} -\left( x_{1}^{2}+x_{2}^{2}\right) \\ &{} \ \ \text {s.t.}\,\, \, \, &{} x_{1}^{2}+x_{2}^{2}+4x_{1}+3\le 0\\ &{} &{}x_{2}\le 0. \end{array} \end{aligned}$$

Let $f_{1}(x_{1},x_{2})=x_{1}^{8}+x_{1}x_{2}+x_{1}^{2}+x_{2}^{2},\, f_{2}(x_{1},x_{2})=x_{1}^{2}-3,\,f(x_1, x_2)=\max _{j=1,2} f_j (x_1, x_2 ),\,h(x_{1},x_{2})=x_{1}^{2}+x_{2}^{2},\, g_{1}(x_{1},x_{2})=x_{1}^{2}+x_{2}^{2}+4x_{1}+3$ and $g_{2}(x_{1},x_{2})=x_{2}$. Then $f_{1},\ f_{2},\ h,\ g_{1},\ g_{2}$ are convex polynomials. Moreover, $h^{*}(u_{1},u_{2})=\frac{1}{4} (u_{1}^{2}+u_{2}^{2})$. We can see that $\overline{x}=(-1,0)$ is a solution of $(\mathrm{EP}_{3})$ and $\inf \mathrm{(EP}_{3}\mathrm{)}=1$.

Let $\overline{\lambda }=(4,1),\,\overline{\mu }_{1}=1$. Then, for any $u\in {\mathbb {R}}^{2}$ and $x\in {\mathbb {R}}^{2}$,

$$\begin{aligned}&\overline{\mu }_{1}f_{1}\left( x\right) +\left( 1-\overline{\mu }_{1}\right) f_{2}\left( x\right) +\sum \limits _{i=1}^{2}\overline{\lambda }_{i}g_{i}\left( x\right) +h^{*}\left( u\right) -\langle u,x\rangle \\&\quad = {\textstyle \left( \frac{1}{2}u_{1}-x_{1}\right) ^{2}\!+\!\left( \frac{1}{2} u_{2}\!-\!x_{2}\right) ^{2}\!+\!\left( x_{1}^{4}-1\right) ^{2}+2\left( x_{1}^{2}-1\right) ^{2}\!+\!5\left( x_{1}+1\right) ^{2} +\left( x_{1}+x_{2}+1\right) ^{2}}\\&\qquad {\textstyle +\left( x_{1}-x_{2}+1\right) ^{2}+\left( x_{1}+\frac{1}{2}x_{2}+1\right) ^{2}+\frac{7}{4} x_{2}^{2}+1}. \end{aligned}$$

So, for each $u\in \mathrm{dom}h^{*}$

$$\begin{aligned} \overline{\mu }_{1}f_{1}(x)+(1-\overline{\mu }_{1})f_{2}(x)+\sum _{i=1}^{2} \overline{\lambda }_{i}g_{i}(x)+h^{*}(u)-\langle u,x\rangle -f(\overline{ x})+h(\overline{x})\ge 0. \end{aligned}$$

It verifies the optimality condition of Corollary 4.2. $\square$

4.2 Minimax fractional programs

In this subsection, we derive global optimality characterizations for fractional programs, involving convex polynomials.

Corollary 4.3

Let $f_{j},\,\ j=1,\ldots ,l$ and $g_{i}:{\mathbb {R}}^{n}\rightarrow {\mathbb {R}},\ i=1,2,\ldots ,m$ be convex polynomials. Assume that $f_{j}(x)>0$ over the feasible set $K:=\left\{ x\in {\mathbb {R}}^{n}:g_{i}(x)\le 0,\ \ i=1,\ldots ,m\right\} ,\,K\ne \emptyset$ and the Slater condition holds. Let $\overline{x}\in K$ and $\overline{t}=\max _{j=1,\ldots ,l}\frac{f_{j}(\overline{x} )}{||\overline{x}||+1}$. Then, $\overline{x}$ is a solution of

$$\begin{aligned} (\mathrm{FP}_{1})\inf _{x\in {\mathbb {R}}^{n}}\max _{j=1,\ldots ,l}\left\{ \frac{ f_{j}(x)}{||x||+1}\ :\ \ g_{i}(x)\le 0,\ \ i=1,\ldots ,m\right\} , \end{aligned}$$

if and only if, for any $u\in {\mathbb {R}}^{n},\,||\frac{u}{\overline{t}} ||_{*}\le 1$, there exist $\lambda \in {\mathbb {R}}_{+}^{m}$, and $\mu \in \Delta$ such that

$$\begin{aligned} \sum _{j=1}^{l}\mu _{j}f_{j}(\cdot )+\sum \limits _{i=1}^{m}\lambda _{i}g_{i}(\cdot )- \overline{t}-\langle u,\cdot \rangle \ge 0. \end{aligned}$$

Proof

As $\overline{t}=\max _{j=1,\ldots ,l}\frac{f_{j}(\overline{x})}{ ||\overline{x}||+1},\ \overline{t}=\inf (\mathrm{FP}_{1})\in {\mathbb {R}}_{+}$, if and only if,

$$\begin{aligned} \inf _{x\in K}\left\{ \max _{j=1,\ldots ,l}f_{j}(x)-\overline{t}h(x)\right\} =0. \end{aligned}$$

(12)

Let $h(x)=||x||+1$. Then,

$$\begin{aligned} (\overline{t}h)^{*}(u)=\left\{ \begin{array}{ll} -\overline{t} &{}\quad \text {if}\,\,||\frac{u}{\overline{t}}||_{*}\le 1 \\ +\infty &{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

By Corollary 4.2, $\overline{x}\in K$ is a solution of (12), if and only if, for any $u\in \mathrm{dom}(\overline{t}h)^{*}$, there exist $\lambda \in {\mathbb {R}}_{+}^{m}$ and $\mu \in \Delta$ such that

$$\begin{aligned} \ \sum _{j=1}^{l}\mu _{j}f_{j}(\cdot )+\sum \limits _{i=1}^{m}\lambda _{i}g_{i}(\cdot )+\left( \overline{t}h\right) ^{*}(u)-\langle u,\cdot \rangle \ge 0. \end{aligned}$$

Thus, $\overline{x}\in K$ is a solution of $(\mathrm{FP}_{1})$ if and only if, for any $u\in \mathrm{dom}(\overline{t}h)^{*}$, there exist $\lambda \in {\mathbb {R}}_{+}^{m}$ and $\mu \in \Delta$ such that $\sum _{j=1}^{l}\mu _{j}f_{j}(\cdot )+\sum \nolimits _{i=1}^{m}\lambda _{i}g_{i}(\cdot )- \overline{t}-\langle u,\cdot \rangle \ge 0$. $\square$

Now, consider the minimax fractional quadratic programs of the form

$$\begin{aligned} (\mathrm{FP}_{2})\ \ \ \inf _{x\in {\mathbb {R}}^{n}}\max _{j=1,\ldots ,l}\left\{ \frac{\langle x,A_{j}x\rangle +\langle a_{j},x\rangle +\alpha _{j}}{\langle x,Cx\rangle +\langle c,x\rangle +\delta }\ :\ \ \langle x,B_{i}x\rangle +\langle b_{i},x\rangle +\beta _{i}\le 0,\ \ i=1,\ldots ,m\right\} , \end{aligned}$$

where $A_{1},\ldots ,A_{l},B_{1},\ldots ,B_{m}$ are symmetric and positive semidefinite $n\times n$ matrices, $a_{1},\ldots ,a_{l},\,b_{1},\ldots ,b_{m}\in {\mathbb {R}}^{n}$ and $\alpha _{1},\ldots ,\alpha _{l},\,\beta _{1},\ldots ,\beta _{m}\in {\mathbb {R}}$. The matrix $C$ is $n\times n$ symmetric and positive definite, $c\in {\mathbb {R}}^{n}$ and $\delta \in {\mathbb {R}}$. As before, we assume that $K:=\{x\in {\mathbb {R}}^{n}:\langle x,B_{i}x\rangle +\langle b_{i},x\rangle +\beta _{i}\le 0,\ i=1,\ldots ,m\}\ne \emptyset$.

Corollary 4.4

For problem $(\mathrm{FP}_{2})$, assume that $f_{j}(x)=\langle x,A_{j}x\rangle +\langle a_{j},x\rangle +\alpha _{j}>0,\,h(x)=\langle x,Cx\rangle +\langle c,x\rangle +\delta >0\$over the feasible set $K$ and the Slater condition holds. Assume that $C$ is positive definite. Let $\overline{x}\in K$ and $\overline{t}=\max _{j=1,\ldots ,l}\left\{ \frac{\langle \overline{x},A_{j}\overline{x}\rangle +\langle a_{j},\overline{x}\rangle +\alpha _{j}}{\langle \overline{x},C\overline{x}\rangle +\langle c,\overline{ x}\rangle +\delta }\right\}$. Then, $\overline{x}$ is a solution of $( \mathrm{FP}_{2})$, if and only if, $\forall u\in {\mathbb {R}}^{n},\,\exists \lambda \in {\mathbb {R}}_{+}^{m},\ \mu \in \Delta$ such that

$$\begin{aligned} {\left( \begin{array}{l@{\quad }l} 2\left[ \sum \nolimits _{j=1}^{l}\mu _{j}A_{j}+\sum \nolimits _{i=1}^{m}\lambda _{i}B_{i}\right] &{} \left[ \sum \nolimits _{j=1}^{l}\mu _{j}a_{j}+\sum \nolimits _{i=1}^{m}\lambda _{i}b_{i}-u- \overline{t}c\right] \\ \left[ (\sum \nolimits _{j=1}^{l}\mu _{j}a_{j}+\sum \nolimits _{i=1}^{m}\lambda _{i}b_{i}-u- \overline{t}c)^{T}\right] &{} 2\left[ \sum \nolimits _{j=1}^{l}\mu _{j}\alpha _{j}+\sum \nolimits _{i=1}^{m}\lambda _{i}\beta _{i}+\frac{1}{4\overline{t}}\langle u,C^{-1}u\rangle -\overline{t}\delta \right] \end{array} \right) \succeq 0}. \end{aligned}$$

Proof

Note that, $\inf (\mathrm{FP}_{2})=\overline{t}\in {\mathbb {R}}$, if and only if, $\inf (\mathcal {P}_{\overline{t}})=0$, where

$$\begin{aligned}&\left( \mathcal {P}_{\overline{t}}\right) \ \ \ \ \ \ \ \inf _{x\in K}\left\{ \max _{j=1,\ldots ,l}f_{j}(x)-\overline{t}h(x)\right\} \\&\quad =\inf _{x\in K}\left\{ \max _{j=1,\ldots ,l}\langle x,A_{j}x\rangle +\langle a_{j},x\rangle +\alpha _{j}-\overline{t}\left( \langle x,Cx\rangle +\langle c,x\rangle +\delta \right) \right\} \\&\quad =\inf _{x\in K}\left\{ \max _{j=1,\ldots ,l}\left[ \langle x,A_{j}x\rangle +\langle a_{j},x\rangle +\alpha _{j}-\overline{t}\left( \langle c,x\rangle +\delta \right) \right] -\overline{t}\langle x,Cx\rangle \right\} . \end{aligned}$$

Let $\widehat{f}_{j}(x)=\left[ \langle x,A_{j}x\rangle +\langle a_{j},x\rangle +\alpha _{j}-\overline{t}\left( \langle c,x\rangle +\delta \right) \right] ,\,j=1,\ldots ,l$ and $\widehat{h}(x)=\overline{t}\langle x,Cx\rangle$. We have $\widehat{h}^{*}(u)=\frac{1}{4\overline{t}} \langle u,C^{-1}u\rangle$.

Then, $\overline{x}$ is a solution of $(\mathcal {P}_{\overline{t}})$, if and only if, by Corollary 4.2, for any$~u\in {\mathbb {R}}^{n}$, there exist$~\lambda \in {\mathbb {R}}_{+}^{m}$ and $\mu \in \Delta$ such that

$$\begin{aligned}&\sum _{j=1}^{l}\mu _{j}\left[ \langle x,A_{j}x\rangle +\langle a_{j},x\rangle +\alpha _{j}-\overline{t}\left( \langle c,x\rangle +\delta \right) \right] +\sum \limits _{i=1}^{m}\lambda _{i}(\ \langle x,B_{i}x\rangle +\langle b_{i},x\rangle +\beta _{i}) \\&\quad +\,\frac{1}{4\overline{t}}\langle u,C^{-1}u\rangle -\langle u,x\rangle \ge 0, \end{aligned}$$

which is equivalent to

$$\begin{aligned} {\left( \begin{array}{l@{\quad }l} 2\left[ \sum \nolimits _{j=1}^{l}\mu _{j}A_{j}+\sum \nolimits _{i=1}^{m}\lambda _{i}B_{i}\right] &{} \left[ \sum \nolimits _{j=1}^{l}\mu _{j}a_{j}+\sum \nolimits _{i=1}^{m}\lambda _{i}b_{i}-u- \overline{t}c\right] \\ \left[ (\sum \nolimits _{j=1}^{l}\mu _{j}a_{j}+\sum \nolimits _{i=1}^{m}\lambda _{i}b_{i}-u- \overline{t}c)^{T}\right] &{} 2\left( \sum \nolimits _{j=1}^{l}\mu _{j}\alpha _{j}+\sum \nolimits _{i=1}^{m}\lambda _{i}\beta _{i}+\frac{1}{4\overline{t}}\langle u,C^{-1}u\rangle -\overline{t}\delta \right) \end{array} \right) \succeq 0}. \end{aligned}$$

$\square$

5 Robust solutions of uncertain quadratic problems

In this section, we present characterizations of robust solutions of classes of quadratic optimization problems under data uncertainty.

We begin with a quadratic problem where the data of both the constraints and the objective functions are uncertain. Note that for a $\left( n\times n\right)$ matrix $\Omega ,\ \,||\Omega ||_{\mathrm{spec}}$ is the spectral norm of $\Omega$ and is defined by $||\Omega ||_{\mathrm{spec}}=\sqrt{ \lambda _{\max }(\Omega ^{T}\Omega )}$. Consider the quadratic problem

$$\begin{aligned} \begin{array}{lll} (\mathrm{QP})\ &{} \inf _{x\in {\mathbb {R}}^{n}} &{} \langle x,Ax\rangle +\langle a,x\rangle \ +\alpha \\ &{} \text {s.t. }\ \ \ \ &{} \langle x,B_{i}x\rangle +2\langle b_{i},x\rangle \ +\beta _{i}\le 0,\ \ i=1,\ldots ,m. \end{array} \end{aligned}$$

where 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 {W}_{i}\mathcal {=}\left\{ (B_{i},b_{i},\beta _{i})\in S^{n}\times {\mathbb {R}}^{n}\times {\mathbb {R}}:\left\| \left( \begin{array}{ll} B_{i} &{} b_{i} \\ b_{i}^{T} &{} \beta _{i} \end{array} \right) -\left( \begin{array}{ll} \overline{B}_{i} &{} \overline{b}_{i} \\ \overline{b}_{i}^{T} &{} \overline{\beta }_{i} \end{array} \right) \right\| _{\mathrm{spec}}\le \delta _{i}\right\} , \end{aligned}$$

$\delta _{i}>0$, and $(A,a,\alpha )\in S^{n}\times {\mathbb {R}}^{n}\times {\mathbb {R}}$ is uncertain and it belongs to the uncertainty set

$$\begin{aligned} \mathcal {V}=\left\{ (A_{0},a_{0},\alpha _{0})+\sum _{k=1}^{l}\omega _{k}(A_{k},a_{k},\alpha _{k}):\ \omega =(\omega _{1},\ldots ,\omega _{l})\in {\mathbb {R}}^{l}\right\} , \end{aligned}$$

$\omega =\sum _{j=1}^{p}\tau _{j}v^{j},\ \tau \in \Delta _{p}$ for some $l,\ p\in \mathbb {N},\,v^{1},\ldots ,v^{p}\in {\mathbb {R}}_{+}^{l}$ and $(A_k, a_k, \alpha _k ) \in S^{n}\times {\mathbb {R}}^{n}\times {\mathbb {R}},\,k=1,\ldots ,l$.

The robust counterpart of $(\mathrm{QP})$, that finds a worst-case solution of $\mathrm{(QP)}$, is

$$\begin{aligned} \begin{array}{lll} (\mathrm{RQP}) &{} \inf _{x\in {\mathbb {R}}^{n}}\max _{(A,a,\alpha )\in \mathcal { V}} &{} \langle x,Ax\rangle \!+\!\langle a,x\rangle \ \!+\!\alpha \\ &{} \text {s.t. }\ \ \ &{} \langle x,B_{i}x\rangle \!+\!2\langle b_{i},x\rangle \ \!+\!\beta _{i}\le 0,\ \ \forall (B_{i},b_{i},\beta _{i})\in \mathcal {W}_{i},\ i=1,\ldots ,m. \end{array} \end{aligned}$$

Note that the constraints are enforced for all $(B_{i},b_{i},\beta _{i})$ in the uncertainty set $\mathcal {W}_{i},\ i=1,\ldots ,m$. Following robust optimization [3, 14], an optimal solution of the robust counterpart of an uncertain problem is a robust solution of the uncertain problem.

Let $K:=\{x\in {\mathbb {R}}^{n}:\langle x,B_{i}x\rangle +2\langle b_{i},x\rangle \ +\beta _{i}\le 0,\ \forall (B_{i},b_{i},\beta _{i})\in \mathcal {W}_{i},\ i=1,\ldots ,m\}$.

Theorem 5.1

(Characterization of Robust Solutions) For problem $(\mathrm{QP })$, assume that for $i=1,\ldots ,m,\,\overline{B}_{i}$ is positive semidefinite and the Slater condition holds. Let $\widehat{A} _{j}=A_{0}+\sum _{k=1}^{l}v_{k}^{j}A_{k},\,\widehat{a}_{j}=a_{0}+ \sum _{k=1}^{l}v_{k}^{j}a_{k}$ and $\widehat{\alpha }_{j}=\alpha _{0}+\sum _{k=1}^{l}v_{k}^{j}\alpha _{k}$ for $j=1,\ldots ,p$.

Let $\rho =\max _{j=1,\ldots ,p}\{-\gamma _{\min }(\widehat{A}_{j})\}$. Assume that $\gamma _{\min }(\widehat{A}_{j})<0$ for some $j\in \{1,\ldots$, $p\}$. Then $x^{*}\in K$ is a robust global minimizer of $\mathrm{(QP),}$ if and only if, for any $u\in {\mathbb {R}}^{n}$, there exist $\lambda \in {\mathbb {R}}_{+}^{m}$, and $\mu \in \Delta$ such that

$$\begin{aligned} \left( \begin{array}{l@{\quad }l} {2}\left[ \sum \nolimits _{j=1}^{p}\mu _{j}\widehat{A}_{j}\!+\!\rho I_{n}\!+\!\sum \nolimits _{i=1}^{m}\lambda _{i}(\overline{B}_{i}\!+\!\delta _{i}I_{n})\right] &{} \left[ \sum \nolimits _{j=1}^{p}\mu _{j}\widehat{a}_{j}\!+\!2\sum \nolimits _{i=1}^{m}\lambda _{i} \overline{b}_{i}\!-\!u\right] \\ \left[ \sum \nolimits _{j=1}^{p}\mu _{j}\widehat{a}_{j}\!+\!2\sum \nolimits _{i=1}^{m}\lambda _{i} \overline{b}_{i}\!-\!u\right] ^{T} &{} 2\left[ \sum \nolimits _{i=1}^{m}\lambda _{i}\left( \overline{\beta }_{i}\!+\!\delta _{i}\right) \!+\!\frac{||u||^{2}}{4\rho } \!+\!\sum \nolimits _{j=1}^{p}\mu _{j}\widehat{\alpha }_{j}-\overline{t}\right] \end{array} \right) {\succeq 0,} \nonumber \\ \end{aligned}$$

(13)

where $\overline{t}=\max _{(A,a,\alpha )\in \mathcal {V}}\langle x^{*},Ax^{*}\rangle +\langle a,x^{*}\rangle \ +\alpha .\$

Proof

We first note that for each $x\in {\mathbb {R}}^{n}$

$$\begin{aligned}&\max _{(A,a,\alpha )\in \mathcal {V}}\langle x,Ax\rangle +\langle a,x\rangle \ +\alpha \\&\qquad =\max _{j=1,\ldots ,p}\left\{ \left\langle x,\left( A_{0}+\sum _{k=1}^{l}v_{k}^{j}A_{k}\right) x\right\rangle +\left\langle a_{0}+\sum _{k=1}^{l}v_{k}^{j}a_{k},x\right\rangle \ +\alpha _{0}+\sum _{k=1}^{l}v_{k}^{j}\alpha _{k}\right\} . \end{aligned}$$

Since $\widehat{A}_{j}=A_{0}+\sum _{k=1}^{l}v_{k}^{j}A_{k},\ \widehat{a} _{j}=a_{0}+\sum _{k=1}^{l}v_{k}^{j}a_{k}$ and $\widehat{\alpha }_{j}=\alpha _{0}+\sum _{k=1}^{l}v_{k}^{j}\alpha _{k}$, we have

$$\begin{aligned} \max _{(A,a,\alpha )\in \mathcal {V}}\langle x,Ax\rangle +\langle a,x\rangle \ +\alpha =\max _{j=1,\ldots ,p}\left\{ \langle x,\widehat{A}_{j}x\rangle +\langle \widehat{a}_{j},x\rangle \ +\widehat{\alpha }_{j}\right\} . \end{aligned}$$

(14)

Note also that $K\subseteq \{x\in {\mathbb {R}}^{n}:\langle x,\left( \overline{B }_{i}+\delta _{i}I_{n}\right) x\rangle +2\langle \overline{b}_{i},x\rangle \ +\overline{\beta }_{i}+\delta _{i}\le 0,\ i=1,\ldots ,m\}$ because $\left( \overline{B}_{i}+\delta _{i}I_{n},\overline{b}_{i},\overline{\beta } _{i}+\delta _{i}\right) \in \mathcal {W}_{i},\ i=1,\ldots ,m$.

On the other hand, it is easy to check that, for each $(B_{i},b_{i},\beta _{i})\in \mathcal {W}_{i},\$all the eigenvalues of the matrix $\left( \begin{array}{l@{\quad }l} \overline{B}_{i}+\delta _{i}I_{n} &{} \overline{b}_{i} \\ \overline{b}_{i}^{T} &{} \overline{\beta }_{i}+\delta _{i} \end{array} \right) -\left( \begin{array}{l@{\quad }l} B_{i} &{} b_{i} \\ b_{i}^{T} &{} \beta _{i} \end{array} \right)$ are non-negative, and so, $\left( \begin{array}{l@{\quad }l} \overline{B}_{i}+\delta _{i}I_{n} &{} \overline{b}_{i} \\ \overline{b}_{i}^{T} &{} \overline{\beta }_{i}+\delta _{i} \end{array} \right) -\left( \begin{array}{l@{\quad }l} B_{i} &{} b_{i} \\ b_{i}^{T} &{} \beta _{i} \end{array} \right)$ is a positive semidefinite matrix. Hence,

$$\begin{aligned} \left( \begin{array}{l} x \\ 1 \end{array} \right) ^{T}\ \left( \left( \begin{array}{l@{\quad }l} \overline{B}_{i}+\delta _{i}I_{n} &{} \overline{b}_{i} \\ \overline{b}_{i}^{T} &{} \overline{\beta }_{i}+\delta _{i} \end{array} \right) -\left( \begin{array}{l@{\quad }l} B_{i} &{} b_{i} \\ b_{i}^{T} &{} \beta _{i} \end{array} \right) \right) \left( \begin{array}{l} x \\ 1 \end{array} \right) \ge 0. \end{aligned}$$

This shows that $\{x\in {\mathbb {R}}^{n}:\langle x,\left( \overline{B} _{i}+\delta _{i}I_{n}\right) x\rangle +2\langle \overline{b}_{i},x\rangle \ + \overline{\beta }_{i}+\delta _{i}\le 0,\ i=1,\ldots ,m\}\subseteq K$. Thus, $K=\{x\in {\mathbb {R}}^{n}:\langle x,\left( \overline{B}_{i}+\delta _{i}I_{n}\right) x\rangle +2\langle \overline{b}_{i},x\rangle \ +\overline{ \beta }_{i}+\delta _{i}\le 0,\ i=1,\ldots ,m\}$.

Using (14) and the fact that $K=\{x\in {\mathbb {R}}^{n}:\langle x,\left( \overline{B}_{i}+\delta _{i}I_{n}\right) x\rangle +2\langle \overline{b}_{i},x\rangle \ +\overline{\beta }_{i}+\delta _{i}\le 0,\ i=1,\ldots ,m\}$, the problem $(\mathrm{RQP})$ can be written as

$$\begin{aligned} \begin{array}{ll} \inf _{x\in {\mathbb {R}}^{n}}\max _{j=1,\ldots ,p} &{} \langle x,\widehat{A} _{j}x\rangle +\langle \widehat{a}_{j},x\rangle \ +\widehat{\alpha }_{j}\\ \text {s.t. } &{} \langle x,\left( \overline{B}_{i}+\delta _{i}I_{n}\right) x\rangle +2\langle \overline{b}_{i},x\rangle \ +\overline{\beta }_{i}+\delta _{i}\le 0,\ i=1,\ldots ,m. \end{array} \end{aligned}$$

The quadratic function $\langle x,\widehat{A}_{j}x\rangle +\langle \widehat{a }_{j},x\rangle \ +\widehat{\alpha }_{j}$ can be written as $\langle x,\left( \widehat{A}_{j}+\rho I_{n}\right) x\rangle +\langle \widehat{a}_{j},x\rangle \ +\widehat{\alpha }_{j}\ -\rho ||x||^{2}$ where $\langle x,\left( \widehat{A }_{j}+\rho I_{n}\right) x\rangle +\langle \widehat{a}_{j},x\rangle \ + \widehat{\alpha }_{j}$ is convex for any $j=1,\ldots ,p$ and $\rho =\max _{j=1,\ldots ,p}\{-\gamma _{\min }(\widehat{A}_{j})\}$. By our assumption, $\rho \,>0$. Now, the problem $(\mathrm{RQP})$ becomes

$$\begin{aligned} \begin{array}{l@{\quad }l} \inf _{x\in {\mathbb {R}}^{n}}\max _{j=1,\ldots ,p} &{} \left\{ \langle x,\left( \widehat{A}_{j}+\rho I_{n}\right) x\rangle +\left\langle \widehat{a}_{j},x\right\rangle \ +\widehat{\alpha }_{j}\ -\rho ||x||^{2}\ \right\} \\ \text {s.t. } &{} \langle x,\left( \overline{B}_{i}+\delta _{i}I_{n}\right) x\rangle +2\langle \overline{b}_{i},x\rangle \ +\overline{\beta }_{i}+\delta _{i}\le 0,\ i=1,\ldots ,m. \end{array}\nonumber \\ \end{aligned}$$

(15)

By Corollary 4.2, $x^{*}\in K$ is a solution of (15) if and only if for any $u\in {\mathbb {R}}^{n}$, there exist $\lambda \in {\mathbb {R}}_{+},\mu \in \Delta$ such that

$$\begin{aligned}&\sum \limits _{j=1}^{p}\mu _{j}\left( \langle x,\left( \widehat{A}_{j}+\rho I_{n}\right) x\rangle +\langle \widehat{a}_{j},x\rangle \ +\widehat{\alpha } _{j}\right) \nonumber \\&\quad +\sum \limits _{i=1}^{m}\lambda _{i}\left[ \langle x,\left( \overline{B}_{i}+\delta _{i}I_{n}\right) x\rangle +2\langle \overline{b}_{i},x\rangle \ +\overline{ \beta }_{i}+\delta _{i}\right] +\frac{||u||^{2}}{4\rho }-\langle u,x\rangle - \overline{t}\ge 0,\nonumber \\ \end{aligned}$$

(16)

as required.

Conversely, assume for any $u\in {\mathbb {R}}^{n}$, there exist $\lambda \in {\mathbb {R}}_{+},\mu \in \Delta$ relation (13) holds. The linear matrix inequality (13) can be equivalent to relation (16). Hence, $x^{*}$ is a solution of problem in (15) and then, $x^{*}$ is a robust global minimizer of $(\mathrm{QP})$. $\square$

Let us consider the uncertain trust region problem as a special case of problem $(\mathrm{QP})$

$$\begin{aligned} \begin{array}{lll} (\mathrm{TP}) &{} \inf _{x\in {\mathbb {R}}^{n}} &{} \langle x,Ax\rangle +\langle a,x\rangle +\alpha \\ &{} \text {s.t. }\ \ \ \ &{} ||x-x_{0}||\le s, \end{array} \end{aligned}$$

(17)

where the data $\left( A,a,\alpha \right)$ is uncertain and it belongs to the uncertainty set $\mathcal {V}$, which is given by

$$\begin{aligned} \mathcal {V}=\left\{ (A_{0},a_{0},\alpha _{0})+\sum _{k=1}^{l}\omega _{k}(A_{k},a_{k},\alpha _{k}):\ \omega =(\omega _{1},\ldots ,\omega _{l})\in {\mathbb {R}}^{l}\text { and }\omega =\sum _{j=1}^{p}\tau _{j}v^{j},\ \tau \in \Delta _{p}\right\} , \end{aligned}$$

$l,\ p\in \mathbb {N}$ and $v^{1},\ldots ,v^{p}\in {\mathbb {R}}_{+}^{l}$. We assume that $s>0$ and $x_{0}\in {\mathbb {R}}^{n}$.

The robust counterpart, that finds a worst-case solution of $\mathrm{(TP)}$, is

$$\begin{aligned} \begin{array}{lll} (\mathrm{RP})\ &{} \inf _{x\in {\mathbb {R}}^{n}}\max _{(A,a,\alpha )\in \mathcal {V }} &{} \langle x,Ax\rangle +\langle a,x\rangle \ +\alpha \\ \ &{} \text {s.t. }\ \ \ \ &{} ||x-x_{0}||\le s. \end{array} \end{aligned}$$

Corollary 5.1

(Uncertain Trust-Region Problem) For problem $(\mathrm{TP})$ with data uncertainty $\mathcal {V}$ as above, let $\widehat{A}_{j}=A_{0}+ \sum _{k=1}^{l}v_{k}^{j}A_{k},\,\widehat{a}_{j}=a_{0}+ \sum _{k=1}^{l}v_{k}^{j}a_{k}$ and let $\widehat{\alpha }_{j}=\alpha _{0}+\sum _{k=1}^{l}v_{k}^{j}\alpha _{k}$ for $j=1,\ldots ,p$. Let $\rho =\max _{j=1,\ldots ,p}\{-\gamma _{\min }(\widehat{A}_{j})\}$.

• (i) If $\rho >0$, then a feasible point $x^{*}$ of $(\mathrm{TP})$ is a robust global minimizer of $(\mathrm{TP})$ if and only if, for any $u\in {\mathbb {R}}^{n}$, there exist $\lambda \in {\mathbb {R}}_{+}$ and $\mu \in \Delta _{p}$ such that

  $$\begin{aligned} \left( \begin{array}{l@{\quad }l} {2}\left[ \sum \nolimits _{j=1}^{p}\mu _{j}\widehat{A}_{j}+\left( \rho {+\lambda }\right) {I}_{n}\right] &{} \left[ \sum \nolimits _{j=1}^{p}\mu _{j}\widehat{a}_{j} {-u-2\lambda x}_{0}\right] \\ \left[ \sum \nolimits _{j=1}^{p}\mu _{j}\widehat{a}_{j}{-u-2\lambda x}_{0}\right] ^{T} &{} 2\left[ {\lambda }\left( ||x_{0}||^{2}-s\right) +\frac{||u||^{2} }{4\rho }{-}\overline{t}+\sum \nolimits _{j=1}^{p}\mu _{j}\widehat{\alpha }_{j}\right] \end{array} \right) \succeq 0, \end{aligned}$$

  where $\overline{t}=\max _{(A,a,\alpha )\in \mathcal {V}}\langle x^{*},Ax^{*}\rangle +\langle a,x^{*}\rangle \ +\alpha .\$

• (ii) If $\rho \le 0$, then a feasible point $x^{*}$ of $( \mathrm{TP})$ is a robust global minimizer of $(\mathrm{TP})$ if and only if, there exist $\lambda \in {\mathbb {R}}_{+}$ and $\mu \in \Delta _{p}$ such that

  $$\begin{aligned} \left( \begin{array}{l@{\quad }l} {2}\left[ \sum \nolimits _{j=1}^{p}\mu _{j}\widehat{A}_{j}+{\lambda I}_{n}\right] &{} \left[ \sum \nolimits _{j=1}^{p}\mu _{j}\widehat{a}_{j}{-2\lambda x}_{0}\right] \\ \left[ \sum \nolimits _{j=1}^{p}\mu _{j}\widehat{a}_{j}{-2\lambda x}_{0}\right] ^{T} &{} 2\left[ {\lambda }\left( ||x_{0}||^{2}-s\right) +\sum \nolimits _{j=1}^{p}\mu _{j} \widehat{\alpha }_{j}{-}\overline{t}\right] \end{array} \right) \succeq 0, \end{aligned}$$

  where $\overline{t}=\max _{(A,a,\alpha )\in \mathcal {V}}\langle x^{*},Ax^{*}\rangle +\langle a,x^{*}\rangle \ +\alpha .$

Proof

Note as before that for each $x\in {\mathbb {R}}^{n}$

$$\begin{aligned}&\max _{(A,a,\alpha )\in \mathcal {V}}\langle x,Ax\rangle +\langle a,x\rangle \ +\alpha \\&\quad =\max _{j=1,\ldots ,p}\left\{ \left\langle x,(A_{0}+\sum _{k=1}^{l}v_{k}^{j}A_{k})x\right\rangle +\left\langle a_{0}+\sum _{k=1}^{l}v_{k}^{j}a_{k},x\right\rangle \ +\alpha _{0}+\sum _{k=1}^{l}v_{k}^{j}\alpha _{k}\right\} . \end{aligned}$$

Then, the problem $(\mathrm{RP})$ becomes

$$\begin{aligned} \begin{array}{l@{\quad }l} \inf _{x\in {\mathbb {R}}^{n}}\max _{j=1,\ldots ,p} &{} \langle x,\widehat{A} _{j}x\rangle +\langle \widehat{a}_{j},x\rangle \ +\widehat{\alpha }_{j}\\ \text {s.t. }\ \ \ \ &{} ||x-x_{0}||\,\le s. \end{array} \end{aligned}$$

and the Slater condition holds.

• (i) Assume that $\rho >0$. Let

  $$\begin{aligned} \mathcal {W=}\left\{ (B,b,\beta )\in S^{n}\times {\mathbb {R}}^{n}\times {\mathbb {R}}:\left\| \left( \begin{array}{l@{\quad }l} B &{} b \\ b^{T} &{} \beta \end{array} \right) -\left( \begin{array}{l@{\quad }l} I &{} - x_{0} \\ - x_{0}^{T} &{} ||x_{0}||^{2}-s^{2} \end{array} \right) \right\| _{\mathrm{spec}}\le 0\right\} \end{aligned}$$

  The constraint $||x-x_{0}||\le s$ is equivalent to the quadratic constraint $\langle x,B_{1}x\rangle +2\langle b_{1},x\rangle \ +\beta _{1}\le 0$, where $B_{1}=I,\,b_{1}=-x_{0}$ and $\beta _{1}=||x_{0}||^{2}-s^{2}$. Applying the previous theorem with $m=1$, we obtain the required condition characterizing the robust global minimizer.

• (ii) If $\rho \le 0$, then $\gamma _{\min }(A_{j})\ge 0$ for all $j=1,\ldots ,p$. Let $f_{j}(x)=\langle x,\widehat{A}_{j}x\rangle +\langle \widehat{a}_{j},x\rangle \ +\widehat{\alpha }_{j}$, and $h(x)=0$. Then $f_{j}$ is convex. By Corollary 4.2, the conclusion follows$.\square$

A special case of $(\mathrm{TP})$ occurs when $\left( A,a,\alpha \right) \in \mathcal {V}_{1}:=\mathrm{co}\{\left( A_{j},a_{j},\alpha _{j}\right) \in S^{n}\times {\mathbb {R}}^{n}\times {\mathbb {R}},\ j=1,\ldots ,p\}$, where co denotes the convex hull. The robust counterpart of $(\mathrm{TP})$ in this case is

$$\begin{aligned} \begin{array}{l@{\quad }l@{\quad }l} (\mathrm{RP}_{1}) &{} \inf _{x\in {\mathbb {R}}^{n}}\max _{\left( A,a,\alpha \right) \in \mathcal {V}_{1}} &{} \langle x,Ax\rangle +\langle a,x\rangle +\alpha \\ &{} \text {s.t. }\ \ \ \ &{} ||x-x_{0}||\le s. \end{array} \end{aligned}$$

Corollary 5.2

(Polytope uncertainty) For the problem $(\mathrm{TP})$ with the data uncertainty $\mathcal {V}_{1}$, let $\overline{t}=\,\inf \mathrm{(TP)}$ and let $\rho =\max \{-\gamma _{\min }(A_{j}):j=1,\ldots ,p\}$.

• (i) If $\rho >0$, then a feasible point $x^{*}$ of $\mathrm{(TP)}$ is a robust global minimizer of $\mathrm{(TP)}$, if and only if, for any $u\in {\mathbb {R}}^{n}$, there exist $\lambda \in {\mathbb {R}}_{+}$ and $\mu \in \Delta _{p}$ such that

  $$\begin{aligned} \left( \begin{array}{l@{\quad }l} {2}\left[ \sum \nolimits _{j=1}^{p}\mu _{j}A_{j}+\left( \rho { +\lambda } \right) {I}_{n}\right] &{} \left[ \sum \nolimits _{j=1}^{p}\mu _{j}a_{j}{ -u-2\lambda x}_{0}\right] \\ \left[ \sum \nolimits _{j=1}^{p}\mu _{j}a_{j}{-u-2\lambda x}_{0}\right] ^{T} &{} 2 \left[ {\lambda }\left( ||x_{0}||^{2}-s\right) {+}\frac{ ||u||^{2}}{4\rho }+\sum \nolimits _{j=1}^{p}\mu _{j}\alpha _{j}{-}\overline{ {t}}\right] \end{array} \right) \succeq 0, \end{aligned}$$

  where $\overline{t}=\max _{(A,a,\alpha )\in \mathcal {V}_{1}}\langle x^{*},Ax^{*}\rangle +\langle a,x^{*}\rangle \ +\alpha$.

• (ii) If $\rho \le 0$, then a feasible point $x^{*}$ of $\mathrm{(TP)}$ is a robust global minimizer of $\mathrm{(TP)}$, if and only if, there exist $\lambda \in {\mathbb {R}}_{+}$ and $\mu \in \Delta _{p}$ such that

  $$\begin{aligned} \left( \begin{array}{l@{\quad }l} {2}\left[ \sum \nolimits _{j=1}^{p}\mu _{j}A_{j}+{\lambda I}_{n}\right] &{} \left[ \sum \nolimits _{j=1}^{p}\mu _{j}a_{j}{-2\lambda x}_{0}\right] \\ \left[ \sum \nolimits _{j=1}^{p}\mu _{j}a_{j}{-2\lambda x}_{0}\right] ^{T} &{} 2 \left[ {\lambda }\left( ||x_{0}||^{2}-s\right) {+} \sum \nolimits _{j=1}^{p}\mu _{j}\alpha _{j}{ -}\overline{{t}}\right] \end{array} \right) \end{aligned}$$

  where $\overline{t}=\max _{(A,a,\alpha )\in \mathcal {V}_{1}}\langle x^{*},Ax^{*}\rangle +\langle a,x^{*}\rangle \ +\alpha .\$

Proof

Note that for each $x\in {\mathbb {R}}^{n}$, we have

$$\begin{aligned} \max _{\left( A,a,\alpha \right) \in \mathcal {V}_{1}}\langle x,Ax\rangle +\langle a,x\rangle \ +\alpha =\max _{j=1,\ldots ,p}\langle x,A_{j}x\rangle +\langle a_{j},x\rangle +\alpha _{j}. \end{aligned}$$

The conclusion follows from the same line of arguments as in the proof of the previous Corollary. $\square$

We give an example illustrating Corollary 5.2(i).

Example 5.1

Consider the uncertain problem

$$\begin{aligned} \begin{array}{l@{\quad }l} \min _{x\in {\mathbb {R}}} &{} -x^{2}+ax\ \ \\ \ \ \text {s.t.}\ \ \ \ &{} x^{2}-\frac{1}{4}\ \ \le 0, \end{array} \end{aligned}$$

where $a$ is uncertain and it belongs to the uncertainty set $\mathcal {V=} [-1,1]$. Its robust counterpart is given by

$$\begin{aligned} \begin{array}{l@{\quad }l@{\quad }l} \mathrm{(EP}_{4}\mathrm{)}\ &{} \min _{x\in {\mathbb {R}}}\max _{a\in [-1,1]} &{} \{-x^{2}+ax\}\ \ \ \\ &{} \ \ \text {s.t.}\ \ \ \ &{} x^{2}-\frac{1}{4}\ \ \le 0. \end{array} \end{aligned}$$

Then the problem $\mathrm{(EP}_{4}\mathrm{)}$ can be written as $\inf _{x\in K}\max \{-x^{2}+x,\ -x^{2}-x\}=\inf _{x\in K}\max \{x,\ -x\}-x^{2}$. We can check that $\inf \mathrm{(EP}_{4}\mathrm{)}=0$.

Let $h(x)=x^{2}$, we have $h^{*}(u)=\frac{u^{2}}{4}$ and let

$$\begin{aligned} d(x,u,\lambda ,\mu )&= \mu _{1}(x)+\mu _{2}(-x)+\lambda \Big (x^{2}-\frac{1}{4}\Big )+ \frac{u^{2}}{4}-\langle u,x\rangle \\&= x(2\mu _{1}-1-u)+\lambda \Big (x^{2}-\frac{1}{4}\Big )+\frac{u^{2}}{4}. \end{aligned}$$

Then $d$ can be written as

$$\begin{aligned} d=\left\{ \begin{array}{l@{\quad }l@{\quad }l@{\quad }l} \ \frac{u^{2}}{4}, &{} \hbox {if} \ u\in [-1,1], &{} \hbox {with} \ \lambda =0 &{} \hbox {and}\quad \mu _{1}=\frac{ 1+u}{2}\\ \left( \sqrt{\lambda }x+\frac{2\mu _{1}-1-u}{2\sqrt{\lambda }}\right) ^{2}, &{} \hbox {if} \ u>1, &{} \hbox {with} \ \lambda =\frac{u^{2}+\sqrt{u^{4}-4\left( 2\mu _{1}-1-u\right) ^{2}}}{2}\ge 0 &{} \text {and}\quad \mu _{1}=1 \\ \ \left( \sqrt{\lambda }x+\frac{2\mu _{1}-1-u}{2\sqrt{\lambda }}\right) ^{2}, &{}\hbox {if} \ u<-1, &{} \hbox {with} \ \lambda =\frac{u^{2}+\sqrt{ u^{4}-4\left( 2\mu _{1}-1-u\right) ^{2}}}{2} \ge 0 &{}\hbox {and}\quad \mu _{1}=0. \end{array} \right. \end{aligned}$$

Hence, for any $u\in {\mathbb {R}}^{2}$, there exist $\lambda \in {\mathbb {R}} _{+}$ and $\mu \in \Delta$ such that $d(x,u,\lambda ,\mu )\ge 0$, which is equivalent to the linear matrix inequality of Corollary 5.2 (i).