Convergence Analysis and Improvements for Projection Algorithms and Splitting Methods

Mattias Fält

Forskningsoutput: AvhandlingDoktorsavhandling (sammanläggning)

366 Nedladdningar (Pure)


Non-smooth convex optimization problems occur in all fields of engineering. A common approach to solving this class of problems is proximal algorithms, or splitting methods. These first-order optimization algorithms are often simple, well suited to solve large-scale problems and have a low computational cost per iteration. Essentially, they encode the solution to an optimization problem as a fixed point of some operator, and iterating this operator eventually results in convergence to an optimal point. However, as for other first order methods, the convergence rate is heavily dependent on the conditioning of the problem. Even though the per-iteration cost is usually low, the number of iterations can become prohibitively large for ill-conditioned problems, especially if a high accuracy solution is sought.

In this thesis, a few methods for alleviating this slow convergence are studied, which can be divided into two main approaches. The first are heuristic methods that can be applied to a range of fixed-point algorithms. They are based on understanding typical behavior of these algorithms. While these methods are shown to converge, they come with no guarantees on improved convergence rates.

The other approach studies the theoretical rates of a class of projection methods that are used to solve convex feasibility problems. These are problems where the goal is to find a point in the intersection of two, or possibly more, convex sets. A study of how the parameters in the algorithm affect the theoretical convergence rate is presented, as well as how they can be chosen to optimize this rate.
Tilldelande institution
  • Institutionen för reglerteknik
  • Giselsson, Pontus, handledare
  • Bernhardsson, Bo, Biträdande handledare
  • Banert, Sebastian, Biträdande handledare
Tilldelningsdatum2021 feb. 26
ISBN (tryckt)978-91-7895-763-7
ISBN (elektroniskt)978-91-7895-764-4
StatusPublished - 2021 feb. 2

Bibliografisk information

Defence details
Date: 2021-02-26
Time: 10:15
Place: Lecture hall A, building KC4, Naturvetarvägen 18, Lund University, Faculty of Engineering LTH, Lund Join via Zoom:
External reviewer(s)
Name: Luke, Russell
Title: Professor
Affiliation: University of Göttingen, Germany

Ämnesklassifikation (UKÄ)

  • Reglerteknik


Utforska forskningsämnen för ”Convergence Analysis and Improvements for Projection Algorithms and Splitting Methods”. Tillsammans bildar de ett unikt fingeravtryck.

Citera det här