Interior point methods and simulated annealing for nonsymmetric conic optimization

Riley Badenbroek

Research output: ThesisDoctoral Thesis

Abstract

This thesis explores four methods for convex optimization. The first two are an
interior point method and a simulated annealing algorithm that share a theoretical
foundation. This connection is due to the interior point method’s use of the so-called entropic barrier, whose derivatives can be approximated through sampling.
Here, the sampling will be carried out with a technique known as hit-and-run. By
carefully analyzing the properties of hit-and-run sampling, it is shown that both the interior point method and the simulated annealing algorithm can solve a convex optimization problem in the membership oracle setting. The number of oracle calls made by these methods is bounded by a polynomial in the input size.
The third method is an analytic center cutting plane method that shows promising
performance for copositive optimization. It outperforms the first two methods by
a significant margin on the problem of separating a matrix from the completely
positive cone. The final method is based on Mosek’s algorithm for nonsymmetric conic optimization. With their scaling matrix, search direction, and neighborhood, we define a method that converges to a near-optimal solution in polynomial time.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Tilburg University
Supervisors/Advisors
  • de Klerk, Etienne, Promotor
  • Schweizer, Nikolaus, Co-promotor
Award date24 Feb 2021
Place of PublicationTilburg
Publisher
Print ISBNs978 90 5668 641 3
Publication statusPublished - 2021

Fingerprint Dive into the research topics of 'Interior point methods and simulated annealing for nonsymmetric conic optimization'. Together they form a unique fingerprint.

Cite this