Stochastic Modeling and Optimization Methods for Critical Infrastructure Protection, Volume 2 E-Book
142,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Fachliteratur
- Serie: ISTE Invoiced
- Sprache: Englisch
Stochastic Modeling and Optimization Methods for Critical Infrastructure Protection is a thorough exploration of mathematical models and tools that are designed to strengthen critical infrastructures against threats – both natural and adversarial. Divided into two volumes, this first volume examines stochastic modeling across key economic sectors and their interconnections, while the second volume focuses on advanced mathematical methods for enhancing infrastructure protection.
The book covers a range of themes, including risk assessment techniques that account for systemic interdependencies within modern technospheres, the dynamics of uncertainty, instability and system vulnerabilities. The book also presents other topics such as cryptographic information protection and Shannon’s theory of secret systems, alongside solutions arising from optimization, game theory and machine learning approaches.
Featuring research from international collaborations, this book covers both theory and applications, offering vital insights for advanced risk management curricula. It is intended not only for researchers, but also educators and professionals in infrastructure protection and stochastic optimization.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 338
Veröffentlichungsjahr: 2025
Ähnliche
Table of Contents
Cover
Table of Contents
Title Page
Copyright Page
Preface
PART 1: Mathematical Models and Methods for Risk Mitigation and Defending Critical Infrastructure
Introduction to Part 1
1 Three Approaches to Decision-making Under Risk and Uncertainty for the Critical Infrastructure Protection
1.1. Introduction
1.2. Decision-making in stochastic conditions of risk and uncertainty
1.3. Some traditional risk assessments and worst-case analysis
1.4. Adversarial risk analysis in conditions of terrorist threat
1.5. Conclusion
1.6. Acknowledgments
1.7. List of abbreviations
1.8. References
2 Models of Anti-Terrorist Protection
2.1. Area control tasks
2.2. Simulation of attack and passive defense
2.3. Modeling attack on a market: a linear programming model
2.4. A probabilistic version of the problem of attacking the objective function
2.5. Modeling an attack on resources of optimal systems
2.6. Modeling an attack on the transport system
2.7. Models of protection of transport and information networks
2.8. Stochastic models of passive protection of transport and information networks
2.9. Acknowledgments
2.10. References
3 Allocation of Resources for the Critical Infrastructure Protection
3.1. The hierarchical dynamic programming
3.2. Examples of resource allocation problems
3.3. Conclusion
3.4. Acknowledgments
3.5. References
4 Simulation of the Defender–Attacker Game for Critical Objects Protection
4.1. Introduction
4.2. A simple strategic attacker–defender game
4.3. Generalizations
4.4. Further generalization
4.5. Conclusion
4.6. Acknowledgments
4.7. References
5 Making Decisions and Motion Control in Conditions of Conflict
5.1. Introduction
5.2. Problem statement
5.3. Pontryagin’s first direct method
5.4. Schemes of the method of resolving functions
5.5. Scheme with fixed points of the terminal set solid part
5.6. Connection of the first direct method with the method of resolving functions
5.7. Conclusion
5.8. Acknowledgments
5.9. References
6 Contemporary Stochastic Quasi-gradient Algorithms
6.1. Introduction
6.2. A stochastic optimization problem
6.3. Stochastic approximation
6.4. Application of stochastic quasi-gradient algorithms in machine learning
6.5. Stochastic gradient methods
6.6. Conclusion
6.7. Acknowledgments
6.8. References
7 Two Classes of Optimization Problems for Arcs Capacities Modernization for Fault-tolerant Networks
7.1. Basic concepts for a fault-tolerant network
7.2. Basic LP-problems A and P
7.3. Boolean problems A and P
7.4. Convex problems A and P: decomposition algorithms
7.5. Software: programs SolverA and SolverP
7.6. Acknowledgements
7.7. References
PART 2: Cyber Security of Critical Infrastructure Facilities
Introduction to Part 2
8 Digital Authentication of the Type “friend-or-foe” by Means of One-time Signatures
8.1. Introduction
8.2. Coalition group
8.3. Authentication in public-key cryptography
8.4. Authentication through digital signatures and sigma protocols
8.5. A general description of a “friend-or-foe” authentication protocol using OTSs
8.6. References
9 Main Directions and Basic Mathematical Ideas of Cryptographic Information Security
9.1. Introduction
9.2. Problems and aspects of information security, basic concepts of cryptographic information security
9.3. Classification of cryptosystems
9.4. Symmetric cryptography
9.5. Asymmetric cryptography: public key cryptosystems
9.6. Conclusion
9.7. References
10 Cybersecurity Investments in Networks
10.1. Introduction
10.2. Cybersecurity in SCNs
10.3. Numerical experiments for networks
10.4. Critical and risky SCNs
10.5. Acknowledgements
10.6. References
List of Authors
List of Authors
Index
Summary of Volume 1
Other titles from iSTE in Mathematics and Statistics
End User License Agreement
List of Tables
Chapter 1
Table 1.1. Risk-matrix for events on the transport infrastructure. For a colo...
Table 1.2. Game in installing a new scanner
Chapter 3
Table 3.1. Fictitious input data (costs associated with different levels of pr...
Chapter 6
Table 6.1. Comparison of the speed of convergence of algorithms on a smooth o...
Table 6.2. Comparison of the behavior of algorithms on a non-smooth, non-conv...
Chapter 7
Table 7.1. Scenario 0F; 0.5F; 1F for the network Net (4,4)
Table 7.2. Minimal total cost of arcs capacities for the network Net (6, 16)
Table 7.3. Minimal in terms of total costs for value and creation throughput ...
Chapter 10
Table 10.1. Key metrics for example 1 scenarios
Table 10.2. Key indicators for the scenarios of example 2, equilibrium transa...
List of Illustrations
Chapter 2
Figure 2.1. Examples of vertex covers in two graphs
Figure 2.2. Examples of the smallest vertex covers in the graphs above
Chapter 4
Figure 4.1. Graph of function [4.5]
Figure 4.2. Graph of function [4.7]
Chapter 7
Figure 7.1. Network Net (4,4), four nodes and four arcs
Figure 7.2. Single failures of the network Net (4,4) for scenario 1F
Figure 7.3. Network Net (6, 16) structure
Figure 7.4. Nested block structure of constraint matrix of LP-problems A and ...
Figure 7.5. Block diagrams of the programs SolverA and SolverP
Chapter 9
Figure 9.1. General scheme of secret communication
Figure 9.2. Scytale cipher and Aristotle’s cryptanalysis (see: https://en.wik...
Figure 9.3. Enigma encryption machine (see: https://en.wikipedia.org/wiki/Eni...
Figure 9.4. Six common block cipher modes of operation for encrypting (see: h...
Figure 9.5. With Diffie–Hellman key exchange, two parties arrive at a common ...
Guide
Cover Page
Table of Contents
Title Page
Copyright Page
Preface
Begin Reading
List of Authors
Index
Summary of Volume 1
Other titles from iSTE in Mathematics and Statistics
Wiley End User License Agreement
Pages
iii
iv
xi
xii
1
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
53
54
55
56
57
58
59
60
61
62
63
64
65
67
68
69
70
71
72
73
74
75
76
77
78
79
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
147
149
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
235
236
237
239
240
241
243
244
245
246
247
248
249
250
251
252
253
254
254
255
257
Series EditorNikolaos Limnios
Stochastic Modeling and Optimization Methods for Critical Infrastructure Protection 2
Methods and Tools
Edited by
Alexei A. Gaivoronski
Pavel S. Knopov
Vladimir I. Norkin
Volodymyr A. Zaslavskyi
First published 2025 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUKwww.iste.co.uk
John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USAwww.wiley.com
© ISTE Ltd 2025The rights of Alexei A. Gaivoronski, Pavel S. Knopov, Vladimir I. Norkin and Volodymyr A. Zaslavskyi to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s), contributor(s) or editor(s) and do not necessarily reflect the views of ISTE Group.
Library of Congress Control Number: 2025931358
British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-83669-028-3
Preface
The book presents mathematical models and tools for enhancing critical infrastructure protection against natural threats and adversarial attacks. The book consists of two volumes; the first is devoted to stochastic modeling of various critical sectors of economics and their interconnections, and the second considers mathematical tools for enhancing critical infrastructure protection.
These two volumes offer new results on risk assessment methods, taking into account the large number of systemic connections between the structures of the modern technosphere and the graded nature of damage probability from natural and human-made disasters. The cumulative effect from various risk sources will be investigated, which becomes an important generator of uncertainty and instability due to the nonlinear increase in system vulnerability and a decrease in its adaptation capabilities, when small impacts cause unstable system behavior. The generalizations of the attack and defense antagonistic game, and the rational distribution of defense resources are considered, and methods for solving the corresponding optimization problems are proposed. New mathematical methods of machine learning, based on quasi-gradient methods of stochastic programming, are reviewed.
The research is based on the authors’ results on the theoretical foundations of stochastic systems with aftereffect, stochastic optimal control theory, robust methods of non-smooth and stochastic optimization for solving special optimization problems with a large number of variables and constraints, methods of multi-criteria dynamic optimization, methods of solving two-level stochastic programming problems, stochastic minimax game problems, and graph theory optimization problems. Basic concepts, methods and directions of cryptographic protection of information are considered. The working principles of classical cryptography ciphers and the main results of Shannon’s theory of secret systems are presented. The obtained theoretical results will be applied to solving important problems of risk assessment and monitoring the state of critical infrastructure objects.
The chapters are the result of a series of international projects involving leading scientists from various research institutes in Austria, Norway, Ukraine and other countries in the field of modern stochastic optimization and decision making. These projects were aimed at developing a curriculum for risk management at the master’s and doctoral levels. The studies included in this book contain new research results and also take into account the requirements of research-based education on these topics.
Acknowledgments
Work on parts of the book was supported by the grant CPEA-LT-2016/ 10003 “Advanced collaborative program for research based education on risk management in industry and services under global economic, technological and environmental changes: enhanced edition” of Norwegian Directorate for Higher Education and Skills (HKDIR), managed by the Norwegian University of Science and Technology (NTNU), Trondheim, Norway. It was also supported by the project 2020.02/0121 “Analytical methods and machine learning in control theory and decision-making in conditions of conflict and uncertainty” funded by the National Research Foundation of Ukraine. The work was also supported by the joint project between the International Institute for Applied Systems Analysis (IIASA) and the National Academy of Sciences of Ukraine (NASU) on “Integrated robust modeling and management of food-energy-water-land use nexus for sustainable development” (22-501) and by the projects 0122U00052 and 2.3/25-P of the National Academy of Sciences of Ukraine.
Alexei A. GAIVORONSKIPavel S. KNOPOVVladimir I. NORKINVolodymyr A. ZASLAVSKYI
March 2025
PART 1Mathematical Models and Methods for Risk Mitigation and Defending Critical Infrastructure
Introduction to Part 1
Three approaches to decision-making under risk and uncertainty for the critical infrastructure protection are considered. The first approach concerns protection against natural (stochastic) risks. This consists of reducing stochastic optimization problems using appropriate risk measures to deterministic problems. For this, the apparatus of polyhedral coherent measures of risk is proposed. A second approach is to use worst-case analysis to model countering an intelligent adversary seeking to inflict maximum damage. Some examples of “attacker–defender” and “defender–attacker” models are considered. A third approach uses the adversary risk analysis technique against terrorist risks.
This section also gives an overview of a number of mathematical models and problems for planning anti-terrorist and special actions. These are problems of monitoring a territory, protecting critical infrastructure (described by optimization models), interdicting transport and information networks. It is shown that many territory control problems can be reduced to well-known optimization problems on graphs, shortest paths search and minimal covering on graphs. The problems of protecting critical infrastructure and interdicting networks are reduced to stochastic minimax game problems.
Adaptation of the operations research models and methods to planning of the critical infrastructure protection is considered. Adaptation of these models includes taking into account stochastic, informational and behavioral uncertainty of terrorists. In particular, relevant generalizations of the antagonistic attack–defense game and optimal allocation of protective resources are considered, and methods are proposed to solve the occurring optimization problems.
A two-person (defender–attacker) game simulator is described. The strategies of the players’ model attack and defend resource allocations at the protected objects. The simulator evaluates (by multiple stochastic modeling) the pay-off (gain) function of the game under fixed strategies of the players. The included optimizer finds the optimal strategy of one player under fixed one of the other.
New mathematical models and methods are proposed for solving and controlling movement in conditions of conflict and uncertainty, in particular, the strategies of intercepting moving targets in conditions of counteraction.
Mathematical models, methods of non-differentiable optimization and software for solving problems of finding parameters of fault-tolerant networks, are described. Optimization models of the specified problems are presented in the form of special problems of nonlinear and partially discrete programming with a network structure of the matrix of constraints. The developed algorithms for their solution are based on effective implementations of subgradient methods with space transformation and take into account the structural features of optimization models.
Note
Introduction written by Pavel S. KNOPOV and Vladimir I. NORKIN.
1Three Approaches to Decision-making Under Risk and Uncertainty for the Critical Infrastructure Protection
Three approaches to decision-making under conditions of risk and uncertainty for the protection of critical infrastructure are considered. The first approach concerns protection against natural (stochastic) risks. This consists of reducing stochastic optimization problems using risk measures to deterministic optimization problems. In this connection, the apparatus of polyhedral coherent measures of risk is described. The second approach is to use worst-case analysis from game theory to model countering an intelligent adversary seeking to inflict maximum damage. Examples of “attacker-defender” and “defender-attacker” models are considered. In conditions of terrorist risk, when the attacker’s actions are not sufficiently predictable to use classical game theory, the approach called adversary risk analysis is considered.
1.1. Introduction
Critical infrastructure (CI) are systems whose failure not only affects the security and socioeconomic condition of states, but can also cause cascading destructive processes beyond their borders. Usually, such systems include the following sectors: chemical; communication; critical industries; dams; defense industry; extraordinary events; energetic; financial services; food and agriculture; public services; health care; information technologies; nuclear reactors, materials and waste; transport services; water supply and drainage, etc. (Gheorghe et al. 2018).
The problems of protecting CI and increasing its sustainability are extremely important for every state. This is especially relevant at the present time, when the international security system has been destroyed and a new axis (Russia, Iran and North Korea) supported by China has formed. The risks of military, terrorist, information and other threats have increased dramatically. In turn, global climate processes and the complexity of technical systems significantly increase the threat of abnormal natural phenomena and potential man-made disasters. In such a situation, CI objects can be affected by both natural (man-made) catastrophic phenomena and malicious enemy attacks aimed at causing economic damage and destabilizing the sociopolitical situation.
For example, Russia’s current war against Ukraine is accompanied by the occupation of territory, genocide of the population and large-scale attacks on CI: energy, education, medical, port, dam, agricultural and other facilities of the country. In particular, due to the full-scale invasion of Russia, according to estimates as of May 2024 by the Kyiv School of Economics (Piddubnyi and Goriunov 2024), only the energy sector of Ukraine has suffered direct losses and indirect financial losses in the amount of $56.2 billion. Note that 18 GW of power generating capacity was occupied, in particular, the Zaporizhzhia Nuclear Power Plant; the Kakhovska and Dniprovska hydroelectric power plants and the Zmiivska and Trypilska thermal power plants were completely destroyed; the Ladyzhynska, Burshtynska, Dobrotvirska, Kurakhivska, Kryvorizka and Prydniprovska thermal power plants suffered critical damage of over 80%. About half of the high-voltage power transmission substations were damaged, and all oil refineries and a significant part of the infrastructure for storing oil and oil products were destroyed.
CI protection is a sufficiently complex systemic problem that requires the involvement of a wide range of methods of system analysis and operations research. Consider the specifics of decision-making in conditions of risk and uncertainty for practical tasks. As a rule, decisions are made in them when it is unknown which of the scenarios of the development of events will be implemented in future and which parameters will describe the accompanying processes. For such problems, an adequate methodology and appropriate mathematical techniques are necessary.
Highlight several types of threats that determine the specifics of the mathematical technique used in such conditions. First, CI must be protected from various natural and man-made disasters of a stochastic (non-malicious) nature. This type of uncertainty is modeled using random variables with known or partially known distributions using stochastic risk analysis.
Second, decisions on the CI protection can be made in the context of countering an intelligent adversary. In this case, the process uncertainty is related to the potential actions of the adversary, which, in turn, depend on ours. In such a situation, we must solve the problem simultaneously for ourselves and the adversary, finding equilibrium situations with optimal strategies for each of them. If the adversary seeks to inflict maximum damage, such decisions are based on the worst-case analysis and are described by classical game theory. The objective functions of players are assumed to be known, and minimax strategies of the participants are proposed as solutions. Such games are called zero-sum games because the objective functions of the participants are opposite and each of them wins at the expense of the other.
Third, in the conditions of a terrorist threat, the attacker (terrorist) can pursue their own goals and not seek to cause maximum damage. In addition, we may not know the true goals of the attacker and their potential for choosing a strategy. For example, a terrorist planning an attack on CI may not have strategic thinking or seek to achieve their own goals. Information about the attacker, their resources and intentions is not always available. Such problems do not fit into the framework of classical game theory; for them, we will consider the approach called adversarial risk analysis (ARA) (Banks et al. 2016).
The above considerations determined the content and structure of the chapter, which consists of the following three parts. The first part deals with the methods of finding optimal solutions under conditions of stochastic uncertainty. The method of quantitative risk assessment using appropriate risk measures, which are taken into account as one of the criteria for decision-making, is described.
In the second part, the approach of classical game theory is considered, which involves the worst-case analysis and the search for minimax strategies of players. Some “defender–attacker” and “attacker–defender” models for problems of the CI protection are given (Brown et al. 2006; Lewis 2015).
In the third part, the ARA from Banks et al. (2016) is considered for problems of the protecting CI under a terrorist threat, which offers a technique for finding solutions in models of interaction with the adversary that do not fit into the framework of classical game theory.
Note that the author’s own results are given in the first part of the chapter, and the next two discuss results from Brown et al. (2006); Cox (2008a, 2008b); Lewis (2015); Banks et al. (2016) and Gheorghe et al. (2018).
1.2. Decision-making in stochastic conditions of risk and uncertainty
1.2.1. Definition, classification of risks and assessment procedure
Under conditions of risk and uncertainty, we understand the non-determinism (ambiguity) of scenarios of the development of processes under study, the consequences of which significantly depend on some random (uncertain) parameters. For example, the functioning of a CI object in the event of a flood depends on many factors, such as: weather conditions, the topography of the area and its hydrophilic properties, the carrying capacity of drainage channels, the presence of protective structures, etc. Some of these (weather conditions) are random in nature, which creates corresponding conditions of uncertainty.
By uncertainty, we mean the impossibility of accurately describing certain consequences (results) that may depend on events or processes of various natures at risk – the possibility of unfavorable consequences caused by uncertainty, which are described by potential losses (damages, values, etc.).
Uncertainty can be described by a random variable (r.v.) with a known or unknown probability distribution. In the pioneering work (Knight 1931), situations with known distributions of r.v. are named by conditions of risk, and those in which nothing is known about the distributions are named by conditions of uncertainty.
However, some information about such distributions must be gained, since we cannot get “something from nothing” (some conclusions without information). As a rule, in various practical applications, only partial information is known about the distributions of r.v. The presence of a large set of statistical data does not guarantee the identification of the probability distribution, since knowledge of the past does not mean complete knowledge of the future. In the following, we will talk about conditions of uncertainty, without distinguishing them according to terminology into cases of known, partially known or unknown distributions of r.v.
In conditions of uncertainty, it is important to quantify the potential consequences of decisions made. One of the important criteria for this is the quantification (measure) of risk in the form of potential losses, which is used to assess the optimality of decisions in such conditions. It is clear that the higher the risk, the more careful decisions should be made. The risks for CI objects, given their purpose, can be very significant.
According to the classification by Proske (2008), risks are (1) natural (earthquakes, floods, storms, volcanoes, etc.), (2) technical (breaks of dams, breakdowns of technical systems, aircraft crashes, etc.), (3) health (diseases, epidemics, bioterrorism, etc.) and (4) social (war, terrorism, the poor, etc.). However, such a simple classification is not exhaustive. For example, the catastrophic events at Fukushima in 2011 were caused by the combination of an earthquake and tsunami (natural risks) with a nuclear plant accident (technical risks). Therefore, such a classification can have a more complex nature.
A typical procedure for assessing the risk of an abstract system is as follows:
identification of sources and risk factors;
generation of scenarios of future events;
modeling system behavior according to scenarios;
risk assessment.
Sources and risk factors can be very different. As a rule, risk has a multidimensional nature and is described by various characteristics and criteria. Thus, a catastrophic event can be described by social consequences, economic losses, destroyed objects, etc. In principle, such consequences can be described by the universal value of potential losses L.
Let us imagine an abstract system. Suppose that after performing the first three steps of the procedure described above, we estimated the consequences of modeling the system for each of the scenarios by the amount of potential losses L. In general, as a result, we will get a certain probability distribution of r.v. L, which describes the possible losses of our system. The key question is how do we assess the risk of r.v. L? More precisely, how do we choose function ρ: X → R that describes the risk of r.v. L as ρ(L)?
There are two simple variants of risk assessment. The first option from probabilistic analysis describes the risk by the average value of losses; the second option (from game theory) from probabilistic analysis describes the risk by the value of the maximum losses (worst-case). Both of these have drawbacks. So, the average losses is an unreliable criterion, and the worst-case losses is too conservative. The average value, in principle, cannot reliably describe features of a r.v. distribution similar to the “average temperature in a hospital”. In turn, worst-case losses often overestimate risk; at the time of their use, large complex systems, in particular, nuclear plants, would hardly be built. Such a risk assessment is fully justified only in the case of uncertainty caused by malicious actions of an enemy.
In conditions of stochastic (non-malicious) uncertainty, similar considerations lead to the need to use the approach developed in the topic of so-called risk measures. Let us consider it below.
1.2.2. Elements of polyhedral coherent measures of risk
There are many functions that have been proposed as risk measures. In particular, the fundamental paper on portfolio theory (Markowitz 1952) considered dispersion in this capacity. A modern view of the classes of functions from which to choose a measure of risk can be found, for example, in Rockafellar (2007) and Rachev et al. (2009).
One of the most famous functions today is the concept of coherent measure of risk (CMR) (Arzner et al. 1999), which consists of the following. Let on a probability space (Ω, Σ, P0), r.v. X : Ω → R of financial flow be given. A function ρ : X → R is called a CMR if it satisfies the following four axioms:
where c is a deterministic monetary value, and inequality “≤FSD” for r.v. in A4 means the first-order stochastic dominance.
As is known from Arzner et al. (1999), this is equivalent to the following representation of ρ(.):
where EP[.] is the mathematical expectation on the probability measure P, and Q is some convex weakly* closed set of probability measures that uniquely defines ρ(.). Such a measure interprets the potential loss of flow X, which is described for each scenario (elementary event) by the value (–X).
In the case when r.v. X describes the losses L (damages, costs, etc.) – quantities characterized by the order “the less, the better” – the corresponding CMR uses a construction similar to [1.1], but without the “minus” sign on the r.v., that is:
Function [1.2] is used in decision-making problems, where minimum functions are used as criteria and in upper constraints, since this means exactly such an order of preferences. Representation [1.1] is used for maximum functions, since in this case the ordering changes to the opposite.
Recall that a finite discretely distributed (d.d.) r.v. X can be represented by a finite set of scenario values x = (x1, …, xn) with corresponding probabilities . The concept of polyhedral CMR (PCMR) was introduced in Kirilyuk (2004), where to description [1.1] (or [1.2]) for d.d. r.v. a polyhedrality of set Q was additionally postulated, that is, its representation in the following form:
where B and c are the matrix and vector of appropriate dimensions.
Following Kirilyuk (2014a), let us divide the description of the set Q from [1.3] into standard and meaningful parts. Let us represent the matrix B and the vector c as:
where B0 and c0 in [1.4] are standard:
and B1 and c1 describe the meaningful part in ratio [1.4], which, in fact, determines the measure of risk in form of [1.2]–[1.5].
The presence of the standard part in the form of B0 and c0 is related to the description in [1.3] of the standard condition for scenario probabilities: , presented in [1.5] in the form of two inequalities: and .
Examples of PCMR
Ex1) Average losses .
Ex2) Maximum losses (worst-case). Then Q is the set of all possible probability measures, so its description lacks a meaningful part in the form of B1 and c1.
Ex3) Conditional value-at-risk (CVaR) (Rockafellar and Uryasev 2000). For CVaRα(X), matrix B1 and vector c1 have the following form:
where I is a unit matrix and p0 is a vector of scenario probabilities.
Other examples of risk measures that fall into this class are also known. Their description can be found in Kirilyuk (2023a), where the definition of PCMR is extended to a more general functional space.
It is not difficult to see that in the description of measures from examples Ex1 and Ex3, there is a vector of scenario probabilities p0, that is, the set Q that determines the risk measure in [1.2] depends on the initial probability measure.
In many practical problems, it is possible to model the scenarios of future events and scenario values of r.v., but it is difficult to identify their scenario probabilities p0. The last ones can only be estimated (from above and below). For such situations, called cases of imprecise probabilities, suitable robust versions are proposed for PCMR.
The above-noted dependence of the set Q on p0 in [1.2] allows us to interpret it as a set-valued mapping (s.m.) Q(p0) that determines the appropriate measure of risk (see examples Ex1 and Ex3). This makes it possible to construct a PCMR in the absence of accurate information on the vector of scenario probabilities p0.
Let it be known only that it belongs to some set (ambiguity) UP, that is, p0 ∈ UP. Then, it is natural to build a measure that takes into account the increase of the risk of potential losses due to the set of UP. For this purpose, its so-called robust version is built based on the initial risk measure ρ0 of form [1.2] and set UP (Kirilyuk 2008):
where Q(p0) is s.m. of initial measure , is the convex closed shell.
Construction in the form [1.6] on the initial measure ρ0 in the form [1.2] is, as a rule, not a trivial task (Kirilyuk 2008). However, it is greatly simplified with a simple set structure of UP, for example, in the case of imprecise scenario probabilities. Then, the vector p0 is represented by its lower and upper estimates pl, pu respectively, and the appropriate set UP has the form:
where inequalities for vectors p is the component-wise ones.
As is known from Kirilyuk (2014a), in this case, the robust versions of measures from examples Ex1–Ex3 are PCMRs, which are described in the forms [1.2]–[1.5] with the following attributes.
Ex1’) For average losses: , .
Ex2’) For maximum losses: B1 and c1 are absent.
Ex3’) For CVaRα: B1 = I, .
Note that more interesting examples of robust versions of PCMR can be found in Kirilyuk (2023a, 2023b).
Let us further consider the use of the PCMR apparatus to reduce stochastic programming (SP) and robust optimization (RO) problems to deterministic optimization problems.
1.2.3. Reduction of SP and RO problems to PCMR problems
The reduction of a wide class of SP and RO problems to PCMR problems is described in Kirilyuk (2015). Let us present some facts from there.
Consider an optimization problem in which there is uncertainty in the form of some random parameter Y:
where the set M has a simple structure, and the meaning of symbol “min” and inequalities in the constraints due to the uncertainty of the parameter Y will be specified later in the text.
Let us have a probability space (Ω, F, P) on which the probability distribution of the parameter Y is specified, that is Y : Ω → Rs; then for each of the elementary events (scenarios) ω ∈ Ω, the value fi(x, Y(ω)), i = 0, …, m is described. So, with measurability fi(x, Y(ω)), i = 0, …, m, their distribution is given. Since the value Y = Y(ω) is completely determined by scenario ω, to shorten the notation, we will write fi(x, ω) instead of fi(x, Y(ω)).
In such a notation, the previously described optimization problem has the form:
Now, problem [1.7] can be specified depending on the preferences of a decision-maker (DM) and certain stochastic criteria for taking into account the values of functions fi(x, ω), i = 0, …, m can be chosen.
For example, “min” f0(x, ω) and fi(x, ω), i = 1, …, m can be understood in the sense of average, the worst-case, or other values of these r.v., and the fulfillment of the constraints can be understood with some probability. As a rule, in the formulation of RO problems, such a criterion is the worst-case value of r.v., although other options are possible.
For example, in SP, we can consider an optimization problem in which the average values of the corresponding functions are used as the criterion and constraints:
Such an optimization (on average) is simple but unreliable, and the consideration of constraints on the average does not seem justified at all. The following statement of the SP problem from Klamroth et al. (2013) looks more rational:
in which, similarly to [1.8], the average value of the criterion is optimized, but the admissibility of solutions (in the sense of constraints) is guaranteed for all possible scenarios ω.
We present the statement of the SP problem, in which the fulfillment of constraints is guaranteed only with certain probabilities:
Now, let us consider some problem statements of RO. Let us start with the following minimax problem, called strict RO in Ben-Tal (2009):
This problem, like [1.9], guarantees the admissibility of solutions for all possible values of ω ∈ Ω, but optimizes the criterion for the worst-case scenario (elementary event) of the distribution.
Sometimes, the minimax criterion is used, but at the same time the requirements regarding the admissibility of the solution in all possible scenarios are relaxed. This condition is guaranteed, only in some nominal scenario . Such a problem is called the reliable RO one in Klamroth et al. (2013):
It is clear that it coincides with statement [1.11] if δi = 0, i = 1, …, m.
It was shown in Kirilyuk (2015) that the presented problems of SP and RO, except for [1.10], can be reduced to the following problem of deterministic optimization with PCMR:
where ρi(.), i = 0, 1, …, m are PCMRs of form [1.2]–[1.5], which are constructed on fi(x.ω), i = 1, …, m.
Note that problem [1.10] reduces to [1.12] only in the following sense. In problem [1.10], probabilistic constraints can be replaced by equivalent ones using value-at-risk (VaR) measure (Jorion 2006):
In turn, the measure CVaRα(.), as is known (Ben-Tal 2009), is the best upper convex approximation of VaRα(.); therefore, inequalities [1.13] can be approximated as:
When applying such a CVaR approximation to the initial probabilistic constraints, the modified problem [1.10] is reduced to form [1.12], in which ρi(.), i = 1, …, m are chosen from Ex3.
Note that a transition from one formulation of the problem to another one in problem [1.12] occurs due to the selection of the appropriate PCMR. Technically, this is realized by choosing the appropriate matrix B1 and vector c1 from [1.4] (see examples Ex1–Ex3).
In the case of imprecise scenario probabilities for risk assessment, it is useful to use robust versions of such measures from examples Ex1’–Ex3’. So, then the measures ρi(.), i = 0, …, m in [1.12] are understood in this sense.
Let us now consider problem [1.12]. It is clear that this statement is not limited to the already mentioned examples of SP and RO problems, but is more general, as it can be applied to any risk measures from the PCMR class.
Besides, this problem is some minimax statement, where the internal extremum is generated by constructing a risk measure. If the functions are convex in x, then [1.12] is a convex programming problem and can be solved by appropriate numerical methods. However, the search for solutions is greatly simplified if functions fi(x.ω), i = 0, …, m are linear, that is, for linear optimization problems.
Let functions fi(x.ω), i = 0, …, m be linear in x, that is , i = 0, …, m, where denotes the scalar product, and the set M has a simple structure, for example, in the form of a convex polyhedron. Then, our initial problem [1.7] has the form:
Turning to problem [1.12], we obtain:
If space of elementary events–scenarios Ω describes a discrete finite distribution, then vectors li(ω) and quantities ai(ω), i = 0, …, m are distributed over n scenarios (ω1, …, ωn), and this distribution can be represented by the corresponding matrices and vectors. Entering the notation:
where lij(ωk) is jth component of lith vector in scenario ωk, taking into account the PCMR construction, we rewrite the problem [1.14] as:
Let us denote for each of the polyhedral sets Qi, i = 0, …, m the matrix and vector representing them as Bi, ci, that is:
describing the standard and substantive parts for Bi, ci, i = 0, …, m as , and , respectively.
In such a notation, problem [1.15] has the form:
Now we can show how the search for a solution to problem [1.16] is reduced to the solution of the corresponding linear programming (LP) problem.
THEOREM (Kirilyuk 2015).– If problem [1.16] is compatible, then its optimal solution is appropriate component x of a solution (ν0, …, νm, x) of the following LP problem:
and the values in the solutions of these problems coincide.
By substituting into [1.17] different variants of the meaningful parts of the matrices and vectors describing the corresponding PCMs, we can technologically solve problems [1.14] as LP problems for the entire class of PCMs.
For decision-making under conditions of uncertainty, it is important to consider not only risks, but also potential benefits (reward) for DM. Therefore, decisions in such conditions are made according to a reward–risk ratio, which is described by appropriate functions. For example, sometimes a reward in conditions of known distributions of r.v. estimated by the average value (profit, utility, etc.).
The important class of linear optimization problems under uncertainty are portfolio optimization problems according to a reward–risk ratio, where some reward functions and risk measures are considered for this. They are, respectively, the average return and some PCMR for conditions of known distributions of r.v., and some reward functions and a robust version of the PCMR for conditions of imprecise scenario probabilities. Formulations results on the topic can be found in Kirilyuk (2014a, 2014b).
We note that a wide class of problems for the protection of CI from natural and man-made disasters fits completely into formulation of optimization problems under conditions of stochastic uncertainty of form [1.7]. Therefore, they can be reduced either to some specific formulation of SP and RO problems, taking into account the possible preferences of a DM or, generally speaking, to problems of using PCMR in the form of [1.10]. In the nonlinear case, such problems are more difficult to solve, and in the linear case, they allow for effective search for an solutions by reducing them to ordinary LP problems and applying standard LP techniques to the latter.
1.3. Some traditional risk assessments and worst-case analysis
Let us consider further the situation of decision-making under the conditions of the risk of an adversary attack on CI. Unlike the previous section, where risks were generated by stochastic uncertainty, in such tasks, the risks are caused by potential malicious actions of an adversary, about which we remain uncertain. This significantly changes the approach to the assessment of such risks.
