Some First-order Algorithms For Structured Optimizations

In the real world applications, there are quite a few structured optimizations aris-ing from the fields such as electrical engineering, statistics, and computer science, including digital signal processing, signal enhancement, natural imaging processing, matrix processing, medical imaging processing, and traffic network analysis, and etc. Solving such problem constitutes a critical step in an emerging methodology in these applications, hence, it is important to develop efficient algorithms for it. In this thesis, we consider four types of structured optimizations derived from the above applications.These optimization problems, more or less, have some favorable structures, e.g., separability. If we use the standard methods, such as interior-point methods, to solve these problems, these good structures could be totally ignored. Additionally, the stan-dard methods such as interior point methods are not directly amenable to large prob-lems due to their inherent high computational complexity.As a result, we need to develop dedicated algorithms that are able to handle the specific structure of the problem. In recent years, the first-order algorithms such as "forward-backward splitting method","augmented Lagrangian method", or "proximal point algorithm" have attracted more and more attentions from the researchers. In fact, the low per-iteration cost of these algorithms gives them better ability to handle large-scale problem. These algorithms have been extensively studied in the field of nonlinear programming, providing abundant theory and practical improvements. Additionally, the favorable structure of the problem under consideration can be utilized to simplify the subproblem.However, these algorithms could still have limitations, e.g., their subproblems can be difficult or expensive to solve. One remedy is allowing inexact minimization which is equivalent to solving a relaxed subproblem in each iteration, and we require the relaxed subproblem to be implementable, e.g., when the relaxed subproblem is simple enough to have a closed form solution. Although the algorithms based on above idea can work well for a few types of problems, it is still possible to improve them further. On one hand, the algorithms based on inexact minimization can suffer from the slow convergence. On the other hand, the relaxed subproblem may not always have a closed form solution.In fact, most of the above first-order algorithms can be interpreted from the aspect of variational inequality (VI), and their convergence analysis can be categorized into a unified framework. Under this framework, we are able to develop new algorithms based on our need. Specially, for saving the cost, we can require the algorithms to be implementable for the specific problem by taking the advantage of problem structure.In this thesis, we propose several such algorithms for four types of optimization problems, and demonstrate their efficiencies in the numerical experiments by compar-ing them with some state-of-the-art algorithms. Each of these algorithms is only for one type of problem, hence, they are not general-purpose methods, and not designed to replace the standard methods, however, for the specific problem they are designed for, these dedicated algorithms are proved to be efficient and practical.