NSF 1301660: Solving Large Sum-of-Squares Optimization Problems in Control by Exploiting the Parallel Structure of Polya’s Algorithm

Project Description:

In this project, we propose new parallel algorithms for stability analysis and control of systems with a large number of states. Recently, convex approaches such as Sum-of-Squares (SOS) have been proposed for solving problems involving optimization of polynomials. These algorithms rely on semidefinite programming (SDP) to parameterize the positive polynomials. In this project, we look at alternative parameterizations of the cone of positive polynomials which are structured in a way which can be parallelized efficiently. Specifically, we focus on the Polya's lemma and show that the associated conditions can be implemented in a decentralized architecture such as on a cluster or supercomputer.

Project Duration:

09/01/2011-08/31/2015

Project Personnel:

Matthew M. Peet (PI), Arizona State University
Reza Kamyar (PhD), Arizona State University

International Collaborators:

Pedro P. L. D. Peres, The University of Campinas. Campinas, Brasil

Software Products:

Handelman Tools (Matlab Code)

Based on the Paper:
Constructing Piecewise Polynomial Lyapunov Functions Over Arbitrary Convex Polytopes Using Handelman's Basis
53rd IEEE Conference on Decision and Control. Los Angeles, CA. December 15-17, 2014.

Introduction:A Matlab code for local stability analysis of nonlinear ODEs defined by polynomial vector fields using Handelman's theorem for positivity over polytopes.

This toolbox:
1. Requires Matlab 2011a or later.
2. Requires that a working version of SeDuMi be installed.
3. Requires the entire folder be placed in the path along with sub-folders.
4. Is executed using the file handelman_arbitrary_triangles.m

[Handelman_Tool.zip]- Stability Analysis Package

Polya Parallel Tools (MPI)

Based on the Paper:
Solving Large-Scale Robust Control Problems by Exploiting the Parallel Structure of Polya's Theorem
IEEE Transactions on Automatic Control, Vol. 58, No. 8, Aug. 2013, pp. 1931-1947.

Introduction: A Linux Implementation of our parallel computing algorithm for robust stability of linear uncertain systems with uncertain parameters in the unit simplex.

This toolbox:
1. This relatively undocumented code requires MPI, LAPACK, and BLAS, the latter of which are included in the directory SDP3.
2. To install, run the file Makefile file located in the SDP3 directory.
3. For detailed instructions, contact rkamyar@asu.edu.

[Polya_Parallel.zip]- Parallel Computing Framework

Associated Publications at ASU:

Student Theses:

Reza Kamyar (PhD), Arizona State University
Parallel Optimization of Polynomials for Large-Scale Problems in Stability and Control
Defended January, 2016.
Thesis - [arXiv:math] [.pdf] [.ps]
Defense Talk - [.pdf] [.ps]

Journal Publications:

R. Kamyar and M. M. Peet
Polynomial Optimization with Applications to Stability Analysis and Control - Alternatives to Sum-of-Squares
Discrete and Continuous Dynamical Systems - Series B. Special Issue on "Constructive and computational methods in Lyapunov and stability theory". Vol. 20, No. 9, pp2383--2417. (Survey Paper).
[arXiv] [.pdf] [.ps]

R. Kamyar, M. M. Peet and Y. Peet
Solving Large-Scale Robust Control Problems by Exploiting the Parallel Structure of Polya's Theorem
IEEE Transactions on Automatic Control, Vol. 58, No. 8, Aug. 2013, pp. 1931-1947.
[arXiv] [.pdf] [.ps]

CDC/ACC Conference Publications:

R. Kamyar and M. Peet
Constructing Piecewise Polynomial Lyapunov Functions Over Arbitrary Convex Polytopes Using Handelman's Basis
53rd IEEE Conference on Decision and Control. Los Angeles, CA. December 15-17, 2014.
[arXiv] [.pdf] [.ps] [slides]

R. Kamyar and M. Peet
Decentralized Polya’s Algorithm for Stability Analysis of Large-scale Nonlinear Systems
52nd IEEE Conference on Decision and Control. Florence, IT. December 10-13, 2013.
[arXiv] [.pdf] [.ps] [slides]

R. Kamyar and M. Peet
Decentralized Computation for Robust Stability of Large-scale Systems with Parameters on the Hypercube
51st IEEE Conference on Decision and Control, Maui, HI. December 15-17, 2012. pp. 6529-6264..
[arXiv] [.pdf] [.ps]

R. Kamyar and M. M. Peet
Solving Large-Scale Robust Control Problems by Exploiting the Parallel Structure of Polya's Theorem
American Control Conference, Montreal, CA. June 27-29, 2012. pp. 5948-5954.
[arXiv] [.pdf] [.ps]

M. M. Peet and Y. V. Peet
A Parallel-Computing Solution for Optimization of Polynomials
Proceedings of the American Control Conference, Baltimore, MD. June 30-July 2, 2010.
[arXiv] [.pdf] [.ps]