Distributionally robust possibilistic optimization problems

In this paper we consider the following uncertain optimization problem:

In formulation (1), $\boldsymbol{c}\in\mathbb{R}^{n}$ is a vector of objective function coefficients, $\boldsymbol{b}\in\mathbb{R}^{m}$ is a vector of constraint right-hand sides, and $\tilde{\boldsymbol{a}}_{i}$ is a vector of uncertain coefficients of the $i$th constraint. In the following we will use the notation $[m]=\{1,\dots,m\}$. We assume that $\tilde{\boldsymbol{a}}_{i}$ is a random vector in $\mathbb{R}^{n}$ whose realization is unknown when a solution to (1) is determined. A particular realization $\boldsymbol{a}_{i}\in\mathbb{R}^{n}$ of $\tilde{\boldsymbol{a}}_{i}$ is called a scenario. After replacing $\tilde{\boldsymbol{a}}_{i}$ with scenario $\boldsymbol{a}_{i}$, for each $i\in[m]$, we get a deterministic counterpart of (1). The true probability distribution for $\tilde{\boldsymbol{a}}_{i}$ is only partially known. In particular, the set of possible scenarios $\mathcal{U}_{i}\subseteq\mathbb{R}^{n}$ is provided, which is the support of $\tilde{\boldsymbol{a}}_{i}$ or its reasonable approximation. Finally, $\mathbb{X}$ is a nonempty and bounded subset of $\mathbb{R}^{n}$ which restricts the domain of decision variables $\boldsymbol{x}$. If $\mathbb{X}$ is a polyhedron, for example, $\mathbb{X}=\{\boldsymbol{x}\in\mathbb{R}^{n}:\boldsymbol{L}\leq\boldsymbol{x}\leq\boldsymbol{U}\}$, for some $\boldsymbol{L},\boldsymbol{U}\in\mathbb{R}^{n}$, then we get uncertain linear programming problem. If, additionally, $\mathbb{X}\subseteq\{0,1\}^{n}$, then we get uncertain combinatorial optimization problem.

The method of handling the uncertain constraints and solving (1) depends on the information available about $\tilde{\boldsymbol{a}}_{i}$. If $\tilde{\boldsymbol{a}}_{i}$ is a random vector with a known probability distribution, then the $i$th constraint can be replaced with a stochastic chance constraint of the form

where $\epsilon_{i}\in[0,1)$ is a given risk level [8, 21]. If the uncertainty set $\mathcal{U}_{i}$ is the only information provided with $\tilde{\boldsymbol{a}}_{i}$, then the imprecise constraint $\tilde{\boldsymbol{a}}_{i}^{T}\boldsymbol{x}\leq b_{i}$ can be replaced with the following strict robust constraint [2]:

Choosing appropriate uncertainty set $\mathcal{U}_{i}$ is crucial in (2). For the discrete uncertainty, $\mathcal{U}_{i}$ consists of $K$ explicitly listed scenarios [25]. These scenarios correspond to some events which influence the value of $\tilde{\boldsymbol{a}}_{i}$ or can be the result of sampling the random vector $\tilde{\boldsymbol{a}}_{i}$. For the interval uncertainty [25], one provides an interval for each component $\tilde{a}_{ij}$ of $\tilde{\boldsymbol{a}}_{i}=(\tilde{a}_{i1},\dots,\tilde{a}_{in})$ and $\mathcal{U}_{i}$ is the Cartesian product of these intervals (a hyperrectangle in $\mathbb{R}^{n}$). In order to cut off the extreme values of this hyperrectangle, whose probability of occurrence can be negligible, one can add a budget to $\mathcal{U}_{i}$. This budget typically limits deviations of scenarios from some nominal scenario $\hat{\boldsymbol{a}}_{i}\in\mathcal{U}_{i}$ [5, 29]. In another approach $\mathcal{U}_{i}$ is specified as an ellipsoid centered at some nominal scenario $\hat{\boldsymbol{a}}_{i}$ [2]. Using the ellipsoidal uncertainty one can model correlations between the components of $\tilde{\boldsymbol{a}}_{i}$. One can also construct $\mathcal{U}_{i}$ from available data [4], which leads to various data-deriven robust models.

