# Mathematical Foundations of
Robust and Distributionally Robust Optimization

Jianzhe Zhen  Automatic Control Laboratory, Eidgenössische Technische
Hochschule Zürich, Switzerland Daniel Kuhn  College of Management of
Technology, École Polytechnique Fédérale de Lausanne, Switzerland Wolfram
Wiesemann  Imperial College Business School, Imperial College London, United
Kingdom

(April 27, 2021)

###### Abstract

Robust and distributionally robust optimization are modeling paradigms for
decision-making under uncertainty where the uncertain parameters are only
known to reside in an uncertainty set or are governed by any probability
distribution from within an ambiguity set, respectively, and a decision is
sought that minimizes a cost function under the most adverse outcome of the
uncertainty. In this paper, we develop a rigorous and general theory of robust
and distributionally robust nonlinear optimization using the language of
convex analysis. Our framework is based on a generalized ‘primal-worst-equals-
dual-best’ principle that establishes strong duality between a semi-infinite
primal worst and a non-convex dual best formulation, both of which admit
finite convex reformulations. This principle offers an alternative formulation
for robust optimization problems that may be computationally advantageous, and
it obviates the need to mobilize the machinery of abstract semi-infinite
duality theory to prove strong duality in distributionally robust
optimization. We illustrate the modeling power of our approach through convex
reformulations for distributionally robust optimization problems whose
ambiguity sets are defined through general optimal transport distances, which
generalize earlier results for Wasserstein ambiguity sets.

Keywords: (Distributionally) Robust Optimization, Convex Analysis, Optimal
Transport.

##  1 Introduction

Mathematical optimization problems frequently require decisions to be taken
under partial or complete lack of information about key problem parameters:
the topology of a truss needs to be designed before the magnitudes and
directions of the external forces acting upon it are known, a portfolio of
financial assets needs to be built without knowledge of the future asset price
movements, the energy production of a power plant needs to be fixed several
hours before the demands, outputs of intermittent generators and plant/line
failures are known, and the classifying hyperplane of a support vector machine
needs to be selected under incomplete knowledge of the data generating
distribution. These (and many other) applications have in common that key
problem parameters are not only to be considered random, but they are also
governed by probability distributions that are at least partially unknown.

In the last 25 years, robust and distributionally robust optimization have
emerged as promising techniques to model, analyze and optimize decisions under
risk (where some problem parameters constitute random variables) and ambiguity
(where the underlying distributions are only partially known). Robust
optimization assumes that the uncertain problem parameters can take on any
value from within a pre-specified _uncertainty set_ , whereas distributionally
robust optimization models the uncertain parameters as random variables whose
underlying probability distribution can be any distribution from within a pre-
specified _ambiguity set_. In both cases, the decision maker seeks to
determine the best decision in view of the worst realization of the
uncertainty; this is often depicted as a game between the decision maker and
an adversary nature that is ‘in charge’ of the uncertainty.

The vast majority of research in robust and distributionally robust
optimization focuses on well-structured conic optimization problems such as
linear, second-order cone and semi-definite programs. While the presence of
structure simplifies the exposition and ensures computational tractability, it
requires similar arguments to be redeveloped for different problem classes,
and it obfuscates the view on the underlying principles in their full
generality. This concern has been noted by several researchers, and various
attempts have been made to extend the theory of robust and distributionally
robust optimization to general convex optimization problems. Since the main
focus of these works is a computational one, however, mathematical subtleties
that emerge from this generalization are often either incorrectly addressed or
disregarded altogether.

In this paper, we develop a general theory of robust and distributionally
robust optimization from first principles, using the language of convex
analysis. Section 2 first revisits classical duality results for convex
optimization and derives explicit dual optimization problems involving the
conjugates of the objective and constraint functions. Closed-form expressions
are known for conjugates of many basic functions, and a rich calculus is
available to derive closed-form expressions of conjugates of composite
functions from the expressions of the conjugates of the constituent component
functions. Thus, our dual problems often admit a closed-form representation
that can be obtained algorithmically (_e.g._ , by an automated parser). Our
analysis allows the objective and constraint functions of the primal problem
to be arbitrary extended real-valued proper, closed and convex functions. This
generality is crucial since we will dualize problems that involve implicit
constraints or conjugates, but it significantly complicates our analysis.

We then leverage the results of Section 2 to build a unified theory of robust
(Section 3) and distributionally robust (Sections 4 and 5) optimization
problems as well as modern data-driven optimization problems (Section 6),
where the objective function, the constraints as well as the uncertainty or
ambiguity set are described in terms of generic convex functions. At the heart
of our framework lies a generalized ‘primal-worst-equals-dual-best’ principle
that establishes strong duality between a semi-infinite primal worst and a
non-convex dual best formulation, both of which can be reformulated as finite
convex optimization problems.

More specifically, Section 3 studies the primal worst and dual best
formulations of a robust optimization problem. For the primal worst
formulation, we use our results from Section 2 to dualize the embedded
maximization problems over the uncertain parameters. The resulting
reformulations are convex optimization problems that involve the partial
conjugates of the objective and the constraint functions of the original
problem with respect to the uncertain parameters as well as the ‘global’
conjugates of the functions characterizing the uncertainty set. For the dual
best formulation, we show how the non-convexities resulting from
multiplications of Lagrange multipliers with the functions characterizing the
constraints and the uncertainty set of the original problem can be eliminated
systematically by a _perspectivication_ trick. The emerging convexified dual
problem involves the partial conjugates of the objective and the constraint
functions with respect to the original problem’s decision variables (as
opposed to the uncertain parameters) and the (unaltered) functions defining
the uncertainty set, and it may thus offer a closed-form representation in
situations where the primal worst problem involves conjugates that cannot be
calculated analytically. In contrast to the existing literature, our results
extend to robust convex programs with unbounded uncertainty sets, which will
be crucial when we apply our results to uncertainty quantification and
distributionally robust optimization problems.

Section 4 studies distributionally robust optimization problems involving
embedded worst-case expectation—or _uncertainty quantification_ —problems.
These uncertainty quantification problems constitute semi-infinite
optimization problems that maximize the expected value of an uncertainty-
affected disutility function over all probability distributions in some
ambiguity set defined by generalized moment constraints. The semi-infinite
minimization problems dual to these uncertainty quantification problems are
naturally interpreted as robust optimization problems, and thus our
reformulations from Section 3 apply. The resulting tractable reformulations
can be integrated into distributionally robust optimization problems that
minimize over a set of decision variables. We also apply our generalized
primal-worst-equals-dual-best principle to the semi-infinite dual uncertainty
quantification problem (interpreted now as the ‘primal worst’) to show that
its ‘dual best’ counterpart affords a natural interpretation as a finite
reduction of the original uncertainty quantification problem that evaluates
the worst-case expectation only over discrete distributions contained in the
ambiguity set. Using our duality framework from Section 2, we show that the
primal worst and the dual best can be reformulated as explicit convex
optimization problems that are strong duals under simple compactness or Slater
conditions. In combination, these findings allow us to formulate easily
verifiable conditions for strong duality in distributionally robust
optimization, as opposed to the abstract moment conditions traditionally
required by semi-infinite duality theory.

Section 5 extends the results of Section 4 to generalized distributionally
robust optimization problems where the support and moment constraints
characterizing the ambiguity set are non-convex but display a generalized
convexity property with respect to an arbitrary proper convex cone
$\mathcal{C}$. To our best knowledge, such non-linear conic constraints have
not been studied in the context of robust or distributionally robust
optimization, and they raise significant technical challenges. Among others,
the resulting problems involve generalized $\mathcal{C}$-convex perspectives,
which we define for the first time.

Section 6 showcases the generality of our extensions from Section 5 in the
context of distributionally robust optimization problems whose ambiguity sets
contain all distribution within a ball with respect to an optimal transport
distance centered at a discrete distribution. Such problems were first studied
by Pflug and Wozabal (2007) and Pichler and Pflug (2014). Since the discrete
distribution at the center of the ambiguity set is typically identified with
the empirical distribution over a training data set, such problems are often
called _data-driven_. Optimal transport distances generalize the $p$-th
Wasserstein distances for $p\geq 1$, whose transportation cost is defined as
the $p$-th power of some norm. Leveraging the theory of the earlier sections,
we prove that uncertainty quantification problems of this kind admit two
different reformulations as finite convex programs, namely a maximization
problem that determines a worst-case distribution and a minimization problem
that can be used for distributionally robust optimization. Our two convex
reformulations generalize known reformulations for $p=1$ by Mohajerin Esfahani
and Kuhn (2018) and Zhao and Guan (2018) and for $p=\infty$ by Bertsimas et
al. (2019), and they can be applied to general optimal transport-based
uncertainty quantification problems envisaged by Gao and Kleywegt (2016) and
Blanchet and Murthy (2019).

The study of decision-making under incomplete information has a long history.
The distinction between risk and ambiguity, as well as theoretical and
empirical support for decision makers to exhibit ambiguity aversion even if
they are neutral towards risk, appears to have emerged from the economics
literature (Keynes, 1921; Knight, 1921; Gilboa and Schmeidler, 1989; Epstein,
1999). Using mathematical optimization to take optimal decisions under risk
and ambiguity goes back to the works of Scarf (1958) on the newsvendor problem
as well as of Žáčková (1966) on generic linear programs. In both cases,
attention is restricted to specific classes of ambiguity sets, which allows
the worst-case distributions to be determined via intricate _ad hoc_
arguments.

Robust optimization problems are traditionally solved by dualizing the
embedded maximization over all possible uncertainty realizations in the primal
worst problem (El Ghaoui and Lebret, 1997; El Ghaoui et al., 1998; Ben-Tal and
Nemirovski, 1998, 1999, 2000, 2002; Bertsimas and Sim, 2004). If the embedded
maximization problems represent linear conic optimization problems, then the
duals can be constructed explicitly in terms of the original problem data
(Ben-Tal et al., 2009). If the embedded maximization problems constitute
generic convex optimization problems, on the other hand, they may not admit
explicit duals. Instead, the dual objective function is only implicitly
defined as the infimum of the Lagrangian function with respect to the
uncertain parameters. Using Fenchel duality, Ben-Tal et al. (2015) show that
the optimal values of the embedded maximization problems can be expressed as
differences between the support function of the uncertainty set and the
partial conjugates of the constraint (or objective) functions with respect to
the uncertain parameters. Instead of the support function of the uncertainty
set, our reformulation explicitly involves the conjugates of the functions
characterizing the uncertainty set and may therefore be easier to implement
and automate. We refer to Ben-Tal et al. (2009), Bertsimas et al. (2011) and
Gabrel et al. (2014) for comprehensive reviews of robust optimization and its
manifold applications.

Alternatively, robust optimization problems can be studied from the
perspective of the dual best problem. For bounded uncertainty sets, Beck and
Ben-Tal (2009) show that the optimal value of the primal worst problem
coincides with that of the dual best problem if a Slater condition holds.
Gorissen et al. (2014) show how the non-convexities of the dual best problem
can be eliminated in robust optimization problems with linear objective and
linear conic constraint functions over uncertainty sets described by general
convex functions. This result was later extended by Gorissen and den Hertog
(2015) to general robust convex optimization problems. Our results extend the
works of Beck and Ben-Tal (2009) and Gorissen and den Hertog (2015) to robust
optimization problems with unbounded uncertainty sets, which will prove
essential when we apply our results to uncertainty quantification and
distributionally robust optimization problems.

Tractable reformulations for distributionally robust optimization problems can
be derived in different ways. Ben-Tal and Nemirovski (2000), Bertsimas and Sim
(2004), Calafiore and El Ghaoui (2006), Nemirovski and Shapiro (2006), Chen et
al. (2007), Xu et al. (2012) and Bertsimas et al. (2018) rely on classical
probability bounds (such as Hoeffding’s inequality or Bernstein bounds) or
statistical hypothesis tests to derive tractable reformulations. In contrast,
El Ghaoui et al. (2003), Bertsimas and Popescu (2005), Delage and Ye (2010),
Xu and Mannor (2012) and Wiesemann et al. (2014) dualize the uncertainty
quantification problem embedded in the distributionally robust optimization
problem and apply techniques from standard robust optimization to replace the
semi-infinite dual with a finite reformulation. To ensure strong duality
between the primal uncertainty quantification problem and its semi-infinite
dual, this literature stream usually relies on results from semi-infinite
duality theory that are very general but can be tedious to verify and that are
prone to misinterpretations (Isii, 1959, 1962; Shapiro, 2001). A popular
condition is to check whether the bounds on the generalized moments imposed by
the ambiguity set belong to the interior of some moment cone generated by all
non-negative measures (not only the probability measures) on the prescribed
support set. Despite being convex, this moment cone usually lacks an explicit
description in terms of simple convex constraints. In contrast, our conditions
for strong duality, which are based on our generalized primal-worst-equals-
dual-best principle, are typically easy to verify, both theoretically and
algorithmically (_e.g._ , via the solution of a convex optimization problem).

Using the primal-worst-equals-dual-best principle to construct finite
reductions of uncertainty quantification problems was first proposed for the
subclass of chance constrained programs over restricted classes of ambiguity
sets by Hanasusanto et al. (2015, 2017). These papers, however, still rely on
semi-infinite duality theory (and its aforementioned shortcomings) to ensure
strong duality. Han et al. (2015) derive a finite reduction similar to ours by
applying the Richter-Rogosinsky theorem (Shapiro et al., 2009, Theorem 7.37)
and a subsequent induction argument directly to the primal uncertainty
quantification problem. Since the focus of that work is on uncertainty
quantification, however, it does not study the dual of the uncertainty
quantification problem, which is essential to obtain tractable reformulations
for distributionally robust optimization problems.

### Notation.

We use $\overline{\mathbb{R}}$ to denote the extended real numbers. The
calligraphic letters $\mathcal{I}$, $\mathcal{J}$, $\mathcal{K}$,
$\mathcal{L}$ and the corresponding capital Roman letters $I$, $J$, $K$, $L$
are reserved for finite index sets and their respective cardinalities, i.e.,
$\mathcal{I}=\\{1,\dots,I\\}$ etc. The subscript $0$ indicates that the index
set additionally includes $0$, i.e., $\mathcal{I}_{0}=\\{0,\ldots,I\\}$ etc.
We use ri$(\mathcal{X})$ to denote the relative interior of a set
$\mathcal{X}\subseteq\mathbb{R}^{d_{\bm{x}}}$. Any assignment of real values
to the decision variables of an optimization problem is a solution. A solution
is feasible in an optimization problem if it satisfies all the constraints and
attains an objective value other than $+\infty$ ($-\infty$) in a minimization
(maximization) problem; otherwise, it is infeasible. An optimization problem
is feasible if it has at least one feasible solution. We refer to the feasible
region of an optimization problem as the set containing all of its feasible
solutions. A feasible optimization problem is solvable if its optimal value is
attained by a feasible solution, whereas an infeasible optimization problem is
solved by any (necessarily infeasible) solution. Whenever the domain of a
variable in an optimization problem is omitted, it is understood to be the
entire space (whose definition will be clear from the context).

##  2 Convex Optimization

In this section we adapt existing duality results to generic convex
optimization problems with extended real-valued objective and constraint
functions. This flexibility allows us to work with optimization problems whose
objective and constraints involve conjugates. We also discuss regularity
conditions under which the primal and the dual problems are solvable. As we
will see later on, solvability is essential for the existence of worst-case
scenarios and worst-case distributions in robust and distributionally robust
optimization, respectively. By themselves, the results in this section are not
new, however they are dispersed throughout the literature, and they often miss
subtle but—in view of our applications in later sections—crucial regularity
conditions.

We first recall some standard terminology from convex analysis. The domain of
a function $f:\mathbb{R}^{d_{\bm{x}}}\rightarrow\overline{\mathbb{R}}$ is
defined as $\mathop{\rm{dom}}(f)=\\{\bm{x}\in\mathbb{R}^{d_{\bm{x}}}\ |\
f(\bm{x})<+\infty\\}$. The epigraph of $f$ is defined as
$\textnormal{epi}(f)=\\{(\bm{x},\tau)\in\mathbb{R}^{d_{\bm{x}}}\times\mathbb{R}\
|\ f(\bm{x})\leq\tau\\}$. The function $f$ is proper if $f(\bm{x})>-\infty$
for all $\bm{x}\in\mathbb{R}^{d_{\bm{x}}}$ and $f(\bm{x})<+\infty$ for at
least one $\bm{x}\in\mathbb{R}^{d_{\bm{x}}}$, implying that
$\mathop{\rm{dom}}(f)\neq\emptyset$. In addition, $f$ is closed if $f$ is
lower semicontinuous and either $f(\bm{x})>-\infty$ for all
$\bm{x}\in\mathbb{R}^{d_{\bm{x}}}$ or $f(\bm{x})=-\infty$ for all
$\bm{x}\in\mathbb{R}^{d_{\bm{x}}}$.

We next introduce Slater conditions for both sets and optimization problems.
This distinction will enable us to characterize the uncertainty sets whose
associated robust optimization problems are amenable to finite convex
reformulations using the machinery of strong convex duality.

######  Definition 1 (Slater Condition for Sets).

The vector $\bm{x}^{\textnormal{S}}$ is a Slater point of the set
$\mathcal{X}$ represented by $\mathcal{X}=\\{\bm{x}\in\mathbb{R}^{d_{\bm{x}}}\
|\ f_{i}(\bm{x})\leq 0\;\;\forall i\in\mathcal{I},\ h_{j}(\bm{x})=0\;\;\forall
j\in\mathcal{J}\\}$ if __(i)__ $\bm{x}^{\textnormal{S}}\in{\rm
ri}(\mathop{\rm{dom}}(f_{i}))$ as well as $\bm{x}^{\textnormal{S}}\in{\rm
ri}(\mathop{\rm{dom}}(h_{j}))$ for all $i\in\mathcal{I}$ and
$j\in\mathcal{J}$; _(ii)_ $\bm{x}^{\textnormal{S}}\in\mathcal{X}$; and _(iii)_
$f_{i}(\bm{x}^{\textnormal{S}})<0$ for all $i\in\mathcal{I}$ such that $f_{i}$
is nonlinear. The Slater point $\bm{x}^{\textnormal{S}}$ is strict if
$f_{i}(\bm{x}^{\textnormal{S}})<0$ for all $i\in\mathcal{I}$.

Note that the definition of a Slater point depends on the representation of
the set $\mathcal{X}$. In fact, $\mathcal{X}=\\{0\\}$ has a strict Slater
point if represented as $\mathcal{X}=\\{x\in\mathbb{R}\ |\ x=0\\}$, whereas
the alternative representation $\mathcal{X}=\\{x\in\mathbb{R}\ |\ x^{2}\leq
0\\}$ does not admit a Slater point.

######  Definition 2 (Slater Condition for Optimization Problems).

The vector $\bm{x}^{\textnormal{S}}$ is a Slater point of the minimization
problem $\inf\\{f_{0}(\bm{x})\ |\ \bm{x}\in\mathcal{X}\\}$, where
$\mathcal{X}$ is represented as in Definition 1, if $\bm{x}^{\textnormal{S}}$
is a Slater point of $\mathcal{X}$ and $\bm{x}^{\textnormal{S}}\in{\rm
ri}(\mathop{\rm{dom}}(f_{0}))$. The Slater point $\bm{x}^{\textnormal{S}}$ is
strict if it is a strict Slater point of $\mathcal{X}$.

For a maximization problem, we replace the requirement
$\bm{x}^{\textnormal{S}}\in{\rm ri}(\mathop{\rm{dom}}(f_{0}))$ in Definition 2
with $\bm{x}^{\textnormal{S}}\in{\rm ri}(\mathop{\rm{dom}}(-f_{0}))$.

We now define the notions of conjugate functions and perspective functions.

######  Definition 3 (Conjugate Function).

The conjugate of a function
$f:\mathbb{R}^{d_{\bm{x}}}\rightarrow\overline{\mathbb{R}}$ is the function
$f^{*}:\mathbb{R}^{d_{\bm{x}}}\rightarrow\overline{\mathbb{R}}$ defined
through
$f^{*}({{\bm{w}}})=\sup_{\bm{x}}\left\\{{{\bm{x}}}^{\top}{{\bm{w}}}-f({{\bm{x}}})\right\\}.$
The conjugate $(f^{*})^{*}$ of $f^{*}$ is called the biconjugate of $f$ and is
abbreviated as $f^{**}$.

