Optimal Switching Sequence for Switched Linear Systems

DOI10.1137/18M1197928zbMATH Open1444.90105arXiv1805.04677MaRDI QIDQ5111065FDOQ5111065

Zeyang Wu, Qie He

Publication date: 26 May 2020

Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)

Abstract: We study the following optimization problem over a dynamical system that consists of several linear subsystems: Given a finite set of $nimesn$ 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 algorithm 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 finite set of matrices. We derive several sufficient conditions for a set of matrices to have the oligo-vertex property. Numerical results demonstrate the clear advantage of our algorithm in solving large-sized instances of the problem over one state-of-the-art global optimization solver. We also propose 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.

Full work available at URL: https://arxiv.org/abs/1805.04677

zbMATH Keywords

integer programmingexact algorithmoptimal controlswitched systemsjoint spectral radiusbinary matrices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamical systems in optimization and economics (37N40) Integer programming (90C10) Asymptotic enumeration (05A16) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON
• A new polynomial-time algorithm for linear programming
• Introduction to algorithms
• Switching in systems and control
• An efficient algorithm for determining the convex hull of a finite planar set
• Hybrid Control for Switched Linear Systems With Average Dwell Time
• The Complexity of Markov Decision Processes
• Stability and Stabilizability of Switched Linear Systems: A Survey of Recent Results
• Analysis and synthesis of switched linear control systems
• The finiteness conjecture for the generalized spectral radius of a set of matrices
• On the finiteness property for rational matrices
• Approximation of the joint spectral radius using sum of squares
• Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture
• An Elementary Counterexample to the Finiteness Conjecture
• Computationally Efficient Approximations of the Joint Spectral Radius
• Joint Spectral Radius and Path-Complete Graph Lyapunov Functions
• An explicit counterexample to the Lagarias-Wang finiteness conjecture
• A comparison of complete global optimization solvers
• The integer approximation error in mixed-integer optimal control
• When is a pair of matrices mortal?
• The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate
• Exact computation of joint spectral characteristics of linear operators
• Optimal control of hybrid switched systems: a brief survey
• The mortality problem for matrices of low dimensions
• On the Value Functions of the Discrete-Time Switched LQR Problem
• Generating Functions of Switched Linear Systems: Analysis, Computation, and Stability Applications
• Rank-one characterization of joint spectral radius of finite matrix family
• Linear Quadratic Regulation of Switched Systems Using Informed Policies
• Algorithm 1011
• Correction: Rational Design of Antibiotic Treatment Plans: A Treatment Strategy for Managing Evolution and Reversing Resistance
• Antibiotics Time Machines Are Hard to Build

Cited In (8)

• Non-Sturmian sequences of matrices providing the maximum growth rate of matrix products
• Sensitivity analysis for the optimization of switched dynamical processes with state-dependent switching conditions and its application
• Elliptic polytopes and invariant norms of linear operators
• A penalty function-based random search algorithm for optimal control of switched systems with stochastic constraints and its application in automobile test-driving with gear shifts
• Optimization problems involving matrix multiplication with applications in materials science and biology
• Latency vs precision: stability preserving perception scheduling
• Optimal scheduling of discrete-time switched linear systems
• An improved method for approximating the infinite-horizon value function of the discrete-time switched LQR problem

Uses Software

• BARON
• Gurobi

   Recommendations

• Optimally switched linear systems 👍 👎
• Title not available (Why is that?) 👍 👎
• Optimal switching for linear quadratic problem of switched systems in discrete time 👍 👎
• Optimal control of switching systems 👍 👎
• LQR optimization of linear system switching 👍 👎
• Design of switching sequences for controllability realization of switched linear systems 👍 👎
• Optimality criterion for switching systems 👍 👎
• Optimal control of discrete-time switched linear systems 👍 👎
• Synthesis of optimal switched systems 👍 👎
• Optimal scheduling of discrete-time switched linear systems 👍 👎

This page was built for publication: Optimal Switching Sequence for Switched Linear Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111065)