Optimization Online


Constrained trace-optimization of polynomials in freely noncommuting variables

Igor Klep(igor.klep***at***auckland.ac.nz )
Janez Povh(janez.povh***at***fis.unm.si)

Abstract: The study of matrix inequalities in a dimension-free setting is in the realm of free real algebraic geometry (RAG). In this paper we investigate constrained trace and eigenvalue optimization of noncommutative polynomials. We present Lasserre's relaxation scheme for trace optimization based on semidefinite programming (SDP) and demonstrate its convergence properties. Finite convergence of this relaxation scheme is governed by flatness, i.e., a rank-preserving property for associated dual SDPs. If flatness is observed, then optimizers can be extracted using the Gelfand-Naimark-Segal construction and the Artin-Wedderburn theory verifying exactness of the relaxation. To enforce flatness we employ a noncommutative version of the randomization technique championed by Nie. The implementation of these procedures in our computer algebra system NCSOStools is presented and several examples are given to illustrate our results.

Keywords: noncommutative polynomial, optimization, sum of squares, semidefinite programming, moment problem, Hankel matrix, flat extension, Matlab toolbox, real algebraic geometry, free positivity

Category 1: Applications -- Science and Engineering (Basic Sciences Applications )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: University of Auckland and Faculty of information studies in Novo mesto, December 2014

Download: [Postscript][PDF]

Entry Submitted: 12/17/2014
Entry Accepted: 12/17/2014
Entry Last Modified: 12/17/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society