Modification and improved implementation of the RPD method for computing state relaxations for global dynamic optimization

Abstract This paper presents an improved method for computing convex and concave relaxations of the parametric solutions of ordinary differential equations (ODEs). These are called state relaxations and are crucial for solving dynamic optimization problems to global optimality via branch-and-bound (B &B). The new method improves upon an existing approach known as relaxation preserving dynamics (RPD). RPD is generally considered to be among the best available methods for computing state relaxations in terms of both efficiency and accuracy. However, it requires the solution of a hybrid dynamical system, whereas other similar methods only require the solution of a simple system of ODEs. This is problematic in the context of branch-and-bound because it leads to higher cost and reduced reliability (i.e., invalid relaxations can result if hybrid mode switches are not detected numerically). Moreover, there is no known sensitivity theory for the RPD hybrid system. This makes it impossible to compute subgradients of the RPD relaxations, which are essential for efficiently solving the associated B &B lower bounding problems. To address these limitations, this paper presents a small but important modification of the RPD theory, and a corresponding modification of its numerical implementation, that crucially allows state relaxations to be computed by solving a system of ODEs rather than a hybrid system. This new RPD method is then compared to the original using two examples and shown to be more efficient, more robust, and of almost identical accuracy.

Apr 23, 2024 - 22:42
 0  117
Modification and improved implementation of the RPD method for computing state relaxations for global dynamic optimization

Abstract

This paper presents an improved method for computing convex and concave relaxations of the parametric solutions of ordinary differential equations (ODEs). These are called state relaxations and are crucial for solving dynamic optimization problems to global optimality via branch-and-bound (B &B). The new method improves upon an existing approach known as relaxation preserving dynamics (RPD). RPD is generally considered to be among the best available methods for computing state relaxations in terms of both efficiency and accuracy. However, it requires the solution of a hybrid dynamical system, whereas other similar methods only require the solution of a simple system of ODEs. This is problematic in the context of branch-and-bound because it leads to higher cost and reduced reliability (i.e., invalid relaxations can result if hybrid mode switches are not detected numerically). Moreover, there is no known sensitivity theory for the RPD hybrid system. This makes it impossible to compute subgradients of the RPD relaxations, which are essential for efficiently solving the associated B &B lower bounding problems. To address these limitations, this paper presents a small but important modification of the RPD theory, and a corresponding modification of its numerical implementation, that crucially allows state relaxations to be computed by solving a system of ODEs rather than a hybrid system. This new RPD method is then compared to the original using two examples and shown to be more efficient, more robust, and of almost identical accuracy.

What's Your Reaction?

like

dislike

love

funny

angry

sad

wow

Lema Kefyalew Studying a Ph.D. in Civil Engineering (Hydraulic Engineering). Studying Master of Project Management (MPM). Graduated with MSc in Civil Engineering (Hydraulic Engineering). Followed a 12 month Software Engineering program at ALX_Africa (Holberton school). Graduated with BA degree in Management. Graduated with BSc degree in Civil Engineering.