Another approach to handle the uncertainty consists in modeling the uncertain coefficients in (1) by using fuzzy sets. There are a lot of concepts of solving fuzzy optimization problems (see, e.g., [20, 35, 26, 34, 37, 32, 31]) – for a comprehensive description of them we refer the reader to [28]. In one of the most common class of models, $\tilde{\boldsymbol{a}}_{i}$ is a vector of fuzzy intervals whose membership functions are interpreted as possibility distributions for the components of $\tilde{\boldsymbol{a}}_{i}$. A description of possibility theory that offers a general framework of dealing with imprecise or incomplete knowledge can be found, for example, in [14]. It uses two dual possibility and necessity measures to handle the uncertainty. In the possibilistic setting one can replace the uncertain constraints in (1) with fuzzy chance constraints of the form [19, 27, 23]:

where ${\rm N}$ is a necessity measure induced by a possibility distribution for $\tilde{\boldsymbol{a}}_{i}$.

If a partial information about the probability distribution of $\tilde{\boldsymbol{a}}_{i}$ is available, then the so-called distributionally robust approach can be used (see, e.g., [16, 39, 10]). In this approach it is assumed that the true probability distribution ${\rm P}$ for $\tilde{\boldsymbol{a}}_{i}$ belongs to the so-called ambiguity set $\mathcal{P}_{i}$ of probability distributions. For example, one can consider all probability distributions given some bounds on its mean and covariance matrix [10]. Alternatively, the ambiguity set can be specified by providing a family of confidence sets (this approach will be adopted in this paper) [39]. Using the distributionally robust approach, one can consider the following counterpart of the imprecise constraint $\tilde{\boldsymbol{a}}_{i}^{T}\boldsymbol{x}\leq b_{i}$:

where the left hand side is the expected value of the random variable $\tilde{\boldsymbol{a}}_{i}^{T}\boldsymbol{x}$ under a worst probability distribution ${\rm P}\in\mathcal{P}_{i}$. Observe that (3) reduces to (2) if $\mathcal{P}_{i}$ contains all probability distributions with the support $\mathcal{U}_{i}$.

In this paper we propose a new approach in the area of fuzzy optimization. Will show how the distributionally robust optimization can be naturally used in the setting of possibility theory. A preliminary version of the paper has appeared in [17]. We will start by defining a possibility distribution (a membership function of a fuzzy set) for $\tilde{\boldsymbol{a}}_{i}$. This can be done by using both available data or experts knowledge. Following the interpretation of possibility distribution [1, 13], we will define an ambiguity set of probability distributions $\mathcal{P}_{i}$ for $\tilde{\boldsymbol{a}}_{i}$. Finally, we will apply constraints of the type (3) to compute a solution. We will show that the model of uncertainty assumed leads to a family of linear or second order cone constraints. So, the resulting problem is tractable for important cases of (1), for example for the class of linear programming problems.

This paper is organized as follows. In Section 2 we recall basic notions of possibility theory, in particular its probabilistic interpretation assumed in this paper. In Section 3 we discuss the discrete uncertainty representation in which a possibility degree for each scenario is specified. Then the ambiguity set $\mathcal{P}_{i}$ contains a family of discrete probability distributions with a finite support $\mathcal{U}_{i}$. We will show that (3) is then equivalent to a family of linear constraints. In Section 4 we consider the interval uncertainty representation, in which unknown probability distribution for $\tilde{\boldsymbol{a}}_{i}$ has a compact continuous support. We propose a method of defining a continuous possibility distribution for $\tilde{\boldsymbol{a}}_{i}$, which can be built by using available data or experts knowledge. We show that (3) is then equivalent to a family of second order cone constraints.

Let $\Omega$ be a set of alternatives. A primitive object of possibility theory (see, e.g., [1]) is a possibility distribution $\pi:\Omega\rightarrow[0,1]$, which assigns to each element $u\in\Omega$ a possibility degree $\pi(u)$. We only assume that $\pi$ is normal, i.e. there is $u\in\Omega$ such that $\pi(u)=1$. Possibility distribution can be built by using available data or experts opinions (see, e.g., [14]). A possibility distribution $\pi$ induces the following possibility and necessity measures in $\Omega$:

