The Use of Fuzzy Optimization Methods for Radiation Therapy of

Report
Uncertainties in Mathematical
Analysis and Their Use in
Optimization
Congresso Brasileiro de Sistemas Fuzzy
Sorocaba, Brasil
9 de novembro, 2010
Weldon A. Lodwick and Oscar Jenkins
University of Colorado Denver
Department of Mathematical and Statistics Sciences
[email protected]
Abstract: Fuzzy set theory and possibility theory are potent
mathematical languages for expressing transitional (nonBoolean) set belonging and information deficiency (nonspecificity), respectively. We argue that fuzzy and
possibility optimization have a most important role to
play in optimization. Three key ideas are considered:
1) Normative decision making/optimization is often satisficing and
epistemic.
2) Fuzzy set theory and possibility theory are the mathematical
languages well-suited for encapsulating satisficing and epistemic
entities, perhaps, the only mathematical languages we have at
present. As a consequence, fuzzy and possibility optimization are
powerful approaches to satisficing and epistemic decision making,
3) Semantic and structural distinctions between fuzzy sets and
possibility are crucial, especially in fuzzy and possibility
optimization.
Congresso Brasileiro de Sistemas
Fuzzy
2
Outline
Introduction – Why Fuzzy Set Theory, Possibility Theory (in
optimization)?
Elements of Fuzzy Set Theory and Possibility Theory: A
Mathematician’s Point of View
I.
II.
A.
B.
C.
III.
Intervals
Fuzzy Intervals
Possibility
Fuzzy and Possibility Optimization
A.
B.
IV.
Taxonomy
Solution Methods
Theoretical Considerations <If we have time>
A.
B.
C.
Interval Arithmetic as Function Arithmetic
Geometry of convex cones associated with optimization over intervals
Orderings in convex cones associated with optimization over intervals
Congresso Brasileiro de Sistemas
Fuzzy
3
Objectives
• To show the clear distinction between fuzzy set theory and
possibility theory
• To develop two types of possibility analyses
1. Single distribution possibility analysis
2. Dual distribution possibility/necessity analysis – risk
• To demonstrate how the differences between fuzzy set
theory and possibility theory impact optimization
1. Flexible optimization
2. Possibility or evaluation optimization
3. Possibility/necessity or dual evaluation optimization
4. Mixed optimization
Congresso Brasileiro de Sistemas
Fuzzy
4
This presentation will state the obvious
• Some of what is presented has been known for some time,
but perhaps not quite from the same point of view, so we
hope to bring greater clarity
• My point of view is mathematical and as an area editor for
the journal Fuzzy Sets and Systems
• There will be some new(er) things
– Upper/lower optimization, what we call dual evaluation
optimization , dual distribution optimization
– Interval analysis of linear functions with non-linear slopes over
compact domains in order to compute and do mathematical
analysis with intervals and fuzzy intervals <if we have time>
– All orders associated with intervals and associated geometry <if
there is time>
Congresso Brasileiro de Sistemas
Fuzzy
5
Point of View
Fuzzy sets do not model uncertainty
Congresso Brasileiro de Sistemas
Fuzzy
6
Uncertainty Models - Possibility
Information deficiency - the lack of determinism
Congresso Brasileiro de Sistemas
Fuzzy
7
Fuzzy – Transition set belonging
It has nothing to do with this cartoon from my newspaper
except I hope this talk will indeed GET FUZZY
Congresso Brasileiro de Sistemas
Fuzzy
8
I. Introduction – Why fuzzy or possibility theory (in
optimization)?
• Many optimization models are satisficing – decision
makers do not know what is deterministically “the best.”
A model is useful if the solutions are good enough.
• Many optimization models are epistemic – they model
what we, as humans, know about a system rather than the
system itself. For example, an automatic pilot of an
airplane models the system’s physics. A fuzzy logic chip
that controls a rice cooker is epistemic in that it
encapsulates what we know about cooking rice, not the
physics of cooking rice.
• Fuzzy and possibility optimization models are well-suited
for and most flexible in representing satisficing and
epistemic normative criteria.
Congresso Brasileiro de Sistemas
Fuzzy
9
General Mathematical Approach
• Possibility theory as has been articulated by Didier Dubois
and Henri Prade, and others, over the last three decades has
put it on a solid mathematical foundation. They, and
others, have also helped put fuzzy set theory that was
created by Lotfi Zadeh onto a solid foundation. A solid
mathematical foundation is able to order our fuzzy and
possibilistic thoughts and applications.
• We, in this presentation, seek to clarify how fuzzy set
theory and possibility theory are used in mathematical
analysis, particularly in optimization. This, hopefully, will
order approaches to optimization problems.
Congresso Brasileiro de Sistemas
Fuzzy
10
Prof. H. J. Rommelfanger (2004)"The advantages of fuzzy
optimization models in practical use," Fuzzy Optimization
and Decision Making, 3, pp. 295),
1. Linear programming is the most widely used OR
method.
2. Of the 167 production (linear) programming systems
investigated and surveyed by Fandel, ( Fandel, G.
(1994), only 13 of these were run as “purely“ linear
programming systems.
3. Thus, even with this most highly used and applied
operations research method, there is a discrepancy
between classical deterministic linear programming and
what was/is actually used in practice!
Congresso Brasileiro de Sistemas
Fuzzy
11
Some Thoughts
• Deterministic and stochastic optimization models require
1. Single-value unique distributions for the random
variable coefficients, right-hand side values,
2. Deterministic relationships (inequalities, equalities)
3. Real-valued functions or distribution functions to
maximize, minimize.
4. Thus, any large scale model requires significant data
gathering efforts. If the model has projections of future
values, we have no determinism nor certainty.
Congresso Brasileiro de Sistemas
Fuzzy
12
My Colleagues’ Critique of Fuzzy/Possibilistic Optimization
• What is done with fuzzy/possibility optimization can be
done by deterministic or probabilistic (stochastic)
optimization.
• Corollary: Since all fuzzy/possibilistic optimization
models are transformed into real-valued linear or nonlinear programming problems, we do not need fuzzy nor
possibility optimization.
• Show me an example for which fuzzy/possibilistic
optimization solves the problem and deterministic or
stochastic do not.
Congresso Brasileiro de Sistemas
Fuzzy
13
A (Fuzzy) Mathematician’s Reply
• Just because the foundation of probability theory was put
into the context of real analysis does not negate the value of
probability as a separate branch distinct from real analysis.
• Just because stochastic optimization models stated as
recourse or chance constraints are translated into realvalued mathematical programming problems does not
negate the value of stochastic optimization as a separate
branch of optimization.
Corollary: Just because fuzzy and possibility optimization
translate to a standard linear or nonlinear programming
problem does not negate its value as a separate study in
optimization theory
Congresso Brasileiro de Sistemas
Fuzzy
14
The Value of Fuzzy and Possibility Optimization
• Flexible programming (what is called fuzzy programming)
has no equivalent in classical optimization theory with the
richness and robustness that fuzzy set theory brings. This
is the contribution of fuzzy set theory to optimization.
• Upper/lower bounds on optimization models arising from
necessity (pessimistic) and possibility (optimistic) have no
equivalent in optimization theory. This is a unique
contribution possibility theory to optimization.
• Possibility theory is a rich and robust mathematical
language for representing epistemic and satisficing
objective. No classical mathematical language exists for
stating epistemic or satisficing objectives and constraints as
robust/rich as fuzzy set
theory
and
possibility
theory.
Congresso Brasileiro de Sistemas
15
Fuzzy
A (Fuzzy) Mathematician’s Reply
• A representation of a mathematical problem always begins
in its “native” environment of origin. For example, one
always begins a nonlinear problem by stating the problem
in its nonlinear environment. After stating the problem in
its full nonlinear setting, one may then turn it into a linear
system. Most (all) convergence and error analysis is
based on knowing from where the problem came.
• If the problem is epistemic and/or satisficing, or fuzzy
(transitional set belonging) or involves information
deficiency, one states the problem in the space from which
the problem came. Then, and only then, does one makes
the “approximation” or translation into what is possible to
solve.
Congresso Brasileiro de Sistemas
Fuzzy
16
Some Further Thoughts of Prof. Rommelfanger
From an email discussion, Rommelfanger relates the
following. “In fact Herbert Simon develops a decision
making approach which he calls the Concept of Bounded
Rationality. He formulated the following two theses.
Thesis 1: In general a human being does not strive for
optimal decisions, but s/he tends to choose a course of
action that meets minimum standards for satisfaction.
The reason for this is that truly rational research can
never be completed.
Congresso Brasileiro de Sistemas
Fuzzy
17
Some Further Thoughts of Prof. Rommelfanger
Thesis 2: Courses of alternative actions and
consequences are in general not known a priori,
but they must be found by means of a search
procedure.” That is we do not often know ahead
of time. If we did, we would, perhaps, not have a
problem.
Congresso Brasileiro de Sistemas
Fuzzy
18
PRINCIPLE OF LEAST COMMITMENT
A useful approach in flexible and possibility (also
stochastic) optimization is the Principle of Least
Commitment which states:
Only commit when you must.
Corollary 1: (For fuzzy and possibility optimization)
Carry the full extent of uncertainty and gradualness
until one must choose.
Corollary 2: (For men) Only make the commitment in
marriage when you have to.
Congresso Brasileiro de Sistemas
Fuzzy
19
II. Elements of Fuzzy Set Theory and Possibility Theory:
A Mathematician’s Point of View
• Fuzzy set theory is the mathematics of transitional (nonBoolean) set belonging
Example (Fuzzy): Tumorness of a pixel – a pixel is both
cancerous and non-cancerous at the same time (conjuctive)
• Possibility theory is the mathematics of information
deficiency, non-specificity (non-deterministic), uncertainty
Example (Possibility): My evaluation of the age of the
outgoing president of Brasil. {45 or 46 or … 59 or 60 or }
Note: Lula’s age exists, it is a real number (not fuzzy) in
counter-distinction with the boundary between cancerous
and non-cancerous cells which is inherently transitional.
Congresso Brasileiro de Sistemas
Fuzzy
20
Fuzzy and Possibility
Theorem 1:There is nothing uncertain about a fuzzy set.
Theorem 2:There is nothing uncertain about a fuzzy set.
Proof: Once fuzzy sets are uniquely defined by their
membership function, we know the belonging transition
precisely. The membership value of 1 means
membership with certainty. The membership value of 0
means non-membership with certainty.
Corollary: Fuzzy optimization is not optimization under
uncertainty!!!! Fuzzy optimization is flexible
(transitional) optimization. We will return to this
subsequently.
Congresso Brasileiro de Sistemas
Fuzzy
21
Fuzzy and Possibility – Dubois/Prade
• Fuzzy is conjunctive (and) – a fuzzy entity is more than
one thing at once (an element is and isn’t in the set to a
certain degree). In image segmentation (fuzzy clustering)
a pixel belongs to various classes at once even though a
pixel is a distinct non-overlapping unit.
• Possibility is disjunctive (or) – my guess at outgoing
President Lula’s age is a distribution over distinct set of
elements {… or 45 or 46 or … 59 or 60 or …}. I would
have a distribution value for these distinct elements (all
real numbers in this case). However, the age of outgoing
president exists as a real number, but my knowledge
(epistemic state) is a possibility distribution.
Congresso Brasileiro de Sistemas
Fuzzy
22
Probability Alone is Insufficient to Describe All Uncertainty
Example: Suppose all that is known is that x∈[1,4]. Clearly,
x∈[1,4] implies that the real value that x represents is not
certain (albeit bounded). If the uncertainty that x∈[1,4]
represents were probabilistic (x is a random variable that
lies in this interval), then every distribution having support
contained in [1,4] would be equally valid given. Thus, if one
chooses the uniform probability density distribution on
[1,4],
p(x) = 1/3, 1≤x≤4,
p(x) = 0 otherwise,
we clearly lose information.
Congresso Brasileiro de Sistemas
Fuzzy
23
View of Uncertainty
Congresso Brasileiro de Sistemas
Fuzzy
24
Probability Alone is Insufficient to Describe all Uncertainty
• The approach that keeps the entire uncertainty considers
it as all distributions whose support is [1,4] as equally
valid.
• The pair of cumulative distributions that bound all
cumulative distributions with this given support is
depicted in Figure 1.
• This pair is a possibility (upper blue
distribution)/necessity (lower red distribution)pair.
Congresso Brasileiro de Sistemas
Fuzzy
25
Probability Alone is Insufficient to Describe all Uncertainty
• Note that the green line (uniform cumulative distribution)
is precisely what in interval analysis would be the most
sensible choice when no other information is at hand
except the interval itself, “Choose the midpoint when one
must choose.”
• However, one does not have to choose a uniform
distribution at the beginning of an analysis which is the
approach of the Principle of Least Commitment.
• Analysis with the dual upper/lower bounds does not lose
information.
Congresso Brasileiro de Sistemas
Fuzzy
26
Structure of mathematical analysis in flexible and
possibility optimization
Optimization requires:
1. Objective function(s) – way to determine (compute) what an
optima is
2. Relationships – a description of how variables and parameters
are associated (equality and inequality).
3. Constraint set – a way to determine (compute) how the set of
relationships are linked (equations/inequalities are linked or
aggregated by “and” or “or” or t-norms)
REMARK: Fuzzy and possibility optimization state each of these
components of the structure in a particular mathematical
language that is distinct from deterministic and probabilistic
statements of the same structure.
Congresso Brasileiro de Sistemas
Fuzzy
27
Entities of Fuzzy and Possibility Optimization
The entities are:
1. Intervals
2. Fuzzy intervals
3. Single possibility distributions
4. Dual possibility/necessity distributions
Congresso Brasileiro de Sistemas
Fuzzy
28
1. Entities of Analysis - Intervals
An interval [x] = [a,b] = {x | a ≤ x ≤ b}. For example, [x]=
[1,4]. There are two views of an interval:
• New type of number (an interval number) described by two
real numbers a, and b, a ≤ b, the lower and upper bound [x]
= {a,b} Warmus, Sunaga, and Moore approach.
• A set [x] = {x | a ≤ x ≤ b} which we will represent as a
function (the set of single-valued linear functions with nonnegative slopes over compact domain [0,1].
• A single-valued linear function with non-negative slope
over a compact domain [0,1] (Lodwick 1999):
[ x ]  f (  x )  (1   x ) x   x x
 wxx  x,
0   x  1, (w idth) w x  x  x
Congresso Brasileiro de Sistemas
Fuzzy
29
Entities of Analysis - Intervals
• When an interval is represented and operated on by
its lower/upper bounds {a,b} as a new type of
number, then the ensuing algebraic structure is
more limited than necessary. It is an algebra of
vectors in  2, an algebra of two points (upper half
plane determined by y=x), a subset of  in fact.
• If an interval is considered as a set or a singlevalued function with non-negative slope over a
compact [0,1] domain, then the ensuing algebraic
structure is that of sets or functions which is richer.
2
Congresso Brasileiro de Sistemas
Fuzzy
30
Entities of Analysis - Intervals
b) Two interesting anomalies associated with intervals:
i. [a] ≤ [b] and [a] ≥ [b] does not imply [a] = [b]. Consider
[2,3]x ≤ [3,6] → x ≤ 1 and
[2,3]x ≥ [3,6] → x ≥ 3
These two result in the empty set.
But [2,3]x = [3,6] → x = [3/2,2] since [2,3][3/2,2]=[3,6]
ii. [2,3][½, ⅓]x = [3,6][½, ⅓]
[1,1]x = [3/2,2]
[½, ⅓] is not an interval, it belongs to the lower half plane
where inverses of intervals live (in a non-interval space).
Congresso Brasileiro de Sistemas
Fuzzy
31
2. Entities of Analysis - Fuzzy Intervals
Triangular Fuzzy Interval – We will call this a fuzzy interval
since a fuzzy interval (see next slide) is more general.
Congresso Brasileiro de Sistemas
Fuzzy
32
2. Entities of Analysis - Fuzzy Intervals
Trapazoid Fuzzy Interval: What is an element of this set?
Congresso Brasileiro de Sistemas
Fuzzy
33
Entities of Analysis - Fuzzy Intervals
1. A fuzzy interval can be automatically translated into
a possibility distribution and thus may be a model for
both the lack of specificity as well as transition
depending on the semantics.
2. Thus, fuzzy intervals have or take on a dual nature that of capturing or modeling gradualness of
belonging and capturing or modeling non-specificity.
Possibility is tied to uncertainty.
3. This dual nature of fuzzy intervals is the source of
much confusion.
Congresso Brasileiro de Sistemas
Fuzzy
34
3. Entities of Analysis – Single Possibility Distribution
Possibility models non-specificity, information deficiency
and is a mathematical structure developed by L. Zadeh in
1978 (first volume of Fuzzy Sets and Systems). Since
possibility is not additive, a dual to possibility, necessity,
is required to have a more complete mathematical
structure. Necessity was developed by Dubois and Prade
in 1988. In particular, if we know the possibility of a set
A, it is not known what the possibility of the complement
of a fuzzy set A, A C,in contradistinction to probability.
The dual to possibility, necessity is required. Given the
C
possibility of a set A, the necessity of A is known.
Congresso Brasileiro de Sistemas
Fuzzy
35
Possibility Distributions - Construction
There are at least four ways to construct possibility and necessity
distributions:
1. Given a set of probabilities (interval-value probabilities):
  { p ( x ), x   ,   I index set}
P os ( x )  sup p  ( x ), N ec ( x )  inf p  ( x )
 I
 I
2. Given an unknown probability p(x) such that
p ( x )   f ( x ), f ( x )  construct consistent necessity/p ossibility pairs


p ( x )  [ N ec ( x ), Pos ( x )].
Jamison/Lodwick 2002, Fuzzy Sets and Systems
3. Given a probability assignment function m whose focal elements
are nested, construct necessity/possibility distributions which are
the plausibility/belief functions of Demster and Shafer theory.
Here probabilities are know on sets (not elements of sets)
Congresso Brasileiro de Sistemas
Fuzzy
36
4. Entities of Analysis – Dual Possibility Distributions
A fuzzy interval, generates a possibility and necessity pair.
Congresso Brasileiro de Sistemas
Fuzzy
37
Possibility Dubois, Kerre, Mesair, and Prade 2000
Handbook, 3 probabilistic views of a fuzzy interval
1. The imprecise probability view whereby M encodes a set of
(cumulative) probability measures shown in Figure 3 between the
dashed blue line (possibility) and the dotted green line (necessity).
This is our first construction.
2. The pair of PDFs view whereby M is defined by two random
variables x⁻ and x⁺ with cumulative distributions in blue and green
of Figure 3. This is our fourth construction.
3. The random set view whereby M encodes the one point coverage
function of a random interval, defined by the probability measure on
the unit interval (for instance the uniformly distributed one) and a
family of nested intervals (the α-levels), via a multi-valued mapping
from (0,1] to ℝ, following Dempster. This is our third construction.
Congresso Brasileiro de Sistemas
Fuzzy
38
III. Fuzzy/Possibilistic Optimization
• We turn our attention to optimization
• First a classification
• Semantics and solutions methods
Congresso Brasileiro de Sistemas
Fuzzy
39
What We Know About Optimization
Optimization models are normative models that are most
often constrained. Thus, from this perspective, there are
three key parts to a fuzzy, possibility, and interval
optimization problem
 The normative criterion (or criteria) – the (realvalued) objective function
 The constraint set – that which defines the limits of
resources under which the model operates
The relationships (soft/flexible?)
Congresso Brasileiro de Sistemas
Fuzzy
40
An Example of Fuzzy/Possibility Optimization
The radiation therapy problem (RTP)
For a given radiation machine, obtain a set of beam
angles and beam intensities at these angles so that
the delivered dosage kills the tumor while sparing
surrounding healthy tissue through which
radiation must travel to reach the tumor.
Congresso Brasileiro de Sistemas
Fuzzy
41
Congresso Brasileiro de Sistemas
Fuzzy
42
Linear Accelerator
Accelerator Structure
Electrons are emitted from the electron gun, reach ~0.99c (c=the speed of light) in the accelerator structure and for
photon production (which is all we are concerned with for optimization) the electrons strike a tungsten target
which produces the high energy photons (known as bremsstrahlung x-rays)
Microwave cavities propagating Electric fields used to accelerate electrons in a linear path .
Electron gun
Sends electron bunches
into the cavities, timed
with the E fields.
Congresso Brasileiro de Sistemas
Fuzzy
43
X-ray Target
Converts electron beam to
x-rays through
bremsstrahlung, (it is
retractable).
Bending Magnet
Achromatic focusing of
electron beam before
striking target.
Flattening Filter
Flattens x-ray beam
intensity, retractable.
Primary Collimator
Scattering Foil
Flattens electron
beam intensity
through multiple
scattering (it is
retractable).
Mirror
Multi-Leaf Collimator
Carrousel
Carries flattening filter and
scattering foils.
Congresso Brasileiro de Sistemas
Fuzzy
44
Multi-leaf collimators shape the
photon beam to conform to the target
(conventional 3D treatment) or to
modulate the dose (Intensity
Modulated Radiotherapy, IMRT)
Shaping the Radiation Beam
Multileaf Collimator
Congresso Brasileiro de Sistemas
Fuzzy
46
y
S  (,  )
b ( ,  )
r
  (r , )


x
( ,  / 2   )
tumor
critical organ 1
critical organ 2
body
Ss
Source
S
…
XsM
P
T
S1
Xsm
Xs3
pixel
Xs2
Xs1
Congresso Brasileiro de Sistemas
Fuzzy
48
Congresso Brasileiro de Sistemas
Fuzzy
49
pencil
pixel
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2, 19
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
5, 24
0
.172
.828
.5
0
0
.172
.828
0
0
0
.172
0
0
0
0
6, 23
.5
.828
.172
0
0
.5
.828
.172
0
0
.5
.828
0
0
0
.5
10, 27
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
14, 31
0
0
0
.5
0
0
.5
.828
0
.5
.828
.172
.5
.828
.172
0
15, 30
0
0
.828
.5
0
.828
.5
0
.828
.5
0
0
.5
0
0
0
12
17
11
10
B
B
9
4
13
16
B
C1
C2
B
3
19
B
T
B
2
20
B
B
18
1
1
4
25
26
27
28
Congresso Brasileiro de Sistemas
Fuzzy
50
The Flexible/Possibility Optimization Model
J
m in f ( x ) 
x
(m inim ize total radiation)
j
j
subject to:
 A x  Tideal  p t , p t  0, t indices of tum or voxels
T
 A x  Tideal  q t , q t  0,
T
 A x  d ideal  rc , rc  0, c k indices of critical tissue
T
ck
k
k
x0
Congresso Brasileiro de Sistemas
Fuzzy
51
Optimization Under Uncertainty - RTP
The general uncertainty optimization model for RTP
considered here is:
~T x
min c
subject to
~ ~ ~
: Bx  b
0  x  x (max beam intensity)
where
 Abody

Acriticals
B 
 Atumor

  Atumor
~


b body

~

b criticals
 and b~  
~


b tumor


~
  btumor

Congresso Brasileiro de Sistemas
Fuzzy






52
Observations About the RTP
• Objective function – (1) probability of turning a healthy
non-cancerous cell into a cancerous cell. (2) Minimize the
maximum radiation to a cancer cell. (3) Minimize total
radiation. (4) All three.
• Matrix – the classification of a pixel – fuzzy, the location
of a pixel (breathing) – fuzzy location is transitional.
• Right-hand Side – a target or possibility?
• A radiation oncologist would like any solution that
satisfies the constraints, though one which gives a minimal
damage to health cells is preferable. The best treatment is
100% radiation needed to the tumor and 0% to all other
parts – impossible. A radiation oncologist is a satisficer!
Congresso Brasileiro de Sistemas
Fuzzy
53
Taxonomy – Fuzzy and Possibility Optimization
1. Flexible Optimization – Fuzzy (Zadeh/Bellman 1970,
Tanaka/Okuda/Asai 1974, Zimmermann 1976)
2. Single Distribution Optimization – Single Possibility or
Single Necessity Optimization (Inuiguchi 1991,
Lodwick/Jamison 1997)
3. Dual Distribution Optimization – Paired Possibility
Necessity Optimization (Thipwiwatpotjana/Lodwick 2009,
Thipwiwatpotjana 2010) – Risk of taking a particular action
4. Mixed Flexible/Evaluation Optimization – Fuzzy and
Possibility  Random Set Optimization (Lodwick/Jamison
2008, Lodwick/Thipwiwatpotjana 2009, Thipwiwatpotjana
2010)
Congresso Brasileiro de Sistemas
Fuzzy
54
Harvey Greenberg: A Structural View of Optimization
rim
opt z  c x
T
B
r
O
Rel b i
Ax
D
m
Y
This view (rim and body) is useful in deterministic linear
programming since it partitions the problem into
anatomically useful elements for duality and
mathematical programming modeling languages like
AMPLE, GAMS since the data (parameters) A, b, and c are
separated from the “model.”
55
The General Programming Problem
The general deterministic mathematical
programming problem we consider here is:
z  m in f ( x , c )
subject to:
g i ( x , a )  bi , i  1,
h j ( x , d )  e j , j  1,
(1)
,M1
, M 2.
c is the objective coefficient rim value
b and e are the right-hand side rim values
a and d are the body coefficient values
56
1. Flexible Programming
a) Soft constraints relationships ≤ and/or = that
take on a flexible meaning. For example, we may
have a stated constraint to be "Come as close as
possible or come as close as possible without
violation some hard constraints." The extent of the
flexibility will need to be specified. For our RTP
example, a constraint on a critical organ in the path
of the radiation beam may be, "Come as close as
possible to 20 units of radiation for the spinal chord,
but never exceed 30 units of radiation."
Congresso Brasileiro de Sistemas
Fuzzy
57
Flexible Programming
b) The objective function expresses an
acceptable set of desired targets. For example, for
the RTP example, two objective function targets
might be, “Try to stay below R units of total
radiation delivered to the lungs and minimize the
probability of turning a healthy cell into a
cancerous one.” The objective function becomes
a (flexible) constraint.
Congresso Brasileiro de Sistemas
Fuzzy
58
Flexible Programming
c) The right-hand-side value of a constraint is
a fuzzy interval which is semantically a target.
For example, for the RTP example, we might
have, the constraint, "Do not deliver less than 58
units of radiation to the tumor, preferably between
59 units and 61 units, but never exceed 62 units."
This is depicted on the next slide.
Congresso Brasileiro de Sistemas
Fuzzy
59
When the fuzzy interval right-hand side value is semantically
a target, we have a flexible constraint resulting is a flexible
programming problem.
Congresso Brasileiro de Sistemas
Fuzzy
60
Fuzzy Optimization: Decision Making for Flexible
(Fuzzy) Programming
Given the set of decisions   { x  domain D   n .}
Find the optimal decision, that is,
sup
x
h ( F ( x ),..., F ( x )),
1
n
w here h :[0,1]n  [0,1]
(1)
is an aggregation operator (such as max). Observe
that the decision space  is a real-valued set (also
called crisp set).
Congresso Brasileiro de Sistemas
Fuzzy
61
2. Single (Possibility) Distribution Optimization
a) Interval, fuzzy interval, possibility cost
coefficients of the objective function rim
parameter c with real valued coefficient constraint
coefficient a, b, d, e ∈ ℝ. In this case we have a
family of objective functions and we need to
minimize of this family of functions which is
typically done using an evaluation function. Here
the objective is not a target, but inherently has
uncertainty in its cost rim value.
Congresso Brasileiro de Sistemas
Fuzzy
62
Single (Possibility) Distribution Optimization
b) The objective function parameter c ∈ ℝ, a so called
“crisp” value where we have interval, probability,
possibility, fuzzy interval, and one or two of the following
- parameters a, d interval, fuzzy interval, possibility and/or
right-hand values b, e are possibility. When a, d are
possibility, we have uncertainty (lack of specificity) in the
model itself. When the values b, e are possibility we do
not have a target (semantically or data-wise) but we have
uncertainty. While the representation (as a fuzzy interval)
is the same, the semantics and methods are radically
different.
Congresso Brasileiro de Sistemas
Fuzzy
63
Single Distribution Optimization
To repeat: The constraint depicted in Figure 4, when it
occurs as a right-hand side rim value, may also be
interpreted as information deficiency, lack of specificity,
that is, a possibility distribution. This is uncertainty in
the right-hand side rim data. This is radically different
than being a target with preferential values even though
both target and uncertainty may be (are) represented as
fuzzy intervals!
Congresso Brasileiro de Sistemas
Fuzzy
64
Decision Making for Possibility
Given the set of crisp decisions   { x  domain D   n .}
and the set of possibility distributions representing the
uncertain outcomes from selecting decision

