Elements of robustness and optimal control for infrastructure networks

2018-02-22An infrastructure system is formally modeled as a network, whose topology is described by a directed or undirected graph, and whose nodes and links are associated with physical quantities such as node potential and link flow. Two canonical physical laws occurring in multiple infrastructure networks are considered to relate these physical quantities. The first one is flow conservation law. It requires zero net flow at every node. The second physical law, referred to as diffusion law, requires a strictly monotonic relationship between link flow and the potential difference between the incident nodes. The linear version of diffusion law plus flow conservation law defines the class of DC networks. The flow over a DC network is uniquely determined by node supply-demands and link weights. We are interested in finding a weight that produces a maximal feasible flow, i.e, flow satisfying capacity constraints, for given supply-demands over a DC network. The solution relies on minimizing a congestion function that is neither convex nor differentiable. Based on the derived directional derivative of the congestion function and properties proved for flow-weight Jacobian matrix, we show that every local minimum of the congestion function is a global minimum. ❧ The flexibility of choosing weight is also adopted as a control mechanism to maximize the robustness of a DC network toward disturbances to nominal supply-demand. The margin of robustness is defined as the radius of the largest L1 ball of disturbances for which there exists a weight within specified bounds such that the resulting flow is feasible. Computation of this margin is posed as a non-convex optimization problem. A multi-level programming approach is developed to solve the problem for reducible networks, i.e., a class of networks with certain sparsity properties. The approach is based on a novel notion of equivalent capacity function, which is proven to possess a strong quasi-concavity property for link reducible networks. This property further facilitates an easy solution to the multilevel programming formulation for a subclass of reducible networks, that we call type I tree reducible networks. ❧ Another major consideration in robust operation of infrastructure networks is to prevent cascading failure, i.e., a phenomenon under which the initial failure of a small number of links due to an exogenous event is followed by a sequence of link failures due to the interplay between physics, network topology, and controls. We consider DC networks and model cascading failure as a discrete-time dynamical system featuring a hybrid state consisting of a set variable for the active link and a continuous variable for supply-demand. While link weight is assumed fixed, load shedding, i.e., decreasing the magnitude of supply-demand, is adopted as the control mechanism to stop failure propagation. The control objective is to minimize the amount of load to be shed. We propose two approaches for computing an optimal control, and provide time complexity analysis for these approaches. The first approach, geared towards a certain class of networks that we call type II tree reducible networks, decomposes the global non-convex problem into a system of coupled local non-convex problems, which can be solved to optimality in two iterations. The second approach transforms the continuous reachable set equivalently into a finite set by leveraging and extending tools for arrangement of hyperplanes and convex polytopes. ❧ Finally, we adapt the Alternating Direction Method of Multipliers (ADMM) to develop a distributed algorithm for computing finite horizon optimal control for traffic flow over transportation networks and present its convergence properties