Optimal switching sequence for switched linear systems
Zeyang Wu (wuxx1164umn.edu)
Abstract: 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.
Keywords: Switched linear systems, Optimal control, Discrete optimization, Computational 16 complexity, Convex geometry, Enumerative combinatorics
Category 1: Combinatorial Optimization
Category 2: Applications -- Science and Engineering (Control Applications )
Category 3: Other Topics (Dynamic Programming )
Citation: Zeyang Wu, Qie He. Optimal switching sequence for switched linear systems. Technical Report, University of Minnesota, May 2018.
Entry Submitted: 05/10/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|