49N05 Linear optimal control problems [See also 93C05]
Dynamic network flow problems model the temporal evolution of flows over time and also consider changes of network parameters such as capacities, costs, supplies, and demands over time. These problems have been extensively studied in the past because of their important role in real world applications such as transport, traffic, and logistics. This has led to many results, but the more challenging continuous time model still lacks some of the key features such as network related optimality conditions and algorithms that are available in the static case.
The aim of this paper is to advance the state of the art for dynamic network flows by developing the continuous time analogues of several well-known optimality conditions for static network flows. Specifically, we establish a reduced cost optimality condition, a negative cycle optimality condition, and a strong duality result for a very general class of dynamic
network flows. The underlying idea is to construct a dual feasible solution that proves optimality when the residual network (with respect to a given flow) contains no dynamic cycles with negative cost. We also discuss a generic negative cycle-canceling algorithm resulting from the corresponding optimality criterion and point out promising directions for future research.
In this work we consider the so-called Lur'e matrix equations that arise e.g. in model reduction and linear-quadratic infinite time horizon optimal control. We characterize the set of solutions in terms of deflating subspaces of even matrix pencils. In particular, it is shown that there exist solutions which are extremal in terms of definiteness. It is shown how these special solutions can be constructed deflating subspaces of even matrix pencils.