**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]