  


CONSTRAINED POLYNOMIAL OPTIMIZATION PROBLEMS WITH NONCOMMUTING VARIABLES
Kristijan Cafuta (kristijan.cafutafe.unilj.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;  GelfandNaimarkSegal (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 (Semidefinite Programming ) Category 2: Optimization Software and Modeling Systems (Problem Solving Environments ) Citation: SIAM Journal on Optimization, 2012, vol. 22, no. 2, pp. 363383. Download: [PDF] Entry Submitted: 03/21/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  