-

 

 

 




Optimization Online





 

CONSTRAINED POLYNOMIAL OPTIMIZATION PROBLEMS WITH NONCOMMUTING VARIABLES

Kristijan Cafuta (kristijan.cafuta***at***fe.uni-lj.si)
Igor Klep (igor.klep***at***fmf.uni-lj.si)
Janez Povh (janez.povh***at***fis.unm.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 semide nite 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.

Download: [PDF]

Entry Submitted: 03/21/2011
Entry Accepted: 03/21/2011
Entry Last Modified: 04/25/2012

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
Mathematical Optimization Society