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.

No additional funding sources recorded.