x   , denoted Ψ x  { Fˆ xi , i  1,..., n},
find the decision that produces the “best” (optimal) of
possible outcomes with respect to an outcome ordering U.
That is,
Congresso Brasileiro de Sistemas
Fuzzy
65
Single Distribution Optimization
su p
x
U ( Fˆ x1 , ..., Fˆ xn ),
(2)
w h ere U ( Fˆ x1 , ..., Fˆ xn ) rep resen ts th e "evalu atio n " (o rd erin g ) o f
th e set o f p o ssib le o u tco m es Ψ  { Ψ
F o r ex a m p le, if Fˆ x1

x
| x  } .
2ˆ x1  3ˆ x 2 , th en each
x  ( x1 , x 2 )T in d u ces/g en erates a p o ssib ility
d istrib u tio n via th e exten tio n p rin cip le.
Congresso Brasileiro de Sistemas
Fuzzy
66
Flexible and Possibility Optimization
• Fuzzy decision making selects from a set of crisp
elements ordered by an aggregation operator h whose
domain is the set of vectors [0,1]n (see equation (1)).
The aggregation operator h may be min or a t-norm.
• Possibilistic decision making selects from a set of
crisp elements ordered by an evaluation operator U
whose domain is the set of distributions
Ψ  { Fˆ i , i  1, ..., n},
x
x
(see equation (2)). The evaluation operator U may be
the “expected average.”
Congresso Brasileiro de Sistemas
Fuzzy
67
3. Dual Evaluation Optimization
• When we wish to analyze the risk of taking a decision
based on lack of information, we use upper/lower
bounds on the uncertainty.
• Interval data is transformed into upper/lower
distributions, probability data is transformed into
upper/lower distributions, single possibility is
transformed into upper/lower.
• There are constructions to transform interval-valued
distributions, clouds, and sets of probabilities into
upper/lower distributions
Congresso Brasileiro de Sistemas
Fuzzy
68
4. Mixed (Flexible and Evaluation) Optimization
a) Interval-Valued Probability Measure
Programming - Any of the coefficients a, b, c, d, e
may be interval, fuzzy, possibilistic where there
may be a mixture of types within one constraint
statement. These mixed values can be and should
(must) be transformed into interval-valued
probability distributions or clouds or random sets.
These are the theories that are supersets of
intervals, probabilities, fuzzy sets, possibilities
though arguably, random sets are the most general.
Congresso Brasileiro de Sistemas
Fuzzy
69
Mixed (Flexible and Evaluation) Optimization
b) Random Set Programming - Any of the coefficients
a, b, c, d, e may be interval, fuzzy, possibility where
there may be a mixture of types within one
constraint statement may be transformed into
random sets. Interval-valued probability
optimization, I think, is the most straight forward
approach (easiest to implement).
Congresso Brasileiro de Sistemas
Fuzzy
70
IV. Theoretical Consideration <OSCAR>
A. Geometry
B. Order Relations
Congresso Brasileiro de Sistemas
Fuzzy
71
Interval Arithmetic
The usual interval arithmetic (called here standard interval
arithmetic, SIA) on intervals has no additive or
multiplicative identity – SIA was created independently
by Warmus (1956) Poland, Sunaga (1958) Japan, Moore
(1959) USA.
Interval Addition/Subtraction
L et X
I
X X
I
 [2, 3], then
