  


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 nbyn matrices and an ndimensional 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 moderatesized instance is challenging to solve to optimality for stateoftheart 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 oligovertex 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 oligovertex property. Nu merical results demonstrate the clear advantage of our algorithm in solving largesized instances of the problem over one stateoftheart global solver. We also pose several open questions on the oligovertex 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. Download: [PDF] Entry Submitted: 05/10/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  