Campuses:

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).
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
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
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,
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
Subscribe to RSS - Semidefinite programming