where $A^{c}=\Omega\setminus A$ is the complement of $A$. In this paper we assume that the possibility distribution $\pi$ represents uncertainty in $\Omega$, i.e. some knowledge about uncertain quantity $\tilde{u}$ taking values in $\Omega$. We now recall, following [13], a probabilistic interpretation of the pair $[\Pi,{\rm N}]$ induced by the possibility distribution $\pi$. Define

In this case $\sup_{{\rm P}\in\mathcal{P}(\pi)}{\rm P}(A)=\Pi(A)$ and $\inf_{{\rm P}\in\mathcal{P}(\pi)}{\rm P}(A)={\rm N}(A)$ (see [13, 15, 9]). So, the possibility distribution $\pi$ in $\Omega$ encodes a family of probability measures in $\Omega$. Any probability measure ${\rm P}\in\mathcal{P}(\pi)$ is said to be consistent with $\pi$ and for any event $A\subseteq\Omega$ the inequalities

hold. A detailed discussion on the expressive power of (5) can also be found in [38].

Observe that $\mathcal{P}(\pi)$ is nonempty due the assumption that $\pi$ is normalized. Indeed, the probability distribution such that ${\rm P}(\{u\})=1$ for some $u\in\Omega$ such that $\pi(u)=1$ is in $\mathcal{P}(\pi)$. To see this consider two cases. If $u\notin A$, then ${\rm N}(A)=0$ and ${\rm P}(A)\geq{\rm N}(A)=0$. If $u\in A$, then ${\rm P}(A)=1\geq{\rm N}(A)$.

Consider uncertain constraint $\tilde{\boldsymbol{a}}^{T}\boldsymbol{x}\leq b$, where $\tilde{\boldsymbol{a}}$ is a random vector in $\mathbb{R}^{n}$ with an unknown probability distribution (in order to simplify notation we skip the index $i$ in the constraint). In this section we assume that the support $\mathcal{U}$ of $\tilde{\boldsymbol{a}}$ is finite, i.e. $\mathcal{U}=\{\boldsymbol{a}_{1},\dots,\boldsymbol{a}_{K}\}$ is the set of all possible, explicitly listed scenarios (realizations of $\tilde{\boldsymbol{a}}$) which can occur with a positive probability. We thus consider the discrete uncertainty model [25, 22]. Let $\mu$ be a membership function of a fuzzy set in $\mathcal{U}$, $\mu:\mathcal{U}\rightarrow[0,1]$. We will interpret $\mu$ as a possibility distribution $\pi$ in the scenario set $\mathcal{U}$, i.e. $\pi=\mu$. In order to simplify presentation, we will identify each scenario $\boldsymbol{c}_{i}\in\mathcal{U}$ with its index $i\in[K]$. We can thus assume that $\pi$ is a possibility distribution in the index set $[K]$, $\pi:[K]\rightarrow[0,1]$. The value of $\pi(i)$ is the possibility degree for scenario $\boldsymbol{a}_{i}$. Assume also w.l.o.g. that $\pi(1)\geq\pi(2)\geq\dots\geq\pi(K)$ and thus $\pi(1)=1$.

Given $\pi$, we can now construct an ambiguity set $\mathcal{P}(\pi)$ of probability distributions for $\tilde{\boldsymbol{a}}$ by using (4). Because $\mathcal{P}(\pi)$ contains only discrete probability distributions in $[K]$, we get

and we can describe $\mathcal{P}(\pi)$ by the following system of linear constraints:

In description (6) the first set of constraints model the condition ${\rm P}(A)\geq 1-\Pi(A^{c})={\rm N}(A)\text{ for all events }A\subset[K]$, ($\Omega=[K]$). Notice that the formulation (6) has exponential number of constraints. In the following, we will show how to reduce the number of constraints to $O(K)$.

