A Sums-of-Squares Extension of Policy Iterations

File Description SizeFormat 
1503.08090v1.pdfWorking paper570.8 kBAdobe PDFView/Open
Title: A Sums-of-Squares Extension of Policy Iterations
Authors: Adjé, A
Garoche, P-L
Magron, V
Item Type: Report
Abstract: In order to address the imprecision often introduced by widening operators in static analysis, policy iteration based on min-computations amounts to considering the characterization of reachable value set of a program as an iterative computation of policies, starting from a post-fixpoint. Computing each policy and the associated invariant relies on a sequence of numerical optimizations. While the early research efforts relied on linear programming (LP) to address linear properties of linear programs, the current state of the art is still limited to the analysis of linear programs with at most quadratic invariants, relying on semidefinite programming (SDP) solvers to compute policies, and LP solvers to refine invariants. We propose here to extend the class of programs considered through the use of Sums-of-Squares (SOS) based optimization. Our approach enables the precise analysis of switched systems with polynomial updates and guards. The analysis presented has been implemented in Matlab and applied on existing programs coming from the system control literature, improving both the range of analyzable systems and the precision of previously handled ones.
Issue Date: 27-Mar-2015
18-Aug-2015
URI: http://hdl.handle.net/10044/1/25724
Copyright Statement: © 2015 The Authors
Notes: 20 pages, 1 figure
Appears in Collections:Faculty of Engineering
Electrical and Electronic Engineering



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commonsx