The Homogeneous Interior-Point Algorithm: Nonsymmetric Cones, Warmstarting, and Applications

Anders Skajaa

Research output: Book/ReportPh.D. thesis

818 Downloads (Pure)

Abstract

The overall topic of this thesis is convex conic optimization, a sub-field of mathematical optimization that attacks optimization problem with a certain geometric structure. These problems allow for modelling of an extremely wide range of real-world problems, but the availability of solution algorithms for these problems is still limited.

The goal of this thesis is to investigate and shed light on two computational aspects of homogeneous interior-point algorithms for convex conic optimization:
The first part studies the possibility of devising a homogeneous interior-point method aimed at solving problems involving constraints that require nonsymmetric cones in their formulation. The second part studies the possibility of warmstarting the homogeneous interior-point algorithm for conic problems. The main outcome of the first part is the introduction of a completely new homogeneous interior-point algorithm designed to solve nonsymmetric convex conic optimization problems. The algorithm is presented in detail and then analyzed. We prove its convergence and complexity. From a theoretical viewpoint, it is fully competitive with other algorithms and from a practical viewpoint, we show that it holds lots of potential, in several cases being superior to other solution methods.

The main outcome of the second part of the thesis is two new warmstarting schemes for the homogeneous interior-point algorithm for conic problems. Again, we first motivate and present the schemes and then analyze them. It is proved that they, under certain circumstances, result in an improved worst-case complexity as compared to a normal coldstart. We then move on to present an extensive series of computational results substantiating the practical usefulness of these warmstarting schemes. These experiments include standard benchmarking problem test sets as well as an application from smart energy systems.
Original languageEnglish
Place of PublicationKgs. Lyngby
PublisherTechnical University of Denmark
Number of pages149
Publication statusPublished - 2013
SeriesIMM-PHD-2013
Number311
ISSN0909-3192

Fingerprint

Dive into the research topics of 'The Homogeneous Interior-Point Algorithm: Nonsymmetric Cones, Warmstarting, and Applications'. Together they form a unique fingerprint.

Cite this