Transcript Controlling the odds of extreme events

Moment based optimization
Why ignorance is bliss
Bart P.G. Van Parys
Automatic Control Laboratory, ETH Zürich
www.control.ethz.ch
Introduction
Calculate and control the odds (frequency) of extreme events occurring.
We are usually ignorant about the exact distribution .
How much information is really required to make meaningful estimates
or informed decisions ?
• Two 19th century results, one 21th century generalization.
C.F. Gauß (1821)
P.L. Chebyshev (1867)
Simple example : Belgian population
Example : determine percentage of Belgians taller then 190 cm based on
• Mean : =171.5 cm,
• Std. dev. : =7.5 cm ?
Quetelet resorted to omniscient approach
Belgian males
1
0.9
0.8
Chebyshev’s inequality drops normality
0.7
probability
0.6
0.5
0.4
0.3
0.2
0.1
0
140
150
160
170
180
length [cm]
190
200
210
Simple example : Belgian population
Example : determine percentage of Belgians taller then 190 cm based on
• Mean : =171.5 cm,
• Std. dev. :
=7.5 cm ?
Quetelet resorted to omniscient approach
Chebyshev’s inequality drops normality
Gauß uses unimodality
1 Calculating t he odds of ext reme event s
Generalized Chebyshev
and Gauss bounds
Generalized
probability
bounds
Problem
: What is probability
the worst-case probability
Problem
: Worst-case
of the that t he
n
random
variable
›
falls
out
side
a
set
Ξ
™
R
? Assume
event
based only on
only:
• Mean Mean : µ œ Rn
• Second Second
moment
moment : S = Σ + µµ €
) - €
*
• Open set
Open set : Ξ = x ai x < bi , ’ i = 1, . . . , k
Dist ribution
is unimodal with mode m
• Distribution
is unimodal
Ξ
Σ
µ
m
An infinit e dimensional convex optimization problem:
An infinite
dimensional convex optimization problem :
sup
P(Rn \ Ξ)
P
s.t .
•
•
P œ P (µ, S) f l P n
P (µ, S) = Set of distributions consist ent wit h moments (µ, S)
= Set of distributions consistent with
P n = Set of all unimodal distribut ions
= Set of all unimodal distributions
T heorem (Van Parys 2014) : Equivalent to a finit e dimensional convex problem !
Bart Van Parys
Moment based optimization
D-IT ET Evaluat ion
4
Theorem (Van Parys) : Equivalent to finite dimensional convex problem.
Ignorance is bliss…
•NP hard if distribution is Normal !
Contents
Calculate
the odds
Control
the odds
Controlling the odds of extreme events
Different ways to characterize the uncertain terms
• Bounded uncertainty or known distribution
• Partial moments: minimal statistical information (mean and variance)
Design objectives
• Bound frequency of constraint violation
• Robust performance in some sense
ng the odds of extreme events
Controlling the odds of extreme events
Shape state variance using control policy
e variance
Σ x using t he cont rol policy K
(A + B K ) Σ x (A + B K )
€
+ E
#
› k › k€
$
Ξ
Σx
0
such that
n steady stat e
P œP (0, Σ x ) :
P{ x œΞ}
/
Æ– .
St at e space Rn
Theorem (Van Parys) : Bounding the odds of outliers is a convex
(Van
Parys 2013)
Bounding
thewhen
probability
of outliers
amounts to a conv
constraint
on the: control
policy
constraint
set is symmetric.
on the control policy
’ P œP (µ, S) :
lim sup P{ xk œΞ}
/
Æ– ≈ ∆ K œC.
kæ Œ
constraint set Ξ is symmetric.
Conclusion
A new fundamental result for bounding the probability of extreme
events.
Extends and connects classical methods of Gauß and Chebyshev.
Applications in power systems, control design, machine learning,
economics, etc.
Many extensions and variations are possible :
•Moment ambiguity, multi-modality and symmetry
•Bounds on severity of extreme events
Thank you
Bart P.G. Van Parys
Daniel Kuhn
Paul J. Goulart
Manfred Morari