Some geometric results in semidefinite programming
type: Item
instance of: scholarly article
title: Some geometric results in semidefinite programming
zbMATH Open document ID: 0839.90093
DOI: 10.1007/BF01100204
author: A. J. Goldman
author: Motakuri V. Ramana
published in: Journal of Global Optimization
publication date: 1996-01-23T00:00:00Z
review text: Certain geometric results are developed for the feasible regions of semidefinite programs, called spectrahedra. Firstly, a characterization of the faces of spectrahedra is developed. Specifically, given a point \(x\) in a spectrahedron \(G\), we derive an expression for the minimal face of \(G\) that contains \(x\). This yields, among other things, characterizations of extreme points and extreme rays of spectrahedra. Then an investigation of polars of spectrahedra is carried out. In particular, a notion of the algebraic polar of a spectrahedra is introduced and it is shown that the usual polar is the closure of the well described algebraic polar. By employing some of the analysis here, the first author has subsequently developed the first polynomial size gap-free dual program for semidefinite programming.
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 52B12
zbMATH DE Number: 836800
zbMATH Keywords: convex geometry
zbMATH Keywords: semidefinite programs
zbMATH Keywords: spectrahedra
zbMATH Keywords: algebraic polar
MaRDI profile type: Publication
cites work: Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
cites work: Cones of diagonally dominant matrices
cites work: Simultaneous Diagonalisation of Several Hermitian Matrices
cites work: Joint ranges of Hermitian matrices and simultaneous diagonalization
cites work: Duality and asymptotic solvability over cones
cites work: Q3923971
cites work: Q4127646
cites work: Combinatorial properties and the complexity of a max-cut approximation
cites work: Semi-Definite Matrix Constraints in Optimization
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Extremal correlation matrices
cites work: Q3216686
cites work: Geometric algorithms and combinatorial optimization
cites work: Matrix Analysis
cites work: Q4703904
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Q4324980
cites work: Large-Scale Optimization of Eigenvalues
cites work: Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices
cites work: Open questions in complexity theory for numerical optimization
cites work: Convex Analysis
cites work: Some applications of optimization in matrix theory
full work available at URL: https://doi.org/10.1007/bf01100204
OpenAlex ID: W2065706751
description: scientific article; zbMATH DE number 836800