A framework of distributionally robust possibilistic optimization Romain Guillaume1 Adam Kasperski2 and Pawe l Zieli nski2 1Universit e de Toulouse-IRIT Toulouse France romain.guillaumeirit.fr

2025-04-30 0 0 486.12KB 22 页 10玖币
侵权投诉
A framework of distributionally robust possibilistic optimization
Romain Guillaume1, Adam Kasperski∗2, and Pawe l Zieli´nski2
1Universit´e de Toulouse-IRIT Toulouse, France, romain.guillaume@irit.fr
2Wroc law University of Science and Technology, Wroc law, Poland,
{adam.kasperski,pawel.zielinski}@pwr.edu.pl
Abstract
In this paper, an optimization problem with uncertain constraint coefficients is con-
sidered. Possibility theory is used to model uncertainty. Namely, a joint possibility
distribution in constraint coefficient realizations, called scenarios, is specified. This pos-
sibility distribution induces a necessity measure in a scenario set, which in turn describes
an ambiguity set of probability distributions in a scenario set. The distributionally robust
approach is then used to convert the imprecise constraints into deterministic equivalents.
Namely, the left-hand side of an imprecise constraint is evaluated by using a risk measure
with respect to the worst probability distribution that can occur. In this paper, the Con-
ditional Value at Risk is used as the risk measure, which generalizes the strict robust, and
expected value approaches commonly used in literature. A general framework for solving
such a class of problems is described. Some cases which can be solved in polynomial time
are identified.
Keywords: robust optimization; possibility theory; fuzzy optimization; fuzzy intervals; con-
ditional value at risk
1 Introduction
Modeling uncertainty in optimization problems has been a subject of extensive research in
recent decades. This is due to the fact that in most applications, the exact values of input
data in optimization models are unknown before a solution must be determined. Two basic
questions arise while dealing with this uncertainty. The first is about the model of uncertainty
adopted. The answer depends on the knowledge available about the input data. If the true
probability distribution for uncertain parameters is known, then various stochastic models
can be used (see, e.g., [20]). For example, the uncertain constraints can be replaced with
the so-called chance constraints, in which we require that they be satisfied with a given
probability [7]. On the other hand, when only the set of possible realizations of the parameters
(called a scenario set) is available, the robust approach is widely utilized (see, e.g., [2]). In the
strict robust approach the constraints must be satisfied for all possible realizations of input
data (scenarios). This strong requirement can be softened by introducing a budget, i.e. some
limit on the amount of uncertainty [4].
∗Corresponding author
1
arXiv:2210.15193v2 [math.OC] 6 Sep 2023
In practice, an intermediate case often arises. Namely, partial information about the
probability distributions is known, which leads to the so-called distributionally robust mod-
els. The left-hand side of an uncertain constraint is then evaluated by means of some risk
measure with respect to the worst probability distribution that can occur. Typically, the
expected value is chosen as the risk measure. In this case, the decision-maker is risk neutral.
Information about the distribution parameters, such as the mean or covariance matrix, can
be reconstructed from statistical data, resulting in a class of data-driven problems [3]. On the
other hand, some information about the distributions can be derived from the knowledge of
experts or past experience. In this case, a possibilistic uncertainty model can be appropriate
(see, e.g., [19]).
In this paper, we will show how the possibility theory [13] can be used in the context of
distributionally robust optimization. Possibility theory offers a framework for dealing with
uncertainty. In many practical situations, it is possible to say which realizations of the problem
parameters are more likely to occur than others. Therefore, the common uncertainty sets used
in robust optimization are too inaccurate. Also, focusing on the worst parameter realizations
may lead to a large deterioration of the quality of the computed solutions (the large price of
robustness). On the other hand, due to the lack of statistical data or the complex nature of
the world, precise probabilistic information often cannot be provided. Then, the possibility
theory, whose axioms are less rigorous than the axioms of probability theory, can be used
to handle uncertainty. In this paper, we will use some relationships between possibility and
probability theories, which allows us to define a class of admissible probability distributions for
the problem parameters. Namely, a possibility distribution in the set of parameter realizations
induces a necessity measure in this set, which can be seen as a lower bound on the probability
measure [11]. We will further take into account the risk aversion of decision-makers by using
a risk measure called Conditional Value at Risk (CVaR for short) [29]. CVaR is a convex
coherent risk measure that possesses some favorable computational properties. Using it,
we can generalize the strict robust, and expected value-based approaches. In this paper, we
show a general framework for solving a problem with uncertain parameters under the assumed
model of uncertainty based on the above possibility-probability relationship. We also propose
a method of constructing a joint possibility distribution for the problem parameters, which
leads to tractable reformulations that can be solved efficiently by some standard off-the-shelf
solvers. This paper is an extended version of [17], where one particular uncertainty model
was discussed.
The approach considered in this paper belongs to the area of fuzzy optimization in which
many solution concepts have been proposed in the literature (see, e.g., [25]). Generally, fuzzy
sets can be used to model uncertainty or preferences in optimization models. In the former
case (used in this paper), the membership function of a fuzzy set is interpreted as a possibil-
ity distribution for the values of some uncertain quantity [13]. This interpretation leads to
various solution concepts (see, e.g. [22,25] for surveys). For example, fuzzy chance constraints
can be used in which a constraint with fuzzy coefficients should be satisfied with the highest
degree of possibility or necessity [24]. Furthermore, the uncertain objective function with
fuzzy coefficients can be replaced with a deterministic equivalent by using some defuzzifica-
tion methods [28]. Some recent applications of fuzzy robust optimization methods can be
found, for example, in [23,27]. Our approach is new in this area. It uses a link between fuzzy
and stochastic models established by the possibility theory. This allows us to use well-known
stochastic methods under the fuzzy (possibilistic) model of uncertainty. Our model is illus-
trated with two examples, namely continuous knapsack and portfolio selection problems. Its
2
validation on real problems is an interesting area of further research.
This paper is organized as follows. In Section 2, we consider an uncertain constraint and
present various methods of converting such a constraint into deterministic equivalents. In
Sections 3 and 4, we recall basic notions of possibility theory. In particular, we describe some
relationships between possibility and probability theories, which allow us to build a model
of uncertainty in which a joint possibility distribution is specified in the set of scenarios. In
Section 5 we discuss some tractable cases of our model, which can be converted into linear
or second-order cone programming problems. In Section 6, we characterize the complex-
ity of basic classes of optimization problems, such as linear programming or combinatorial
ones. Finally, in Section 7, we illustrate our concept with two computational examples - the
continuous knapsack and portfolio selection problems.
2 Handling uncertain constraints
Consider the following uncertain linear constraint:
˜
a
a
aTx
x
x≤b, (1)
where x
x
x∈Xis a vector of decision variables with a domain X⊆Rn,˜
a
a
a= (˜aj)j∈[n]is a vector
of uncertain parameters, ˜ajis a real-valued uncertain variable and b∈Ris a prescribed
bound. A particular realization a
a
a= (aj)j∈[n]∈Rnof ˜
a
a
ais called a scenario and the set of all
possible scenarios, denoted by U, is called the scenario set or uncertainty set. Intuitively, the
uncertain constraint (1) means that a
a
aTx
x
x≤bis satisfied by a solution x
x
x∈Xof an optimization
problem for some or all scenarios a
a
a∈ U, depending on a method of handling the uncertain
constraints.
Let P(U) be the set of all probability distributions in U. In this paper, we assume that ˜
a
a
a
is a random vector with probability distribution in P(U). The true probability distribution P
for ˜
a
a
acan be unknown or only partially known. The latter case can be expressed by providing
an ambiguity set of probability distributions P ⊆ P(U), so that P is only known to belong
to Pwith high confidence. There are many ways of constructing the set P. Most of them are
based on statistical data available for ˜
a
a
a, which enables us to estimate the moments (expected
values or covariance matrix) or the distribution shape (see, e.g., [9, 15, 32]). In the absence
of statistical data, one can try to estimate Pusing experts’ opinions. In Sections 3 and 4 we
will show how to construct an ambiguity set of probability distributions Pby using a link
between fuzzy and stochastic models established by possibility theory.
In order to convert (1) into a deterministic equivalent, one can use the following distribu-
tionally robust constraint [9, 32]:
sup
P∈P
EP[˜
a
a
aTx
x
x]≤b(2)
or equivalently
EP[˜
a
a
aTx
x
x]≤b∀P∈ P,
where EP[·] is the expected value with respect to the probability distribution P ∈ P. If
P=P(U), then (2) reduces to the following strict robust constraint [2]:
sup
a
a
a∈U
a
a
aTx
x
x≤b. (3)
3
Indeed, if P=P(U), then probability equal to 1 is assigned to scenario a
a
a∈ U maximizing a
a
aTx
x
x
(i.e. to a worst scenario for x
x
x). The strict robust constraint is known to be very conservative,
as it can lead to a large deterioration of the quality of the solutions computed. One can
limit the number of scenarios by adding a budget to U[4] to overcome this drawback. This
budget narrows the set Uto scenarios that are at some prescribed distance to a given nominal
scenario ˆ
a
a
a∈ U. We thus assume that scenarios far from ˆ
a
a
aare unlikely to occur.
We can generalize (2) by introducing a convex non-decreasing function g:R→R, and
considering the following constraint:
sup
P∈P
EP[g(˜
a
a
aTx
x
x)] ≤b. (4)
For example, the function gcan be interpreted as a disutility for the values of a
a
aTx
x
x, where a
a
a
is a scenario in U. In particular, gcan be of the form g(y) = y, in which case we get (2).
Notice that g(˜
a
a
aTx
x
x) is a function of the random variable ˜
a
a
aTx
x
x, so it is also a random variable.
By using the expectation in (4), one assumes risk neutrality of decision-makers. In order to
take an individual decision-maker’s risk aversion into account, one can replace the expectation
with the Conditional Value At Risk (called also Expected Shortfall) [29]. If X is a real random
variable, then the Conditional Value At Risk with respect to the probability distribution
P∈ P is defined as follows:
CVaRϵ
P[X] = inf
t∈R(t+1
1−ϵEP[X −t]+),(5)
where ϵ∈[0,1) is a given risk level and [x]+= max{0, x}. Notice that CVaR0
P[X] = EP[X].
On the other hand, if ϵ→1, then CVaRϵ
P[X] is equal to the maximal value that X can take.
We will consider the following constraint:
sup
P∈P
CVaRϵ
P[g(˜
a
a
aTx
x
x)] ≤b(6)
or equivalently, by using (5):
sup
P∈P
inf
t∈R(t+1
1−ϵEP[g(˜
a
a
aTx
x
x)−t]+)≤b. (7)
The parameter ϵ∈[0,1) models risk aversion of decision-makers. If ϵ= 0, then (7) is
equivalent to (4). On the other hand, when ϵ→1, then (7) becomes
sup
a
a
a∈U′
g(a
a
aTx
x
x)≤b, (8)
where U′⊆ U is the subset of scenarios that can occur with a positive probability for some
distribution in P. Thus, the approach based on the Conditional Value At Risk generalizes (3)
and (4). Moreover, the CVaR criterion can be used to establish a conservative approximation
of the chance constraints [26], namely
CVaRϵ
P[g(˜
a
a
aTx
x
x)] ≤b⇒P(g(˜
a
a
aTx
x
x)≤b)≥ϵ. (9)
Using condition (9) we conclude that a solution feasible to (6) is also feasible to the following
robust chance constraint:
inf
P∈P P(g(˜
a
a
aTx
x
x)≤b)≥ϵ. (10)
Optimization models with (10) can be hard to solve. They are typically nonconvex, whereas
the models with (6) can lead to more tractable optimization problems.
4
3 Possibility distribution-based model for uncertain constraints
Let Ω be a set of alternatives. A primitive object of possibility theory (see, e.g., [1]) is a
possibility distribution π: Ω →[0,1], which assigns to each element u∈Ω a possibility
degree π(u). We only assume that πis normal, i.e. there is u∈Ω such that π(u) = 1. The
possibility distribution can be built by using available data or experts’ opinions (see, e.g., [13]).
A possibility distribution πinduces the following possibility and necessity measures in Ω:
Π(A) = sup
u∈A
π(u), A ⊆Ω,(11)
N(A)=1−Π(Ac) = 1 −sup
u∈Ac
π(u), A ⊆Ω,(12)
where Ac= Ω \Ais the complement of event A. In this paper we assume that πrepresents
uncertainty in Ω, i.e. some knowledge about the uncertain quantity ˜utaking values in Ω.
We now recall, following [11], a probabilistic interpretation of the pair [Π,N] induced by the
possibility distribution π. Define
Pπ={P : ∀Ameasurable N(A)≤P(A)}={P : ∀Ameasurable Π(A)≥P(A)}.(13)
In this case supP∈PπP(A) = Π(A) and infP∈PπP(A) = N(A) (see [8, 11, 14]). Therefore, the
possibility distribution πin Ω encodes a family of probability measures in Ω. Any probability
measure P ∈ Pπis said to be consistent with πand for any event A⊆Ω the inequalities
N(A)≤P(A)≤Π(A) (14)
hold. A detailed discussion on the expressive power of (14) can also be found in [30]. Using
the assumption that πis normal, one can show that Pπis not empty. In fact, the probability
distribution such that P({u}) = 1 for some u∈Ω with π(u) = 1 is in Pπ. To see this, consider
two cases. If u /∈A, then N(A) = 0 and P(A)≥N(A) = 0. If u∈A, then P(A)=1≥N(A).
Assume that π:Rn→[0,1] is a joint possibility distribution for the vector of uncertain
parameters ˜
a
a
ain the constraint (1). The value of π(a
a
a), a
a
a∈Rn, is the possibility degree
for scenario a
a
a. A detailed method of constructing πwill be shown in Section 4. By (13),
the possibility distribution πinduces an ambiguity set Pπof probability distributions for ˜
a
a
a,
consistent with π. Define
C(λ) = {a
a
a∈Rn:π(a
a
a)≥λ}, λ ∈(0,1].(15)
The set C(λ) contains all scenarios a
a
a∈Rn, whose possibility of occurrence is at least λ. We
will also use C(0) to denote the support of π, i.e the smallest subset (with respect to inclusion)
of Rnsuch that N(C(0)) = 1. By definition (15), C(λ), λ∈[0,1], is a family of nested sets, i.e.
C(λ2)⊆ C(λ1) if 0 ≤λ1≤λ2≤1. We will make the following, not particularly restrictive,
assumptions about π:
Assumption 1.
1. There is a scenario ˆ
a
a
a∈Rnsuch that π(ˆ
a
a
a) = 1.
2. πis continuous in C(0).
3. The support C(0) of πcoincides with the scenario set Uand is a compact set.
5
摘要：

AframeworkofdistributionallyrobustpossibilisticoptimizationRomainGuillaume1,AdamKasperski∗2,andPawelZieli´nski21Universit´edeToulouse-IRITToulouse,France,romain.guillaume@irit.fr2WroclawUniversityofScienceandTechnology,Wroclaw,Poland,{adam.kasperski,pawel.zielinski}@pwr.edu.plAbstractInthispaper,ano...

展开>> 收起<<
A framework of distributionally robust possibilistic optimization Romain Guillaume1 Adam Kasperski2 and Pawe l Zieli nski2 1Universit e de Toulouse-IRIT Toulouse France romain.guillaumeirit.fr.pdf

共22页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：22 页 大小：486.12KB 格式：PDF 时间：2025-04-30

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 22
评分 收藏
分享
立即下载
客服
关注