The indicator function
$\delta_{\mathcal{X}}:\mathbb{R}^{d_{\bm{x}}}\rightarrow\overline{\mathbb{R}}$
of a set $\mathcal{X}\subseteq\mathbb{R}^{d_{\bm{x}}}$ is defined through
$\delta_{\mathcal{X}}({\bm{x}})=0$ if $\bm{x}\in\mathcal{X}$ and
$\delta_{\mathcal{X}}({\bm{x}})=+\infty$ if $\bm{x}\notin\mathcal{X}$. The
support function
$\delta^{*}_{\mathcal{X}}:\mathbb{R}^{d_{\bm{x}}}\rightarrow\overline{\mathbb{R}}$
of a set $\mathcal{X}\subseteq\mathbb{R}^{d_{\bm{x}}}$ is defined through
$\delta_{\mathcal{X}}^{*}({\bm{w}})=\sup_{\bm{x}\in\mathcal{X}}\
\\{\bm{x}^{\top}{\bm{w}}\\}$. Note that the support function of $\mathcal{X}$
coincides with the conjugate of the indicator function of $\mathcal{X}$, which
justifies our notation.

######  Definition 4 (Perspective Functions).

The convex perspective of a proper, closed and convex function
$f:\mathbb{R}^{d_{\bm{x}}}\rightarrow\overline{\mathbb{R}}$ is the function
$\underline{f}:\mathbb{R}^{d_{\bm{x}}}\times\mathbb{R}_{+}\rightarrow\overline{\mathbb{R}}$
defined through $\underline{f}(\bm{x},t)=tf(\bm{x}/t)$ if $t>0$ and
$\underline{f}(\bm{x},0)=\delta_{\mathop{\rm{dom}}(f^{*})}^{*}({\bm{x}})$.
Similarly, the concave perspective of a function $f$ for which $-f$ is proper,
closed and convex is the function
$\overline{f}:\mathbb{R}^{d_{\bm{x}}}\times\mathbb{R}_{+}\rightarrow\overline{\mathbb{R}}$
defined through $\overline{f}(\bm{x},t)=tf(\bm{x}/t)$ if $t>0$ and
$\overline{f}(\bm{x},0)=-\delta_{\mathop{\rm{dom}}((-f)^{*})}^{*}({\bm{x}})$.

One can show that for $t>0$, the epigraph of $\underline{f}(\cdot,t)$
coincides with the epigraph of $f$ multiplied by $t$. Moreover, the epigraph
of $\underline{f}$ coincides with the closure of the cone generated by
$\mathop{\rm{epi}}(f)\times\\{1\\}\subseteq\mathbb{R}^{d_{\bm{x}}}\times\mathbb{R}$.
Finally, our definitions of the convex and concave perspectives satisfy

$\underline{f}(\bm{x},0)=\displaystyle\underset{(\bm{x}^{\prime},t^{\prime})\rightarrow(\bm{x},0)}{\lim\inf}t^{\prime}f\left(\bm{x}^{\prime}/t^{\prime}\right)\qquad\text{and}\qquad\overline{f}(\bm{x},0)=\displaystyle\underset{(\bm{x}^{\prime},t^{\prime})\rightarrow(\bm{x},0)}{\lim\sup}t^{\prime}f\left(\bm{x}^{\prime}/t^{\prime}\right)$
(1)

for convex and concave $f$, respectively, and
$\bm{x}\in\mathbb{R}^{d_{\bm{x}}}$ (Rockafellar, 1970, p. 67 and Theorem
13.3). For ease of notation, we henceforth use $tf(\bm{x}/t)$ to denote both
$\underline{f}(\bm{x},t)$ and $\overline{f}(\bm{x},t)$. The correct
interpretation of $0f(\bm{x}/0)$ will be clear from the context. Specifically,
$0f(\bm{x}/0)$ should be interpreted as $\underline{f}(\bm{x},0)$ if $f$ is
convex and as $\overline{f}(\bm{x},0)$ if $f$ is concave. This convention is
justified in view of (1).

By construction, the convex perspective of a proper, closed and convex
function is guaranteed to be proper, closed and convex; see Proposition B.2.

######  Example 1 (Perspective Functions).

Define $f:\mathbb{R}\rightarrow\overline{\mathbb{R}}$ through
$f(x)=\delta_{\\{x_{0}\\}}(x)$ for some $x_{0}\neq 0$, and note that $f$ is
proper, closed and convex. An elementary calculation shows that the convex
perspective of $f$ is given by $\underline{f}(x,t)=\delta_{\\{tx_{0}\\}}(x)$
for every $x\in\mathbb{R}$ and $t\geq 0$, which is also proper, closed and
convex. Note, however, that
$\underline{f}(x,0)=\delta_{\\{0\\}}(x)\neq+\infty=\lim_{t\downarrow
0}tf(x/t)$, where the last equality holds because $x_{0}\neq 0$. This example
shows that if one were to define $\underline{f}(x,0)=\lim_{t\downarrow
0}tf(x/t)$, as is sometimes done in the literature, then the resulting
perspective would fail to be closed. As a second example, define
$f:\mathbb{R}\rightarrow\overline{\mathbb{R}}$ through $f(x)=|x|$, and note
that $f$ is again proper, closed and convex. The convex perspective of $f$ is
given by $\underline{f}(x,t)=|x|$ for every $x\in\mathbb{R}$ and $t\geq 0$,
which is also proper, closed and convex. This example shows that if one were
to define $\underline{f}(x,0)=\delta_{\\{0\\}}(x)$, as is sometimes done in
the literature, then the resulting perspective would fail to be closed.

Consider now a generic nonlinear optimization problem of the following form.

$\begin{array}[]{l@{\quad}l@{\qquad}l}\displaystyle\inf&\displaystyle
f_{0}(\bm{x})\\\ \displaystyle\rm{s.t.}&\displaystyle f_{i}(\bm{x})\leq
0&\displaystyle\forall i\in\mathcal{I}\\\ &\displaystyle\bm{x}\text{
free}\end{array}$ (P)

Primal Problem

Here, the objective and constraint functions are extended real-valued
functions $f_{i}:\mathbb{R}^{d_{\bm{x}}}\rightarrow\overline{\mathbb{R}}$ for
$i\in\mathcal{I}_{0}$. In the remainder of this section, we assume that
problem (P) is convex, that is, we assume that its objective and constraint
functions satisfy the following regularity condition.

  * (F)

The function $f_{i}$ is proper, closed and convex for each
$i\in\mathcal{I}_{0}$.

We now introduce the problem dual to (P).

$\begin{array}[]{l@{\quad}l@{\qquad}l}\displaystyle\sup&\lx@intercol\displaystyle\mspace{-8.0mu}-f_{0}^{*}\left(\bm{w}_{0}\right)-\sum_{i\in\mathcal{I}}\lambda_{i}f_{i}^{*}\left(\bm{w}_{i}/\lambda_{i}\right)\hfil\lx@intercol\\\
\displaystyle\rm{s.t.}&\displaystyle\sum_{i\in\mathcal{I}_{0}}\bm{w}_{i}=\bm{0}\\\
&\displaystyle\bm{w}_{i}\textnormal{ free}&\displaystyle\forall
i\in\mathcal{I}_{0}\\\ &\displaystyle\bm{\lambda}\geq\bm{0}\\\ \end{array}$
(D)

Dual Problem

The dual problem (D) maximizes the (negative) infimal convolution of the
conjugate objective function as well as the perspectives of the conjugate
constraint functions. Note that the problems (P) and (D) are not symmetric,
that is, it is not straightforward to express (P) as an instance of (D) or
vice versa. As a result, we will need to derive some of the duality results
explicitly for both the primal and the dual problem. While it is possible to
derive a symmetric primal-dual pairing, the resulting optimization problems
would require extensive additional notation that is not required for the
remainder of the paper.

######  Theorem 1 (Weak Duality).

The infimum of (P) is larger or equal to the supremum of (D).

Theorem 1 implies that (D) is necessarily infeasible whenever (P) is
unbounded, and that (P) is necessarily infeasible whenever (D) is unbounded.

######  Theorem 2 (Strong Duality).

The following statements hold.

  1. (i)

If (P) or (D) admits a Slater point, then the infimum of (P) coincides with
the supremum of (D), and (D) or (P) is solvable, respectively.

  2. (ii)

If the feasible region of (P) or (D) is nonempty and bounded, then the infimum
of (P) coincides with the supremum of (D), and (P) or (D) is solvable,
respectively.

Below we provide an example of two mutually dual convex optimization problems
with a strictly positive duality gap. We also showcase that the presence of a
positive duality gap critically depends on the representation of these
problems, that is, simple equivalent reformulations of the primal (dual) may
change the dual (primal) and eliminate the duality gap.

######  Example 2 (Representation-Dependence of Duality Results).

Consider an instance of problem (P) adapted from Exercise 5.21 by Boyd and
Vandenberghe (2004) with two decision variables $x_{1}$ and $x_{2}$, a convex
objective function $f_{0}(\bm{x})=e^{-x_{1}}$ and a single convex constraint
function defined through $f_{1}(\bm{x})=x_{1}^{2}/x_{2}$ if $x_{2}\geq 0$ and
$f_{1}(\bm{x})=\infty$ otherwise. The fraction $x_{1}^{2}/x_{2}$ should be
interpreted as the convex perspective of $x_{1}^{2}$ whenever $x_{2}\geq 0$.
Thus, $f_{0}$ and $f_{1}$ are both proper and closed. Note that this instance
of (P) violates both conditions in Theorem 2. Moreover, any feasible solution
satisfies $x_{1}=0$ and thus attains the optimal value $1$ of (P). A direct
calculation reveals that

