Efficient representation of the solution to multi-parametric quadratic programming for control applications

In this thesis, we consider a multi-parametric Quadratic Program (mp-QP) and address the problem of determining an efficient representation of its solution. A main motivation for studying this problem is Model Predictive Control (MPC) for linear constrained systems. According to the MPC strategy, at each time instant, the control input sequence that minimizes a finite horizon quadratic cost subject to linear constraints is computed and then the first control input is applied. The resulting quadratic program can be repeatedly solved online based on the current state value. However, this limits the applicability of MPC to slow dynamics, as in the process industry where it originated. In order to expand the domain of application of MPC, one can resort to an alternative approach where the state is interpreted as a vector of multiple parameters, and the associated mp-QP is solved offline to determine the control input sequence as an explicit function of the state, which is then stored for its online usage. This, however, might still pose some practical issues since the explicit MPC solution is a (continuous) piecewise affine function (PWA) defined over a polyhedral partition of the state space, which can be quite complex and hard to store and evaluate. One needs in fact to measure the state of the system, determine its position within the polyhedral partition (point location problem) and finally evaluate the affine function associated to the identified element of the partition. If the dimensionality of the system and the number of regions are high, this procedure becomes too time-consuming to be completed in one sampling period. Moreover, when the number of polyhedral region is large, the memory demand can be too high for the device on which the control law is implemented. Motivated by the need of practicable MPC implementation strategies, the goal of this thesis is to investigate effective representations of the PWA solution to an mp-QP. In particular, we shall study three alternatives: deep neural networks with Rectified Linear Units (ReLU) as activation functions; the decomposition of a continuous PWA function into two convex PWA functions, which can be expressed as the pointwise maximum of a set of affine functions; the use of convex lifting for solving the point location problem by introducing a further PWA function defined on the same poolyhedral partition which is convex and hence can be expressed as the pointwise maximum of a set of affine functions. After examining each of them separately, we evaluate their strengths and weaknesses on a comparative example, focusing on memory requirements and computational effort involved in their implementation.

In questa tesi si considerano problemi di programmazione quadratica multi-parametrica (mp-QP) e si affronta il problema di determinare una rappresentazione efficiente della loro soluzione. I problemi mp-QP sono di interesse, in particolare, nel contesto del controllo e più precisamente nell'ambito del controllo predittivo (Model Predictive Control - MPC) di sistemi lineari vincolati. La strategia MPC prevede di calcolare ad ogni istante di tempo la sequenza di ingressi di controllo che minimizza una funzione costo su orizzonte finito che nel caso di interesse è quadratica e soggetta a vincoli lineari, per poi applicare il primo della sequenza. Il programma quadratico risultante può venire risolto online ad ogni istante di tempo sulla base del valore misurato dello stato a quell'istante. Tuttavia, ciò limita l'applicabilità dell'MPC a sistemi con dinamiche lente, come quelli dell'industria di processo dove l'MPC ha avuto origine. Per espandere il dominio di applicazione dell'MPC, si può ricorrere a un approccio alternativo dove lo stato viene interpretato come un vettore di parametri, e il mp-QP associato è risolto offline in modo da determinare la sequenza di ingressi di controllo come funzione esplicita dello stato, che viene poi tenuta in memoria per il suo utilizzo online. Ciò, tuttavia, può presentare comunque alcuni problemi pratici dato che la soluzione dell'explicit MPC è una funzione affine a tratti (PWA) definita su una partizione poliedrica dello spazio di stato e può quindi essere piuttosto complessa e onerosa da immagazzinare in memoria e da valutare online. È infatti necessario misurare lo stato del sistema, determinare la sua posizione all'interno della partizione poliedrica (point location problem) e infine valutare la funzione affine associata all'elemento della partizione che è stato identificato. Se la dimensione del sistema e il numero di regioni sono elevati, questa procedura diventa troppo onerosa per essere completata all'interno di un periodo di campionamento. Inoltre, se il numero di regioni poliedriche è elevato, la richiesta di memoria può eccedere i limiti imposti dal dispositivo su cui è implementata la legge di controllo. Motivato dalla necessità di strategie che rendano l'implementazione della strategia MPC praticabile, l'obiettivo di questa tesi è investigare rappresentazioni efficaci della soluzione PWA di un mp-QP. In particolare, studiamo tre alternative: l'uso di reti neurali profonde con unità di attivazione lineare rettificata (Rectified Linear Unit - ReLU); la scomposizione di una funzione PWA continua in due PWA convesse, che possono essere espresse come massimo di un insieme di funzioni affini; l'uso del cosiddetto convex lifting per la risoluzione del problema di point location introducendo un'ulteriore funzione PWA, definita sulla partizione poliedrica, che sia convessa e dunque esprimibile come massimo di un insieme di funzioni affini. Dopo aver esaminato ognuna di queste alternative separatamente, valutiamo i loro punti di forza e di debolezza su un esempio comparativo, concentrandoci sui requisiti di memoria e sullo sforzo computazionale necessari per la loro implementazione.