Optimization Online


Optimal switching sequence for switched linear systems

Zeyang Wu (wuxx1164***at***umn.edu)
Qie He (qhe***at***umn.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.

Download: [PDF]

Entry Submitted: 05/10/2018
Entry Accepted: 05/24/2018
Entry Last Modified: 07/01/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society