I
 [2, 3]  [2, 3]
 [2, 3]  [  3,  2]
 [  1,1], not [0, 0]
Congresso Brasileiro de Sistemas
Fuzzy
72
Arithmetic
N O T E : H ow ever , if let
X
I
 [2, 3], and Y = [2,3] then
X
I
Y
I
 [2, 3]  [2, 3]
I
 [2, 3]  [  3,  2 ]
 [  1,1].
W e seek an arithm etic w hich distinguishe s betw een
X
I
 X
I
and X
I
Y
I
even w hen X
Congresso Brasileiro de Sistemas
Fuzzy
I
Y .
I
73
Arithmetic
Multiplicative inverse (lack of in definitional interval
arithmetic):
X
I
 [1, 2]
X
I
X
I
 [m in{1 / 1,1 / 2}, m ax{1 / 1,1 / 2}]
1
 [ ,1] not [1,1]
2
Congresso Brasileiro de Sistemas
Fuzzy
74
Arithmetic: Consequences of DIA
1. Sub-distributive: XI(YI + ZI)  XIYI + XIZI
2. Multiple instances of a variable, e.g. XIXI + XIYI,
means we will, most often, overestimate.
3. Since fuzzy arithmetic has traditionally been
implemented as definitional interval arithmetic on αcuts of fuzzy intervals, the above problem is
compounded in the setting of fuzzy sets over real
numbers.
Why should we care? When doing fuzzy arithmetic (ala
Kaufmann and Gupta), the usual interval arithmetic on
alpha levels may, usually do, lead to overestimations
and thus not the tightest constraints. This is a
characteristic of the arithmetic used NOT the
Congresso Brasileiro de Sistemas
75
underlying problem.
Fuzzy
Constraint Fuzzy Intervals and Gradual Numbers
Lodwick 1999 – Constraint Interval Arithmetic (CIA – not
to be confused with an institution, the constraint
intelligence agency). We start by redefining an interval
as the relationship (function, graph) of a single variable
X (  X )  { x | w X  X  x , 0    1, w X  x  x }.
I
As a graph, this representation is a set parameterized by a
single variable λ where the endpoints are data/inputs
and the variable is constrained to lie between 0 and 1,
hence the name.
As a function it is linear function of a single variable with
non-negative slope over a compact set [0,1]
Congresso Brasileiro de Sistemas
Fuzzy
76
Constrained Arithmetic: Operations
Z
I
 [ z, z]  X
 {z | z  x
w here z 
I
Y
I
w e w ill drop the superscript I
y ,  x  X (  X ), y  Y (  Y ), 0   X ,  Y  1}
m in Z , and z 
0   X ,  Y 1
m ax Z
0   X ,  Y 1
Consequences – operations on functions
X  X  { w x  x  x    w x  x  x }
 [0, 0 ]
