Safety verification of iterative algorithms over polynomial vector fields

Mardavij Roozbehani, Alexandre Megretski, Eric Feron

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Iterative algorithms such as the Newton method or the steepest gradient method appear in real-time software to solve online optimization problems as part of autonomous decision making algorithms. Proving safety and in particular convergence properties of such methods in their generic form is hopeless. However, for a special class of problems over a limited range of inputs and uncertain parameters, such task may become possible. In this paper, we consider applications of the Newton method to polynomial root finding and suggest new methods, based on Lyapunov invariance analysis and sum of squares programming to prove convergence and other performance properties of such algorithms. Generic forms for such Lyapunov invariants are presented and it is shown how the search for the certificates of performance can be formulated as a sum of squares program. The proof methods can be automated and thus integrated within a verification and validation workspace for software verification. © 2006 IEEE.
Original languageEnglish (US)
Title of host publicationProceedings of the IEEE Conference on Decision and Control
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages6061-6067
Number of pages7
ISBN (Print)1424401712
DOIs
StatePublished - Jan 1 2006
Externally publishedYes

Fingerprint Dive into the research topics of 'Safety verification of iterative algorithms over polynomial vector fields'. Together they form a unique fingerprint.

Cite this