Pierre-Loïc Garoche
- Published in print:
- 2019
- Published Online:
- January 2020
- ISBN:
- 9780691181301
- eISBN:
- 9780691189581
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691181301.003.0010
- Subject:
- Mathematics, Applied Mathematics
This chapter aims at providing the intuition behind convex optimization algorithms and addresses their effective use with floating-point implementation. It first briefly presents the algorithms, ...
More
This chapter aims at providing the intuition behind convex optimization algorithms and addresses their effective use with floating-point implementation. It first briefly presents the algorithms, assuming a real semantics. As outlined in Chapter 4, convex conic programming is supported by different methods depending on the cone considered. The most known approach for linear constraints is the simplex method by Dantzig. While having an exponential-time complexity with respect to the number of constraints, the simplex method performs well in general. Another method is the set of interior point methods, initially proposed by Karmarkar and made popular by Nesterov and Nemirovski. They can be characterized as path-following methods in which a sequence of local linear problems are solved, typically by Newton's method. After these algorithms are considered, the chapter discusses approaches to obtain sound results.Less
This chapter aims at providing the intuition behind convex optimization algorithms and addresses their effective use with floating-point implementation. It first briefly presents the algorithms, assuming a real semantics. As outlined in Chapter 4, convex conic programming is supported by different methods depending on the cone considered. The most known approach for linear constraints is the simplex method by Dantzig. While having an exponential-time complexity with respect to the number of constraints, the simplex method performs well in general. Another method is the set of interior point methods, initially proposed by Karmarkar and made popular by Nesterov and Nemirovski. They can be characterized as path-following methods in which a sequence of local linear problems are solved, typically by Newton's method. After these algorithms are considered, the chapter discusses approaches to obtain sound results.
Pierre-Loïc Garoche
- Published in print:
- 2019
- Published Online:
- January 2020
- ISBN:
- 9780691181301
- eISBN:
- 9780691189581
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691181301.003.0004
- Subject:
- Mathematics, Applied Mathematics
This chapter presents the formalisms describing discrete dynamical systems and gives an overview on the convex optimization tools and methods used to compute the analyses. A dynamical system is a ...
More
This chapter presents the formalisms describing discrete dynamical systems and gives an overview on the convex optimization tools and methods used to compute the analyses. A dynamical system is a typical object used in control systems or in signal processing. In some cases, it is eventually implemented in a program to perform the desired feedback control to a cyber-physical system. Language-wise, model-based languages such as LUSTRE, ANSYS SCADE, or MATLAB Simulink provide primitives to build these dynamical systems or controllers relying on simpler constructs. In terms of programs, such dynamical systems can easily be implemented as a “while true loop” initialized by the initial state and performing the update f. The simplest systems are usually directly coded in the target language, while more advanced systems are compiled through autocoders.Less
This chapter presents the formalisms describing discrete dynamical systems and gives an overview on the convex optimization tools and methods used to compute the analyses. A dynamical system is a typical object used in control systems or in signal processing. In some cases, it is eventually implemented in a program to perform the desired feedback control to a cyber-physical system. Language-wise, model-based languages such as LUSTRE, ANSYS SCADE, or MATLAB Simulink provide primitives to build these dynamical systems or controllers relying on simpler constructs. In terms of programs, such dynamical systems can easily be implemented as a “while true loop” initialized by the initial state and performing the update f. The simplest systems are usually directly coded in the target language, while more advanced systems are compiled through autocoders.
Jeremy A. Lauer, Alec Morton, and Melanie Bertram
- Published in print:
- 2019
- Published Online:
- December 2019
- ISBN:
- 9780190912765
- eISBN:
- 9780190912796
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780190912765.003.0005
- Subject:
- Philosophy, Philosophy of Science
Cost-effectiveness analysis (CEA) is a form of economic evaluation concerned with efficiency: that is, with achieving the most for the resources (“value for money”). This chapter explains the appeal ...
More
Cost-effectiveness analysis (CEA) is a form of economic evaluation concerned with efficiency: that is, with achieving the most for the resources (“value for money”). This chapter explains the appeal and relevance of CEA and describes its use in localized and strategic decision-making. Localized decision-making (marginal CEA using thresholds) poses the risk of “baking in” past allocation errors, while strategic decision-making (generalized CEA) can be impractical due to the large amount of information required, among other considerations. The authors provide an example of using CEA to evaluate a program for tuberculosis treatment and close with some recommendations for using CEA in strategic planning, which is a hybrid approach linking the localized and strategic approaches to CEA and remedying thereby some of the defects of each.Less
Cost-effectiveness analysis (CEA) is a form of economic evaluation concerned with efficiency: that is, with achieving the most for the resources (“value for money”). This chapter explains the appeal and relevance of CEA and describes its use in localized and strategic decision-making. Localized decision-making (marginal CEA using thresholds) poses the risk of “baking in” past allocation errors, while strategic decision-making (generalized CEA) can be impractical due to the large amount of information required, among other considerations. The authors provide an example of using CEA to evaluate a program for tuberculosis treatment and close with some recommendations for using CEA in strategic planning, which is a hybrid approach linking the localized and strategic approaches to CEA and remedying thereby some of the defects of each.
Pierre-Loïc Garoche
- Published in print:
- 2019
- Published Online:
- January 2020
- ISBN:
- 9780691181301
- eISBN:
- 9780691189581
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691181301.003.0005
- Subject:
- Mathematics, Applied Mathematics
This chapter focuses on the computation of invariant for a discrete dynamical system collecting semantics. Invariants or collecting semantics properties are properties preserved along all executions ...
More
This chapter focuses on the computation of invariant for a discrete dynamical system collecting semantics. Invariants or collecting semantics properties are properties preserved along all executions of a system and verified in all reachable states. A subset of these invariants are defined as inductive. Inductive invariants are properties, or relationships between variables, that are inductively preserved by one transition of considered systems. Intuitively, it is not required to consider a reachable state and all (or part of) its past while arguing about the validity of the invariant, but only the single state. Applying the induction principle, this chapter obtains that any state satisfying the property is mapped to a next state preserving that same property.Less
This chapter focuses on the computation of invariant for a discrete dynamical system collecting semantics. Invariants or collecting semantics properties are properties preserved along all executions of a system and verified in all reachable states. A subset of these invariants are defined as inductive. Inductive invariants are properties, or relationships between variables, that are inductively preserved by one transition of considered systems. Intuitively, it is not required to consider a reachable state and all (or part of) its past while arguing about the validity of the invariant, but only the single state. Applying the induction principle, this chapter obtains that any state satisfying the property is mapped to a next state preserving that same property.
Pierre-Loïc Garoche
- Published in print:
- 2019
- Published Online:
- January 2020
- ISBN:
- 9780691181301
- eISBN:
- 9780691189581
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691181301.003.0006
- Subject:
- Mathematics, Applied Mathematics
This chapter considers other configurations aside from the direct synthesis of invariants as bound templates. A first case arises when the methods shown in the previous chapter only synthesizes the ...
More
This chapter considers other configurations aside from the direct synthesis of invariants as bound templates. A first case arises when the methods shown in the previous chapter only synthesizes the template but not the bound. A second appears when one wants to analyze a system with multiple templates. This chapter looks at bounds on each variable and considers the templates 𝑝(𝑥) = 𝑥²𝑖 for each variable 𝑥𝑖 in state characterization 𝑥 ∈ Σ. The chapter thus proposes a policy iteration algorithm, based on sum-of-squares (SOS) optimization, to refine such template bounds. In practice, the chapter uses it by combining a Lyapunov-based template obtained using one of the previous methods with additional templates encoding bounds on some variables or property specific templates.Less
This chapter considers other configurations aside from the direct synthesis of invariants as bound templates. A first case arises when the methods shown in the previous chapter only synthesizes the template but not the bound. A second appears when one wants to analyze a system with multiple templates. This chapter looks at bounds on each variable and considers the templates 𝑝(𝑥) = 𝑥²𝑖 for each variable 𝑥𝑖 in state characterization 𝑥 ∈ Σ. The chapter thus proposes a policy iteration algorithm, based on sum-of-squares (SOS) optimization, to refine such template bounds. In practice, the chapter uses it by combining a Lyapunov-based template obtained using one of the previous methods with additional templates encoding bounds on some variables or property specific templates.
Alan Bollard
- Published in print:
- 2019
- Published Online:
- January 2020
- ISBN:
- 9780198846000
- eISBN:
- 9780191881244
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198846000.003.0005
- Subject:
- Economics and Finance, Economic History
The only way through the wartime Leningrad siege was a winter ice road across a lake, monitored by a brilliant young Soviet mathematician. Leonid Kantorovich had been brought up in the chaos of ...
More
The only way through the wartime Leningrad siege was a winter ice road across a lake, monitored by a brilliant young Soviet mathematician. Leonid Kantorovich had been brought up in the chaos of post-Czarist Russia, and during his pioneering career invented linear programming to help Soviet industry become more efficient, then worked out mathematical ways to improve the planning of the whole Soviet economy. But this was dangerous work, as Stalin disapproved of economists and cybernetics, had sent many to the gulags, and was trying to run the economy himself, despite all the practical problems of wartime central planning without prices.Less
The only way through the wartime Leningrad siege was a winter ice road across a lake, monitored by a brilliant young Soviet mathematician. Leonid Kantorovich had been brought up in the chaos of post-Czarist Russia, and during his pioneering career invented linear programming to help Soviet industry become more efficient, then worked out mathematical ways to improve the planning of the whole Soviet economy. But this was dangerous work, as Stalin disapproved of economists and cybernetics, had sent many to the gulags, and was trying to run the economy himself, despite all the practical problems of wartime central planning without prices.
