Edinburgh Research Archive logo

Edinburgh Research Archive

University of Edinburgh homecrest
View Item 
  •   ERA Home
  • Mathematics, School of
  • Mathematics thesis and dissertation collection
  • View Item
  •   ERA Home
  • Mathematics, School of
  • Mathematics thesis and dissertation collection
  • View Item
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.

Randomly assembled cyclic multi-block ADMM: a fast method for large-scale linearly constrained quadratic optimization

View/Open
Mihic2021.pdf (853.1Kb)
Date
22/02/2022
Item status
Restricted Access
Embargo end date
22/02/2023
Author
Mihic, Kresimir
Metadata
Show full item record
Abstract
This work is motivated by a simple question: how to find a relatively good solution to a very large optimization problem in a limited amount of time. We consider the linearly constrained convex minimization model with an objective function that is the sum of multiple separable functions and a coupled quadratic function. Such problems naturally arise from applications such as machine and statistical learning, image processing, portfolio management, tensor decomposition, matrix completion or decomposition, manifold optimization, data clustering and many other problems of practical importance. This thesis focuses on the development of new algorithms that are based on the alternating direction method of multipliers (ADMM). The first part proposes a randomly assembled multi-block and cyclic alternating direction method of multipliers (RAC-ADMM), a novel ADMM algorithm with which we hope to mitigate both the problem of slow convergence and the issues with divergence that arise when the multi-block ADMM is applied to convex problems with cross-block coupled variables. We discuss the theoretical properties of RAC-ADMM and show when random assembling helps and when it hurts; allowing us to develop criteria for almost sure convergence. The second part utilizes the aforementioned theoretical guidance on RAC-ADMM to investigate solution methods for continuous and mixed integer quadratic problems (QPs, MIQPs). First, we develop a robust and efficient general-purpose QP solver, RACQP, capable of detecting infeasible and unbounded problems. Next, we devise two extensions that enable RACQP to address MIQP – one applicable to situations where a solution needs to be found rapidly but some level of primal infeasibility can be tolerated; and the other that implements a custom branch-and-bound algorithm. Multiple numerical tests, conducted on both randomly-generated and large-scale benchmark instances show that, for most quadratic optimization problems, RACQP matches, and often exceeds, the computational efficiency of commercial solvers and competing ADMM-based solvers.
URI
https://hdl.handle.net/1842/38603

http://dx.doi.org/10.7488/era/1866
Collections
  • Mathematics thesis and dissertation collection

Library & University Collections HomeUniversity of Edinburgh Information Services Home
Privacy & Cookies | Takedown Policy | Accessibility | Contact
Privacy & Cookies
Takedown Policy
Accessibility
Contact
feed RSS Feeds

RSS Feed not available for this page

 

 

All of ERACommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsPublication TypeSponsorSupervisorsThis CollectionBy Issue DateAuthorsTitlesSubjectsPublication TypeSponsorSupervisors
LoginRegister

Library & University Collections HomeUniversity of Edinburgh Information Services Home
Privacy & Cookies | Takedown Policy | Accessibility | Contact
Privacy & Cookies
Takedown Policy
Accessibility
Contact
feed RSS Feeds

RSS Feed not available for this page