Complexity, exactness, and rationality in polynomial optimization

• 成果类型: Article
• 署名作者: Bienstock, Daniel; Del Pia, Alberto; Hildebrand, Robert
• 署名单位: Columbia University; University of Wisconsin System; University of Wisconsin Madison; Virginia Polytechnic Institute & State University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01818-3
• 发表日期: 2023
• 页码: 661-692
• 关键词: interior-point methods; algorithm; systems

摘要

We focus on rational solutions or nearly-feasible rational solutions that serve as certificates of feasibility for polynomial optimization problems. We show that, under some separability conditions, certain cubic polynomially constrained sets admit rational solutions. However, we show in other cases that it is NP Hard to detect if rational solutions exist or if they exist of any reasonable size. We extend this idea to various settings including near feasible, but super optimal solutions and detecting rational rays on which a cubic function is unbounded. Lastly, we show that in fixed dimension, the feasibility problem over a set defined by polynomial inequalities is in NP by providing a simple certificate to verify feasibility. We conclude with several related examples of irrationality and encoding size issues in QCQPs and SOCPs.