{"id":152,"date":"2026-02-11T08:20:30","date_gmt":"2026-02-11T08:20:30","guid":{"rendered":"https:\/\/almoa.aau.at\/?page_id=89"},"modified":"2026-03-28T19:26:13","modified_gmt":"2026-03-28T18:26:13","slug":"dc-7-approximately-optimal-interior-point-methods-for-conic-programs","status":"publish","type":"page","link":"https:\/\/almoa.aau.at\/?page_id=152","title":{"rendered":"DC 7 &#8211; Approximately Optimal Interior Point Methods for Conic Programs"},"content":{"rendered":"<div class=\"dc-project\">\r\n<p class=\"wp-block-paragraph\"><strong>Project Title:<\/strong> Approximately Optimal Interior Point Methods for Conic Programs<br \/><strong>Doctoral Candidate:<\/strong> N.N.<br \/><strong>Host Institution:\u00a0<\/strong>CWI Amsterdam<br \/><strong>Supervisors:<\/strong> <a href=\"https:\/\/homepages.cwi.nl\/~dadush\/\">Daniel Dadush<\/a>, <a href=\"https:\/\/www.lix.polytechnique.fr\/~liberti\/\">Leo Liberti<\/a><\/p>\r\n\r\n\r\n\r\n<p class=\"wp-block-paragraph\"><strong>Objectives:<\/strong> Interior Point Methods (IPMs) yield the most practically efficient approach for solving large structured convex programs to high accuracy. Iterations of an IPM require solving an expensive system of linear equations, and hence it is crucial to minimise the number of iterations. From a theoretical perspective, the predominant approach has been to design IPMs with good worst-case convergence rates, which tend to give extremely pessimistic estimates of empirical performance. Moving away from this paradigm, the DC will design IPMs whose performance can be directly compared to a natural geometric lower &#8211; the minimum number of linear segments needed to traverse the neighbourhood of the path &#8211; which was very recently shown to be possible for linear programming. As a first research direction, the DC will explore whether approximately optimal IPMs can be designed for conic quadratic and semidefinite programs, which would substantially increase the applicability of the new theory. As a second direction, the DC will analyse the average case performance of these methods, with the goal of demonstrating that IPMs can provably perform better than their worst-case rates suggest on large classes of instances. Finally, the DC will implement these new IPMs to test whether they achieve speedups (in terms of iteration counts) on practical instances, including semidefinite relaxations of the optimal power flow problem as well as LP relaxations of multi-stage network planning problem.<\/p>\r\n\r\n\r\n\r\n<p class=\"wp-block-paragraph\"><strong>Expected Results:<\/strong> New interior point methods for conic programs with approximately optimal iteration complexity, as well as improved complexity estimates for linear programming. Smoothed analysis of the central path length for linear programs with Gaussian data. Publicly available implementations of the new IPMs together with an experimental evaluation of their performance on Netlib instances.<\/p>\r\n\r\n\r\n\r\n<p class=\"wp-block-paragraph\"><strong>Planned secondment:<\/strong> 3 months at Mosek (E. Andersen) during the 2nd year to gain experience with the implementation of interior point methods; 4 months at IP Paris (L. Liberti) just before the beginning of the 3rd year to gain experience with random projection methods and their potential to speed up IPM iterations<\/p>\r\n\r\n\r\n\r\n<p class=\"wp-block-paragraph\"><strong>Degree awarding institution:<\/strong> Universiteit Utrecht<\/p>\r\n<p><strong>Note:<\/strong> Due to the 4-year PhD programme at Universiteit Utrecht, the contract of DC 7 will be extended to 4 years.<\/p>\r\n<\/div>","protected":false},"excerpt":{"rendered":"<p>Project Title: Approximately Optimal Interior Point Methods for Conic ProgramsDoctoral Candidate: N.N.Host Institution:\u00a0CWI AmsterdamSupervisors: Daniel Dadush, Leo Liberti Objectives: Interior Point Methods (IPMs) yield the most practically efficient approach for solving large structured convex programs to high accuracy. Iterations of an IPM require solving an expensive system of linear equations, [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_crdt_document":"","footnotes":""},"class_list":["post-152","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/almoa.aau.at\/index.php?rest_route=\/wp\/v2\/pages\/152","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/almoa.aau.at\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/almoa.aau.at\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/almoa.aau.at\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/almoa.aau.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=152"}],"version-history":[{"count":7,"href":"https:\/\/almoa.aau.at\/index.php?rest_route=\/wp\/v2\/pages\/152\/revisions"}],"predecessor-version":[{"id":877,"href":"https:\/\/almoa.aau.at\/index.php?rest_route=\/wp\/v2\/pages\/152\/revisions\/877"}],"wp:attachment":[{"href":"https:\/\/almoa.aau.at\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=152"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}