Let us partition the set of indices $[K]$ into $\ell$ disjoint sets $I_{1},\dots,I_{\ell}$ such that the elements of $I_{j}$ have the same possibility degrees and the possibility degrees of the elements in $I_{j}$ are greater than the possibility degrees of the elements in $I_{k}$ for any $j>k$. For example, let $\boldsymbol{\pi}=(1,1,0.5,0.5,0.3,0.3,0.3,0.1)$ be a possibility distribution (a fuzzy set) in $[K]$ for $K=8$ (i.e. a possibility distribution in the set of eight scenarios). Then $I_{1}=\{1,2\}$, $I_{2}=\{3,4\}$, $I_{3}=\{5,6,7\}$, $I_{4}=\{8\}$. Let $\pi^{j}$ be the possibility degree of the elements in $I_{j}$. In the example we have $\pi^{1}=1$, $\pi^{2}=0.5$, $\pi^{3}=0.3$ and $\pi^{4}=0.1$.

For the sample possibility distribution $\boldsymbol{\pi}=(1,1,0.5,0.5,0.3,0.3,0.3,0.1)$, the ambiguity set $\mathcal{P}(\pi)$ can be described by the following system of constraints:

Using Proposition 1, the value of $\max_{{\rm P}\in\mathcal{P}(\pi)}\mathrm{\mathbf{E}}_{\rm P}[\tilde{\boldsymbol{a}}^{T}\boldsymbol{x}]$, for a given $\boldsymbol{x}$, can be computed by using the following linear program:

Consider two boundary cases of the proposed model. If $\pi(k)=1$ for some $k\in[K]$, and $\pi(i)=0$ for each $i\neq k$, then $\boldsymbol{a}_{k}$ is the only scenario which can occur. The constraint (3) reduces then to $\boldsymbol{a}_{k}^{T}\boldsymbol{x}\leq b$. If $\pi(i)=1$ for all $i\in[K]$, then $\mathcal{P}(\pi)=\{\boldsymbol{p}\in[0,1]^{K}:\sum_{i\in[K]}p_{i}=1\}$ and (3) becomes the strict robust constraint (2) for $\mathcal{U}=\{\boldsymbol{a}_{1},\dots,\boldsymbol{a}_{K}\}$. Theorem 1 yields the following corollary.

Corollary 1 shows that the resulting deterministic counterpart of uncertain linear programming problem (1), under the discrete uncertainty model, is polynomially solvable and thus can be solved efficiently by standard off-the-shelf solvers.

Let us again focus on an uncertain constraint $\tilde{\boldsymbol{a}}^{T}\boldsymbol{x}\leq b$, where $\tilde{\boldsymbol{a}}=(\tilde{a}_{1},\dots,\tilde{a}_{n})$ is a random vector in $\mathbb{R}^{n}$ with an unknown probability distribution having now a compact continuous support $\mathcal{U}\subseteq\mathbb{R}^{n}$. We will start by describing the support $\mathcal{U}$. Next, we will propose a continuous possibility distribution $\pi$ in $\mathcal{U}$ which will induce an ambiguity set of probability distributions $\mathcal{P}(\pi)$ according to (4). This possibility distribution can be provided by experts or can be estimated by using available data. Assume that for each component $\tilde{a}_{j}$ of $\tilde{\boldsymbol{a}}$ a nominal (expected, the most probable) value $\hat{a}_{j}$ and an interval $[\hat{a}_{j}-\underline{a}_{j},\hat{a}_{j}+\overline{a}_{j}]$ containing possible values of $\tilde{a}_{j}$ are known. Let

i.e. $\mathcal{B}(0)$ is a hyperrectangle containing possible scenarios $\boldsymbol{a}$ (realizations of $\tilde{\boldsymbol{a}}$). The components of $\tilde{\boldsymbol{a}}$ are often correlated. Also, the probability that a subset of components will take the extreme values can be very small or even 0. So, $\mathcal{B}(0)$ is typically an overestimation of the support $\mathcal{U}$ of $\tilde{\boldsymbol{a}}$. In robust optimization some limit for the deviations of scenarios from the nominal vector $\hat{\boldsymbol{a}}$ is often assumed, i.e. $\delta(\boldsymbol{a})\leq\Gamma$, where $\delta(\boldsymbol{a})$ is a deviation prescribed. The parameter $\Gamma\geq 0$ is called a budget and it controls the amount of uncertainty in $\mathcal{U}$. One can define, for example, $\delta(\boldsymbol{a})=||\boldsymbol{a}-\hat{\boldsymbol{a}}||_{1}$, which leads to the continuous budgeted uncertainty [29]. In this paper, following [2, 3] we use

