Generating linear, semidefinite, and second-order cone optimization problems for numerical experiments

Abstract

The numerical performance of algorithms can be studied using test sets or procedures that generate such problems. This paper proposes various methods for generating linear, semidefinite, and second-order cone optimization problems. Specifically, we are interested in problem instances requiring a known optimal solution, a known optimal partition, a specific interior solution, or all these together. In the proposed problem generators, different characteristics of optimization problems, including dimension, size, condition number, degeneracy, optimal partition, and sparsity, can be chosen to facilitate comprehensive computational experiments. We also develop procedures to generate instances with a maximally complementary optimal solution with a predetermined optimal partition to generate challenging semidefinite and second-order cone optimization problems. Generated instances enable us to evaluate efficient interior-point methods for conic optimization problems.

Keywords:

• Problem generator
• conic optimization
• linear optimization
• semidefinite optimization
• second-order cone optimization

Disclosure statement

This paper was prepared for informational purposes by the Global Technology Applied Research Center of JPMorgan Chase & Co. This paper is not a product of the Research Department of JPMorgan Chase & Co., or its affiliates. Neither JPMorgan Chase & Co. nor any of its affiliates makes any explicit or implied representation or warranty and none of them accept any liability in connection with this paper, including, without limitation, with respect to the completeness, accuracy, or reliability of the information contained herein and the potential legal, compliance, tax, or accounting effects thereof. This document is not intended as investment research or investment advice, or as a recommendation offer, or solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to be used in any way for evaluating the merits of participating in any transaction. No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work is supported by Defense Advanced Research Projects Agency as part of the project W911NF2010022: The Quantum Computing Revolution and Optimization: Challenges and Opportunities; and by the National Science Foundation (NSF) under Grant No. 2128527.

Notes on contributors

Mohammadhossein Mohammadisiahroudi

Mohammadhossein Mohammadisiahroudi is a Ph.D. candidate at Lehigh University (Department of Industrial and System Engineering), working in Quantum Computing and Optimization Lab under the supervision of Prof. Tamás Terlaky. He received his master's degree from the Sharif University of Technology and bachelor's degree from the Iran University of Science and Technology, both in Industrial Engineering. His research focuses on developing, analyzing, and implementing quantum and classical algorithms for solving challenging optimization problems. His research was recipient of the 2023 Inform Computing Society Best Student Paper Prize as runner-up and 2023 Van Hoesen Family Best Publication Award.

Ramin Fakhimi

Ramin Fakhimi received his BSc in Industrial Engineering from Ferdowsi University of Mashhad and his MSc in Industrial Engineering from the Sharif University of Technology. He earned his Ph.D. in Industrial and Systems Engineering at Lehigh University in 2023 under the guidance of Professors Tamás Terlaky and Luis F. Zuluaga. His research focuses on mathematical optimization problems. Currently, he works as a Decision Scientist at The Walt Disney Company.

Brandon Augustino

Brandon Augustino is a Global Technology Applied Research Senior Associate at JPMorgan Chase working on quantum computing. Prior this appointment, he was a Postdoctoral Associate at the Sloan School of Management at Massachusetts Institute of Technology. He received his Ph.D. in Industrial and Systems Engineering from Lehigh University. His work focuses on the development of quantum algorithms for optimization and scientific computing.

Tamás Terlaky

Tamás Terlaky is the George N. and Soteria Kledaras '87 Endowed Chair Professor at Lehigh University. He has published four books, edited over ten books and journal special issues and published over 200 research papers. Terlaky received the Egerváry Award of the Hungarian Operations Research Society, the H.G. Wagner Prize of INFORMS, and the Outstanding Innovation in Service Science Engineering Award of IISE. He is a Fellow of IFORS, the Canadian Academy of Engineering, SIAM, INFORMS, and the Fields Institute. He is the Editor in Chief of JOTA. His research interest includes conic and quantum computing optimization, interior point methods, computational optimization, cancer treatment optimization, and optimization of the operations of correctional systems.