Sparse optimization models are ubiquitous in machine learning, statistics, finance, signal processing, imaging science, geophysics and many other arears.  Concerned with the huge computational burdens of the interior point methods (IPMs)  for solving  big scale problems, more researchers and practitioners tend to adopt first order methods such as Nesterov’s accelerated proximal gradient (APG) methods and the alternating direction methods of multipliers (ADMM) for the rescue. While these first order methods have enjoyed very successful stories for some interesting applications, they encounter insurmountable difficulties in dealing with many real data problems of big scales even only with a low or moderate solution quality. New ideas for solving these problems are in urgent needs.

In this mini-course, we intend to introduce highly efficient and robust semismooth Newton based proximal point algorithms by fully exploring the second order sparsity exhibited in these  sparse optimization models such as in the lasso/fused lasso/group lasso and support vector machine models. We shall divide this course into four parts:

(1)       In the first part, we shall start with the introduction of the Moreau-Yosida regularization of convex functions to induce semismooth functions. This part is about the differential properties of the proximal mappings, which are non-differentiable.

(2)       In the second part, we shall give a brief description on Newton’s method for nonsmooth equations developed in the last three decades.

(3)       In the third part, we shall present error bound results for piecewise convex quadratic functions and beyond and introduce the proximal point algorithms.  The error bounds are for the convergence rate analysis of optimization algorithms.

(4)       In the last part, we shall demonstrate how the results in the first three parts can be put together to produce the promised semismooth Newton based proximal point algorithms for solving big sparse optimization problems.  Numerical examples with the real data are used to illustrate the power of the introduced algorithms. .

Prerequisites: Essentially nothing is required except for some basic knowledge about convex analysis.

[Note: This mini-course is mainly based on my joint works with my colleague Professor Kim-Chuan Toh and many other collaborators.]