where $\boldsymbol{B}$ is a given $n\times n$ matrix. Notice that $\delta(\boldsymbol{a})=(\boldsymbol{a}-\hat{\boldsymbol{a}})^{T}\boldsymbol{\Sigma}(\boldsymbol{a}-\hat{\boldsymbol{a}})$, where $\boldsymbol{B}=\boldsymbol{\Sigma}^{\frac{1}{2}}$ for some postive semidefinite matrix $\boldsymbol{\Sigma}$. For example, $\boldsymbol{\Sigma}$ can be an estimation of the covariance matrix for $\tilde{\boldsymbol{a}}$ (see, e.g., [6]). Therefore

is an ellipsoid in $\mathbb{R}^{n}$. We postulate that $\mathcal{B}(0)\cap\mathcal{E}(0)$ contains all possible realizations of $\tilde{\boldsymbol{a}}$, i.e. ${\rm P}(\mathcal{B}(0)\cap\mathcal{E}(0))=1$. Hence $\mathcal{B}(0)\cap\mathcal{E}(0)$ is the estimation of the support of $\tilde{\boldsymbol{a}}$. In the following, we will construct a possibility distribution for $\tilde{\boldsymbol{a}}$, which can be easily built from $\hat{a}_{j},\underline{a}_{j},\overline{a}_{j}$, $j\in[n]$, matrix $\boldsymbol{B}$ and the budget $\Gamma$.

Let $\pi_{\tilde{a}_{j}}$ be a possibility distribution for the component $\tilde{a}_{j}$ of $\tilde{\boldsymbol{a}}$, such that that $\pi_{\tilde{a}_{j}}(\hat{a}_{j})=1$, $\pi_{\tilde{a}_{j}}(\hat{a}_{j}-\underline{a}_{j})=\pi_{\tilde{a}_{j}}(\hat{a}_{j}+\overline{a}_{j})=0$, $\pi_{\tilde{a}_{j}}$ is continuous, strictly increasing in $[\hat{a}_{j}-\underline{a}_{j},\hat{a}_{j}]$ and continuous strictly decreasing in $[\hat{a}_{j},\hat{a}_{j}+\overline{a}_{j}]$. One can identify the possibility distribution $\pi_{\tilde{a}_{j}}$ with membership function $\mu_{\tilde{a}_{j}}$ of a fuzzy interval $\braket{\hat{a}_{j},\underline{a}_{j},\overline{a}_{j}}_{z_{1}-z_{2}}$ shown in Figure 1a (i.e. $\pi_{\tilde{a}_{j}}=\mu_{\tilde{a}_{j}}$). Let

be the $\lambda$-cut of $\tilde{a}_{j}$. It is easy to check that $\tilde{a}_{j}(\lambda)=[\underline{a}_{j}(\lambda),\overline{a}_{j}(\lambda)]$ is an interval for each fixed $\lambda\in(0,1]$. Set $[\underline{a}_{j}(0),\overline{a}_{j}(0)]=[\hat{a}_{i}-\underline{a}_{j},\hat{a}_{j}+\overline{a}_{j}]$. The function $\underline{a}_{j}(\lambda)$, the left profile of $\pi_{\tilde{a}_{j}}$, is continuous and strictly increasing and the function $\overline{a}_{j}(\lambda)$, the right profile of $\pi_{\tilde{a}_{j}}$, is continuous and strictly decreasing for $\lambda\in[0,1]$. For the fuzzy interval $\braket{\hat{a}_{j},\underline{a}_{j},\overline{a}_{j}}_{z_{1}-z_{2}}$, the $\lambda$-cut of $\tilde{a}_{j}$ can be computed by using the following formula:

