Optimal switching sequence for switched linear systems

We study the following optimization problem over a dynamical system that consists of several linear subsystems: Given a finite set of n-by-n matrices and an n-dimensional vector, find a sequence of K matrices, each chosen from the given set of matrices, to maximize a convex function over the product of the K matrices and the given vector. This simple problem has many applications in operations research and control, yet a moderate-sized instance is challenging to solve to optimality for state-of-the-art optimization software. We propose a simple exact algo- rithm for this problem. Our algorithm runs in polynomial time when the given set of matrices has the oligo-vertex property, a concept we introduce in this paper for a set of matrices. We derive several sufficient conditions for a set of matrices to have the oligo-vertex property. Nu- merical results demonstrate the clear advantage of our algorithm in solving large-sized instances of the problem over one state-of-the-art global solver. We also pose several open questions on the oligo-vertex property and discuss its potential connection with the finiteness property of a set of matrices, which may be of independent interest.


Zeyang Wu, Qie He. Optimal switching sequence for switched linear systems. Technical Report, University of Minnesota, May 2018.



View Optimal switching sequence for switched linear systems