Sparse noncommutative polynomial optimization

Klep, Igor (author), Magron, Victor (author), Povh, Janez (author)

This article focuses on optimization of polynomials in noncommuting variables, while taking into account sparsity in the input data. A converging hierarchy of semidefinite relaxations for eigenvalue and trace optimization is provided. This hierarchy is a noncommutative analogue of results due to Lasserre (SIAM J Optim 17(3):822-843, 2006) and Waki et al. (SIAM J Optim 17(1):218-242, 2006). The Gelfand-Naimark-Segal construction is applied to extract optimizers if flatness and irreducibility conditions are satisfied. Among the main techniques used are amalgamation results from operator algebra. The theoretical results are utilized to compute lower bounds on minimal eigenvalue of noncommutative polynomials from the literature.

• Language: English
• Keywords: noncommutative polynomial, sparsity pattern, semialgebraic set, semidefinite programming, eigenvalue optimization, trace optimization, GNS construction
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FS - Faculty of Mechanical Engineering; FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2021
• Number of pages: Str. [1-41]
• PID: 20.500.12556/RUL-124550
• UDC: 512.622(045)
• ISSN on article: 0025-5610
• DOI: 10.1007/s10107-020-01610-1
• COBISS.SI-ID: 49537283
• Publication date in RUL: 01.02.2021

KLEP, Igor, MAGRON, Victor and POVH, Janez, 2021, Sparse noncommutative polynomial optimization. Mathematical programming [online]. 2021. P. 1–41. [Accessed 17 April 2025]. DOI 10.1007/s10107-020-01610-1. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=124550

Record is a part of a journal

• Title: Mathematical programming
• Shortened title: Math. program.
• Publisher: North-Holland, Springer
• ISSN: 0025-5610
• COBISS.SI-ID: 5015818

Secondary language

• Language: Slovenian

Abstract

Ta članek se osredotoča na optimizacijo polinomov v nekomutativnih spremenljivkah, ob upoštevanju redkosti v vhodnih podatkih. Najprej predstavimo konvergentno hierarhijo semidefinitnih poenostavitev za optimizacijo lastnih vrednosti in sledi. Ta hierarhija je nekomutativni analog rezultatov iz SIAM J Optim 17 (3): 822-843, 2006 in iz SIAM J Optim 17 (1): 218-242, 2006. V nadaljevanju uporabimo konstrukcijo Gelfand - Naimark - Segal za iskanje optimizatorjev, če so izpolnjeni pogoji sploščenosti in ireducibilnosti. Med glavnimi uporabljenimi tehnikami so postopki združevanja iz operaterske algebre. Rezultati so uporabni za izračun spodnjih meja minimalne lastne vrednosti nekomutativnih polinomov iz literature.

• Keywords: nekomutativni polinom, redki polinomi, semialgebraična množica, semidefinitno programiranje, optimizacija lastnih vrednosti, optimizacija sledi, GNS postopek