Verifying exactness of relaxations for robust semi-definite programs by solving polynomial systems
type: Item
instance of: scholarly article
title: Verifying exactness of relaxations for robust semi-definite programs by solving polynomial systems
zbMATH Open document ID: 1175.65059
author: S. G. Dietz
author: Carsten W. Scherer
published in: Linear Algebra and its Applications
publication date: 2008-10-06T00:00:00Z
review text: The general robust semidefinite programming (SDP) problem addressed in this paper covers a multitude of robust optimization problems arising in various fields of engineering (signal processing, systems and control, structural optimization). The linear matrix inequality (LMI) techniques are suitable for solve such challenging problems. The typical form of an SDP problem is to minimize, for a given vector and some Hermitian matrices (satisfying a linear inequality), a functional over the entire \(n\)-dimensional real space. The matrices involved depend on a parameter. When the parameter is considered as a random variable, the family of LMI constraints is sampled on a finite grid of parameter values, at the risk of possibly missing crucial parameter values. The question arises: for what set of parameter values, the optimal value of the genuine robust SDP problem coincides with its sampled version? Relaxations are constructed which guarantee that the constraint is robustly feasible. The authors discuss two different approximations of the robust SDP that lead to upper and lower bounds of the genuine optimal value. Also a condition for verifying whether a computed relaxation is exact, is derived. Another problem in connection with the exactness test discussed by the authors is the problem of finding all common zeros for given polynomials in many variables. Two algorithms are proposed in this case. The theoretical presentation is illustrated by one performed numerical example.
reviewed by: Iulian Coroian
Mathematics Subject Classification ID: 65H10
Mathematics Subject Classification ID: 90C51
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 65H04
zbMATH DE Number: 5349149
zbMATH Keywords: relaxations
zbMATH Keywords: verifying of exactness
zbMATH Keywords: polynomial systems
zbMATH Keywords: robust semidefinite programming
zbMATH Keywords: linear matrix inequality
zbMATH Keywords: verification of exactness
zbMATH Keywords: algorithms
zbMATH Keywords: numerical example
MaRDI profile type: Publication
full work available at URL: j.laa.2008.05.009
OpenAlex ID: W2059812312
cites work: Numerical Polynomial Algebra
cites work: Q4821526
cites work: Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
cites work: Advanced techniques for clearance of flight control laws
cites work: Randomized algorithms for analysis and control of uncertain systems. With a foreword by M. Vidyasagar
cites work: Uncertain convex programs: randomized solutions and confidence levels
cites work: LMI relaxations in robust control
cites work: .878-approximation algorithms for MAX CUT and MAX 2SAT
cites work: On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty
cites work: Robust Solutions to Uncertain Semidefinite Programs
cites work: Relaxations for Robust Linear Matrix Inequality Problems with Verifications for Exactness
cites work: Q3128879
cites work: Induced L2-norm control for LPV systems with bounded parameter variation rates
cites work: Robust solutions of linear programming problems contaminated with uncertain data
cites work: Recent contributions to linear semi-infinite optimization
cites work: Q4209232
cites work: Q4226951
cites work: The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
cites work: Q3806684
cites work: Characterizing the solution set of polynomial systems in terms of homogeneous forms: an LMI approach
cites work: Robust solutions of uncertain linear programs
cites work: Matrix sum-of-squares relaxations for robust semi-definite programs
cites work: An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones
DOI: 10.1016/J.LAA.2008.05.009
description: scientific article; zbMATH DE number 5349149