X  X  { w x  x  x    w x  x  x  , 0  X }
 [1,1]
Congresso Brasileiro de Sistemas
Fuzzy
77
Constraint Interval Arithmetic
• Remark 1: CIA has an additive identity, namely,
[0,0] and a multiplicative identity, namely,
[1,1] . And CIA distinguishes between [x]-[x]
and [x]-[y], when [x]=[y].
• There is a relationship between CIA and Klir’s
earlier 1997 paper “Fuzzy arithmetic with
requisite constraints”, FSS 91 (1997). His
results are the same for each α-level as those of
CIA. However, our parameterization using λx
and the use of constrained global optimization
on 0≤ λx ≤1 is different and more general since
Klir’s arithmetic is case-based.
Congresso Brasileiro de Sistemas
Fuzzy
78
Gradual Number (2008)
Gradual Number (Fortin, Dubois, Fargier,
2008) is an assignment of a unique value
for each α-cut (viewed on the y-axis). The
next two slides will make this clear.
Congresso Brasileiro de Sistemas
Fuzzy
79
Gradual Numbers
From a fuzzy interval to a gradual number
Congresso Brasileiro de Sistemas
Fuzzy
80
Gradual Numbers
Examples of assignment functions, that is, gradual numbers
(r(α ), s(α), and t(α) for 0 ≤ α ≤ 1)
Congresso Brasileiro de Sistemas
Fuzzy
81
Constraint Fuzzy Arithmetic (CFA)
CFA, when applied to fuzzy interval arithmetic α-level by αlevel, is simply CIA applied α –level by α –level. This is
illustrated in the following example. A gradual number is
an element of a fuzzy set (interval). From the CFA point of
view, an element of a fuzzy set (interval) is simply
X (  X ( ))  { x | w X ( )  X ( )  x  , w X ( )  x   x  ,
I
0   X ( )  1, 0    1}.
This is simply an assignment of one (and only one) lambda
value  ( ) for each α –level, a single instantiation (pick one
value from each α –level interval) for each α. Thus,
I
X (  X ( )) is a gradual number and an element of the fuzzy
set (interval).
Congresso Brasileiro de Sistemas
82
Fuzzy
Optimization of Constraint Fuzzy Intervals and
Gradual Numbers
• Elizabeth (Untiedt) Stock 2010 – "Gradual
numbers and fuzzy optimization," PhD Thesis,
University of Colorado Denver, Department of
Mathematical and Statistical Sciences.
• Phantipa Thipwiwatpotjana 2010 - Linear
programming problems for generalized
uncertainty," Ph.D. Thesis,University of Colorado,
Department of Mathematical and Statistical
Sciences.
Congresso Brasileiro de Sistemas
Fuzzy
83

similar documents