Optimal Switching Sequence for Switched Linear Systems
From MaRDI portal
Publication:5111065
integer programmingexact algorithmoptimal controlswitched systemsjoint spectral radiusbinary matrices
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)
Abstract: We study the following optimization problem over a dynamical system that consists of several linear subsystems: Given a finite set of matrices and an -dimensional vector, find a sequence of matrices, each chosen from the given set of matrices, to maximize a convex function over the product of the 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.
Recommendations
- Optimally switched linear systems
- Optimal switching sequence of a class of switched systems with parameter uncertainty
- 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
Cites work
- scientific article; zbMATH DE number 3155071 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- A comparison of complete global optimization solvers
- A new polynomial-time algorithm for linear programming
- Algorithm 1011: Improved invariant polytope algorithm and applications
- An Elementary Counterexample to the Finiteness Conjecture
- An efficient algorithm for determining the convex hull of a finite planar set
- An explicit counterexample to the Lagarias-Wang finiteness conjecture
- Analysis and synthesis of switched linear control systems
- Antibiotics time machines are hard to build
- Approximation of the joint spectral radius using sum of squares
- Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture
- Computationally Efficient Approximations of the Joint Spectral Radius
- Correction: Rational Design of Antibiotic Treatment Plans: A Treatment Strategy for Managing Evolution and Reversing Resistance
- Exact computation of joint spectral characteristics of linear operators
- Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON
- Generating Functions of Switched Linear Systems: Analysis, Computation, and Stability Applications
- Hybrid Control for Switched Linear Systems With Average Dwell Time
- Introduction to algorithms
- Joint spectral radius and path-complete graph Lyapunov functions
- Linear Quadratic Regulation of Switched Systems Using Informed Policies
- Numerical methods for mixed-integer optimal control problems
- On the Value Functions of the Discrete-Time Switched LQR Problem
- On the finiteness property for rational matrices
- Optimal control of hybrid switched systems: a brief survey
- Rank-one characterization of joint spectral radius of finite matrix family
- Stability and Stabilizability of Switched Linear Systems: A Survey of Recent Results
- Switching in systems and control
- The Complexity of Markov Decision Processes
- The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate
- The finiteness conjecture for the generalized spectral radius of a set of matrices
- The integer approximation error in mixed-integer optimal control
- The mortality problem for matrices of low dimensions
- When is a pair of matrices mortal?
Cited in
(8)- 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
- Elliptic polytopes and invariant norms of linear operators
- Optimization problems involving matrix multiplication with applications in materials science and biology
- Sensitivity analysis for the optimization of switched dynamical processes with state-dependent switching conditions and its application
- Non-Sturmian sequences of matrices providing the maximum growth rate of matrix products
- Optimal scheduling of discrete-time switched linear systems
- Latency vs precision: stability preserving perception scheduling
- An improved method for approximating the infinite-horizon value function of the discrete-time switched LQR problem
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)
