The main research goal of this grant was the development and implementation of optimization methods for solving large-scale problems arising in applications such as signal processing. The field of mathematical optimization involves identifying a solution that optimizes a particular objective. Many problems in science and engineering such as curve fitting, airfoil design, scheduling, power grid planning, and supply chain management can be posed as optimization problems. Our work focused on three areas: (i) optimization method design, (ii) numerical linear algebra underlying the optimization methods, and (iii) applications to signal processing.

(i) Optimization method design: We developed mathematical software that can solve large-scale optimization problems using trust-region methods based on quasi-Newton methods. Trust-region methods define a region in which a model to the objective function is hoped to be a reasonably-accurate approximation and compute a search direction within this region. Gradient-based optimization methods generally fall into two categories, with trust-region methods being one of them and line-search methods being the other. Quasi-Newton methods are used when the second-derivative matrix is difficult to compute or invert, with the latter being true in general for large-scale problems. For this grant, the quasi-Newton trust-region methods that the we developed were shown to outperform well-established trust-region and line-search methods on a standard test set of optimization problems. Our trust-region methods exploit the compact representation of quasi-Newton matrices, which results in a fast and accurate subproblem solution at each iteration.

(ii) Numerical linear algebra: A key component to the success of our trust-region methods is the compact representation of the quasi-Newton matrices. In work related to these methods, we extended the compact representation of the most widely-used quasi-Newton matrix (the Broyden-Fletcher-Goldfarb-Shanno matrix) to a whole class of quasi-Newton matrices. In addition, we developed efficient solvers that are able to compute solutions of very large systems of linear equations involving these matrices.

(iii) Image processing: We applied these techniques to inverse problems arising in image processing. In particular, we solved problems where the true signal has an underlying sparsity structure that can be leveraged for higher accuracy reconstruction. These problems appear in compressed sensing (CS) applications. The methods that we developed have been demonstrated to outperform existing CS software not only in improving the error in the signal reconstruction but in enforcing the sparsity structure in the solution.