Semi-Smooth Newton Methods for Selected Applications

Recently we suggested two strategies for globalizing semi-smooth Newton methods for convex quadratic optimization problems with box-constraints. The problem appears as a basic building block in many applications, for instance in the context of sequential quadratic optimization methods. It also turns up in problems from mathematical physics and computer science. Our new approaches have several preferable features like simplicity, finding the exact numerical solution and easy implementation. We demonstrated that our methods outperform other available approaches on a large and diverse set of benchmark instances. Hence they are the state-of-the-art methods for this problem class. During our Erwin Schrödinger-Fellowship we aim to extend our approaches in several directions. During our research visit of Prof. Pablo Parrilo and his team at the Massachusetts Institute of Technology we plan to apply our methods for non-negative matrix factorization, L1-norm minimization and their combination, non-negative sparse coding. Our main research question is: Can the strong practical performance of our methods also be achieved within appropriate frameworks for tackling these important applications? First tests demonstrate that the successful extension of our methods for these applications is very likely and due to the importance of the applications also quite beneficial. Recently we examined a combination of an augmented Lagrangian method with our new methods described above to tackle general convex quadratic optimization problems. This problem class constitutes one of the most important types of optimization problems besides linear programming. First computational experiments indicate a very promising practical performance of our approach on large-scale instances. But so far our method lacks a thorough convergence theory, this means a proof that our approach always yields the optimal solution for all possible instances. The detailed analysis of projections on general polytopes is needed for developing such a theory. While developing a convergence theory is very challenging, the impact of extending our extremely fast methods to general convex quadratic problems would be very high. Prof. Parrilo is an expert in the areas described above. Hence the implementation of the research ideas suggested greatly benefits from his expertise. In summary on the one hand we aim to use our new methods within existing frameworks for solving many relevant applications in the areas compressed sensing, face recognition, clustering, computer vision, signal processing and bioinformatics. The degree of complexity of this intent is well assessable and the successful implementation is very likely. Additionally we want to extend our approaches such that they are applicable to general convex quadratic optimization problems. The complexity of theoretical mathematical results required for reaching this goal is very high. But if we succeed in realizing this extension, it is quite possible that our approach replaces interior-point methods as the state-of-the-art algorithm for solving general convex quadratic optimization problems. This would be a considerable achievement with a very high impact.

We suggested two strategies for globalizing semi-smooth Newton methods for convex quadratic optimization problems with box-constraints. The problem appears as a basic building block in many applications, for instance in the context of sequential quadratic optimization methods to solve more general nonlinear problems. It also appears in problems from mathematical physics and computer science (compressed sensing, face recognition). Our approaches are purely combinatorial and have several preferable features like simplicity (no tuning parameters), finding the exact numerical solution, insensitivity with respect to initialization and easy implementation. We demonstrated that our semi-smooth Newton methods outperform projected gradient methods, projected quasi-Newton methods, standard active set methods and block principal pivoting methods on a large and diverse set of benchmark instances. During my Erwin Schrödinger-Fellowship with Prof. Pablo Parrilo at the Massachusetts Institute of Technology we aimed to extend our state-of-the- art algorithms for convex quadratic optimization problems with box-constraints in several directions. Initially we applied our methods (with necessary modifications, e.g. strategies to exploit the special structure of the objective function) to non-negative matrix factorization and L1- norm minimization. If L1-regularization is combined with non-negative matrix factorization, the resulting problem is called non-negative sparse coding. For solving this problem, a combinations of semi-smooth Newton methods for non-negative matrix factorization and L1- norm minimization can be used. Though with the help of a series of computational experiments on a variety of benchmark instances, we established that our methods could not improve the best specialized algorithms for the respective problem classes. However, we were able to show that our methods, including their convergence theory, can be extended to the (bound) linear complementarity problem, which is a generalization of convex quadratic optimization problems with box-constraints. For this problem class, our extended methods significantly outperformed the best algorithms from literature on a large, diverse set of benchmark instances in terms of required computation time. Linear complementarity problems are essential for the solution of many applications, such as bimatrix games, market and traffic equilibrium models, option pricing, portfolio models and elastoplastic structural analysis.