# Semidefinite programming

Thursday, September 7, 2017 - 10:40am - 11:15am

Mihailo Jovanovic (University of Southern California)

We consider the problem of the optimal selection of a subset of available sensors or actuators in large-scale dynamical systems. By replacing a combinatorial penalty on the number of sensors or actuators with a convex sparsity-promoting term, we cast this problem as a semidefinite program (SDP). The solution of the resulting convex optimization problem is used to select sensors (actuators) in order to gracefully degrade performance relative to the optimal Kalman filter (Linear Quadratic Regulator) that uses all available sensing (actuating) capabilities.

Friday, November 21, 2008 - 2:45pm - 3:30pm

Pablo Parrilo (Massachusetts Institute of Technology)

The Lovasz theta body TH(G) is a well-known relaxation of the stable set

polytope STAB(G) that is computable using semidefinite programming. These

ideas can be extended via sum of squares techniques to other combinatorial

optimization problems, providing a natural generalization of the theta body

for general polynomial ideals. In this talk we describe these general

techniques, and characterize finite point sets whose theta body coincides

with its convex hull. This is joint work with Joao Gouveia and Rekha Thomas

(U. Washington).

polytope STAB(G) that is computable using semidefinite programming. These

ideas can be extended via sum of squares techniques to other combinatorial

optimization problems, providing a natural generalization of the theta body

for general polynomial ideals. In this talk we describe these general

techniques, and characterize finite point sets whose theta body coincides

with its convex hull. This is joint work with Joao Gouveia and Rekha Thomas

(U. Washington).

Thursday, January 28, 2016 - 2:00pm - 2:50pm

Venkat Chandrasekaran (California Institute of Technology)

Extracting structured planted subgraphs from large graphs is a fundamental question that arises in a range of application domains. We describe a computationally tractable approach based on convex optimization to recover certain families of structured graphs that are embedded in larger graphs containing spurious edges. Our method relies on tractable semidefinite descriptions of majorization inequalities on the spectrum of a matrix, and we give conditions on the eigenstructure of a planted graph in relation to the noise level under which our algorithm succeeds.

Tuesday, January 26, 2016 - 10:15am - 11:05am

Didier Henrion (Centre National de la Recherche Scientifique (CNRS))

Optimal experimental design consists of choosing measurements to maximize the information or, equivalently, minimize noise. For linear regression, a popular criterion is D-optimality, which seeks to maximize the determinant of the information matrix. Maximization is with respect to the weights of a discrete measure whose atoms (measurement basis vectors) are given a priori. The information matrix contains moments of degree two of this measure, and

its inverse is the error covariance matrix. The resulting determinant

its inverse is the error covariance matrix. The resulting determinant

Wednesday, November 19, 2008 - 2:00pm - 2:45pm

Christoph Helmberg (Technische Universität Chemnitz-Zwickau)

Joint work with Michael Armbruster (TU Chemnitz),

Marzena Fuegenschuh (TU Darmstadt), and

Alexander Martin (TU Darmstadt).

Semidefinite relaxations are known to deliver good approximations

for combinatorial optimization problems like graph bisection. Using

the spectral bundle method it is possible to exploit structural

properties of the underlying problem and to apply, even to sparse

large scale instances, cutting plane methods, probably the most

successful technique in linear programming. We set up a common

Marzena Fuegenschuh (TU Darmstadt), and

Alexander Martin (TU Darmstadt).

Semidefinite relaxations are known to deliver good approximations

for combinatorial optimization problems like graph bisection. Using

the spectral bundle method it is possible to exploit structural

properties of the underlying problem and to apply, even to sparse

large scale instances, cutting plane methods, probably the most

successful technique in linear programming. We set up a common

Thursday, January 18, 2007 - 9:30am - 10:30am

Bernd Sturmfels (University of California, Berkeley)

Given a semidefinite program, specified by matrices

with rational entries, each coordinate of its optimal solution

is

an algebraic number. We study the degree of the minimal

polynomials

of these algebraic numbers. Geometrically, this degree counts

the

critical points attained by a linear functional on a fixed rank

locus in a linear space of symmetric matrices. We determine

this degree

using methods from complex algebraic geometry, such as

projective duality,

with rational entries, each coordinate of its optimal solution

is

an algebraic number. We study the degree of the minimal

polynomials

of these algebraic numbers. Geometrically, this degree counts

the

critical points attained by a linear functional on a fixed rank

locus in a linear space of symmetric matrices. We determine

this degree

using methods from complex algebraic geometry, such as

projective duality,

Thursday, January 18, 2007 - 3:00pm - 3:50pm

Didier Henrion (Centre National de la Recherche Scientifique (CNRS))

Joint work by Jean-Bernard Lasserre, Johan Löfberg, Christophe Prieur and Emmanuel Trélat.

The new release 3.0 of the Matlab package GloptiPoly is introduced

through an application to a class of nonlinear optimal control problems

for which the data (differential equations, state and control constraints,

cost) are multivariate polynomials. GloptiPoly 3.0 is aimed at solving

The new release 3.0 of the Matlab package GloptiPoly is introduced

through an application to a class of nonlinear optimal control problems

for which the data (differential equations, state and control constraints,

cost) are multivariate polynomials. GloptiPoly 3.0 is aimed at solving