4 papers
An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix
Riley Badenbroek, Etienne de Klerk
We propose an analytic center cutting plane method to determine if a matrix is completely positive, and return a cut that separates it from the completely positive cone if not. Thi…
An Algorithm for Nonsymmetric Conic Optimization Inspired by MOSEK
Riley Badenbroek, Joachim Dahl
We analyze the scaling matrix, search direction, and neighborhood used in MOSEK's algorithm for nonsymmetric conic optimization [Dahl and Andersen, 2019]. It is proven that these c…
Simulated annealing with hit-and-run for convex optimization: rigorous complexity analysis and practical perspectives for copositive programming
Riley Badenbroek, Etienne de Klerk
We give a rigorous complexity analysis of the simulated annealing algorithm by Kalai and Vempala [Math of OR 31.2 (2006): 253-266] using the type of temperature update suggested by…
Complexity Analysis of a Sampling-Based Interior Point Method for Convex Optimization
Riley Badenbroek, Etienne de Klerk
We develop a short-step interior point method to optimize a linear function over a convex body assuming that one only knows a membership oracle for this body. The approach is based…