An algorithm for nonsymmetric conic optimization inspired by MOSEK. (4th May 2022)

• Record Type: Journal Article
• Authors: Badenbroek, Riley; Dahl, Joachim
• Is Part Of: Optimization methods and software. Volume 37:Number 3(2022)
• Page Start: 1027
• Page End: 1064
• Publication Date: 2022-05-04
• Subjects: MOSEK -- interior point method -- conic optimization -- nonsymmetric cones -- homogeneous model -- self-dual embedding; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2021.1882457
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We analyse the scaling matrix, search direction, and neighbourhood used in MOSEK's algorithm for nonsymmetric conic optimization [J. Dahl and E.D. Andersen, A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization, preprint (2019)]. It is proven that these can be used to compute a near-optimal solution to the homogeneous self-dual model in polynomial time. This provides a theoretical foundation for MOSEK's nonsymmetric conic algorithm. The main steps in the analysis are sandwiching MOSEK's scaling matrix between the primal and dual barrier's Hessians, and using this information to carefully check all the neighbourhood conditions after a small, improving step is taken.