$f_{0}^{*}(\bm{w}_{0})=\left\\{\begin{array}[]{cl}-w_{01}\log(-w_{01})+w_{01}&\
{\rm if}\ w_{01}\leq 0\text{ and }w_{02}=0,\\\ +\infty&\
\rm{otherwise,}\end{array}\right.$

where we use the standard convention that $0\log(0)=0$, and

$f_{1}^{*}(\bm{w}_{1})=\left\\{\begin{array}[]{cl}0&\ {\rm if}\
\frac{1}{4}w_{11}^{2}+w_{12}\leq 0,\\\ +\infty&\
\rm{otherwise.}\end{array}\right.$

The dual problem (D) can therefore be expressed as

$\begin{array}[]{c@{\quad}l@{\quad}l}\displaystyle\sup&\displaystyle
w_{01}\log(-w_{01})-w_{01}\\\
\displaystyle\rm{s.t.}&\displaystyle\bm{w}_{0}+\bm{w}_{1}=\bm{0}\\\
&\displaystyle\frac{w_{11}^{2}}{4\lambda_{1}}+w_{12}\leq 0,\;\;w_{01}\leq
0,\;\;w_{02}=0\\\ &\bm{w}_{0},\bm{w}_{1}\ {\rm free}\\\ &\lambda_{1}\geq
0.\end{array}$

Note that this instance of (D) violates both conditions in Theorem 2. Any
feasible solution satisfies $\bm{w}_{0}=\bm{w}_{1}=\bm{0}$ and thus attains
the optimal value $0$ of (D). We conclude that the duality gap amounts to $1$.
Furthermore, Lemma A.1 allows to recover the primal problem (P) by dualizing
(D). However, all of these conclusions break down if we simplify (P) or (D) by
eliminating redundant constraints and variables. For example, as any primal
feasible solution satisfies $x_{1}=0$, problem (P) is equivalent to the linear
program $\inf\\{1\mid x_{2}\geq 0\\}$, which admits a Slater point and
therefore has a strong dual that is no longer equivalent to (D). Similarly, as
any dual feasible solution satisfies $\bm{w}_{0}=\bm{w}_{1}=\bm{0}$, problem
(D) is equivalent to the linear program $\sup\\{0\mid\lambda_{1}\geq 0\\}$,
which admits a Slater point and therefore has a strong dual that is no longer
equivalent to (P). Therefore, the dual of the dual may not be equivalent to
the primal if one simplifies the dual problem.

Based on the data of the primal problem (P), it is often difficult to verify
whether the dual problem (D) admits a Slater point. However, a dual Slater
point is guaranteed to exist whenever the primal feasible region is nonempty
and bounded. While this result seems futile in view of Theorem 2, it will play
an important role in Section 3, where we need to verify that certain dualized
embedded optimization problems admit Slater points in order to invoke strong
duality for the outer optimization problems.

######  Proposition 3 (Sufficient Condition for a Dual Slater Point).

If the feasible region of (P) is nonempty and bounded, then (D) admits a
strict Slater point.

The next example shows that the reverse implication of Proposition 3 does not
hold in general.

######  Example 3 (Unbounded Dual Feasible Region for Primal with a Slater
Point).

Consider an instance of problem (P) with $I=3$, $f_{0}(x)=x$, $f_{1}(x)=x-1$,
$f_{2}(x)=1-x$ and $f_{3}(x)=-x$. It can be easily verified that (P) admits a
Slater point. We can readily verify that the corresponding dual problem (D)
can be expressed as

$\begin{array}[]{l@{\quad}l@{\quad}l}\sup&-\lambda_{1}+\lambda_{2}\\\
\rm{s.t.}&w_{0}+w_{1}+w_{2}+w_{3}=0,\;\;w_{0}=1\\\
&w_{1}=\lambda_{1},\;\;w_{2}=-\lambda_{2},\;\;w_{3}\leq 0\\\
&w_{0},w_{1},w_{2}\textnormal{ free},\;\;\bm{\lambda}\geq\bm{0}.\end{array}$

Clearly, the feasible region of (D) is unbounded.

The following remark will be useful in Section 3 when we wish to replace
embedded optimization problems with their duals without changing the feasible
region of the outer optimization problem.

######  Remark 1 (Strict Inequalities).

If (P) admits a strict Slater point $\bm{x}^{\rm S}$, then any feasible
solution $\bm{x}$ of (P) can be expressed as the limit of a sequence of strict
Slater points $\bm{x}_{n}=\frac{1}{n}\bm{x}^{\rm S}+(1-\frac{1}{n})\bm{x}$,
$n\in\mathbb{N}$, and its objective function value satisfies
$f_{0}(\bm{x})=\liminf_{n\rightarrow\infty}f_{0}(\bm{x}_{n})$. Indeed, we have

$\displaystyle
f_{0}(\bm{x})\;\leq\;\liminf_{n\rightarrow\infty}f_{0}(\bm{x}_{n})\;\leq\;\liminf_{n\rightarrow\infty}\left\\{\frac{1}{n}f_{0}(\bm{x}^{\rm
S})+\left(1-\frac{1}{n}\right)f_{0}(\bm{x})\right\\}\;=\;f_{0}(\bm{x}),$

where the two inequalities follow from the closedness and the convexity of
$f_{0}$, respectively. Therefore, replacing weak inequalities by strict
inequalities in (P) does not change the infimum of (P) if (P) admits a strict
Slater point.

##  3 Robust Convex Optimization

We first extend the notions of conjugates and perspectives to functions
$f(\bm{x},\bm{z})$ with two arguments, where the first argument $\bm{x}$
should be interpreted as a decision variable, while the second argument
$\bm{z}$ represents an exogenous uncertain parameter.

######  Definition 5 (Partial Conjugates).

The partial conjugate of a function
$f:\mathbb{R}^{d_{\bm{x}}}\times\mathbb{R}^{d_{\bm{z}}}\rightarrow\overline{\mathbb{R}}$
with respect to its first argument is the function
$f^{*1}:\mathbb{R}^{d_{\bm{x}}}\times\mathbb{R}^{d_{\bm{z}}}\rightarrow\overline{\mathbb{R}}$
defined through
$f^{*1}(\bm{w},\bm{z})=\sup_{\bm{x}\in\mathbb{R}^{d_{\bm{x}}}}\left\\{\bm{w}^{\top}\bm{x}-f(\bm{x},\bm{z})\right\\}$.
Likewise, the partial conjugate of $f$ with respect to its second argument is
the function
$f^{*2}:\mathbb{R}^{d_{\bm{x}}}\times\mathbb{R}^{d_{\bm{z}}}\rightarrow\overline{\mathbb{R}}$
defined through
$f^{*2}(\bm{x},\bm{y})=\sup_{\bm{z}\in\mathbb{R}^{d_{\bm{z}}}}\left\\{\bm{y}^{\top}\bm{z}-f(\bm{x},\bm{z})\right\\}.$

######  Definition 6 (Partial Perspectives).

If
$f:\mathbb{R}^{d_{\bm{x}}}\times\mathbb{R}^{d_{\bm{z}}}\rightarrow\overline{\mathbb{R}}$
is proper, closed and convex in its first argument, then we define its convex
partial perspective
$\underline{f}:\mathbb{R}^{d_{\bm{x}}}\times\mathbb{R}_{+}\times\mathbb{R}^{d_{\bm{z}}}\rightarrow\overline{\mathbb{R}}$
through $\underline{f}(\bm{x},t,\bm{z})=tf(\bm{x}/t,\bm{z})$ if $t>0$ and
$\underline{f}(\bm{x},0,\bm{z})=\delta^{*}_{\mathop{\rm{dom}}(f^{*1}(\cdot,\bm{z}))}(\bm{x})$.
If $-f$ is proper, closed and convex in its second argument, then we define
its concave partial perspective
$\overline{f}:\mathbb{R}^{d_{\bm{x}}}\times\mathbb{R}^{d_{\bm{z}}}\times\mathbb{R}_{+}\rightarrow\overline{\mathbb{R}}$
through $\overline{f}(\bm{x},\bm{z},t)=tf(\bm{x},\bm{z}/t)$ if $t>0$ and
$\overline{f}(\bm{x},\bm{z},0)=-\delta^{*}_{\mathop{\rm{dom}}((-f)^{*2}(\bm{x},\cdot))}(\bm{z})$.

For ease of notation, we henceforth use $tf(\bm{x}/t,\bm{z})$ and
$tf(\bm{x},\bm{z}/t)$ to denote $\underline{f}(\bm{x},t,\bm{z})$ and
$\overline{f}(\bm{x},\bm{z},t)$, respectively.

Consider now the parametric optimization problem

$\begin{array}[]{l@{\quad}l@{\qquad}l}\inf&f_{0}(\bm{x},\bm{z}_{0})\\\
\rm{s.t.}&f_{i}(\bm{x},\bm{z}_{i})\leq 0&\displaystyle\forall
i\in\mathcal{I}\\\ &\bm{x}\text{ free}\end{array}$ (P-S)

Primal Scenario Problem
whose objective and constraint functions
$f_{i}:\mathbb{R}^{d_{\bm{x}}}\times\mathbb{R}^{d_{\bm{z}}}\rightarrow\overline{\mathbb{R}}$
are parameterized by uncertain parameters $\bm{z}_{i}$, $i\in\mathcal{I}_{0}$.
We henceforth refer to the parametric optimization problem corresponding to a
fixed scenario $(\bm{z}_{0},\dots,\bm{z}_{I})$ of the uncertain parameters as
the (primal) scenario problem. In the remainder of this section, we assume
that (P-S) is convex, that is, we assume that its objective and constraint
functions satisfy the following regularity condition.

  * (RF)

The function $f_{i}(\bm{x},\bm{z}_{i})$ is proper, closed and convex in
$\bm{x}$ for every fixed $\bm{z}_{i}$, and $-f_{i}(\bm{x},\bm{z}_{i})$ is
proper, closed and convex in $\bm{z}_{i}$ for every fixed $\bm{x}$ across all
$i\in\mathcal{I}_{0}$.

Assumption (RF) implies that $f_{i}$ is real-valued for every
$i\in\mathcal{I}_{0}$. Indeed, as $f_{i}(\bm{x},\bm{z}_{i})$ is proper in
$\bm{x}$ for every $\bm{z}_{i}$, we have $f_{i}(\bm{x},\bm{z}_{i})>-\infty$
for every $\bm{x}$ and $\bm{z}_{i}$. Similarly, as $-f_{i}(\bm{x},\bm{z}_{i})$
is proper in $\bm{z}_{i}$ for every $\bm{x}$, we have
$f_{i}(\bm{x},\bm{z}_{i})<+\infty$ for every $\bm{x}$ and $\bm{z}_{i}$. In
particular, the assumption (RF) thus implies that ${\rm
ri}(\mathop{\rm{dom}}(f_{i}))={\rm
ri}(\mathop{\rm{dom}}(-f_{i}))=\mathbb{R}^{d_{\bm{x}}}\times\mathbb{R}^{d_{\bm{z}}}$
for all $i\in\mathcal{I}_{0}$. As any convex function is continuous on the
relative interior of its domain, this implies that $f_{i}(\bm{x},\bm{z}_{i})$
is continuous in $\bm{x}$ for all fixed $\bm{z}_{i}$ and continuous in
$\bm{z}_{i}$ for all fixed $\bm{x}$.

In analogy to Section 2, we consider the problem dual to (P-S).

$\begin{array}[]{l@{\quad}l@{\qquad}l}\sup&\lx@intercol\displaystyle\mspace{-8.0mu}-f_{0}^{*1}\left(\bm{w}_{0},\bm{z}_{0}\right)-\sum_{i\in\mathcal{I}}\lambda_{i}f_{i}^{*1}(\bm{w}_{i}/\lambda_{i},\bm{z}_{i})\hfil\lx@intercol\\\
\rm{s.t.}&\displaystyle\sum_{i\in\mathcal{I}_{0}}\bm{w}_{i}=\bm{0}\\\
&\bm{w}_{i}\textnormal{ free}&\forall i\in\mathcal{I}_{0}\\\
&\bm{\lambda}\geq\bm{0}\end{array}$ (D-S)

Dual Scenario Problem

Since condition (F) from Section 2 is satisfied, Theorem 1 implies that the
problems (P-S) and (D-S) satisfy a weak duality relationship. In addition,
strong duality between (P-S) and (D-S) as well as primal and dual solvability
hold under the relevant conditions of Theorem 2.

The scenario problem (P-S) may have different optimal solutions for different
scenarios. Before the uncertainty is revealed, it is therefore unclear which
of these optimal solutions should be implemented. In the following we assume
that all uncertain parameters $\bm{z}_{i}$, $i\in\mathcal{I}_{0}$, reside in
the nonempty uncertainty set

$\mathcal{Z}=\left\\{\bm{z}\in\mathbb{R}^{d_{\bm{z}}}\mid c_{\ell}(\bm{z})\leq
0\;\;\forall\ell\in\mathcal{L}\right\\}$ (2)

described by the constraint functions
$c_{\ell}:\mathbb{R}^{d_{\bm{z}}}\rightarrow\overline{\mathbb{R}}$,
$\ell\in\mathcal{L}$. In the remainder of this section, we assume that these
constraint functions obey the following regularity condition.

  * (C)

The function $c_{\ell}$ is proper, closed and convex for each
$\ell\in\mathcal{L}$.

Assumption (C) immediately implies that the uncertainty set $\mathcal{Z}$ is
closed.

A popular approach to disambiguate the uncertain convex program (P-S) is to
solve its robust counterpart, which seeks a decision that minimizes the worst-
case objective across all $\bm{z}_{0}\in\mathcal{Z}$ and is feasible for all
possible $\bm{z}_{i}\in\mathcal{Z}$, $i\in\mathcal{I}$. Formally, the robust
counterpart can be expressed as follows.

$\begin{array}[]{l@{\quad}l@{\qquad}l}\inf&\displaystyle\sup_{\bm{z}_{0}\in\mathcal{Z}}f_{0}(\bm{x},\bm{z}_{0})\\\
\rm{s.t.}&\displaystyle\sup_{\bm{z}_{i}\in\mathcal{Z}}f_{i}(\bm{x},\bm{z}_{i})\leq
0&\displaystyle\forall i\in\mathcal{I}\\\ &\bm{x}\text{ free}\end{array}$
(P-W)

Primal Worst Problem

Note that $\sup_{\bm{z}_{i}\in\mathcal{Z}}f_{i}(\bm{x},\bm{z}_{i})\leq 0$ if
and only if $f_{i}(\bm{x},\bm{z}_{i})\leq 0$ for all
$\bm{z}_{i}\in\mathcal{Z}$, $i\in\mathcal{I}$. As it solves the uncertain
primal problem (P-S) under the most pessimistic uncertainty realizations, the
robust counterpart (P-W) is sometimes referred to as the primal worst problem.
Closely related to the primal worst is the dual best problem, which solves the
dual scenario problem (D-S) under the most optimistic uncertainty
realizations.

$\begin{array}[]{l@{\quad}l@{\qquad}l}\sup&\lx@intercol\displaystyle\mspace{-8.0mu}-f_{0}^{*1}\left(\bm{w}_{0},\bm{z}_{0}\right)-\sum_{i\in\mathcal{I}}\lambda_{i}f_{i}^{*1}(\bm{w}_{i}/\lambda_{i},\bm{z}_{i})\hfil\lx@intercol\\\
\rm{s.t.}&\displaystyle\sum_{i\in\mathcal{I}_{0}}\bm{w}_{i}=\bm{0}\\\
&\bm{w}_{i}\textnormal{
free},\;\;\bm{z}_{i}\in\mathcal{Z}&\displaystyle\forall i\in\mathcal{I}_{0}\\\
&\bm{\lambda}\geq\bm{0}\end{array}$ (D-B)

Dual Best Problem

Note that in (D-B) the uncertainty realizations $\bm{z}_{i}$,
$i\in\mathcal{I}_{0}$, are decision variables that can be chosen freely within
the uncertainty set $\mathcal{Z}$. As (D-B) accommodates only finitely many
decision variables and constraints, it is at least principally amenable to
numerical solution. Unfortunately, (D-B) is generically non-convex as it
involves partial perspectives of (jointly) convex functions.

######  Example 4 (Non-Convexity of Problem (D-B)).

Consider an instance of problem (P-W) with $I=d_{\bm{x}}=d_{\bm{z}}=1$,
$\mathcal{Z}=\mathbb{R}$, $f_{0}(x,z_{0})=xz_{0}$ and
$f_{1}(x,z_{1})=\frac{1}{2}x^{2}+z_{1}$. Then, we can readily compute

$f_{0}^{*1}(w_{0},z_{0})=\begin{cases}0&\text{if $w_{0}=z_{0}$}\\\
\infty&\text{if $w_{0}\neq z_{0}$}\end{cases}\quad\text{ and }\quad
f_{1}^{*1}\left(w_{1},z_{1}\right)=\frac{w_{1}^{2}}{2}-z_{1},$

which results in the following instance of problem (D-B).

$\begin{array}[]{l@{\quad}l@{\quad}l}\sup&\displaystyle-\frac{w_{1}^{2}}{2\lambda_{1}}+\lambda_{1}z_{1}\\\
\rm{s.t.}&w_{0}+w_{1}=0,\;\;w_{0}=z_{0}\\\
&w_{0},w_{1},z_{0},z_{1}\textnormal{ free},\;\;\lambda_{1}\geq 0\end{array}$

Using the format $(w_{0},w_{1},z_{0},z_{1},\lambda_{1})$ to denote solutions
of (D-B), it is easy to verify that both $(1,-1,1,2,\frac{1}{2})$ and
$(0,0,0,0,0)$ are feasible in (D-B) with the same objective value $0$. Even
though their equally weighted convex combination
$(\frac{1}{2},-\frac{1}{2},\frac{1}{2},1,\frac{1}{4})$ is also feasible, its
objective value amounts to $-\frac{1}{4}<\frac{1}{2}\cdot 0+\frac{1}{2}\cdot
0$. Therefore, the instance of (D-B) at hand is non-convex.

The primal worst and dual best problems satisfy a weak duality relationship.

######  Theorem 4 (Weak Duality for (P-W) and (D-B)).

The infimum of the primal worst problem (P-W) is larger or equal to the
supremum of the dual best problem (D-B).

###### Proof.

For any fixed ${\bm{z}}_{i}\in\mathcal{Z}$, $i\in\mathcal{I}_{0}$, the
problems (P-W) and (D-B) collapse to instances of (P-S) and (D-S),
respectively. Then, the following inequalities directly follow from Theorem 1.

$\displaystyle\inf_{\bm{x}\in\mathcal{X}({\bm{z}}_{1},\ldots,{\bm{z}}_{I})}f_{0}(\bm{x},{\bm{z}}_{0})$
$\displaystyle\geq\sup_{\sum_{i\in\mathcal{I}_{0}}\bm{w}_{i}=\bm{0}\atop\bm{\lambda}\geq\bm{0}}-f_{0}^{*1}\left(\bm{w}_{0},{\bm{z}}_{0}\right)-\sum_{i\in\mathcal{I}}\lambda_{i}f_{i}^{*1}(\bm{w}_{i}/\lambda_{i},{\bm{z}}_{i})$
$\displaystyle\implies\quad\sup_{\\{\bm{z}_{i}\\}_{i\in\mathcal{I}_{0}}\subseteq\mathcal{Z}}\inf_{\bm{x}\in\mathcal{X}(\bm{z}_{1},\ldots,\bm{z}_{I})}f_{0}(\bm{x},\bm{z}_{0})$
$\displaystyle\geq\sup_{\\{\bm{z}_{i}\\}_{i\in\mathcal{I}_{0}}\subseteq\mathcal{Z}}\sup_{\sum_{i\in\mathcal{I}_{0}}\bm{w}_{i}=\bm{0}\atop\bm{\lambda}\geq\bm{0}}-f_{0}^{*1}\left(\bm{w}_{0},\bm{z}_{0}\right)-\sum_{i\in\mathcal{I}}\lambda_{i}f_{i}^{*1}(\bm{w}_{i}/\lambda_{i},\bm{z}_{i}),$

where
$\mathcal{X}(\bm{z}_{1},\ldots,\bm{z}_{I})=\left\\{\bm{x}\in\mathbb{R}^{d_{\bm{x}}}\
|\ f_{i}(\bm{x},\bm{z}_{i})\leq 0\;\;\forall i\in\mathcal{I}\right\\}$. Note
that the right-hand side of the second inequality is equivalent to (D-B),
while left-hand side is upper bounded by (P-W) because

$\inf_{\bm{x}\in\mathcal{X}(\bm{z}_{1},\ldots,\bm{z}_{I})}\sup_{\\{\bm{z}_{i}\\}_{i\in\mathcal{I}_{0}}\subseteq\mathcal{Z}}f_{0}(\bm{x},\bm{z}_{0})\;\;\geq\;\;\sup_{\\{\bm{z}_{i}\\}_{i\in\mathcal{I}_{0}}\subseteq\mathcal{Z}}\inf_{\bm{x}\in\mathcal{X}(\bm{z}_{1},\ldots,\bm{z}_{I})}f_{0}(\bm{x},\bm{z}_{0})$

due to the min-max inequality. ∎

As (P-W) involves embedded maximization problems and as (D-B) is generally
non-convex (see Example 4), both problems appear to be difficult to solve. In
the following we will demonstrate, however, that under mild conditions both
(P-W) and (D-B) can be reformulated as polynomial-size convex programs (P-W′)
and (D-B′) that are amenable to solution with off-the-shelf solvers. While
useful for computation, these reformulations will also allow us to prove
strong duality between (P-W) and (D-B). To this end, we first summarize the
relationships among the problems (P-W), (P-W′), (D-B) and (D-B′) in Figure 1.

$\inf\eqref{eq:pw-ro}$ $\sup\eqref{eq:db-ro}$$\inf\eqref{eq:pw-cvx-
ro}$$\sup\eqref{eq:db-cvx-ro}$Theorem 4Theorem 8

Proposition 5  _(ii)_ ,  _(iii)_

Proposition 5  _(i)_

Proposition 6  _(i)_

Proposition 6  _(ii)_ ,  _(iii)_

Theorem 7  _(ii)_ ,  _(iii)_ Theorem 7  _(i)_ Figure 1: Illustration of the
relationships among (P-W), (P-W′), (D-B) and (D-B′). The optimal values of
these problems are non-increasing in the directions of the arcs. Dashed arcs
represent universal inequalities, while the solid arcs represent inequalities
that hold under regularity conditions.

We now show that (P-W) can be reduced to the following problem by dualizing
the maximization problems that are embedded in (P-W).

$\begin{array}[]{l@{\quad}l@{\qquad}l}\inf&\displaystyle(-f_{0})^{*2}\left(\bm{x},\bm{y}_{00}\right)+\sum_{\ell\in\mathcal{L}}\nu_{0\ell}c_{\ell}^{*}\left(\bm{y}_{0\ell}/\nu_{0\ell}\right)\\\
\rm{s.t.}&\displaystyle(-f_{i})^{*2}\left(\bm{x},\bm{y}_{i0}\right)+\sum_{\ell\in\mathcal{L}}\nu_{i\ell}c_{\ell}^{*}\left(\bm{y}_{i\ell}/\nu_{i\ell}\right)\leq
0&\displaystyle\forall i\in\mathcal{I}\\\
&\displaystyle\sum_{\ell\in\mathcal{L}_{0}}\bm{y}_{i\ell}=\bm{0}&\displaystyle\forall
i\in\mathcal{I}_{0}\\\ &\bm{x}\textnormal{ free}\\\
&\bm{y}_{i\ell}\textnormal{ free}&\displaystyle\forall
i\in\mathcal{I}_{0},\;\forall\ell\in\mathcal{L}_{0}\\\ &\nu_{i\ell}\geq
0&\displaystyle\forall
i\in\mathcal{I}_{0},\;\forall\ell\in\mathcal{L}\end{array}$ (P-W′)

Reformulated Primal Worst Problem

Problem (P-W′) is convex since its objective function and its constraints
involve infimal convolutions of the conjugate objective and constraint
functions $f_{i}$ as well as the perspectives of the conjugate constraint
functions $c_{\ell}$ describing the uncertainty set (_cf._ Proposition B.5).

######  Proposition 5 (Convex Reformulation of (P-W)).

The following statements hold.

  1. (i)

The infimum of (P-W) is smaller or equal to that of (P-W′).

  2. (ii)

If $\mathcal{Z}$ admits a Slater point, then the infima of (P-W) and (P-W′)
coincide, and (P-W) is solvable if and only if (P-W′) is solvable.

  3. (iii)

If $\mathcal{Z}$ is compact and (P-W) admits a strict Slater point, then the
infima of (P-W) and (P-W′) coincide, and (P-W) is solvable whenever (P-W′) is
solvable.

Note that in Proposition 5  _(iii)_ , the solvability of (P-W) does not imply
the solvability of (P-W′). Nevertheless, one can construct a sequence of
feasible solutions to (P-W′) from a solution to (P-W) that asymptotically
attain the same optimal value.

###### Proof of Proposition 5.

To show that (P-W′) upper bounds (P-W), we dualize the embedded maximization
problems in (P-W) that evaluate the worst-case uncertainty realizations in the
objective and the constraint functions. Specifically, for any fixed
$i\in\mathcal{I}_{0}$ and $\bm{x}\in\mathbb{R}^{d_{\bm{x}}}$, we have

$\displaystyle\sup_{\bm{z}_{i}\in\mathcal{Z}}f_{i}(\bm{x},\bm{z}_{i})$
$\displaystyle=-\begin{cases}\inf\hskip 1.42262pt&-f_{i}(\bm{x},\bm{z}_{i})\\\
\rm{s.t.}&c_{\ell}(\bm{z}_{i})\leq 0\qquad\forall\ell\in\mathcal{L}\\\
&\bm{z}_{i}\textnormal{ free}\end{cases}$ (3a)
$\displaystyle\leq-\begin{cases}\sup\
&\displaystyle-(-f_{i})^{*2}\left(\bm{x},\bm{y}_{i0}\right)-\sum_{\ell\in\mathcal{L}}\nu_{i\ell}c_{\ell}^{*}\left(\bm{y}_{i\ell}/\nu_{i\ell}\right)\\\
\rm{s.t.}&\displaystyle\sum_{\ell\in\mathcal{L}_{0}}\bm{y}_{i\ell}=\bm{0}\\\
&\bm{y}_{i\ell}\textnormal{ free}\qquad\qquad\forall\ell\in\mathcal{L}_{0}\\\
&\nu_{i\ell}\geq 0\mspace{38.0mu}\qquad\forall\ell\in\mathcal{L},\end{cases}$
(3b)

where the inequality follows from Theorem 1, which applies because the
assumptions (RF) and (C) imply that (3a) satisfies assumption (F) from Section
2. Interchanging the minus sign and the supremum operator in (3b) results in a
minimization problem. Substituting the resulting minimization problem into
(P-W) for every $i\in\mathcal{I}_{0}$ and then merging the infimum operators
in the objective and removing the infimum operators in the constraints yields
(P-W′), and thus the infimum of (P-W) is indeed smaller or equal to that of
(P-W′). Note that if the optimal solution of (3b) is not attained for some
$i\in\mathcal{I}$, then removing the infimum operators in the constraints may
lead to a further restriction of the problem and therefore result in a higher
optimal value.

As for assertion  _(ii)_ , assume that $\mathcal{Z}$ admits a Slater point
$\bm{z}^{\rm S}$. As
$\mathop{\rm{dom}}(-f_{i}(\bm{x},\cdot))=\mathbb{R}^{d_{\bm{x}}}$ due to
assumption (RF), $\bm{z}^{\rm S}$ is also a Slater point for the minimization
problem in (3a). By Theorem 2  _(i)_ , the duality gap between (3a) and (3b)
thus vanishes, and the dual problem (3b) is solvable. This implies that the
infima of (P-W) and (P-W′) coincide and that any optimizer of (P-W) can be
combined with optimizers of the dual subproblems (3b) for
$i\in\mathcal{I}_{0}$ to construct an optimizer for (P-W′).

As for assertion  _(iii)_ , assume finally that $\mathcal{Z}$ is compact and
that problem (P-W) admits a strict Slater point $\bm{x}^{\rm S}$. In this
case, the functions
$F_{i}(\bm{x})=\sup_{\bm{z}_{i}\in\mathcal{Z}}f_{i}(\bm{x},\bm{z}_{i})$,
$i\in\mathcal{I}_{0}$, are convex and continuous in $\bm{x}$ by virtue of
assumption (RF). Indeed, $F_{i}(\bm{x})$ is convex and closed because
$f_{i}(\bm{x},\bm{z}_{i})$ is convex and closed in $\bm{x}$ for every fixed
$\bm{z}_{i}$. Moreover, $F_{i}(\bm{x})$ is finite for every fixed $\bm{x}$ due
to Weierstrass’ extreme value theorem, which applies because $\mathcal{Z}$ is
compact and $-f_{i}(\bm{x},\bm{z}_{i})$ is closed (and thus lower
semicontinuous) in $\bm{z}_{i}$. As any convex function is continuous on the
relative interior of its domain, we may thus conclude that each $F_{i}$ is
continuous on $\mathbb{R}^{d_{\bm{x}}}$. By forming convex combinations with
the strict Slater point $\bm{x}^{\rm S}$, one can now use the continuity and
convexity of the functions $F_{i}$, $i\in\mathcal{I}_{0}$, to prove that any
$\bm{x}$ feasible in (P-W) can be represented as a limit of strict Slater
points for (P-W). Therefore, (P-W) is equivalent to

$\begin{array}[]{l@{\quad}l@{\qquad}l}\inf&\displaystyle\sup_{\bm{z}_{0}\in\mathcal{Z}}f_{0}(\bm{x},\bm{z}_{0})\\\
\rm{s.t.}&\displaystyle\sup_{\bm{z}_{i}\in\mathcal{Z}}f_{i}(\bm{x},\bm{z}_{i})<0&\forall
i\in\mathcal{I}\\\ &\bm{x}\text{ free.}\end{array}$ (4)

We can now dualize the embedded maximization problems in (4) as in the proof
of assertion  _(i)_. The compactness of $\mathcal{Z}$ implies via Theorem 2
_(ii)_ that the duality gap between (3a) and (3b) vanishes. The minimization
problems resulting from interchanging the minus sign and the supremum operator
in (3b) can then be substituted back into (4), the infimum operators in the
objective can be merged, and the infimum operators in the constraints can be
removed to obtain a variant of (P-W′) with strict inequalities. Note that
because the constraints in (4) are strict, the infimum operators in the
constraints may indeed be removed without restricting the problem even if the
corresponding subproblems are not solvable. Next, we argue that the strict
inequalities in the resulting problem can again be relaxed to weak
inequalities without changing the problem’s optimal value. By Remark 1, this
is the case if problem (P-W′) admits a strict Slater point. Such a strict
Slater point can be constructed by combining the strict Slater point
$\bm{x}^{\rm S}$ of (P-W) with strict Slater points
$(\\{\bm{y}_{i_{\ell}}^{\rm S},\nu_{i_{\ell}}^{\rm S}\\}_{\ell})$ for the dual
subproblems, $i\in I_{0}$, which exist thanks to Proposition 3. Thus, the
infima of (P-W) and (P-W′) are indeed equal.

Finally, to see that the solvability of (P-W′) implies the solvability of
(P-W), assume that
$(\bm{x}^{\star},\\{\bm{y}^{\star}_{i\ell},\nu^{\star}_{i\ell}\\}_{i,\ell})$
solves (P-W′). The above reasoning then implies that the optimal value of
(P-W′) amounts to $F_{0}(\bm{x}^{\star})$, which in turn shows that
$\bm{x}^{\star}$ solves (P-W). ∎

Next, we argue that under mild conditions the non-convex dual best problem
(D-B) is equivalent to the following finite convex optimization problem.

$\begin{array}[]{l@{\quad}l@{\qquad}l}\displaystyle\sup&\lx@intercol\displaystyle\mspace{-8.0mu}-f_{0}^{*1}\left(\bm{w}_{0},\bm{z}_{0}\right)-\sum_{i\in\mathcal{I}}\lambda_{i}f_{i}^{*1}(\bm{w}_{i}/\lambda_{i},\bm{\upsilon}_{i}/\lambda_{i})\hfil\lx@intercol\\\
\rm{s.t.}&\displaystyle\sum_{i\in\mathcal{I}_{0}}\bm{w}_{i}=\bm{0}\\\
&c_{\ell}(\bm{z}_{0})\leq 0&\displaystyle\forall\ell\in\mathcal{L}\\\
&\lambda_{i}c_{\ell}(\bm{\upsilon}_{i}/\lambda_{i})\leq 0&\displaystyle\forall
i\in\mathcal{I},\;\forall\ell\in\mathcal{L}\\\ &\bm{w}_{i}\textnormal{
free}&\displaystyle\forall i\in\mathcal{I}_{0}\\\ &\bm{z}_{0}\textnormal{
free},\;\;\bm{\lambda}\geq\bm{0}\\\ &\bm{\upsilon}_{i}\textnormal{
free}&\displaystyle\forall i\in\mathcal{I}\end{array}$ (D-B′)

Reformulated Dual Best Problem

Intuitively, one can think of problem (D-B′) as being obtained from (D-B) by
multiplying the inequalities involving $\bm{z}_{i}$ by $\lambda_{i}$,
$i\in\mathcal{I}$ and via the variable substitution
$\bm{\upsilon}_{i}\leftarrow\lambda_{i}\bm{z}_{i}$. Since the perspective of a
convex function is convex, the resulting model (D-B′) is indeed a convex
problem.

The equivalence of (D-B) and (D-B′) was first established for robust linear
programs with compact uncertainty sets (Gorissen et al., 2014, Lemma 1) and
then generalized to robust nonlinear programs with compact uncertainty sets
(Gorissen and den Hertog, 2015, Theorem 1). In the following, we relax the
compactness condition and demonstrate that the nonlinear programs (D-B) and
(D-B′) remain equivalent if the uncertainty set admits a Slater point. This
alternative result is useful for the analysis of distributionally robust
optimization problems, which can often be reformulated as robust optimization
problems with unbounded uncertainty sets (see Section 4).

######  Proposition 6 (Convex Reformulation of (D-B)).

The following statements hold.

  1. (i)

The supremum of (D-B) is smaller or equal to that of (D-B′).

  2. (ii)

If (D-B) admits a strict Slater point, then the suprema of (D-B) and (D-B′)
coincide, and (D-B′) is solvable whenever (D-B) is solvable.

  3. (iii)

If $\mathcal{Z}$ is bounded, then the suprema of (D-B) and (D-B′) coincide,
and (D-B′) is solvable if and only if (D-B) is solvable.

Note that in Proposition 6  _(ii)_ , the solvability of (D-B′) does not imply
the solvability of (D-B). Nevertheless, one can construct a sequence of
feasible solutions to (D-B) from a solution to (D-B′) that asymptotically
attain the same optimal value.

###### Proof of Proposition 6.

As for  _(i)_ , we prove that any feasible solution to (D-B) corresponds to a
feasible solution to (D-B′) with the same objective value. To this end, select
any $(\\{\bm{w}_{i},\bm{z}_{i}\\}_{i},\bm{\lambda})$ feasible in (D-B) and
define $\bm{\upsilon}_{i}=\lambda_{i}\bm{z}_{i}$ for $i\in\mathcal{I}$. We
show that
$(\\{\bm{w}_{i}\\}_{i},{\bm{z}}_{0},\bm{\lambda},\left\\{{\bm{\upsilon}}_{i}\right\\}_{i})$
is feasible in (D-B′) and attains the same objective value. Indeed, it is
clear that $\lambda_{i}c_{\ell}(\bm{\upsilon}_{i}/\lambda_{i})\leq 0$ for all
$\ell\in\mathcal{L}$ and $i\in\mathcal{I}$ with $\lambda_{i}>0$. If
$\lambda_{i}=0$ for some $i\in\mathcal{I}$, on the other hand, we have
$\bm{\upsilon}_{i}=\bm{0}$ and

$0c_{\ell}(\bm{0}/0)\;=\;\delta^{*}_{\mathop{\rm{dom}}(c^{*}_{\ell})}(\bm{0})\;=\;0\qquad\forall\ell\in\mathcal{L},$

where the first equality follows from the definition of the convex
perspective, while the second equality holds because $c^{*}_{\ell}$ inherits
properness from $c_{\ell}$ (Rockafellar, 1970, Theorem 12.2) and because the
support function of $\mathop{\rm{dom}}(c^{*}_{\ell})\neq\emptyset$ vanishes at
the origin. All other constraints of (D-B′) are trivially satisfied. Next, we
show that the objective value of
$(\\{\bm{w}_{i},\bm{z}_{i}\\}_{i},\bm{\lambda})$ in (D-B) equals that of
$(\\{\bm{w}_{i}\\}_{i},{\bm{z}}_{0},\bm{\lambda},\left\\{{\bm{\upsilon}}_{i}\right\\}_{i})$
in (D-B′). Indeed, it is clear that
$\lambda_{i}f_{i}^{*1}(\bm{w}_{i}/\lambda_{i},\bm{\upsilon}_{i}/\lambda_{i})=\lambda_{i}f_{i}^{*1}(\bm{w}_{i}/\lambda_{i},\bm{z}_{i})$
for all $i\in\mathcal{I}$ with $\lambda_{i}>0$. If $\lambda_{i}=0$ for some
$i\in\mathcal{I}$, on the other hand, then $\bm{\upsilon}_{i}=\bm{0}$, and the
convex perspective function $0f_{i}^{*1}(\bm{w}_{i}/0,\bm{0}/0)$ is defined as
the support function of the domain of $(f_{i}^{*1})^{*}$. As
$(f_{i}^{*1})^{*}=(-f_{i})^{*2}$ due to Proposition B.6, we may thus conclude
that

$\displaystyle 0f_{i}^{*1}(\bm{w}_{i}/0,\bm{0}/0)\;$
$\displaystyle=\;\delta^{*}_{\mathop{\rm{dom}}((-f_{i})^{*2})}(\bm{w}_{i},\bm{0})$
$\displaystyle=\;\sup_{\bm{x}}\left\\{\bm{w}_{i}^{\top}\bm{x}\ |\
\exists\bm{y}\in\mathbb{R}^{d_{\bm{z}}}:(-f_{i})^{*2}(\bm{x},\bm{y})<+\infty\right\\}$
$\displaystyle=\;\delta_{\\{\bm{0}\\}}(\bm{w}_{i})$
$\displaystyle=\;\delta^{*}_{\mathop{\rm{dom}}(f_{i}(\cdot,\bm{z}_{i}))}(\bm{w}_{i})\;=\;0f_{i}^{*1}(\bm{w}_{i}/0,\bm{z}_{i}),$

where the third equality follows from Rockafellar (1970, Theorem 12.2), which
ensures that for any $\bm{x}\in\mathbb{R}^{d_{\bm{x}}}$ the partial conjugate
$(-f_{i})^{*2}(\bm{x},\cdot)$ of the proper function $-f_{i}(\bm{x},\cdot)$ is
also proper. Thus, for any $\bm{x}\in\mathbb{R}^{d_{\bm{x}}}$, there exists
$\bm{y}\in\mathbb{R}^{d_{\bm{z}}}$ with
$(-f_{i})^{*2}(\bm{x},\bm{y})<+\infty$, which implies that $\bm{x}$ is
actually free, and the supremum evaluates to $+\infty$ unless
$\bm{w}_{i}=\bm{0}$. The fourth equality holds because
$\mathop{\rm{dom}}(f_{i}(\cdot,\bm{z}_{i}))=\mathbb{R}^{d_{\bm{x}}}$ for every
$\bm{z}_{i}\in\mathbb{R}^{d_{\bm{z}}}$, and the last equality follows from the
definition of the partial convex perspective and from Theorem 12.2 of
Rockafellar (1970), which implies that
$(f_{i}^{*1})^{*1}(\cdot,\bm{z}_{i})=f_{i}(\cdot,\bm{z}_{i})$. In summary, we
have shown that the optimal value of (D-B) does not exceed that of (D-B′), and
thus assertion _(i)_ follows.

Assume now that
$(\\{\bm{w}_{i}^{\textnormal{S}},{\bm{z}}_{i}^{\textnormal{S}}\\}_{i},\bm{\lambda}^{\textnormal{S}})$
is a strict Slater point for problem (D-B), which implies that
$\bm{\lambda}^{\textnormal{S}}>\bm{0}$. In that case,
$(\\{\bm{w}_{i}^{\textnormal{S}}\\}_{i},{\bm{z}}_{0}^{\textnormal{S}},\bm{\lambda}^{\textnormal{S}},\left\\{{\bm{\upsilon}}_{i}^{\textnormal{S}}\right\\}_{i})$
with
${\bm{\upsilon}}_{i}^{\textnormal{S}}=\lambda_{i}^{\textnormal{S}}\cdot{\bm{z}}_{i}^{\textnormal{S}}$,
$i\in\mathcal{I}$, is a strict Slater point for problem (D-B′). To prove
assertion _(ii)_ , we show that any feasible solution to (D-B′) corresponds to
a sequence of feasible solutions to (D-B) that asymptotically attain a non-
inferior objective value. This implies that the optimal value of (D-B′) is
smaller or equal to that of (D-B), and together with assertion _(i)_ we can
then conclude that the optimal values of (D-B) and (D-B′) coincide. To this
end, select any solution
$(\\{\bm{w}_{i}\\}_{i},{\bm{z}}_{0},\bm{\lambda},\left\\{{\bm{\upsilon}}_{i}\right\\}_{i})$
feasible in (D-B′) and any $\epsilon>0$. As the feasible region of (D-B′) is
convex and the objective function of (D-B′) is concave, there exists
$\theta\in(0,1)$ such that the solution
$(\\{\bm{w}_{i}^{\epsilon}\\}_{i},{\bm{z}}_{0}^{\epsilon},\bm{\lambda}^{\epsilon},\left\\{{\bm{\upsilon}}_{i}^{\epsilon}\right\\}_{i})$
defined through

$(\\{\bm{w}_{i}^{\epsilon}\\}_{i},{\bm{z}}_{0}^{\epsilon},\bm{\lambda}^{\epsilon},\left\\{{\bm{\upsilon}}_{i}^{\epsilon}\right\\}_{i})=\theta\cdot(\\{\bm{w}_{i}\\}_{i},{\bm{z}}_{0},\bm{\lambda},\left\\{{\bm{\upsilon}}_{i}\right\\}_{i})\;+\;(1-\theta)\cdot(\\{\bm{w}_{i}^{\textnormal{S}}\\}_{i},{\bm{z}}_{0}^{\textnormal{S}},\bm{\lambda}^{\textnormal{S}},\left\\{{\bm{\upsilon}}_{i}^{\textnormal{S}}\right\\}_{i})$
(5)

is feasible in (D-B′) and attains an objective function value that is at least
as large as that of
$(\\{\bm{w}_{i}\\}_{i},{\bm{z}}_{0},\bm{\lambda},\left\\{{\bm{\upsilon}}_{i}\right\\}_{i})$
minus $\epsilon$. Setting
$\bm{z}^{\epsilon}_{i}=\bm{\upsilon}^{\epsilon}_{i}/\lambda^{\epsilon}_{i}$
for all $i\in\mathcal{I}$, which is possible because
$\bm{\lambda}^{\epsilon}>\bm{0}$, it is clear that
$(\\{\bm{w}_{i}^{\epsilon},\bm{z}_{i}^{\epsilon}\\}_{i},\bm{\lambda}^{\epsilon})$
is feasible in (D-B) and attains the same objective value as
$(\\{\bm{w}_{i}^{\epsilon}\\}_{i},{\bm{z}}_{0}^{\epsilon},\bm{\lambda}^{\epsilon},\left\\{{\bm{\upsilon}}_{i}^{\epsilon}\right\\}_{i})$
in (D-B′). As
$(\\{\bm{w}_{i}\\}_{i},{\bm{z}}_{0},\bm{\lambda},\left\\{{\bm{\upsilon}}_{i}\right\\}_{i})$
and $\epsilon>0$ were chosen arbitrarily, the supremum of (D-B) is thus at
least as large as that of (D-B′). Together with assertion _(i)_ , we thus
conclude that the suprema of (D-B) and (D-B′) coincide. Moreover, since our
proof of assertion _(i)_ has shown that any feasible solution to (D-B)
corresponds to a feasible solution to (D-B′) with the same objective value,
(D-B′) is solvable whenever (D-B) is solvable.

Assume now that $\mathcal{Z}$ is bounded. To prove assertion _(iii)_ , we show
that any feasible solution to (D-B′) corresponds to a feasible solution to
(D-B) with the same objective value. Together with assertion _(i)_ , this
implies that the optimal values of (D-B) and (D-B′) coincide. To this end,
select any solution
$(\\{\bm{w}_{i}\\}_{i},{\bm{z}}_{0},\bm{\lambda},\left\\{{\bm{\upsilon}}_{i}\right\\}_{i})$
feasible in (D-B′), and define $\bm{z}_{i}=\bm{\upsilon}_{i}/\lambda_{i}$ if
$\lambda_{i}>0$ and $\bm{z}_{i}=\bm{z}_{0}$ if $\lambda_{i}=0$,
$i\in\mathcal{I}$. Lemma B.7  _(i)_ implies that if $\lambda_{i}=0$, then
$\bm{v}_{i}$ must be a recession direction for the uncertainty set
$\mathcal{Z}$. As $\mathcal{Z}$ is nonempty and bounded, this in turn implies
that $\bm{v}_{i}=\bm{0}$. Using the same reasoning as in the proof of
assertion _(i)_ , one can thus show that
$\lambda_{i}c_{\ell}(\bm{\upsilon}_{i}/\lambda_{i})=\lambda_{i}c_{\ell}(\bm{z}_{i})$
for all $\ell\in\mathcal{L}$ and $i\in\mathcal{I}$ and
$\lambda_{i}f_{i}^{*1}(\bm{w}_{i}/\lambda_{i},\bm{\upsilon}_{i}/\lambda_{i})=\lambda_{i}f_{i}^{*1}(\bm{w}_{i}/\lambda_{i},\bm{z}_{i})$
for all $i\in\mathcal{I}$. This implies that
$(\\{\bm{w}_{i},\bm{z}_{i}\\}_{i},\bm{\lambda})$ is feasible in (D-B) and
attains the same objective value as
$(\\{\bm{w}_{i}\\}_{i},{\bm{z}}_{0},\bm{\lambda},\left\\{{\bm{\upsilon}}_{i}\right\\}_{i})$
in (D-B′). Note that our proof of assertion _(i)_ has shown that any feasible
solution to (D-B) corresponds to a feasible solution to (D-B′) with the same
objective value, and our proof of assertion _(iii)_ has shown that any
feasible solution to (D-B′) corresponds to a feasible solution to (D-B) with
the same objective value. Since the optimal values of both problems coincide,
we can conclude that (D-B) is solvable if and only if (D-B′) is solvable. ∎

######  Remark 2 (Equivalence of (D-B) and (D-B′) without a Strict Slater
Point).

