Logo eprints

Proximal algorithms for structured nonconvex optimization

Themelis, Andreas (2018) Proximal algorithms for structured nonconvex optimization. Advisor: Patrinos, Prof Panagiotis. Coadvisor: Bemporad, Prof. Alberto . pp. 215. [IMT PhD Thesis]

[img] Text
Themelis_phdthesis.pdf - Published Version
Available under License Creative Commons Attribution No Derivatives.

Download (1MB)


Due to their simplicity and versatility, splitting algorithms are often the methods of choice for many optimization problems arising in engineering. “Splitting” complex problems into simpler subtasks, their complexity scales well with problem size, making them particularly suitable for large-scale applications where other popular methods such as IP or SQP cannot be employed. There are, however, two major downsides: 1) there is no satisfactory theory in support of their employment for nonconvex problems, and 2) their efficacy is severely affected by ill conditioning. Many attempts have been made to overcome these issues, but only incomplete or case-specific theories have been established, and some enhancements have been proposed which however either fail to preserve the simplicity of the original algorithms, or can only offer local convergence guarantees. This thesis aims at overcoming these downsides. First, we provide novel tight convergence results for the popular DRS and ADMM schemes for nonconvex problems, through an elegant unified framework reminiscent of Lyapunov stability theory. “Proximal envelopes”, whose analysis is here extended to nonconvex problems, prove to be the suitable Lyapunov functions. Furthermore, based on these results we develop enhancements of splitting algorithms, the first that 1) preserve complexity and convergence properties, 2) are suitable for nonconvex problems, and 3) achieve asymptotic superlinear rates.

Item Type: IMT PhD Thesis
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
PhD Course: Computer Decision and System Science
Identification Number: 10.6092/imtlucca/e-theses/262
NBN Number: urn:nbn:it:imtlucca-27288
Date Deposited: 26 Jul 2019 08:54
URI: http://e-theses.imtlucca.it/id/eprint/262

Actions (login required, only for staff repository)

View Item View Item