Tamás Terlaky awarded NSF grant to study complexity of semidefinite and polynomial optimization

Tamás TerlakyAmong information engineers and scientists driving advances in theoretical computer science, control theory, statistics, quantum information sciences, and quantum computing in general, the topics of semidefinite and polynomial optimization (SDO and PO) attract great interest.

With support from the National Science Foundation Division of Computing and Communication Foundations, Tamás Terlaky, a professor of industrial and systems engineering at Lehigh University, is seeking to enhance the research community’s understanding of this complexity while laying the groundwork for future advances in high performance and quantum computing methods.

“High performance computing has witnessed a steady advance in the efficiency of what are known as interior-point methods, or IPMs,” says Terlaky. “But there are limits to their effectiveness, and known instances where even these highly effective IPMs fail to provide accurate solution. SDO methods, coupled with insights from real algebraic geometry lays the foundation to utilize the inherent power of quantum computing, and so have enormous potential to spark innovation in the quantum computing space.”

The project, On the Complexity of Semidefinite and Polynomial Optimization Through the Lens of Real Algebraic Geometry, commenced October 2021, and aims to address several key questions on the complexity of SDO and PO through the lens of real algebraic geometry. The results of this project will deepen the understanding of the complexity in SDO and PO and have the potential to impact other disciplines, including quantum information sciences, where the emerging area of quantum IPMs with their unique advantages offer unprecedented intellectual challenges.

This is an interdisciplinary “NSF Collaborative Research” project, where Lehigh and Purdue researchers partner to tackle hard problems. The lead PI at the Department of Mathematics of Purdue University is Ali Mohammad-Nezhad joined by Co-PI Saugata Basu. Ali is a 2018 Ph.D. Lehigh ISE graduate.