Nonsmooth Analysis and Numerical Optimization Techniques beyond Convexity

Portland State University, Portland OR

Investigators

Abstract

Convex analysis and optimization play a crucial role by providing the mathematical foundation and methods for solving problems in a variety of fields. At the same time, recent applications in these fields require optimization techniques beyond convexity. Although convex optimization techniques and numerical algorithms have been the topics of extensive research for more than 50 years, solving large-scale optimization problems without the presence of convexity remains a challenge. In this project, the principal investigator aims to develop new theoretical results in convex and nonsmooth analysis, and new numerical algorithms, for the optimization of nonconvex functions that are not necessarily differentiable, especially functions that are the difference of convex functions. Optimization problems of this sort arise in multi-facility location, clustering, machine learning, compressed sensing, and imaging applications. The investigator and his colleagues develop, implement, and test numerical algorithms for solving such problems. With no requirement on differentiability and convexity, these numerical algorithms bring new methods for solving complex optimization problems in different fields of application. This project aims to develop new theory of nonsmooth analysis and optimization methods for solving optimization problems without imposing conditions of differentiability or convexity. Based on a variational geometric approach, the first goal of this project is to develop new results in nonsmooth analysis to deal with optimization problems in which the objective functions are nondifferentiable and nonconvex. This approach provides a systematic development of nonsmooth analysis, making it accessible to researchers from different fields. The second goal of the project is to develop numerical algorithms for solving nonconvex optimization problems, especially those whose objective functions are representable as differences of convex functions, and to apply them to problems in multi-facility location, clustering and hierarchical clustering, machine learning, compressed sensing, and imaging. The investigator and his colleagues particularly focus on problems that involve different norms or constraints, requiring advances in smoothing and initialization techniques. They address the important issues of existence and uniqueness of optimal solutions of the models, initialization techniques based on global optimization methods, implementation of the algorithms for comparison and testing on artificial and real data sets, and the convergence rate of the algorithms. The results contribute to the development of nonsmooth analysis and its use in building and analyzing numerical algorithms for nonsmooth optimization problems that are not convex.