Prof. Tamás Terlaky, PhD
Alcoa Endowed Chair Professor
Quantum Computing Optimization Laboratory
Department of Industrial and Systems Engineering
Lehigh University
Bethlehem, PA, USA
e-mail: terlaky@lehigh.edu
webpage: https://coral.ise.lehigh.edu/terlaky/
Title of the invited lecture: Quantum Interior Point Methods (QIPMs) with Iterative Refinement for Linear and Semidefinite Optimization
Authors: Tamás Terlaky
QIPMs build on classic polynomial time IPMs. In QIPMs we apply Quantum Linear System Algorithms (QLSAs) to solve Newton systems within IPMs to gain quantum speedup in solving Linear Optimization (LO) and Semidefinite Optimization (SDO) problems. Due to their inexact nature, QLSAs mandate the development of inexact variants of IPMs which by default are inexact infeasible methods. We also discuss “quantum inspired” Inexact-Feasible IPMs (IF-IPMs) for LO and SDO problems, using novel Newton systems to generate inexact but feasible steps. We show that IF-QIPMs enjoys the to-date best iteration complexity. Further, we explore how QLSAs can be used efficiently in iterative refinement (IR) schemes to find optimal solutions without excessive calls to QLSAs. Notably, the IR-IPM scheme enjoys quadratic convergence of the optimality gap.
Short CV:
Dr. Terlaky has published four books, edited over ten books and journal special issues and published over 200 research papers. Topics include theoretical and algorithmic foundations of mathematical optimization; nuclear reactor core reloading, oil refinery, VLSI design, radiation therapy treatment, and inmate assignment optimization; quantum computing.
Dr. Terlaky is Editor-in-Chief of the Journal of Optimization Theory and Applications. He has served as associate editor of ten journals and has served as conference chair, conference organizer, and distinguished invited speaker at conferences all over the world. He was general Chair of the INFORMS 2015 Annual Meeting, a former Chair of INFORMS’ Optimization Society, Chair of the ICCOPT Steering Committee of the Mathematical Optimization Society, Chair of the SIAM AG Optimization, and Vice President of INFORMS. He received the MITACS Mentorship Award; Award of Merit of the Canadian Operational Society, Egerváry Award of the Hungarian Operations Research Society, H.G. Wagner Prize of INFORMS, Outstanding Innovation in Service Science Engineering Award of IISE. He is Fellow of INFORMS, SIAM, IFORS, The Fields Institute, and elected Fellow of the Canadian Academy of Engineering. He was the opening Plenary Speaker at ISMP’2024 in Montreal.