Convergence analysis and applications of two optimization algorithms

  • Yaonan Ma

Student thesis: Doctoral Thesis


Nowadays, many optimization problems in real applications share a separable structure in the objective and it becomes more and more common to solve these problems by decomposition methods such as fast iterative shrinkage-thresholding algorithm (FISTA), generalized alternating direction method of multipliers (GADMM), and first-order primal-dual algorithm (PD), to name just a few. In this thesis, we focus on two optimization algorithms for solving convex programs: θ-scheme and a preconditioned primal-dual algorithm. For the θ-scheme, we first present an elaborative convergence analysis in a Hilbert space and propose a general convergent inexact θ-scheme. Second, for unconstrained problems, we prove the convergence of the θ-scheme and show a sublinear convergence rate in terms of the objective function. Furthermore, a practical inexact θ-scheme is derived to solve l_2-loss based problems and its convergence is proved. Third, for constrained problems, even though the convergence of the θ-scheme is available in the literature, yet its sublinear convergence rate is unknown until we provide one via a variational reformulation of the solution set. Besides, in order to relax the condition imposed on the θ-scheme, we propose a new variant and show its convergence. Finally, some preliminary numerical experiments demonstrate the efficiency of the θ-scheme and our proposed methods. For the preconditioned primal-dual algorithm, noticing that a practical step size cannot lie in the theoretical region, we show that the range of dual step size can be enlarged by 1/3 at most and at the same time, the convergence and a sublinear convergence rate can be ensured. Therefore, this practical step size can indeed guarantee the convergence. Furthermore, if more regularity conditions are imposed on objective functions, we can obtain a linear convergence rate. Finally, some connection with other methods is revealed. In future work, we focus on the acceleration of the θ-scheme. Some preliminary numerical experiments demonstrate the potential efficiency of our proposed accelerated θ-scheme. Therefore, it would be our priority of further study.

Date of Award23 Jul 2019
Original languageEnglish
SupervisorLizhi LIAO (Supervisor)

User-Defined Keywords

  • Convergence
  • Mathematical optimization

Cite this