Algorithms and stability analysis for optimization problems with sparsity

Xu, Jialiang (2019). Algorithms and stability analysis for optimization problems with sparsity. University of Birmingham. Ph.D.

Preview

Xu2019PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (1MB) | Preview

Abstract

The optimization models with sparsity arise in many areas of science and engineering, such as compressive sensing, image processing, statistical learning and machine learning. In this thesis, we study a general 10-minimization model, which can be used to deal with many practical applications. Firstly, we show some theoretical properties of the solutions of this model. Then, two types of re-weighted 11-algorithms will be developed from both the perspectives of primal and dual spaces, respectively. The primal re-weighted 11-algorithms will be derived through the 1st-order approximation of the so-called merit functions for sparsity. The dual re-weighted 11-algorithms for the general 10-model will be developed based on the reformulation of the general 10-model as a certain bilevel programming problem under the assumption of strict complementarity. We conduct numerical experiments to demonstrate the efficiency of the primal and dual re-weighted 11-algorithms and compare with some existing algorithms. We also establish a general stability result for a class of 11-minimization approach which is broad enough to cover many important special cases. Unlike the existing stability results developed under the null space property and restricted isotonic property, we use a classic Hoffman's theorem to establish a restricted-weak-RSP-based stability result for this class of 11-minimization approach.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):