Tim Mitchell | Software

PSARNOT: (Pseudo)Spectral Abscissa|Radius Nonsmooth Optimization Test

PSARNOT (rhymes with Carnot, as in car-no) is a test set intended for evaluating methods for nonsmooth optimization. It is comprised of data files and software, implemented in MATLAB. PSARNOT includes 200 nonsmooth nonconvex constrained optimization problems and new test problems can be easily generated.

The test problems

Each PSARNOT test example is a constrained nonsmooth optimization problem arising from controller design, where the objective and constraint functions are (robust) stability measures for linear dynamical systems. PSARNOT supports the following nonsmooth functions:

spectral abscissa (non-locally Lipschitz, unbounded below)
spectral radius (non-locally Lipschitz, bounded below)
ε-pseudospectral abscissa (locally Lipschitz, unbounded below)
ε-pseudospectral radius (locally Lipschitz, bounded below).

The routines in PSARNOT not only compute these values but also compute their respective gradients.

The goal of each test problem is to design a single controller matrix for one or more static-output-feedback (SOF) plants by optimizing one or more of the four stability measures listed above.

The objective, for a chosen fixed subset of the SOF plants, is to first stabilize them all, and then continue to reduce their stability measures (in attempt to increase their robustness to noise). This is done by specifying a min-max objective function to minimize the maximum of their chosen stability measures.
The constraint is that the SOF plants in the complement set, i.e. those not appearing in the objective, must remain stable (again with respect to the choice of stability measures listed above).

PSARNOT includes data for 100 non-locally-Lipschitz spectral radius optimization test problems and 100 locally-Lipschitz ε-pseudospectral radius optimization test problems. For more details on the exact mathematical definition of these problems, and how they were generated, we refer the interested reader respectively to Section 4 and Section 6.1 of the paper mentioned below.

Spectral radius optimization example (non-locally Lipschitz)

The four rows show the spectral configurations for four controllers produced by different optimization methods. The left three columns, in blue, indicate the SOF plants being optimized while while the right two columns, in red, indicate the SOF plants that must remain stable. All the plants have dimension seven and each plant's seven eigenvalues are depicted with plus signs. The blue and red circles indicate the spectral radius of each plant, for the objective and constraint plants respectively. On the objective plots, the dashed black circle corresponds to the max spectral radius of the three plants in the objective for that particular method’s controller. The dashed black circle on the constraint plots is the unit circle (the stability boundary).

As can be seen from the figure above, this non-locally-Lipschitz spectral radius optimization PSARNOT test problem exhibits a high degree of nonsmoothness. In the objective, for three out of the four controllers, the spectral radius of each plant is tied with one another (that is, the tie is across plants in the objective for a single controller). The two plants in constraint are similarly tied for the same three controllers and furthermore, their individual constraint functions are active, i.e. the spectral radius of each of these plants is equal to the stability boundary. Finally, for many of the plants, we observe that there are multiple eigenvalues (excluding conjugates) whose moduli are attaining their plant's spectral radius and that some of these eigenvalues are clustering and/or coalescing into double eigenvalues.

Pseudospectral radius example (locally Lipschitz)

The four rows show the ε-pseudospectral configurations for four controllers produced by different optimization methods, for a fixed value of ε. The left four columns, in blue, indicate the SOF plants being optimized while while the right column, in red, indicates the single SOF plant that must remain stable. All the plants have dimension eight and each plant's eight eigenvalues are depicted with plus signs. The blue and red contours indicate the ε-pseudospectral boundary of each plant, for the objective and constraint plants respectively. On the objective plots, the dashed black circle corresponds to the max ε-pseudospectral radius of the four plants in the objective for that particular method’s controller. The dashed black circle on the constraint plots is the unit circle (the stability boundary).

This PSARNOT example, now a locally-Lipschitz ε-pseudospectral radius optimization problem, also exhibits a high degree of nonsmoothness. For all of the four controllers, we see that for the objective, the ε-pseudospectral radius of each plant is tied with one another (again, meaning that the tie is across plants in the objective for a single controller). Furthermore, for three of the controllers, the contraint is also active, with the ε-pseudospectral radius of these three plants being equal to the stability boundary. Finally, for nearly all of the plants, we observe that there are multiple points on the ε-pseudospectral boundary (again excluding conjugates) that are attaining their plant's ε-pseudospectral spectral radius.

How to install and use PSARNOT

Download the latest version of PSARNOT on GitLab (v1.0).
For pseudospectral abscissa and radius test problems, PSARNOT requires that Emre Mengi's robust stability routines are installed and available on the search path in MATLAB. Specifically, PSARNOT requires the pspa and pspr routines for computing the pseudospectral abscissa and radius, respectively.
Add the desired location of the extracted PSARNOT folder to the search path in MATLAB.
To read the PSARNOT documentation, enter: help psarnotObjectiveFunction help psarnotConstraintFunction help psarnotMakeFunctionHandles
PSARNOT includes two data files: sof_data_sradius.mat sof_data_psradius.mat that respectively contain 100 spectral radius and 100 ε-pseudospectral radius PSARNOT test instances. Each data file contains a single MATLAB cell array of length 100 called sof_data.
PSARNOT test instances can be loaded as follows: load('sof_data_psradius.mat'); instance = sof_data{10}; n_var = instance.n_var; obj_fn = @(x) psarnotObjectiveFunction(instance,x); con_fn = @(x) psarnotConstraintFunction(instance,x); The number of variables n_var and anonymous function handles obj_fn and con_fn, which take a single column vector x of length n_var as input, can be directly used with many optimization packages. Other packages may require that the PSARNOT problem data instance and the psarnotObjectiveFunction and psarnotConstraintFunction functions are provided separately.
PSARNOT also provides a helper function for creating the anonymous function handles for the objective and constraint functions: load('sof_data_psradius.mat'); instance = sof_data{10}; [n_var,obj_fn,con_fn,all_fn] = psarnotMakeFunctionHandles(instance); The all_fn function handle, which can be used with optimization packages such as GRANSO, also takes a single argument x but it evaluates the objective and contraint functions, and their gradeints, all simultaneously.

Additional test problems

If you generate new PSARNOT test examples and do not mind sharing them, please let us know so that a list of PSARNOT test sets can be maintained here.

Citing

If you publish work that either refers to or makes use of PSARNOT, please cite the following paper:

A BFGS-SQP Method for Nonsmooth, Nonconvex, Constrained Optimization and its Evaluation using Relative Minimization Profiles
Frank E. Curtis, Tim Mitchell, and Michael L. Overton
Optimization Methods and Software, 32(1):148–181, 2017.

When referring to this software, please also include which version was used, e.g. PSARNOT v1.0.

License

PSARNOT is licensed under the GNU Affero General Public License, version 3.

PSARNOT contains two minor subroutines that are licensed under the GNU General Public License, version 3. These subroutines, which are identified by their GPL v3 license headers, are modified code derived from the PSAPSR package, specifically my v1.3-1.4 modified branch.