Proposition 6  _(ii)_ remains valid if (D-B) admits a feasible solution
$(\\{\bm{w}_{i},{\bm{z}}_{i}\\}_{i},\bm{\lambda})$ with $\bm{\lambda}>\bm{0}$
instead of a strict Slater point. Indeed, the only property of a strict Slater
point needed in the proof is that $\bm{\lambda}>\bm{0}$.

Having identified easily verifiable conditions under which (P-W) and (D-B) are
equivalent to their respective convex reformulations (P-W′) and (D-B′), we are
now ready to prove that (P-W′) and (D-B′) are dual to each other and thus
enjoy various weak and strong duality relationships.

######  Theorem 7 (Duality Results for (P-W′) and (D-B′)).

The following statements hold.

  1. (i)

The infimum of (P-W′) is larger or equal to the supremum of (D-B′).

  2. (ii)

If (P-W′) or (D-B′) admits a Slater point, then the infimum of (P-W′)
coincides with the supremum of (D-B′), and (D-B′) or (P-W′) is solvable,
respectively.

  3. (iii)

If the feasible region of (P-W′) or (D-B′) is nonempty and bounded, then the
infimum of (P-W′) coincides with the supremum of (D-B′), and (P-W′) or (D-B′)
is solvable, respectively.

###### Proof.

We show that (P-W′) and (D-B′) can be viewed as instances of (P) and (D),
respectively. Assertions  _(i)_ , _(ii)_ and _(iii)_ can then be derived from
Theorems 1 and 2. For ease of exposition, we first rewrite the convex
optimization problem (P-W′) more concisely as

$\begin{array}[]{l@{\quad}l@{\qquad}l}\inf&\displaystyle\varphi_{0}(\bm{x},\\{\bm{y}_{0\ell},\nu_{0\ell}\\}_{\ell})\\\
\rm{s.t.}&\displaystyle\varphi_{i}(\bm{x},\\{\bm{y}_{i\ell},\nu_{i\ell}\\}_{\ell})\leq
0&\forall i\in\mathcal{I}\\\ &\psi^{+}_{ik}(\\{y_{i\ell k}\\}_{\ell})\leq
0&\forall i\in\mathcal{I}_{0},\ \forall k\in\mathcal{K}\\\
&\psi^{-}_{ik}(\\{y_{i\ell k}\\}_{\ell})\leq 0&\forall i\in\mathcal{I}_{0},\
\forall k\in\mathcal{K}\\\ &\bm{x},\,\bm{y}_{i\ell}\textnormal{ free}&\forall
i\in\mathcal{I}_{0},\;\forall\ell\in\mathcal{L}_{0}\\\
&\nu_{i\ell}\textnormal{ free}&\forall
i\in\mathcal{I}_{0},\;\forall\ell\in\mathcal{L},\end{array}$ (6)

where the extended real-valued functions $\varphi_{i}$ for
$i\in\mathcal{I}_{0}$ are defined through

