Tilburg University promotie PhD Defense

PhD Defense R.M. Badenbroek MSc

Date: Time: 16:00 Location: Aula

Interior Point Methods and Simulated Annealing for Nonsymmetric Conic Optimization

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.

 

  • Location: Cobbenhagen building, Aula 
  • Supervisor: Prof. E. de Klerk
  • Co-supervisor: Dr. N.F.F. Schweizer

We still offer a live stream for our ceremonies.

Live stream