Optimization Online


SDP vs. LP relaxations for the moment approach in some performance evaluation problems

J.B. Lasserre (lasserre***at***laas.fr)
T. Prieto-Rumeau (tprieto***at***estad.ucm.es)

Abstract: Given a Markov process we are interested in the numerical computation of the moments of the exit time from a bounded domain. We use a moment approach which, together with appropriate semidefinite positivity moment conditions, yields a sequence of semidefinite programs (or SDP relaxations), depending on the number of moments considered, that provide a sequence of nonincreasing (resp. nondecreasing) upper (resp. lower) bounds. The results are compared to the linear Hausdorff moment conditions approach considered in the LP-relaxations of Helmes. The SDP relaxations are shown to be more general and more precise than the LP relaxation

Keywords: LP-relaxations; SDP-relaxations; Semidefinite Programming

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Finance and Economics )

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

Citation: Stochastic Models 20 (2004), 439--456.


Entry Submitted: 05/04/2004
Entry Accepted: 05/04/2004
Entry Last Modified: 09/18/2006

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