$\displaystyle\varphi_{i}(\bm{x},\\{\bm{y}_{i\ell},\nu_{i\ell}\\}_{\ell})$
$\displaystyle=\left\\{\begin{array}[]{c@{\quad}l}\displaystyle(-f_{i})^{*2}\left(\bm{x},\bm{y}_{i0}\right)+\sum_{\ell\in\mathcal{L}}\nu_{i\ell}c_{\ell}^{*}\left(\bm{y}_{i\ell}/\nu_{i\ell}\right)&\text{if
$\nu_{i\ell}\geq 0$,}\ \ell\in\mathcal{L},\\\
+\infty&\text{otherwise,}\end{array}\right.$

the linear equalities in (P-W′) are split into two sets of linear inequalities
defined through

$\displaystyle\psi^{+}_{ik}(\\{y_{i\ell
k}\\}_{\ell})=\sum_{\ell\in\mathcal{L}_{0}}y_{i\ell k}\quad\text{ and
}\quad\psi^{-}_{ik}(\\{y_{i\ell
k}\\}_{\ell})=-\sum_{\ell\in\mathcal{L}_{0}}y_{i\ell k},\qquad\forall
i\in\mathcal{I}_{0},\ \forall k\in\mathcal{K},$

and $y_{i\ell k}$ is the $k$-th element of the vector $\bm{y}_{i\ell}$ for
every $k\in\mathcal{K}=\\{1,\ldots,K\\}$, where $K=d_{\bm{z}}$.

Note that (6) can be viewed as an instance of (P). Moreover, one can show that
its objective and constraint functions satisfy assumption (F), that is, one
can show that $\varphi_{i}$, $\bm{\psi}^{+}_{i}$ and $\bm{\psi}^{-}_{i}$ are
proper, closed and convex for every $i\in\mathcal{I}_{0}$. To see this, note
first that the partial conjugate $(-f_{i})^{*2}$ is proper, closed and convex
by Proposition B.5 and by Theorem 12.2 of Rockafellar (1970), which apply
because $f_{i}$ obeys assumption (RF). Similarly, the convex perspective
$\nu_{i\ell}c_{\ell}^{*}(\bm{y}_{i\ell}/\nu_{i\ell})$ defined for
$\nu_{i\ell}\geq 0$ is proper, closed and convex by Proposition B.2 and by
Theorem 12.2 of Rockafellar (1970), which apply because $c_{\ell}$ obeys
assumption (C). Thus, $\varphi_{i}$ constitutes a sum of proper, closed and
convex functions with different arguments and is therefore also proper, closed
and convex.111The fact that the summands do not share common arguments is
crucial here. The sum of the two proper, closed and convex functions
$\delta_{[0,1]}(x)$ and $\delta_{[2,3]}(x)$ in the common argument
$x\in\mathbb{R}$, for example, is not proper. Finally, $\psi^{+}_{ik}$ and
$\psi^{-}_{ik}$ are linear functions and therefore proper, closed and convex.

If we interpret (6) as an instance of (P), denote the variables conjugate to
$\bm{x}$ and $\nu_{i\ell}$ by $\bm{w}_{i}$ and $u_{i\ell}$, respectively, and
denote the variables conjugate to $\bm{y}_{i\ell}$ by
$\bm{r}_{i\ell},\bm{r}^{+}_{i\ell}$ and $\bm{r}^{-}_{i\ell}$, then the
corresponding instance of (D) can be represented as

$\begin{array}[]{l@{\quad}l@{\qquad}l}\sup&\lx@intercol\displaystyle\mspace{-8.0mu}-\varphi_{0}^{*}(\bm{w}_{0},\\{\bm{r}_{0\ell},u_{0\ell}\\}_{\ell})-\sum_{i\in\mathcal{I}}\Bigg{[}\lambda_{i}\varphi_{i}^{*}\left(\frac{\bm{w}_{i}}{\lambda_{i}},\frac{\\{\bm{r}_{i\ell}\\}_{\ell}}{\lambda_{i}},\frac{\\{u_{i\ell}\\}_{\ell}}{\lambda_{i}}\right)+\hfil\lx@intercol\\\
&\lx@intercol\displaystyle\mspace{245.0mu}\sum_{k\in\mathcal{K}}v_{ik}^{+}(\psi^{+}_{ik})^{*}\left(\frac{\\{r^{+}_{i\ell
k}\\}_{\ell}}{v_{ik}^{+}}\right)+\sum_{k\in\mathcal{K}}v_{ik}^{-}(\psi^{-}_{ik})^{*}\left(\frac{\\{r^{-}_{i\ell
k}\\}_{\ell}}{v_{ik}^{-}}\right)\Bigg{]}\hfil\lx@intercol\\\
\rm{s.t.}&\displaystyle\sum_{i\in\mathcal{I}_{0}}\bm{w}_{i}=\bm{0}&\forall\ell\in\mathcal{L}_{0}\\\
&\bm{r}_{i\ell}+\bm{r}^{+}_{i\ell}+\bm{r}^{-}_{i\ell}=\bm{0}&\forall
i\in\mathcal{I}_{0},\;\forall\ell\in\mathcal{L}_{0}\\\ &u_{i\ell}=0&\forall
i\in\mathcal{I}_{0},\;\forall\ell\in\mathcal{L}\\\
&\bm{w}_{i},\,r_{i\ell},\,\bm{r}^{+}_{i\ell},\,\bm{r}^{-}_{i\ell}\textnormal{
free}&\forall i\in\mathcal{I}_{0},\;\forall\ell\in\mathcal{L}_{0}\\\
&\bm{\lambda},\,\bm{v}_{i}^{+},\,\bm{v}_{i}^{-}\geq\bm{0}&\forall
i\in\mathcal{I}_{0},\end{array}$ (7)

where $r^{+}_{i\ell k}$ and $r^{-}_{i\ell k}$ are the $k$-th elements of the
respective vectors $\bm{r}^{+}_{i\ell}$ and $\bm{r}^{-}_{i\ell}$ for every
$k\in\mathcal{K}$, and
$(\bm{\lambda},\\{\bm{v}_{i}^{+},\bm{v}_{i}^{-}\\}_{i})$ are the dual
variables associated with the three sets of inequalities in (6). Note that
$u_{i\ell}$ is forced to $0$ in (7) because its conjugate variable
$\nu_{i\ell}$ only appears in the objective (if $i=0$) or in the $i$-th
constraint (if $i\in\mathcal{I}$) of the primal problem (6). The conjugate of
$\varphi_{i}$, $i\in\mathcal{I}_{0}$, can be calculated explicitly as

$\displaystyle\varphi_{i}^{*}(\bm{w}_{i},\\{\bm{r}_{i\ell},u_{i\ell}\\}_{\ell})\;$
$\displaystyle=\;\sup_{\bm{x},\bm{y}_{i0}}\left\\{\bm{w}_{i}^{\top}\bm{x}+\bm{r}_{i0}^{\top}\bm{y}_{i0}-(-f_{i})^{*2}(\bm{x},\bm{y}_{i0})\right\\}$
$\displaystyle\qquad\qquad+\sum_{\ell\in\mathcal{L}}\sup_{\bm{y}_{i\ell}\atop\nu_{i\ell}>0}\left\\{u_{i\ell}\nu_{i\ell}+\bm{r}_{i\ell}^{\top}\bm{y}_{i\ell}-\nu_{i\ell}c_{\ell}^{*}\left(\frac{\bm{y}_{i\ell}}{\nu_{i\ell}}\right)\right\\}$
$\displaystyle=\;f_{i}^{*1}(\bm{w}_{i},\bm{r}_{i0})+\sum_{\ell\in\mathcal{L}}\sup_{\nu_{i\ell}>0}\left\\{u_{i\ell}\nu_{i\ell}+\nu_{i\ell}c_{\ell}\left(\bm{r}_{i\ell}\right)\right\\}$
$\displaystyle=\;\left\\{\begin{array}[]{c@{\quad}l}f_{i}^{*1}(\bm{w}_{i},\bm{r}_{i0})&\text{if
}u_{i\ell}+c_{\ell}\left(\bm{r}_{i\ell}\right)\leq
0\;\;\forall\ell\in\mathcal{L}\\\ +\infty&\text{otherwise.}\end{array}\right.$

Note that we may restrict $\nu_{i\ell}$ to be strictly positive because the
convex perspective of $c^{*}_{\ell}$ at $\nu_{i\ell}=0$ is defined as the
lower semicontinuous extension of the perspective for $\nu_{i\ell}>0$; see
(1). The second equality then follows from Proposition B.6, which applies
because $f_{i}$ satisfies assumption (RF), and from Theorem 16.1 of
Rockafellar (1970), which applies because $c_{\ell}$ satisfies assumption (C).

Similarly, the conjugates of $\psi^{+}_{ik}$ and $\psi^{-}_{ik}$ can be
expressed as follows.

$\displaystyle(\psi^{+}_{ik})^{*}(\\{r^{+}_{i\ell k}\\}_{\ell})$
$\displaystyle=\left\\{\begin{array}[]{c@{\quad}l}0&\text{if }r^{+}_{i\ell
k}=1\;\;\forall\ell\in\mathcal{L}_{0}\\\
+\infty&\text{otherwise}\end{array}\right.$
$\displaystyle(\psi^{-}_{ik})^{*}(\\{r^{-}_{i\ell k}\\}_{\ell})$
$\displaystyle=\left\\{\begin{array}[]{c@{\quad}l}0&\text{if }r^{-}_{i\ell
k}=-1\;\;\forall\ell\in\mathcal{L}_{0}\\\
+\infty&\text{otherwise.}\end{array}\right.$

Substituting the formulas for $\varphi_{i}^{*}$, $(\psi^{+}_{ik})^{*}$ and
$(\psi^{-}_{ik})^{*}$ into (7) with $\bm{z}_{0}=\bm{v}_{0}^{+}-\bm{v}_{0}^{-}$
and $\bm{v}_{i}=\bm{v}_{i}^{+}-\bm{v}_{i}^{-}$, $i\in\mathcal{I}$, and
eliminating the variables $\bm{r}_{i\ell}$, $\bm{r}^{+}_{i\ell}$,
$\bm{r}^{-}_{i\ell}$ and $u_{i\ell}$, $i\in\mathcal{I}_{0}$ and
$\ell\in\mathcal{L}_{0}$, finally yields (D-B′). ∎

We now demonstrate that the duality gap between (P-W) and (D-B) vanishes
provided that one out of two complementary regularity conditions holds.

######  Theorem 8 (Strong Duality for (P-W) and (D-B)).

The following statements hold.

  1. (i)

If (P-W) admits a strict Slater point and $\mathcal{Z}$ is bounded, then the
infimum of (P-W) coincides with the supremum of (D-B), and (D-B) is solvable.

  2. (ii)

If the feasible region of (P-W) is nonempty and bounded and $\mathcal{Z}$ is
bounded, then the infimum of (P-W) coincides with the supremum of (D-B), and
(P-W) is solvable.

  3. (iii)

If (D-B) admits a strict Slater point, then its supremum coincides with the
infimum of (P-W), and (P-W) is solvable.

###### Proof.

As for assertion _(i)_ , assume that (P-W) admits a strict Slater point
$\bm{x}^{\rm S}$ and that the uncertainty set $\mathcal{Z}$ is nonempty (by
assumption) and compact (by assumption (C) and the assertion). Then the infima
of (P-W) and (P-W′) coincide due to Proposition 5  _(iii)_. Moreover, since
$f_{i}$ is real-valued, the problem (3b) admits a strict Slater point
$(\\{\bm{y}^{\rm S}_{i\ell},\nu^{\rm S}_{i\ell}\\}_{\ell})$ for fixed
$\bm{x}^{\rm S}$ and for every $i\in\mathcal{I}_{0}$ due to Proposition 3. We
can combine these strict Slater points to a Slater point for problem (P-W′),
and Theorem 7  _(ii)_ implies that (P-W′) and (D-B′) satisfy strong duality,
and (D-B′) is solvable. The claim then follows from Proposition 6  _(iii)_ ,
which ensures that the suprema of (D-B) and (D-B′) coincide, and that (D-B) is
solvable because (D-B′) is solvable.

As for assertion _(ii)_ , assume that the feasible region of (P-W) is nonempty
and bounded and that $\mathcal{Z}$ is bounded. Note that problem (P-W) can be
represented more concisely as

$\inf_{\bm{x}}\left\\{F_{0}(\bm{x})\ |\ F_{i}(\bm{x})\leq 0\;\;\forall
i\in\mathcal{I}\right\\},$ (8)

where $F_{i}(\bm{x})=\sup_{\bm{z}_{i}\in\mathcal{Z}}f_{i}(\bm{x},\bm{z}_{i})$
constitutes a pointwise maximum of convex functions and is therefore convex.
Moreover, as $\mathcal{Z}$ is compact and $f_{i}(\bm{x},\bm{z}_{i})$ is
continuous in $\bm{z}_{i}$ for every $\bm{x}$, $F_{i}(\bm{x})$ is indeed
finite for every $\bm{x}$, i.e.,
$\mathop{\rm{dom}}(F_{i})=\mathbb{R}^{d_{\bm{x}}}$. As any finite-valued
convex function is continuous, we may thus conclude that $F_{i}$ is proper,
closed and convex. The problem dual to (8) can be expressed as

$\max_{\bm{\lambda}\geq\bm{0},\bm{w}}\left\\{-F^{*}_{0}\left(\bm{w}_{0}\right)-\sum_{i\in\mathcal{I}}\lambda_{i}F^{*}_{i}(\bm{w}_{i}/\lambda_{i})\
\bigg{|}\ \sum_{i\in\mathcal{I}_{0}}\bm{w}_{i}=\bm{0}\right\\}.$ (9)

As the feasible region of (P-W) is nonempty and bounded, Theorem 2  _(ii)_
ensures that strong duality holds and (P-W) is solvable, while Proposition 3
implies that (9) admits a strict Slater point $(\bm{\lambda}^{\rm
S},\\{\bm{w}^{\rm S}_{i}\\}_{i})$. It remains to be shown that (9) is
equivalent to the dual best problem (D-B). To this end, we will show that

$\lambda_{i}F_{i}^{*}(\bm{w}_{i}/\lambda_{i})=\inf_{\bm{z}_{i}\in\mathcal{Z}}\lambda_{i}f_{i}^{*1}(\bm{w}_{i}/\lambda_{i},\bm{z}_{i})$
(10)

for any fixed $\lambda_{i}\geq 0$ and $\bm{w}_{i}\in\mathbb{R}^{d_{\bm{x}}}$,
$i\in\mathcal{I}$. Problem (D-B) is then obtained by substituting (10) into
(9), and the assertion follows. To show (10), assume first that
$\lambda_{i}>0$. We then have that

$\displaystyle\lambda_{i}F_{i}^{*}(\bm{w}_{i}/\lambda_{i})$
$\displaystyle=\lambda_{i}\sup_{\bm{x}}\left\\{\bm{x}^{\top}\bm{w}_{i}/\lambda_{i}-\sup_{\bm{z}_{i}\in\mathcal{Z}}f_{i}(\bm{x},\bm{z}_{i})\right\\}$
$\displaystyle=\inf_{\bm{z}_{i}\in\mathcal{Z}}\lambda_{i}\sup_{\bm{x}}\left\\{\bm{x}^{\top}\bm{w}_{i}/\lambda_{i}-f_{i}(\bm{x},\bm{z}_{i})\right\\}$
$\displaystyle=\inf_{\bm{z}_{i}\in\mathcal{Z}}\lambda_{i}f_{i}^{*1}(\bm{w}_{i}/\lambda_{i},\bm{z}_{i}),$

where the second equality follows from Sion’s min-max theorem (Sion, 1958),
which applies because $\mathcal{Z}$ is compact and $f_{i}$ is a convex-concave
saddle function that is continuous in each of its arguments, while the last
equality follows from the definition of the partial conjugate. If
$\lambda_{i}=0$, on the other hand, then we have

$0F_{i}^{*}(\bm{w}_{i}/0)\;\;=\;\;\delta^{*}_{\mathop{\rm{dom}}(F_{i})}(\bm{w}_{i})\;\;=\;\;\delta_{\\{0\\}}(\bm{w}_{i})\;\;=\;\;\inf_{\bm{z}_{i}\in\mathcal{Z}}\delta^{*}_{\mathop{\rm{dom}}(f_{i}(\cdot,\bm{z}_{i}))}(\bm{w}_{i})\;\;=\;\;\inf_{\bm{z}_{i}\in\mathcal{Z}}0f_{i}^{*1}(\bm{w}_{i}/0,\bm{z}_{i}),$

where the first equality follows from the definition of the convex
perspective, while the second equality holds because
$\mathop{\rm{dom}}(F_{i})=\mathbb{R}^{d_{\bm{x}}}$. Similarly, the third
equality holds because
$\mathop{\rm{dom}}(f_{i}(\cdot,\bm{z}_{i}))=\mathbb{R}^{d_{\bm{x}}}$ for every
$\bm{z}_{i}\in\mathbb{R}^{d_{\bm{z}}}$, while the last equality follows from
the definition of the partial convex perspective. Thus, (10) holds for all
$\bm{\lambda}\geq\bm{0}$ and $\bm{w}_{i}\in\mathbb{R}^{d_{\bm{x}}}$,
$i\in\mathcal{I}$.

As for assertion _(iii)_ , assume that (D-B) admits a strict Slater point
$(\\{\bm{w}^{\rm S}_{i},\bm{z}_{i}^{\rm S}\\}_{i},\bm{\lambda}^{\rm S})$. Then
the suprema of (D-B) and (D-B′) coincide due to Proposition 6  _(ii)_.
Moreover, it is easy to verify that $(\\{\bm{w}_{i}^{\rm
S}\\}_{i},{\bm{z}}_{0}^{\rm S},\bm{\lambda}^{\rm
S},\left\\{{\bm{\upsilon}}_{i}^{\rm S}\right\\}_{i})$ is a strict Slater point
for (D-B′) where ${\bm{\upsilon}}_{i}^{\rm S}={\bm{z}}_{i}^{\rm
S}\cdot{\lambda}_{i}^{\rm S}$ for $i\in\mathcal{I}$. Therefore, the problems
(P-W′) and (D-B′) satisfy strong duality, and (P-W′) is solvable due to
Theorem 7  _(ii)_. Finally, the infima of (P-W) and (P-W′) coincide, and (P-W)
is solvable as (P-W′) is solvable due to Proposition 5  _(ii)_ , which applies
since any $\bm{z}_{i}^{\rm S}$ is a Slater point of $\mathcal{Z}$. The claim
then follows. ∎

######  Remark 3 (Strong Duality for (P-W) and (D-B) without a Strict Slater
Point).

Theorem 8 (iii) remains valid if (D-B) admits a Slater point
$(\\{\bm{w}_{i},{\bm{z}}_{i}\\}_{i},\bm{\lambda})$ with $\bm{\lambda}>\bm{0}$
instead of a strict Slater point. Similarly as for Proposition 6 (ii), the
only property of $(\\{\bm{w}_{i},{\bm{z}}_{i}\\}_{i},\bm{\lambda})$ required
in the proof, beyond it being a Slater point, is that $\bm{\lambda}>\bm{0}$.

######  Remark 4 (Heterogeneous Uncertainty Sets).

All results of Section 3 extend in a straightforward manner to situations in
which the objective function and the constraints of problem (P-W) are equipped
with individual uncertainty sets $\mathcal{Z}_{i}$, $i\in\mathcal{I}_{0}$, all
of which satisfy assumption (C).

##  4 Uncertainty Quantification and Distributionally Robust Optimization

An uncertainty quantification problem seeks a distribution that maximizes the
expected value of a Borel measurable disutility function $g(\tilde{\bm{z}})$
over all probability distributions of the random vector $\tilde{\bm{z}}$
within a given set $\mathscr{P}$. As uncertainty about the distribution of a
random object is usually termed ambiguity, we henceforth refer to
$\mathscr{P}$ as the ambiguity set.

$\displaystyle\begin{array}[]{l}\displaystyle\sup_{{\mathbb{P}}\in\mathscr{P}}{\mathbb{E}}_{\mathbb{P}}\left[g(\tilde{\bm{z}})\right]\end{array}$

Primal Uncertainty Quantification Problem

To ensure that the expectation in (4) is defined for all measurable disutility
functions, we set
${\mathbb{E}}_{\mathbb{P}}\left[g(\tilde{\bm{z}})\right]=-\infty$ whenever the
expectation of the positive and negative parts of $g(\tilde{\bm{z}})$ are both
infinite. This convention means that infeasibility dominates unboundedness. In
the first part of this section, we assume that the disutility function
$g:\mathbb{R}^{d_{\bm{z}}}\rightarrow\overline{\mathbb{R}}$ is decision-
independent and representable as a pointwise maximum of $I\in\mathbb{N}$
component functions
$g_{i}:\mathbb{R}^{d_{\bm{z}}}\rightarrow\overline{\mathbb{R}}$ for
$i\in\mathcal{I}$, that is, $g(\bm{z})=\max_{i\in\mathcal{I}}g_{i}(\bm{z})$,
which satisfy the following regularity condition.

  * (G)

The function $-g_{i}$ is proper, closed and convex for each $i\in\mathcal{I}$.

Intuitively, the disutility function $g$ is thus a pointwise maximum of
finitely many concave functions. Note that every piecewise affine continuous
function can be represented in this way, and every continuous function on a
compact set can be approximated arbitrarily closely by a piecewise affine
continuous function. In addition, we assume that the ambiguity set
$\mathscr{P}$ is nonempty and contains all distributions that satisfy
$J\in\mathbb{N}$ moment conditions. Specifically, we assume that

$\mathscr{P}=\left\\{{\mathbb{P}}\in\mathscr{P}_{0}(\mathcal{S})\;\left|\;{\mathbb{E}}_{\mathbb{P}}\left[\bm{h}(\tilde{\bm{z}})\right]\leq\bm{\mu}\right.\right\\},$

where $\mathcal{S}=\\{\bm{z}\in\mathbb{R}^{d_{\bm{z}}}\mid
c_{\ell}(\bm{z})\leq 0\;\;\forall\ell\in\mathcal{L}\\}$ is a nonempty support
set of the same type as the uncertainty set $\mathcal{Z}$ studied in Section 3
that satisfies assumption (C), $\mathscr{P}_{0}(\mathcal{S})$ represents the
family of all distributions supported on $\mathcal{S}$,
$\bm{\mu}\in\mathbb{R}^{J}$ is a vector of moment bounds, and the Borel
measurable moment functions
$h_{j}:\mathbb{R}^{d_{\bm{z}}}\rightarrow\overline{\mathbb{R}}$,
$j\in\mathcal{J}$, satisfy the following regularity condition.

  * (H)

The function $h_{j}$ is proper, closed and convex for each $j\in\mathcal{J}$.

We set ${\mathbb{E}}_{\mathbb{P}}\left[h_{j}(\tilde{\bm{z}})\right]=\infty$
whenever the expectation of the positive and negative parts of
$h_{j}(\tilde{\bm{z}})$ are both infinite. This follows our convention that
infeasibility dominates unboundedness, and it ensures that distributions under
which the positive part of $h_{j}$ has an infinite expectation for some
$j\in\mathcal{J}$ are excluded from the ambiguity set and therefore infeasible
in (4).

Next, define

$\displaystyle\bar{\mathcal{S}}_{i}=\left\\{\bm{z}\in\mathcal{S}\mid\bm{z}\in\mathop{\rm{dom}}(h_{j})\;\;\forall
j\in\mathcal{J},\;\bm{z}\in\mathop{\rm{dom}}(-g_{i})\right\\}$

for every $i\in\mathcal{I}$. Note that $\bar{\mathcal{S}}_{i}$ is convex by
virtue of assumptions (G) and (H) but may fail to be closed. Throughout this
section, we impose the following regularity condition.

  * (S)

The set $\bar{\mathcal{S}}_{i}$ is nonempty for every $i\in\mathcal{I}$.

Note that any distribution ${\mathbb{P}}$ feasible in (4) must be supported on
$\bar{\mathcal{S}}=\cup_{i\in\mathcal{I}}\bar{\mathcal{S}}_{i}$. Indeed,
${\mathbb{P}}$ must be supported on ${\rm dom}(h_{j})$ for every
$j\in\mathcal{J}$ for otherwise ${\mathbb{P}}$ cannot satisfy the moment
constraint
${\mathbb{E}}_{\mathbb{P}}\left[\bm{h}(\tilde{\bm{z}})\right]\leq\bm{\mu}$.
Similarly, ${\mathbb{P}}$ must be supported on ${\rm
dom}(-g)=\cup_{i\in\mathcal{I}}{\rm dom}(-g_{i})$ for otherwise
${\mathbb{E}}_{\mathbb{P}}[g(\tilde{\bm{z}})]=-\infty$. Thus, we will from now
on refer to $\bar{\mathcal{S}}$ as the effective support set. Note that
$\bar{\mathcal{S}}$ is generically non-convex as it constitutes a finite union
of convex sets, and it may fail to be closed.

Assumption (S) may be imposed without much loss of generality. To see this,
note first that if $\bar{\mathcal{S}}_{i}$ is empty for every
$i\in\mathcal{I}$, then the effective support set $\bar{\mathcal{S}}$ is
empty, and the uncertainty quantification problem (4) is infeasible. We may
thus assume that $\bar{\mathcal{S}}$ is nonempty. In this case, if
$\bar{\mathcal{S}}_{i}=\emptyset$ for some $i\in\mathcal{I}$, then
$g_{i}(\bm{z})=-\infty$ for all $\bm{z}\in\bar{\mathcal{S}}$. This observation
implies that the optimal value of (4) does not change if we remove those
components $g_{i}$ from $g$ for which $\bar{\mathcal{S}}_{i}$ is empty.

Note that (4) constitutes a semi-infinite program with finitely many (moment)
constraints and infinitely many decision variables because it optimizes over
all probability distributions supported on the typically uncountable set
$\mathcal{S}$. The semi-infinite maximization problem (4) admits a dual semi-
infinite minimization problem (D-UQ), which involves only finitely many
decision variables but infinitely many constraints parameterized by the
elements of the effective support set $\bar{\mathcal{S}}$.

$\begin{array}[]{l@{\quad}l}\displaystyle\inf&\displaystyle\alpha+\bm{\mu}^{\top}\bm{\beta}\\\
\rm{s.t.}&\displaystyle\sup_{\bm{z}\in\bar{\mathcal{S}}}\left\\{g(\bm{z})-\alpha-\bm{h}(\bm{z})^{\top}\bm{\beta}\right\\}\leq
0\\\ &\alpha\text{ free},\quad\bm{\beta}\geq\bm{0}\end{array}$ (D-UQ)

Dual Uncertainty Quantification Problem

We first show that (4) and (D-UQ) satisfy a weak duality relationship.

######  Theorem 9 (Weak Duality for (4) and (D-UQ)).

The infimum of (D-UQ) is larger or equal to the supremum of (4).

###### Proof.

The statement trivially holds if either of the problems is infeasible. In the
remainder of the proof we may thus assume that both (4) and (D-UQ) are
feasible. Choose now an arbitrary ${\mathbb{P}}$ feasible in (4) and an
arbitrary $(\alpha,\bm{\beta})$ feasible in (D-UQ). As ${\mathbb{P}}$ is
feasible in (4), we have
${\mathbb{E}}_{\mathbb{P}}\left[h_{j}(\tilde{\bm{z}})\right]<+\infty$ for
every $j\in\mathcal{J}$ and
$\mathbb{E}_{{\mathbb{P}}}[g(\tilde{\bm{z}})]>-\infty$. Thanks to our
conventions for infinite integrals, this ensures that
${\mathbb{P}}[\tilde{\bm{z}}\in\mathop{\rm{dom}}(h_{j})]=1$ for every
$j\in\mathcal{J}$ and
${\mathbb{P}}[\tilde{\bm{z}}\in\mathop{\rm{dom}}(-g)]=1$, respectively. This
implies that ${\mathbb{P}}[\tilde{\bm{z}}\in\bar{\mathcal{S}}]=1$. We then
have

${\mathbb{E}}_{\mathbb{P}}\left[g(\tilde{\bm{z}})\right]\;\leq\;\mathbb{E}_{\mathbb{P}}\left[\alpha+\bm{h}(\tilde{\bm{z}})^{\top}\bm{\beta}\right]\;\leq\;\alpha+\bm{\mu}^{\top}\bm{\beta},$

where the first inequality follows from the constraints in (D-UQ) and our
insight that ${\mathbb{P}}[\tilde{\bm{z}}\in\bar{\mathcal{S}}]=1$, and the
second inequality follows from the constraints in (4) and the nonnegativity of
$\bm{\beta}$. Thus, the objective value of $(\alpha,\bm{\beta})$ in (D-UQ) is
non-inferior to the objective value of ${\mathbb{P}}$ in (4). As the primal
and dual feasible solutions ${\mathbb{P}}$ and $(\alpha,\bm{\beta})$ were
chosen arbitrarily, we may conclude that problem (D-UQ) indeed provides an
upper bound on (4). ∎

Next, we consider the following restriction of problem (4).

$\begin{array}[]{l@{\quad}l@{\qquad}l}\sup&\displaystyle\sum_{i\in\mathcal{I}}\lambda_{i}g(\bm{z}_{i})\\\
\rm{s.t.}&\displaystyle\sum_{i\in\mathcal{I}}\lambda_{i}=1\\\
&\displaystyle\sum_{i\in\mathcal{I}}\lambda_{i}\bm{h}(\bm{z}_{i})\leq\bm{\mu}\\\
&\bm{z}_{i}\in\bar{\mathcal{S}}&\forall i\in\mathcal{I}\\\
&\bm{\lambda}\geq\bm{0}\end{array}$ (FR)

Finite Reduction Problem

Assumption (G) implies that $g(\bm{z}_{i})<+\infty$ for all
$\bm{z}_{i}\in\mathbb{R}^{d_{\bm{z}}}$, and assumption (H) implies that
$h_{j}(\bm{z}_{i})>-\infty$ for all $\bm{z}_{i}\in\mathbb{R}^{d_{\bm{z}}}$ and
$j\in\mathcal{J}$. The restriction $\bm{z}_{i}\in\bar{\mathcal{S}}$, which
further imposes that $h_{j}(\bm{z}_{i})<+\infty$ and $g(\bm{z}_{i})>-\infty$,
thus ensures that the products $\lambda_{i}g(\bm{z}_{i})$ and
$\lambda_{i}\bm{h}(\bm{z}_{i})$ are well-defined even if $\lambda_{i}=0$.
Problem (FR) has intuitive appeal because it evaluates the worst-case expected
disutility across all discrete $I$-point distributions
${\mathbb{P}}\in\mathscr{P}$ with discretization points $\bm{z}_{i}$
restricted to $\bar{\mathcal{S}}$ and corresponding probabilities
$\lambda_{i}$ for $i\in\mathcal{I}$. Therefore, we henceforth refer to (FR) as
a finite reduction of (4). As (FR) constitutes a restriction of (4), it
provides a lower bound on (4) and, by virtue of Theorem 9, on (D-UQ).

We now show that (D-UQ) and (FR) are instances of the primal worst and dual
best robust optimization problems (P-W) and (D-B) studied in Section 3,
respectively, which we will call _ambiguous_ primal worst, (AP-W), and
_ambiguous_ dual best, (AD-B). While (AP-W) and (AD-B) appear to be difficult
to solve, they again admit finite convex reformulations (AP-W′) and (AD-B′)
that are instances of the problems (P-W′) and (D-B′) in Section 3,
respectively. We can then use the results of Section 3 to derive conditions of
strong duality between (AP-W) and (AD-B), which immediately imply equivalence
between the uncertainty quantification problems (4) and (D-UQ) as well as the
finite reduction (FR). These relationships are summarized in Figure 2.

$\inf\eqref{eq:duq}$$\sup\eqref{eq:puq}$$\sup\eqref{eq:fr}$$\inf\eqref{eq:apw}$
$\inf\eqref{eq:apw-cvx}$$\sup\eqref{eq:adb-cvx}$$\sup\eqref{eq:adb}$Theorem 9

Proposition 10

Proposition 11

Proposition 5  _(ii)_ Proposition 5  _(i)_ Theorem 12  _(i)_ ,  _(ii)_ Theorem
7  _(i)_ Proposition 6  _(ii)_ Proposition 6  _(i)_ Figure 2: Illustration of
the relationships among (4), (D-UQ), (FR), (AP-W), (AD-B), (AP-W′) and
(AD-B′). The optimal values of these problems are non-increasing in the
directions of the arcs. Dashed arcs represent universal inequalities, while
the solid arcs represent inequalities that hold under regularity conditions.

Although the dual uncertainty quantification problem (D-UQ) appears to be an
instance of the primal worst problem (P-W), the ‘uncertainty set’
$\bar{\mathcal{S}}$ fails to satisfy the assumption (C) from Section 3 for two
reasons. Firstly, $\bar{\mathcal{S}}$ is generally non-convex as it
constitutes a union of $I$ convex sets corresponding to the $I$ concave pieces
of the disutility function $g$. Secondly, the domains of $h_{j}$ and $-g$ may
not be closed, in which case $\bar{\mathcal{S}}$ cannot be represented as an
instance of $\mathcal{Z}$ that satisfies assumption (C), which is closed by
construction. In addition, the constraint function in (D-UQ) violates the
assumption (RF) since $g$ is not concave in $\bm{z}$. We simultaneously
circumvent all of these issues through the introduction of separate augmented
support sets
$\mathcal{U}_{0}=\mathbb{R}^{d_{\bm{z}}}\times\mathbb{R}^{J}\times\mathbb{R}$
and

$\displaystyle\mathcal{U}_{i}$
$\displaystyle=\\{(\bm{z},\bm{u},t)\in\mathbb{R}^{d_{\bm{z}}}\times\mathbb{R}^{J}\times\mathbb{R}\mid
c_{\ell}(\bm{z})\leq
0\;\;\forall\ell\in\mathcal{L},\;\bm{h}(\bm{z})\leq\bm{u},\;g_{i}(\bm{z})\geq
t\\}\quad\forall i\in\mathcal{I}.$

We can then define the ambiguous primal worst problem as follows.

$\begin{array}[]{l@{\quad}l@{\qquad}l}\inf&\displaystyle\alpha+\bm{\mu}^{\top}\bm{\beta}\\\
\rm{s.t.}&\displaystyle\sup_{(\bm{z}_{i},\bm{u}_{i},t_{i})\in\mathcal{U}_{i}}\left\\{t_{i}-\alpha-\bm{u}_{i}^{\top}\bm{\beta}\right\\}\leq
0&\forall i\in\mathcal{I}\\\ &\alpha\text{
free},\quad\bm{\beta}\geq\bm{0}\end{array}$ (AP-W)

Ambiguous Primal Worst Problem

The ambiguous primal worst problem (AP-W) can be interpreted as an instance of
the primal worst problem (P-W) with the objective function

$f_{0}((\alpha,\bm{\beta}),(\bm{z}_{0},\bm{u}_{0},t_{0}))\;=\;\alpha+\bm{\mu}^{\top}\bm{\beta}+\delta_{\mathbb{R}_{+}^{J}}(\bm{\beta})$
(11a) and the constraint functions
$f_{i}((\alpha,\bm{\beta}),(\bm{z}_{i},\bm{u}_{i},t_{i}))\;=\;t_{i}-\alpha-\bm{u}_{i}^{\top}\bm{\beta}$
(11b)

for $i\in\mathcal{I}$, where the optimization variables $(\alpha,\bm{\beta})$
correspond to $\bm{x}$, and the uncertain parameters
$(\bm{z}_{i},\bm{u}_{i},t_{i})\in\mathcal{U}_{i}$ correspond to
$\bm{z}_{i}\in\mathcal{Z}$ for every $i\in\mathcal{I}_{0}$. Note that the
objective function (11a) of (AP-W) is proper, convex and closed in the
decision variables and constant in the uncertain parameters, while the
constraint functions (11b) of (AP-W) are bi-affine in the decision variables
and the uncertain parameters. Thus, problem (AP-W) satisfies
assumption222Strictly speaking, $f_{0}$ does not satisfy assumption (RF)
because $-f_{0}$ is not proper in the uncertain parameters for
$\bm{\beta}\not\geq\bm{0}$. Since $f_{0}$ is deterministic, however,
maximizing $f_{0}$ over the uncertain parameters will not yield a pathological
worst-case objective function. The lack of properness of $-f_{0}$ in this
special case is therefore unproblematic. Details are omitted for brevity.
(RF). In addition, as the support set $\mathcal{S}$ satisfies assumption (C)
and as the disutility function $g_{i}$ and the moment functions $h_{j}$,
$j\in\mathcal{J}$, satisfy the assumptions (G) and (H), respectively, the
functions defining the augmented support set $\mathcal{U}_{i}$ all satisfy
assumption (C) for every $i\in\mathcal{I}$. Although the effective support set
$\bar{\mathcal{S}}$ in (D-UQ) and (4) fails to satisfy assumption (C), its
constituent sets $\bar{\mathcal{S}}_{i}$, which are nonempty by assumption
(S), are the projections of $\mathcal{U}_{i}$ onto $\mathbb{R}^{d_{\bm{z}}}$
for all $i\in\mathcal{I}$:

$\bm{z}_{i}\in\bar{\mathcal{S}}_{i}\quad\iff\quad\exists\bm{u}_{i}\in\mathbb{R}^{J}\text{
and }t_{i}\in\mathbb{R}\text{ such that
}(\bm{z}_{i},\bm{u}_{i},t_{i})\in\mathcal{U}_{i}.$ (12)

Indeed, $\bm{z}_{i}\in\bar{\mathcal{S}}_{i}$ implies that
$(\bm{z}_{i},\bm{h}(\bm{z}_{i}),g(\bm{z}_{i}))\in\mathcal{U}_{i}$, and the
reverse implication holds since the condition on the right-hand side implies
that $h_{j}(\bm{z}_{i})<+\infty$ for all $j\in\mathcal{J}$ as well as
$g_{i}(\bm{z}_{i})>-\infty$.

Using the equivalence (12), we can now show that problem (D-UQ) is equivalent
to (AP-W).

######  Proposition 10 (Equivalence of (D-UQ) and (AP-W)).

The infima of (D-UQ) and (AP-W) coincide, and (D-UQ) is solvable if and only
if (AP-W) is solvable.

###### Proof.

We show that the robust constraint in (D-UQ) has the same feasible region as
the $I$ robust constraints in (AP-W). As
$g(\bm{z})=\max_{i\in\mathcal{I}}g_{i}(\bm{z})$, the robust constraint in
(D-UQ) is equivalent to

$\displaystyle\quad\max_{i\in\mathcal{I}}\sup_{\bm{z}_{i}\in\bar{\mathcal{S}}}\left\\{g_{i}(\bm{z}_{i})-\alpha-\bm{h}(\bm{z}_{i})^{\top}\bm{\beta}\right\\}\leq
0\quad$
$\displaystyle\iff\quad\max_{i\in\mathcal{I}}\sup_{\bm{z}_{i}\in\bar{\mathcal{S}}_{i}}\left\\{g_{i}(\bm{z}_{i})-\alpha-\bm{h}(\bm{z}_{i})^{\top}\bm{\beta}\right\\}\leq
0$
$\displaystyle\iff\quad\max_{i\in\mathcal{I}}\sup_{(\bm{z}_{i},\bm{u}_{i},t_{i})\in\mathcal{U}_{i}}\left\\{t_{i}-\alpha-\bm{u}_{i}^{\top}\bm{\beta}\right\\}\leq
0,$

where the first equivalence holds because
$\bar{\mathcal{S}}_{i}\subseteq\bar{\mathcal{S}}$ and because
$g_{i}(\bm{z}_{i})=-\infty$ for all $\bm{z}\notin\bar{\mathcal{S}}_{i}$. The
second equivalence follows from (12) and the fact that
$\bm{u}_{i}=\bm{h}(\bm{z}_{i})$ and $t_{i}=g_{i}(\bm{z}_{i})$ maximize the
inner supremum for any fixed admissible $\bm{z}_{i}$, $i\in\mathcal{I}$. The
last inequality in the above expression is manifestly equivalent to the $I$
robust constraints in (AP-W). ∎

The partial conjugates of the objective and constraint functions (11) with
respect to the decision variables ($\alpha,\bm{\beta}$) are given by

$\displaystyle
f_{0}^{*1}((v_{0},\bm{w}_{0}),(\bm{z}_{0},\bm{u}_{0},t_{0}))=\sup_{\alpha,\bm{\beta}\in\mathbb{R}_{+}^{J}}\left\\{v_{0}\alpha+\bm{w}_{0}^{\top}\bm{\beta}-\alpha-\bm{\mu}^{\top}\bm{\beta}\right\\}=\begin{cases}0&\text{if
}v_{0}=1,\bm{w}_{0}\leq\bm{\mu}\\\ +\infty&\text{otherwise}\end{cases}$

and

$\displaystyle
f_{i}^{*1}\left((v_{i},\bm{w}_{i}),(\bm{z}_{i},\bm{u}_{i},t_{i})\right)=\sup_{\alpha,\bm{\beta}}\left\\{v_{i}\alpha+\bm{w}_{i}^{\top}\bm{\beta}-t_{i}+\alpha+\bm{u}_{i}^{\top}\bm{\beta}\right\\}=\begin{cases}-t_{i}&\text{if
}v_{i}=-1,\bm{w}_{i}=-\bm{u}_{i}\\\ +\infty&\text{otherwise}\end{cases}$

for every $i\in\mathcal{I}$. Substituting these expressions into (D-B) and
eliminating the redundant decision variables $v_{i}$ and $\bm{w}_{i}$,
$i\in\mathcal{I}_{0}$, yields the following optimization problem, which we
will henceforth refer to as the ambiguous dual best problem.

$\begin{array}[]{l@{\quad}l@{\qquad}l}\sup&\displaystyle\sum_{i\in\mathcal{I}}\lambda_{i}t_{i}\\\
\rm{s.t.}&\displaystyle\sum_{i\in\mathcal{I}}\lambda_{i}=1\\\
&\displaystyle\sum_{i\in\mathcal{I}}\lambda_{i}\bm{u}_{i}\leq\bm{\mu}\\\
&(\bm{z}_{i},\bm{u}_{i},t_{i})\in\mathcal{U}_{i}&\forall i\in\mathcal{I}\\\
&\bm{\lambda}\geq\bm{0}\end{array}$ (AD-B)

Ambiguous Dual Best Problem

In the following, we show that (AD-B) is equivalent to (FR).

######  Proposition 11 (Equivalence of (FR) and (AD-B)).

The suprema of (FR) and (AD-B) coincide, and (FR) is solvable if and only if
(AD-B) is solvable.

###### Proof.

As $\bar{\mathcal{S}}_{i}$ represents the projection of $\mathcal{U}_{i}$ onto
$\mathbb{R}^{d_{\bm{z}}}$, problem (AD-B) is equivalent to

$\displaystyle\sup$
$\displaystyle\quad\sum_{i\in\mathcal{I}}\lambda_{i}g_{i}(\bm{z}_{i})$ (13)
$\displaystyle\rm{s.t.}$
$\displaystyle\quad\sum_{i\in\mathcal{I}}\lambda_{i}=1$
$\displaystyle\quad\sum_{i\in\mathcal{I}}\lambda_{i}\bm{h}(\bm{z}_{i})\leq\bm{\mu}$
$\displaystyle\quad\bm{z}_{i}\in\bar{\mathcal{S}}_{i}$ $\displaystyle\forall
i\in\mathcal{I}$ $\displaystyle\quad\bm{\lambda}\geq\bm{0}.$

Indeed, the equivalence between (AD-B) and (13) holds due to (12), which
ensures $\bm{z}_{i}\in\bar{\mathcal{S}}_{i}$ if and only if there exist
$\bm{u}_{i}\in\mathbb{R}^{J}$ and $t_{i}\in\mathbb{R}$ with
$(\bm{z}_{i},\bm{u}_{i},t_{i})\in\mathcal{U}_{i}$, and because for any fixed
$(\\{\bm{z}_{i}\\}_{i},\bm{\lambda})$ feasible in (13) it is optimal to set
$\bm{u}_{i}=\bm{h}(\bm{z}_{i})$ and $t_{i}=g_{i}(\bm{z}_{i})$ for all
$i\in\mathcal{I}$.

In the remainder of the proof we will show that (13) is equivalent to (FR). As
$g(\bm{z}_{i})\geq g_{i}(\bm{z}_{i})$ for all
$\bm{z}_{i}\in\bar{\mathcal{S}}_{i}$ and as
$\bar{\mathcal{S}_{i}}\subseteq\bar{\mathcal{S}}$, it is clear that the
optimal value of (FR) provides an upper bound on (13). To prove the converse
inequality, select any $(\\{\bm{z}_{i}\\}_{i},\bm{\lambda})$ feasible in (FR),
and define

$\hat{\mathcal{S}}_{i}=\\{\bm{z}\in\bar{\mathcal{S}}_{i}\ |\ g_{i}(\bm{z})\geq
g_{i^{\prime}}(\bm{z})\;\;\forall
i^{\prime}\in\mathcal{I}\,:\,i^{\prime}<i,\;g_{i}(\bm{z})>g_{i^{\prime}}(\bm{z})\;\;\forall
i^{\prime}\in\mathcal{I}\,:\,i^{\prime}>i\\}$

for all $i\in\mathcal{I}$. Note that these sets form a partition of
$\bar{\mathcal{S}}$. By construction, we have
$g_{i}(\bm{z})=g(\bm{z})>-\infty$ for all $\bm{z}\in\hat{\mathcal{S}}_{i}$.
Next, define
$\mathcal{I}_{i}=\\{i^{\prime}\in\mathcal{I}\mid\bm{z}_{i^{\prime}}\in\hat{\mathcal{S}_{i}}\\}$,
and construct $(\\{\bm{z}^{\prime}_{i}\\}_{i},\bm{\lambda}^{\prime})$ by
setting
$\lambda^{\prime}_{i}=\sum_{i^{\prime}\in\mathcal{I}_{i}}\lambda_{i^{\prime}}$
and
$\bm{z}^{\prime}_{i}=\frac{1}{\lambda^{\prime}_{i}}\sum_{i^{\prime}\in\mathcal{I}_{i}}\lambda_{i^{\prime}}\bm{z}_{i^{\prime}}$
if $\lambda^{\prime}_{i}>0$. Otherwise, if $\lambda^{\prime}_{i}=0$, set
$\bm{z}_{i}^{\prime}$ to an arbitrary point in $\bar{\mathcal{S}}_{i}$, which
is always possible because $\bar{\mathcal{S}}_{i}$ is nonempty due to
assumption (S). As both $-g_{i}$ and $\bm{h}$ are proper, closed and convex
thanks to assumptions (G) and (H), Jensen’s inequality implies that

$\sum_{i^{\prime}\in\mathcal{I}_{i}}\lambda_{i^{\prime}}g(\bm{z}_{i^{\prime}})\;\leq\;\lambda^{\prime}_{i}g_{i}(\bm{z}_{i}^{\prime})\quad\text{and}\quad\lambda^{\prime}_{i}\bm{h}(\bm{z}_{i}^{\prime})\;\leq\;\sum_{i^{\prime}\in\mathcal{I}_{i}}\lambda_{i^{\prime}}\bm{h}(\bm{z}_{i^{\prime}})\;\leq\;\lambda^{\prime}_{i}\bm{\mu}\qquad\forall
i\in\mathcal{I},$

that is, $(\bm{\lambda}^{\prime},\\{\bm{z}^{\prime}_{i}\\}_{i})$ is feasible
in (13) and its objective value in (13) is larger or equal to that of
$(\bm{\lambda},\\{\bm{z}_{i}\\}_{i})$ in (FR). Therefore, the optimal value of
(FR) further provides a lower bound on the optimal value of (13). The above
arguments also reveal that one can construct a feasible solution for (FR) from
a feasible solution of (AD-B) and vice versa. Hence, the claim follows. ∎

In Section 3 we have seen that the seemingly intractable primal worst and dual
best optimization problems (P-W) and (D-B) admit exact reformulations as the
finite convex programs (P-W′) and (D-B′), respectively. If we interpret (AP-W)
as an instance of (P-W) as explained above, then the corresponding instance of
(P-W′) can be constructed as follows. First, we evaluate the partial
conjugates of the objective and constraint functions (11) with respect to the
uncertain parameters and evaluate the conjugates of the constraint functions
defining the uncertain sets. Substituting these (partial and global)
conjugates into (P-W′) and eliminating all the redundant variables with fixed
values then yields the following convex program.

$\begin{array}[]{l@{\quad}l}\inf&\displaystyle\alpha+\bm{\mu}^{\top}\bm{\beta}\\\
\rm{s.t.}&\displaystyle(-g_{i})^{*}\left(\bm{y}^{(0)}_{i}\right)+\sum_{j\in\mathcal{J}}\beta_{j}h_{j}^{*}\left(\frac{\bm{y}^{(1)}_{ij}}{\beta_{j}}\right)+\sum_{\ell\in\mathcal{L}}\nu_{i\ell}c_{\ell}^{*}\left(\frac{\bm{y}^{(2)}_{i\ell}}{\nu_{i\ell}}\right)\leq\alpha\quad\forall
i\in\mathcal{I}\\\
&\displaystyle\bm{y}^{(0)}_{i}+\sum_{j\in\mathcal{J}}\bm{y}^{(1)}_{ij}+\sum_{\ell\in\mathcal{L}}\bm{y}^{(2)}_{i\ell}=\bm{0}\qquad\qquad\qquad\qquad\qquad\quad\quad\
\ \ \forall i\in\mathcal{I}\\\ &\alpha\textnormal{
free},\quad\bm{\beta}\geq\bm{0}\\\
&\bm{y}^{(0)}_{i},\bm{y}^{(1)}_{ij},\bm{y}^{(2)}_{i\ell}\textnormal{
free},\quad\nu_{i\ell}\geq 0\qquad\qquad\qquad\forall i\in\mathcal{I},\
\forall j\in\mathcal{J},\ \forall\ell\in\mathcal{L}\end{array}$ (AP-W′)

Reformulated Ambiguous Primal Worst Problem

The derivation of (AP-W′) is tedious but completely mechanical and requires no
new ideas. Details are omitted for brevity. Similarly, substituting the
objective and constraint functions (11) as well as the constraint functions
defining $\mathcal{U}_{i}$ into (D-B′) yields the following convex program.

$\begin{array}[]{l@{\quad}l@{\qquad}l}\sup&\displaystyle\sum_{i\in\mathcal{I}}\tau_{i}\\\
\rm{s.t.}&\displaystyle\sum_{i\in\mathcal{I}}\lambda_{i}=1\\\
&\displaystyle\sum_{i\in\mathcal{I}}\bm{\omega}_{i}\leq\bm{\mu}\\\
&\lambda_{i}c_{\ell}(\bm{\upsilon}_{i}/\lambda_{i})\leq 0&\forall
i\in\mathcal{I},\ \forall\ell\in\mathcal{L}\\\
&\lambda_{i}\bm{h}(\bm{\upsilon}_{i}/\lambda_{i})\leq\bm{\omega}_{i},\quad\lambda_{i}g_{i}(\bm{\upsilon}_{i}/\lambda_{i})\geq\tau_{i}&\forall
i\in\mathcal{I}\\\ &\bm{\tau}\text{
free},\quad\bm{\lambda}\geq\bm{0},\quad\bm{\omega}_{i},\bm{\upsilon}_{i}\text{
free}&\forall i\in\mathcal{I}\\\ \end{array}$ (AD-B′)

Reformulated Ambiguous Dual Best Problem

As (AP-W), (AD-B), (AP-W′) and (AD-B′) represent instances of (P-W), (D-B),
(P-W′) and (D-B′), respectively, all results of Section 3 are applicable and
offer conditions under which these problems share the same optimal values or
solvability characteristics.

We now establish minimal conditions for strong duality between the finite
convex programs (AP-W′) and (AD-B′). These conditions will also be sufficient
for strong duality between the semi-infinite programs (4) and (D-UQ). We
emphasize that our duality results follow from first principles of convex
analysis and do not rely on the elaborate machinery of abstract semi-infinite
duality theory such as Isii (1962), Anderson and Nash (1987) and Shapiro
(2001).

######  Theorem 12 (Strong Duality for (4) and (D-UQ)).

The following statements hold.

  1. (i)

If (AD-B′) admits a Slater point with $\bm{\lambda}>\bm{0}$, then (AP-W′),
(AP-W), (D-UQ), (4), (FR), (AD-B) and (AD-B′) all have the same optimal value
and (AP-W′) is solvable. Also, if
$(\alpha^{\star},\bm{\beta}^{\star},\\{\bm{y}_{i}^{(0)\star}\\}_{i},\\{\bm{y}_{ij}^{(1)\star}\\}_{ij},\\{\bm{y}_{i\ell}^{(2)\star},\nu_{i\ell}^{\star}\\}_{i\ell})$
solves (AP-W′), then $(\alpha^{\star},\bm{\beta}^{\star})$ solves (D-UQ).

  2. (ii)

If (AP-W′) admits a Slater point and $\mathcal{S}$ is bounded, then (AP-W′),
(AP-W), (D-UQ), (4), (FR), (AD-B) and (AD-B′) all have the same optimal value
and (AD-B′) is solvable. Also, if
$(\bm{\tau}^{\star},\bm{\lambda}^{\star},\\{\bm{\omega}^{\star}_{i},\bm{v}^{\star}_{i}\\}_{i})$
solves (AD-B′), then the discrete distribution that assigns probability
$\lambda^{\star}_{i}$ to the point $\bm{v}_{i}^{\star}/\lambda_{i}^{\star}$
for every $i\in\mathcal{I}$ with $\lambda_{i}^{\star}>0$ solves (4).

The equivalence of (AP-W′), (AP-W), (D-UQ), (4), (FR), (AD-B) and (AD-B′) can
also be shown if (AD-B′) admits a Slater point and $\mathcal{S}$ is bounded or
if (AP-W′) admits a Slater point and (AD-B′) has a feasible solution with
$\bm{\lambda}>\bm{0}$. However, these cases are less relevant in practice.

###### Proof of Theorem 12.

In the absence of any regularity conditions, we have

$\inf\eqref{eq:apw-
cvx}\;\geq\;\inf\eqref{eq:apw}\;=\;\inf\eqref{eq:duq}\;\geq\;\sup\eqref{eq:puq}\;\geq\;\sup\eqref{eq:fr}\;=\;\sup\eqref{eq:adb}$
(14)

where the two equalities follow from Propositions 10 and 11, respectively,
while the first inequality exploits Proposition 5  _(i)_ , the second equality
follows from the weak duality result established in Theorem 9, and the second
inequality holds trivially because (FR) constitutes a restriction of (4).
Proposition 6  _(i)_ further implies that
$\sup\eqref{eq:adb}\leq\sup\eqref{eq:adb-cvx}$. The relationships among the
different problems are also summarized in Figure 2. It remains to be shown
that either of the conditions in assertions  _(i)_ or  _(ii)_ imply the
equivalence of (AD-B) and (AD-B′) as well as strong duality between (AP-W′)
and (AD-B′).

As for assertion  _(i)_ , note first that the Slater point for (AD-B) can be
used to construct a Slater point for (AD-B′) with $\bm{\lambda}>\bm{0}$. The
suprema of (AD-B) and (AD-B′) then coincide thanks to Proposition 6  _(ii)_
and Remark 2. Theorem 7  _(ii)_ further guarantees that the infimum of (AP-W′)
coincides with the supremum of (AD-B′) and that (AP-W′) is solvable. This
allows us to conclude that all problems in (14) have the same optimal value as
(AD-B′). As (AD-B) admits a Slater point, finally, it is clear that the
augmented support set $\mathcal{U}_{i}$ admits a Slater point for every
$i\in\mathcal{I}$, and therefore Propositions 5  _(ii)_ and 10 ensure that if
$(\alpha^{\star},\bm{\beta}^{\star},\\{\bm{y}_{i}^{(0)\star}\\}_{i},\\{\bm{y}_{ij}^{(1)\star}\\}_{ij},\\{\bm{y}_{i\ell}^{(2)\star},\nu_{i\ell}^{\star}\\}_{i\ell})$
solves (AP-W′), then $(\alpha^{\star},\bm{\beta}^{\star})$ solves (D-UQ).

As for assertion  _(ii)_ , note first that the infimum of (AP-W′) coincides
with the supremum of (AD-B′) and that (AD-B′) is solvable. This is an
immediate consequence of Theorem 7  _(ii)_ , which applies because (AP-W′)
admits a Slater point. To show that all problems in (14) have the same optimal
value, it thus remains to prove that the suprema of (AD-B) and (AD-B′)
coincide. To this end, fix any optimal solution
$(\bm{\tau}^{\star},\bm{\lambda}^{\star},\\{\bm{\omega}^{\star}_{i},\bm{v}^{\star}_{i}\\}_{i})$
of (AD-B′), and assume without loss of generality that
$\bm{\omega}^{\star}_{i}=\lambda^{\star}_{i}\bm{h}(\bm{v}^{\star}_{i}/\lambda^{\star}_{i})$
and
$\tau^{\star}_{i}=\lambda^{\star}_{i}g_{i}(\bm{v}^{\star}_{i}/\lambda^{\star}_{i})$
for all $i\in\mathcal{I}$. We now show that this solution gives rise to an
optimal solution
$(\\{\bm{z}^{\star}_{i},\bm{u}^{\star}_{i},t^{\star}_{i}\\}_{i},\bm{\lambda}^{\star})$
of (AD-B) that attains the same optimal value. To this end, set
$\bm{z}^{\star}_{i}=\bm{v}^{\star}_{i}/\lambda^{\star}_{i}$ if
$\lambda^{\star}_{i}>0$, and let $\bm{z}^{\star}_{i}$ be an arbitrary point in
$\bar{\mathcal{S}}_{i}$ otherwise, $i\in\mathcal{I}$. If there is
$i\in\mathcal{I}$ with $\lambda^{\star}_{i}=0$, then Lemma B.7  _(i)_ implies
that $\bm{v}^{\star}_{i}$ is a recession direction for $\mathcal{S}$. As
$\mathcal{S}$ is nonempty and bounded, this in turn implies that
$\bm{v}^{\star}_{i}=\bm{0}$. Using the same reasoning as in the proof of
Proposition 6  _(i)_ , one can show that
$\lambda^{\star}_{i}c_{\ell}(\bm{v}^{\star}_{i}/\lambda^{\star}_{i})=\lambda^{\star}_{i}c_{\ell}(\bm{z}^{\star}_{i})$,
$\lambda^{\star}_{i}\bm{h}(\bm{v}^{\star}_{i}/\lambda^{\star}_{i})=\lambda^{\star}_{i}\bm{h}(\bm{z}^{\star}_{i})$
and
$\lambda^{\star}_{i}g_{i}(\bm{v}^{\star}_{i}/\lambda^{\star}_{i})=\lambda^{\star}_{i}g_{i}(\bm{z}^{\star}_{i})$
for all $i\in\mathcal{I}$ and $\ell\in\mathcal{L}$. Setting
$\bm{u}^{\star}_{i}=\bm{h}(\bm{z}^{\star}_{i})$ and
$t^{\star}_{i}=g_{i}(\bm{z}^{\star}_{i})$ for all $i\in\mathcal{I}$, one
readily verifies that
$(\\{\bm{z}^{\star}_{i},\bm{u}^{\star}_{i},t^{\star}_{i}\\}_{i},\bm{\lambda}^{\star})$
is feasible in (AD-B). Moreover, since
$\sum_{i\in\mathcal{I}}\tau^{\star}_{i}=\sum_{i\in\mathcal{I}}\lambda^{\star}_{i}t^{\star}_{i}$,
this solution attains the same objective value as
$(\bm{\tau}^{\star},\bm{\lambda}^{\star},\\{\bm{\omega}^{\star}_{i},\bm{v}^{\star}_{i}\\}_{i})$
in (AD-B′). Since (AD-B) bounds (AD-B′) from below by Proposition 6  _(i)_ ,
$(\\{\bm{z}^{\star}_{i},\bm{u}^{\star}_{i},t^{\star}_{i}\\}_{i},\bm{\lambda}^{\star})$
must be optimal in (AD-B). The proof of Proposition 11 further implies that
$(\\{\bm{z}^{\star}_{i}\\}_{i},\bm{\lambda}^{\star})$ solves (FR), which is a
restriction of (4). As all problems in (14) share the same optimal value, the
discrete distribution that assigns probability $\lambda^{\star}_{i}$ to the
point $\bm{z}^{\star}_{i}=\bm{v}_{i}^{\star}/\lambda_{i}^{\star}$ for all
$i\in\mathcal{I}$ with $\lambda_{i}^{\star}>0$ indeed solves (4). ∎

######  Remark 5 (Relation to Semi-Infinite Duality Theory).

Strong duality between the primal and dual uncertainty quantification problems
(4) and (D-UQ) can also be established by appealing to the classical duality
theory for generalized moment problems. In order to describe the sufficient
condition that is most frequently used, we denote by
$\mathcal{M}_{+}(\bar{\mathcal{S}})$ the cone of all non-negative Borel
measures supported on $\bar{\mathcal{S}}$ under which the functions $g$ and
$\bm{h}$ are integrable, and we define

$\mathcal{C}=\left\\{\int_{\bar{\mathcal{S}}}(1,\bm{h}(\bm{z}))\,\lambda({\rm
d}\bm{z})\;\Big{|}\;\lambda\in\mathcal{M}_{+}(\bar{\mathcal{S}})\right\\}+\left(\\{0\\}\times\mathbb{R}^{J}_{+}\right),$

which constitutes a Minkowski sum of two convex cones and is thus itself a
convex cone. By virtue of Proposition 3.4 by Shapiro (2001), the supremum of
(4) coincides with the infimum of (D-UQ) if the vector $(1,\bm{\mu})$ resides
in the interior of $\mathcal{C}$. This condition is more general because it
extends to arbitrary measurable functions $g$ and $\bm{h}$, but it is not
always easy to check. Theorem 12 holds under more restrictive conditions as it
relies on the convexity properties of the functions $g_{i}$, $\bm{h}$ and
$c_{\ell}$, but the existence of a Slater point is usually straightforward to
verify by inspection. In addition, Slater points for the finite convex
programs (AP-W′) and (AD-B′) can also be found numerically by solving suitable
auxiliary convex optimization problems. Finally and most importantly, the
conditions of Theorem 12 not only ensure strong duality between the semi-
infinite optimization problems (4) and (D-UQ) but also guarantee that these
semi-infinite optimization problems are equivalent to finite convex programs.
In contrast, the standard approach to distributionally robust optimization
imposes separate regularity conditions to ensure strong duality between the
semi-infinite optimization problems and to ensure that these problems admit
finite convex reformulations.

The following two propositions provide sufficient conditions for the
assumptions of Theorem 12 that may be easier to interpret. The first such
condition relies on the notion of a Slater distribution.

######  Definition 7 (Slater Distribution).

The distribution ${\mathbb{P}}^{\rm S}\in\mathscr{P}_{0}(\bar{\mathcal{S}})$
is a Slater distribution for the uncertainty quantification problem (4) if (i)
${\mathbb{P}}^{\rm S}$ is absolutely continuous on $\mathbb{R}^{d_{\bm{z}}}$,
(ii) ${\mathbb{P}}^{\rm
S}\left[\tilde{\bm{z}}\in\bar{\mathcal{S}}_{i}\right]>0$ for all
$i\in\mathcal{I}$, (iii) $\mathbb{E}_{{\mathbb{P}}^{\rm
S}}[h_{j}(\tilde{\bm{z}})]\leq\mu_{j}$ for all $j\in\mathcal{J}$, with the
inequality being strict if $h_{j}$ is nonlinear, and (iv)
$\mathbb{E}_{{\mathbb{P}}^{\rm S}}[c_{\ell}(\tilde{\bm{z}})]<0$ for all
$\ell\in\mathcal{L}$ where $c_{\ell}$ is nonlinear.

######  Proposition 13 (Slater Points for (AD-B′)).

If the uncertainty quantification problem (4) admits a Slater distribution,
then the convex program (AD-B′) admits a Slater point with
$\bm{\lambda}>\bm{0}$.

###### Proof.

Denote by ${\mathbb{P}}^{\rm S}$ the Slater distribution of (4) that exists by
assumption. We will first argue that for each $i\in\mathcal{I}$ there exists a
probability $\lambda_{i}>0$ and a probability measure ${\mathbb{P}}^{\rm
S}_{i}$ supported on $\bar{\mathcal{S}}_{i}$ such that ${\mathbb{P}}^{\rm
S}=\sum_{i\in\mathcal{I}}\lambda_{i}{\mathbb{P}}^{\rm S}_{i}$. To see this, we
define for every index set $\mathcal{I}^{\prime}\subseteq\mathcal{I}$ the non-
negative Borel measure $\rho_{\mathcal{I}^{\prime}}$ obtained by restricting
${\mathbb{P}}^{\rm S}$ to
$\bar{\mathcal{S}}_{\mathcal{I}^{\prime}}=\\{\bm{z}\in\bar{\mathcal{S}}\mid\bm{z}\in\bar{\mathcal{S}}_{i^{\prime}}~{}\forall
i^{\prime}\in\mathcal{I}^{\prime},~{}\bm{z}\notin\bar{\mathcal{S}}_{i^{\prime}}~{}\forall
i^{\prime}\in\mathcal{I}\backslash\mathcal{I}^{\prime}\\}$, that is, we set
$\rho_{\mathcal{I}^{\prime}}[\mathcal{B}]={\mathbb{P}}^{\rm
S}[\tilde{\bm{z}}\in\mathcal{B}\cap\bar{\mathcal{S}}_{\mathcal{I}^{\prime}}]$
for every Borel set $\mathcal{B}\subseteq\mathbb{R}^{d_{\bm{z}}}$. By
construction, we thus have ${\mathbb{P}}^{\rm
S}=\sum_{\mathcal{I}^{\prime}\subseteq\mathcal{I}}\rho_{\mathcal{I}^{\prime}}$.
Similarly, one readily verifies that
$\sum_{\mathcal{I}^{\prime}\subseteq\mathcal{I}:i\in\mathcal{I}^{\prime}}\rho_{\mathcal{I}^{\prime}}[\bar{\mathcal{S}}_{i}]={\mathbb{P}}^{\rm
S}[\tilde{\bm{z}}\in\bar{\mathcal{S}}_{i}]>0$, which implies that for all
$i\in\mathcal{I}$ there exists an index set
$\mathcal{I}^{\prime}\subseteq\mathcal{I}$ with $i\in\mathcal{I}^{\prime}$ and
$\rho_{\mathcal{I}^{\prime}}[\bar{\mathcal{S}}_{i}]>0$. Next, we define
another family of non-negative Borel measures
$\hat{\rho}_{i}=\sum_{\mathcal{I}^{\prime}\subseteq\mathcal{I}:i\in\mathcal{I}^{\prime}}\frac{1}{|\mathcal{I}^{\prime}|}\rho_{\mathcal{I}^{\prime}}$,
$i\in\mathcal{I}$. Note that $\hat{\rho}_{i}$ is supported on
$\bar{\mathcal{S}}_{i}$ and satisfies
$\hat{\rho}_{i}[\bar{\mathcal{S}}_{i}]>0$ for all $i\in\mathcal{I}$. In
addition, we have ${\mathbb{P}}^{\rm S}=\sum_{i\in\mathcal{I}}\hat{\rho}_{i}$.
Therefore, we can finally define
$\lambda_{i}=\hat{\rho}_{i}[\bar{\mathcal{S}}_{i}]$ and ${\mathbb{P}}^{\rm
S}_{i}=\frac{1}{\lambda_{i}}\hat{\rho}_{i}$ for all $i\in\mathcal{I}$. As
desired, this construction ensures that $\lambda_{i}>0$ and that the
probability measure ${\mathbb{P}}^{\rm S}_{i}$ is supported on
$\bar{\mathcal{S}}_{i}$ such that ${\mathbb{P}}^{\rm
S}=\sum_{i\in\mathcal{I}}\lambda_{i}{\mathbb{P}}^{\rm S}_{i}$. Since
${\mathbb{P}}^{\rm S}$ is a probability measure, the last relation implies
that $\sum_{i\in\mathcal{I}}\lambda_{i}=1$. It is also clear that
${\mathbb{P}}^{\rm S}_{i}$ is absolutely continuous on
$\mathbb{R}^{d_{\bm{z}}}$ for every $i\in\mathcal{I}$. Next, define
$\bm{z}_{i}=\mathbb{E}_{{\mathbb{P}}^{\rm S}_{i}}[\tilde{\bm{z}}]$ for all
$i\in\mathcal{I}$. As $h_{j}$ is proper, closed and convex, we may then use
Jensen’s inequality to verify that

$\sum_{i\in\mathcal{I}}\lambda_{i}h_{j}(\bm{z}_{i})\;\leq\;\sum_{i\in\mathcal{I}}\lambda_{i}\mathbb{E}_{{\mathbb{P}}^{\rm
S}_{i}}[h_{j}(\tilde{\bm{z}})]\;=\;\mathbb{E}_{{\mathbb{P}}^{\rm
S}}[h_{j}(\tilde{\bm{z}})]\;\leq\;\mu_{j}$

for every $j\in\mathcal{J}$, where the last inequality is strict whenever
$h_{j}$ is nonlinear because ${\mathbb{P}}^{\rm S}$ is a Slater distribution.
Similarly, as $c_{\ell}$ is proper, closed and convex, Jensen’s inequality
implies that

$c_{\ell}\left(\sum_{i\in\mathcal{I}}\lambda_{i}\bm{z}_{i}\right)\;\leq\;\sum_{i\in\mathcal{I}}\lambda_{i}c_{\ell}(\bm{z}_{i})\;\leq\;\sum_{i\in\mathcal{I}}\lambda_{i}\mathbb{E}_{{\mathbb{P}}^{\rm
S}_{i}}[c_{\ell}(\tilde{\bm{z}})]\;=\;\mathbb{E}_{{\mathbb{P}}^{\rm
S}}[c_{\ell}(\tilde{\bm{z}})]\;\leq\;0$

for every $\ell\in\mathcal{L}$, where the last inequality is strict whenever
$c_{\ell}$ is nonlinear. We may thus conclude that
$\sum_{i\in\mathcal{I}}\lambda_{i}\bm{z}_{i}$ is a Slater point for the
support set $\mathcal{S}$, which in turn implies via Lemma B.10 that each
$\bm{z}_{i}$, $i\in\mathcal{I}$, is a Slater point for $\mathcal{S}$ provided
that $\bm{z}_{i}\in{\rm ri}(\mathcal{S})$. As ${\mathbb{P}}^{\rm S}_{i}$ is
absolutely continuous on $\mathbb{R}^{d_{\bm{z}}}$ and supported on the convex
set $\bar{\mathcal{S}}_{i}$, one can indeed prove that its mean $\bm{z}_{i}$
belongs even to the interior of $\bar{\mathcal{S}}_{i}\subseteq\mathcal{S}$.
Otherwise, by the separating hyperplane theorem (Boyd and Vandenberghe, 2007,
Section 2.5.1), there exist $\bm{a}\in\mathbb{R}^{d_{\bm{z}}}$,
$\bm{a}\neq\bm{0}$, and $b\in\mathbb{R}$ such that
$\bm{a}^{\top}\bm{z}_{i}\geq b$ and $\bm{a}^{\top}\bm{z}\leq b$ for all
$\bm{z}\in\bar{\mathcal{S}}_{i}$. These two inequalities imply via Theorem
1.6.6 (b) by Ash and Doléans-Dade (2000) that ${\mathbb{P}}^{\rm
S}_{i}[\bm{a}^{\top}\tilde{\bm{z}}=b]=1$, which, however, contradicts the
absolute continuity of ${\mathbb{P}}^{\rm S}_{i}$ on
$\mathbb{R}^{d_{\bm{z}}}$. We have thus shown that $\bm{z}_{i}$ belongs to the
interior of $\bar{\mathcal{S}}_{i}$ and, as a consequence, in particular to
the interior of ${\rm dom}(-g_{i})$, the interior of ${\rm dom}(h_{j})$ for
every $j\in\mathcal{J}$ and the interior of $\mathcal{S}$. By Lemma B.10,
$\bm{z}_{i}$ is thus a Slater point for $\mathcal{S}$. As
$\bm{z}_{i}\in\bar{\mathcal{S}}_{i}$, we may finally select any
$\bm{u}_{i}>\bm{h}(\bm{z}_{i})\in\mathbb{R}^{J}$ and
$t_{i}<g_{i}(\bm{z}_{i})\in\mathbb{R}$ for every $i\in\mathcal{I}$. By
construction, $(\\{\bm{z}_{i},\bm{u}_{i},t_{i}\\}_{i},\bm{\lambda})$
constitutes a Slater point for (AD-B) that satisfies $\bm{\lambda}>\bm{0}$.
This Slater point for (AD-B) can easily be converted to a Slater point for
(AD-B′) that satisfies $\bm{\lambda}>\bm{0}$. ∎

######  Proposition 14 (Slater Points for (AP-W′)).

If the semi-infinite program (D-UQ) admits a strict Slater point and
$\mathcal{S}$ is bounded, then the convex program (AP-W′) admits a strict
Slater point.

###### Proof.

Denote by $(\alpha^{\rm S},\bm{\beta}^{\rm S})$ a strict Slater point of
problem (D-UQ), which exists by assumption. By using similar arguments as in
Proposition 10, one can show that $(\alpha^{\rm S},\bm{\beta}^{\rm S})$ also
constitutes a strict Slater point for (AP-W). If we fix $\alpha=\alpha^{\rm
S}$ and $\bm{\beta}=\bm{\beta}^{\rm S}$, then the embedded maximization
problem in the $i$-th constraint of (AP-W) is equivalent to

$\displaystyle\sup$ $\displaystyle\quad g_{i}(\bm{z}_{i})-\alpha^{\rm
S}-\sum_{j\in\mathcal{J}}h_{j}(\bm{z}_{i})\beta^{\rm S}_{j}$ (15)
$\displaystyle\rm{s.t.}$ $\displaystyle\quad c_{\ell}(\bm{z}_{i})\leq
0\qquad\forall\ell\in\mathcal{L}$ $\displaystyle\quad\bm{z}_{i}\text{ free}$

because the strict inequality $\bm{\beta}^{\rm S}>\bm{0}$ implies that for
every fixed $\bm{z}_{i}$ it is optimal to set $\bm{u}_{i}=\bm{h}(\bm{z}_{i})$
and $t_{i}=g_{i}(\bm{z}_{i})$. As $(\alpha^{\rm S},\bm{\beta}^{\rm S})$ is a
strict Slater point for (AP-W), the optimal value of (15) is strictly smaller
than $0$. Note also that (15) can be viewed as an instance of the minimization
problem (P) that satisfies assumption (F) because the components $g_{i}$,
$i\in\mathcal{I}$, of the disutility function satisfy (G), the moment
functions $h_{j}$, $j\in\mathcal{J}$, satisfy (H) and the constraint functions
$c_{\ell}$, $\ell\in\mathcal{L}$, of the support set satisfy (C). The
corresponding dual minimization problem is given by

$\displaystyle\inf$
$\displaystyle\quad(-g_{i})^{*}\left(\bm{y}^{(0)}_{i}\right)+\sum_{j\in\mathcal{J}}\beta_{j}^{\rm
S}h_{j}^{*}\left(\frac{\bm{y}^{(1)}_{ij}}{\beta_{j}^{\rm
S}}\right)+\sum_{\ell\in\mathcal{L}}\nu_{i\ell}c_{\ell}^{*}\left(\frac{\bm{y}^{(2)}_{i\ell}}{\nu_{i\ell}}\right)-\alpha^{\rm
S}$ (16) $\displaystyle\rm{s.t.}$
$\displaystyle\quad\bm{y}^{(0)}_{i}+\sum_{j\in\mathcal{J}}\bm{y}^{(1)}_{ij}+\sum_{\ell\in\mathcal{L}}\bm{y}^{(2)}_{i\ell}=\bm{0}$
$\displaystyle\quad\bm{y}^{(0)}_{i},\bm{y}^{(1)}_{ij},\bm{y}^{(2)}_{i\ell}\textnormal{
free},\quad\nu_{i\ell}\geq 0\qquad\forall
j\in\mathcal{J},\;\forall\ell\in\mathcal{L}.$

Note that the feasible region of the primal problem (15) coincides with
$\bar{\mathcal{S}}_{i}$ and is thus nonempty for every $i\in\mathcal{I}$
thanks to assumption (S). In addition, it constitutes a subset of
$\mathcal{S}$ and is thus bounded by assumption. Theorem 2  _(ii)_ then
implies that problems (15) and (16) share the same optimal value, which is
strictly smaller than $0$. In addition, Proposition 3 implies that problem
(16) admits a strict Slater point $(\bm{y}^{(0){\rm S}}_{i},\\{\bm{y}^{(1){\rm
S}}_{ij}\\}_{j},\\{\bm{y}^{(2){\rm S}}_{i\ell},\nu^{\rm S}_{i\ell}\\}_{\ell})$
for every $i\in\mathcal{I}$. As the infimum of (16) is strictly smaller than
$0$, we may assume without loss of generality that the objective function
value of this strict Slater point in (16) is strictly negative, too. This is a
direct consequence of Remark 1. By construction, $(\alpha^{\rm
S},\bm{\beta}^{\rm S},\\{\bm{y}^{(0){\rm S}}_{i}\\}_{i},\\{\bm{y}^{(1){\rm
S}}_{ij}\\}_{ij},\\{\bm{y}^{(2){\rm S}}_{i\ell},\nu^{\rm
S}_{i\ell}\\}_{i\ell})$ is thus a strict Slater point for (AP-W′). ∎

Among all sufficient conditions for strong duality between the uncertainty
quantification problems (4) and (D-UQ), the assumptions of Theorem 12  _(i)_
are—in our experience—most frequently satisfied, but they do not guarantee the
solvability of (4). The following corollary shows, however, that (4) can still
be solved asymptotically under these assumptions.

######  Corollary 15 (Approximate Numerical Solution of (4)).

If (AD-B′) admits a Slater point with $\bm{\lambda}>\bm{0}$, then the suprema
of (4) and (AD-B′) coincide, and any $\epsilon$-optimal solution of (AD-B′)
can be used to construct a discrete distribution with $I$ atoms that is
$2\epsilon$-optimal in (4).

###### Proof.

Note first that the suprema of (4) and (AD-B′) coincide by virtue of Theorem
12  _(i)_ , which applies because (AD-B′) admits a Slater point
$(\bm{\tau}^{\mathrm{S}},\bm{\lambda}^{\mathrm{S}},\\{\bm{\omega}_{i}^{\mathrm{S}},\bm{v}_{i}^{\mathrm{S}}\\}_{i})$
with $\bm{\lambda}^{\mathrm{S}}>\bm{0}$. Next, select any tolerance
$\epsilon>0$ and any $\epsilon$-optimal solution
$(\bm{\tau}^{\epsilon},\bm{\lambda}^{\epsilon},\\{\bm{\omega}^{\epsilon}_{i},\bm{v}^{\epsilon}_{i}\\}_{i})$
of problem (AD-B′). If (AD-B′) is unbounded, then we adopt the standard
convention that
$(\bm{\tau}^{\epsilon},\bm{\lambda}^{\epsilon},\\{\bm{\omega}^{\epsilon}_{i},\bm{v}^{\epsilon}_{i}\\}_{i})$
is feasible in (AD-B′) and that its objective function value is larger than or
equal to $1/\epsilon$. Next, define

$(\bm{\tau}^{\theta},\bm{\lambda}^{\theta},\\{\bm{\omega}^{\theta}_{i},\bm{v}^{\theta}_{i}\\}_{i})=\theta\cdot(\bm{\tau}^{\mathrm{S}},\bm{\lambda}^{\mathrm{S}},\\{\bm{\omega}_{i}^{\mathrm{S}},\bm{v}_{i}^{\mathrm{S}}\\}_{i})+(1-\theta)\cdot(\bm{\tau}^{\epsilon},\bm{\lambda}^{\epsilon},\\{\bm{\omega}^{\epsilon}_{i},\bm{v}^{\epsilon}_{i}\\}_{i})$

for any $\theta\in[0,1]$, and note that this solution is feasible in (AD-B′)
as it constitutes a convex combination of two feasible solutions. Note also
that $\bm{\lambda}^{\theta}>\bm{0}$ whenever $\theta>0$. As the objective
function of (AD-B′) is linear and thus continuous, there exists
$\theta\in(0,1]$ such that
$(\bm{\tau}^{\theta},\bm{\lambda}^{\theta},\\{\bm{\omega}^{\theta}_{i},\bm{v}^{\theta}_{i}\\}_{i})$
represents a $2\epsilon$-optimal solution of (AD-B′). Next, fix such a
$\theta$, and define ${\mathbb{P}}$ as the discrete distribution that assigns
probability $\lambda_{i}^{\theta}>0$ to
$\bm{\upsilon}_{i}^{\theta}/\lambda_{i}^{\theta}$ for all $i\in\mathcal{I}$.
As
$(\bm{\tau}^{\theta},\bm{\lambda}^{\theta},\\{\bm{\omega}^{\theta}_{i},\bm{v}^{\theta}_{i}\\}_{i})$
is feasible in (AD-B′), we can readily verify that ${\mathbb{P}}$ is supported
on $\mathcal{S}$ and satisfies

$\mathbb{E}_{{\mathbb{P}}}[\bm{h}(\tilde{\bm{z}})]\;=\;\sum_{i\in\mathcal{I}}\lambda^{\theta}_{i}\,\bm{h}(\bm{\upsilon}_{i}^{\theta}/\lambda_{i}^{\theta})\;\leq\;\sum_{i\in\mathcal{I}}\bm{\omega}^{\theta}_{i}\;\leq\;\bm{\mu},$

which implies that ${\mathbb{P}}\in\mathscr{P}$. Similarly, the objective
function value of ${\mathbb{P}}$ in (AD-B′) satisfies

$\mathbb{E}_{{\mathbb{P}}}[g(\tilde{\bm{z}})]\;=\;\sum_{i\in\mathcal{I}}\lambda^{\theta}_{i}\,g(\bm{\upsilon}_{i}^{\theta}/\lambda_{i}^{\theta})\;\geq\;\sum_{i\in\mathcal{I}}\lambda^{\theta}_{i}\,g_{i}(\bm{\upsilon}_{i}^{\theta}/\lambda_{i}^{\theta})\;\geq\;\sum_{i\in\mathcal{I}}\tau^{\theta}_{i}.$

The last expression non-inferior to $\sup\eqref{eq:adb-cvx}-2\epsilon$ if the
supremum of (AD-B′) is finite and non-inferior to $1/2\epsilon$ otherwise. As