In Proximity of ReLU DNN, PWA Function, and Explicit MPC

Saman Fahandezh-Saadi, Masayoshi TomizukaarXiv 2020 · OpenReview

Abstract

Rectifier (ReLU) deep neural networks (DNN) and their connection with piecewise affine (PWA) functions is analyzed. The paper is an effort to find and study the possibility of representing explicit state feedback policy of model predictive control (MPC) as a ReLU DNN, and vice versa. The complexity and architecture of DNN has been examined through some theorems and discussions. An approximate method has been developed for identification of input-space in ReLU net which results a PWA function over polyhedral regions. Also, inverse multiparametric linear or quadratic programs (mp-LP or mp-QP) has been studied which deals with reconstruction of constraints and cost function given a PWA function.

Introduction

In control theory, Model Predictive Control (MPC) is a premier method for managing systems with strict constraints. However, the real-time computational cost of solving these optimization problems often limits their application. Explicit MPC addresses this by pre-computing optimal control laws, which are represented as Piecewise Affine (PWA) functions—essentially a lookup table of linear controllers assigned to different regions of the state space.

The primary challenge is that as constraints grow, the number of regions in an explicit MPC solution explodes exponentially, making it difficult to store on embedded hardware. This paper explores the mathematical "proximity" between ReLU-based Deep Neural Networks (DNNs), PWA functions, and explicit MPC solutions, suggesting that DNNs can serve as highly efficient, compact representations of complex control policies.

The Conceptual Framework

The core thesis of this work is establishing a formal link between these three mathematical frameworks. As illustrated in the following diagram, ReLU DNNs can be viewed as a compact alternative to the extensive lookup tables typically required by Explicit MPC.

Conceptual mapping between ReLU DNNs, PWA functions, and Explicit MPC

Methodology

The authors employ a mix of theoretical analysis and constructive proofs to bridge these domains:

  • Structural Mapping: Since a ReLU unit is itself a PWA function ($max(0, x)$), any network composed of them is inherently a PWA function.
  • Input-Space Identification: The paper proposes an approximate, sample-based method to "reverse engineer" a trained ReLU DNN. By using indicator functions to track which neurons are "on" or "off," they can extract the specific affine parameters (weights and biases) for every polytopic region the network creates.
  • Inverse mp-LP/QP: The authors discuss taking a PWA function (or a trained DNN) and reconstructing the original optimization problem (multi-parametric Linear or Quadratic Program) that would have produced it.

Geometric Insights: The Bending Effect

A fascinating geometric insight provided by the paper is how layers interact to create complexity. The first layer creates straight-line boundaries (hyperplanes) in the input space. As shown in the visualization below, the second layer's boundaries are also hyperplanes, but they "bend" whenever they cross the boundaries established by the first layer. This explains how deep networks create intricate, non-linear partitions with very few parameters.

The 'bending' effect of hyperplanes across successive layers in a ReLU DNN

Key Results and Discussion

The research reinforces that every continuous PWA function can be represented by a ReLU DNN and can also be obtained as the solution to a multi-parametric linear program. The authors successfully derived equations to compute the exact weight ($u$) and bias ($c$) for any local affine piece of a deep network based on specific neuron activation patterns.

Through a 1D numerical example, they demonstrated the full pipeline: starting with a ReLU DNN, identifying its PWA equivalent, and constructing the corresponding mp-LP optimization problem. This suggests that a tiny network (e.g., 84 parameters) can represent a PWA function that would otherwise require massive memory if stored as a traditional explicit MPC table.

Limitations and Future Work

While the theoretical link is robust, practical implementation for high-dimensional systems remains challenging. The authors admit that the constructive proof for converting PWA functions to mp-LPs is difficult to implement as a scalable algorithm. Furthermore, the sampling requirements for input-space identification may become a bottleneck for very deep or wide networks. Future research is directed toward using Mixed-Integer Linear Programming (MILP) to provide formal stability and safety guarantees for DNN-based control policies, bridging the gap between machine learning efficiency and control engineering rigor.

Summary updated

Abstract

Rectifier (ReLU) deep neural networks (DNN) and their connection with piecewise affine (PWA) functions is analyzed. The paper is an effort to find and study the possibility of representing explicit state feedback policy of model predictive control (MPC) as a ReLU DNN, and vice versa. The complexity and architecture of DNN has been examined through some theorems and discussions. An approximate method has been developed for identification of input-space in ReLU net which results a PWA function over polyhedral regions. Also, inverse multiparametric linear or quadratic programs (mp-LP or mp-QP) has been studied which deals with reconstruction of constraints and cost function given a PWA function.
BibTeX
@misc{fahandezhsaadi2020proximity,
  author = {Saman Fahandezh-Saadi and Masayoshi Tomizuka},
  title = {{In Proximity of ReLU DNN, PWA Function, and Explicit MPC}},
  year = {2020},
  eprint = {2006.05001},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.05001},
}
Figure