CONSTRAINED POLYNOMIAL OPTIMIZATION PROBLEMS WITH NONCOMMUTING VARIABLES
Kristijan Cafuta (kristijan.cafutafe.uni-lj.si)
Abstract: In this paper we study constrained eigenvalue optimization of noncommutative (nc) polynomials, focusing on the polydisc and the ball. Our three main results are as follows: (1) an nc polynomial is nonnegative if and only if it admits a weighted sum of hermitian squares decomposition; (2) (eigenvalue) optima for nc polynomials can be computed using a single semidenite program (SDP) (this sharply contrasts the commutative case where sequences of SDPs are needed); (3) the dual solution to this ''single'' SDP can be exploited to extract eigenvalue optimizers with an algorithm based on two ingredients: - solution to a truncated nc moment problem via flat extensions; - Gelfand-Naimark-Segal (GNS) construction. The implementation of these procedures in our computer algebra system NCSOStools is presented and several examples pertaining to matrix inequalities are given to illustrate our results.
Keywords: noncommutative polynomial, optimization, sum of squares, semide
Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )
Category 2: Optimization Software and Modeling Systems (Problem Solving Environments )
Citation: SIAM Journal on Optimization, 2012, vol. 22, no. 2, pp. 363-383.
Entry Submitted: 03/21/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|