Univariate Representations of Solutions to Generic Polynomial Complementarity Problems

Vu Trung Hieu (), Alfredo Noel Iusem (), Paul Hugo Schmölling () and Akiko Takeda ()
Additional contact information
Vu Trung Hieu: Center for Advanced Intelligence Project, RIKEN
Alfredo Noel Iusem: Fundação Getulio Vargas
Paul Hugo Schmölling: Norwegian University of Science and Technology
Akiko Takeda: Center for Advanced Intelligence Project, RIKEN

Journal of Optimization Theory and Applications, 2025, vol. 207, issue 2, No 7, 22 pages

Abstract: Abstract By using the squared slack variables technique, we demonstrate that the solution set of a general polynomial complementarity problem is the image, under a specific projection, of the set of real zeroes of a system of polynomials. This paper points out that, generically, this polynomial system has finitely many complex zeroes. In such a case, we use symbolic computation techniques to compute a univariate representation of the solution set. Consequently, univariate representations of special solutions, such as least-norm and sparse solutions, are obtained. After that, enumerating solutions boils down to solving problems governed by univariate polynomials. We also provide some experiments on small-scale problems with worst-case scenarios. At the end of the paper, we propose a method for computing approximate solutions to copositive polynomial complementarity problems that may have infinitely many solutions.

Keywords: Polynomial complementarity problem; Solution set; Least-norm solution; Sparse solution; Zero-dimensional ideal; Univariate representation; Gröbner basis; Shape Lemma; 90C33; 13P10; 13P15; 65H04 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-025-02788-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:207:y:2025:i:2:d:10.1007_s10957-025-02788-0

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-025-02788-0

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().