TY - GEN

T1 - Safety verification of iterative algorithms over polynomial vector fields

AU - Roozbehani, Mardavij

AU - Megretski, Alexandre

AU - Feron, Eric

N1 - Generated from Scopus record by KAUST IRTS on 2021-02-18

PY - 2006/1/1

Y1 - 2006/1/1

N2 - 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.

AB - 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.

UR - http://ieeexplore.ieee.org/document/4178069/

UR - http://www.scopus.com/inward/record.url?scp=39649090080&partnerID=8YFLogxK

U2 - 10.1109/cdc.2006.377333

DO - 10.1109/cdc.2006.377333

M3 - Conference contribution

SN - 1424401712

SP - 6061

EP - 6067

BT - Proceedings of the IEEE Conference on Decision and Control

PB - Institute of Electrical and Electronics Engineers Inc.

ER -