We will assume that $\underline{a}_{j},\overline{a}_{j},z_{1},z_{2}>0$. Then $\tilde{a}_{j}(\lambda)$ are nondegenerate intervals (they have nonempty interiors) for each $\lambda\in[0,1)$. The numbers $z_{1}$ and $z_{2}$ control the amount of uncertainty for $\tilde{a}_{j}$ below and over $\hat{a}_{j}$, respectively. In particular, when $z_{1},z_{2}\rightarrow 0$, then $\tilde{a}_{j}$ becomes $\hat{a}_{j}$. On the other hand, if $z_{1},z_{2}\rightarrow\infty$, then $\tilde{a}_{j}$ becomes the closed interval $[\hat{a}_{j}-\underline{a}_{j},\hat{a}_{j}+\overline{a}_{j}]$ (see Figure 1).

The deviation $\delta(\boldsymbol{a})$ depends on an unknown realization of $\tilde{\boldsymbol{a}}$, so we can treat the deviation as an uncertain quantity $\tilde{\delta}$. We can now build the following possibility distribution for $\tilde{\delta}$: $\pi_{\tilde{\delta}}(0)=1$, $\pi_{\tilde{\delta}}$ is continuous and strictly decreasing in $[0,\Gamma]$ and $\pi_{\tilde{\delta}}(\delta)=0$ if $\delta\notin[0,\Gamma]$. Let

be the $\lambda$-cut of $\tilde{\delta}$. Fix $\overline{\delta}(0)=\Gamma$. We can identify $\pi_{\tilde{\delta}}$ with membership function $\mu_{\tilde{\delta}}$ of a fuzzy interval $\tilde{\delta}$ given, for example, in the form of $\braket{0,0,\Gamma}_{z}$ (see Figure 1b). The $\lambda$-cut of $\tilde{\delta}$ is then $\tilde{\delta}(\lambda)=[0,\Gamma(1-\lambda^{z})]$ for $\lambda\in[0,1]$.

We now build the following joint possibility distribution $\pi:\mathbb{R}^{n}\rightarrow[0,1]$, for $\tilde{\boldsymbol{a}}$:

The value of $\pi(\boldsymbol{a})$ is the possibility degree for scenario $\boldsymbol{a}\in\mathbb{R}^{n}$. The first part of the possibility distribution, i.e. $\min\{\pi_{\tilde{a}_{1}}(a_{1}),\pi_{\tilde{a}_{2}}(a_{2}),\dots,\pi_{\tilde{a}_{n}}(a_{n})\}$, is built from the possibility distributions of non-interacting components [11]. The second part $\pi_{\tilde{\delta}}(\delta(\boldsymbol{a}))$ is added to model interactions between the components of $\tilde{\boldsymbol{a}}$. Define the $\lambda$-cut of $\tilde{\boldsymbol{a}}$

It is easily seen that

Set $\mathcal{C}(0)=\mathcal{B}(0)\cap\mathcal{E}(0)$. Observe that $\mathcal{C}(1)=\{\hat{\boldsymbol{a}}\}$. Furthermore $\mathcal{C}(\lambda)$, $\lambda\in[0,1]$, is a family of nested sets, i.e. $\mathcal{C}(\lambda_{1})\subset\mathcal{C}(\lambda_{2})$ if $\lambda_{1}>\lambda_{2}$. By the continuity and monotonicity of $\underline{a}_{j}(\lambda)$, $\overline{a}_{j}(\lambda)$ and $\overline{\delta}(\lambda)$ we get

Notice also that $\mathcal{C}(\lambda)$ is a closed convex set for each $\lambda\in[0,1]$ and has nonempty interior for all $\lambda\in[0,1)$.

In order to construct a tractable reformulation of (3) for $\mathcal{P}(\pi)$ we need to use a discretization of $\mathcal{P}(\pi)$. Choose integer $\ell\geq 0$ and set $\Lambda=\{0,1,\dots,\ell\}$. Define $\lambda_{i}=i/\ell$, $i\in\Lambda$. We consider the following ambiguity set:

Set $\mathcal{P}^{\ell}(\pi)$ is a discrete approximation of $\mathcal{P}(\pi)$. It is easy to verify that $\mathcal{P}(\pi)\subseteq\mathcal{P}^{\ell}(\pi)$ for any $\ell\geq 0$. By fixing sufficiently large constant $\ell$, we obtain arbitrarily close approximation of $\mathcal{P}(\pi)$.