Optimization Online


Convergent relaxations of polynomial optimization problems with non-commuting variables

Stefano Pironio (stefano.pironio***at***unige.ch)
Miguel Navascues (m.navascues***at***imperial.ac.uk)
Antonio Acin (Antonio.Acin***at***icfo.es)

Abstract: We consider optimization problems with polynomial inequality constraints in non-commuting variables. These non-commuting variables are viewed as bounded operators on a Hilbert space whose dimension is not fixed and the associated polynomial inequalities as semidefinite positivity constraints. Such problems arise naturally in quantum theory and quantum information science. To solve them, we introduce a hierarchy of semidefinite programming relaxations which generates a monotone sequence of lower bounds that converges to the optimal solution. We also introduce a criterion to detect whether the global optimum is reached at a given relaxation step and show how to extract a global optimizer from the solution of the corresponding semidefinite programming problem.

Keywords: SDP relaxations, polynomial optimization, quantum theory, non-commuting variables

Category 1: Linear, Cone and Semidefinite Programming

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


Download: [PDF]

Entry Submitted: 03/25/2009
Entry Accepted: 03/25/2009
Entry Last Modified: 01/11/2010

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 Programming Society