PhD Defense R.M. Badenbroek MSc
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.