Workshop GeoLMI on the geometry and algebra of linear matrix inequalities
19-20 November 2009
LAAS-CNRS
University of Toulouse, France
The workshop aims at studying connections between real algebraic geometry and semidefinite programming, with the objective of designing algorithms to model convex semi-algebraic sets as linear matrix inequalities (LMI, affine sections and projections of the cone of positive semidefinite matrices).
Participants
Invited speakers (alphabetical order):
Anita Buckley, Univ. Ljubljana (SI)
Luca Chiantini, Univ. Siena (IT)
Aris Daniilidis, Univ. Barcelona (SP)
Tomaz Kosir, Univ. Ljubljana (SI)
François Glineur, Univ. Cath. Louvain (BE)
Olivier Ruatta, Univ. Limoges (FR)
Mark Spivakovsky, IMT-CNRS Univ. Toulouse (FR)
Victor Vinnikov, Univ. Negev (IL)
Organisers:
Danièle Faenzi, Univ. Pau (FR)
Didier Henrion, LAAS-CNRS, Univ. Toulouse (FR) and Czech Tech. Univ., Prague (CZ)
Roland Hildebrand, LJK-CNRS Univ. Grenoble (FR)
Jérôme Malick, LJK-CNRS Univ. Grenoble (FR)
Jean Vallès, Univ. Pau (FR)
Scientific Programme
Thursday, November 19th
08:30-09:00 Welcome coffee
09:00-09:30 Didier Henrion, LAAS-CNRS Univ. Toulouse (FR) and Czech Tech. Univ. Prague (CZ)
09:30-10:30 Anita Buckley, Univ. Ljubljana (SI)
Pfaffian representations of plane curves
10:30-11:00 Coffee Break
11:00-12:00 Luca Chiantini, Univ. Siena (IT)
On the pfaffian representation of general homogeneous polynomials (slides in pdf format)
12:00-13:30 Lunch Break
13:30-14:30 Victor Vinnikov, Univ. Negev (IL)
Determinantal representations of singular curves
14:30-15:00 Coffee Break
15:00-16:00 Olivier Ruatta, Univ. Limoges (FR)
On LMI occurring in some real semi-algebraic geometry problems
16:00-17:00 Discussion Pannel
Friday, November 20th
09:00-09-30 Welcome coffee
09:30-10:30 Aris Daniilidis, Univ. Autonoma Barcelona (SP)
Generic optimality conditions for semialgebraic convex programs
10:30-11:00 Coffee Break
11:00-12:00 François Glineur, Univ. Cath. Louvain (BE)
12:00-13:30 Lunch Buffet
13:30-14:30 Tomaz Kosir, Univ. Ljubljana (SI)
Determinantal representations of cubic surfaces
14:30-15:30 Mark Spivakovsky, IMT-CNRS Univ. Toulouse (FR)
On the Pierce-Birkhoff conjecture
15:30-16:00 Closing remarks
Venue
Main conference hall (salle de conférences) of LAAS-CNRS, Toulouse.
Access maps and accomodation information can be found here.
The workshop is funded by CNRS, Université Paul Sabatier and Conseil Régional Midi-Pyrénées.
Abstracts
Speaker:
Anita Buckley
Department of Mathematics, University of Ljubljana, Slovenia
Title:
Pfaffian representations of plane curves
Abstract:
Let C be a smooth curve in $\PP^2$ given by an equation $F=0$
of degree $d$. We construct an explicit correspondence between pfaffian
representations of $C$ and rank 2 vector bundles on $C$ with canonical
determinant and no sections. In other words, all linear pfaffian
representations of $F$ are parametrised by an open subset in the moduli
space $M_C(2,K_C)$.
We also consider elementary transformations of linear pfaffian
representations of $C$. Elementary transformations can be interpreted as
actions on a rank 2 vector bundle on $C$ which corresponds to the cokernel
of a pfaffian representation. Any two pfaffian representations of $C$ can
be bridged by a finite sequence of elementary transformations.
Pfaffian representations and elementary transformations are constructed
explicitly (using canonical forms). On a smooth quartic, Aronhold bundles
and theta characteristics (equivalently the 36 symmetric determinantal
representations) are computed.
---
Speaker:
Luca Chiantini
Dipartimento di Scienze Matematiche e Infromatiche,
Università Degli Studi di Siena, Italy
Title:
On the pfaffian representation of general homogeneous polynomials
Abstract:
We show the geometrical background of sheaves theory and some new result
about the representation of general polynomials (mainly in 4 variables)
as pfaffians of matrices of forms of small degree.
----
Speaker:
Aris Daniilidis
Universitat Autonoma de Barcelona, Spain
Title:
Generic optimality conditions for semialgebraic convex programs
Abstract:
In this talk we consider the problem of linear optimization over
a fixed compact convex feasible region which is described by polynomials
(semi-algebraic set). Our goal here is to show that partial smoothness is a
common phenomenon: namely, generically, the optimal solution is unique and
lies on a unique manifold, around which the feasible region is partly
smooth, ensuring finite identification of the manifold by many optimization
algorithms. Furthermore, second-order optimality conditions hold,
guaranteeing smooth behavior of the optimal solution under small
perturbations to the objective.
Based on a joint work with J. Bolte (Paris 6) and A.S. Lewis (Cornell)
----
Speaker:
François Glineur
Center for Operations Research and Econometrics, Universite Catholique de Louvain,
Louvain-la-Neuve, Belgium
Title:
Quadratic approximation of some convex optimization problems
using the arithmetic-geometric mean iteration
Abstract:
We describe a general method to approximate non-semialgebraic sets
(defined by trigonometric and hyperbolic constraints) with
semialgebraic sets (defined by quadratic constraints).
----
Speaker:
Tomaz Kosir
Department of Mathematics, University of Ljubljana, Slovenia
Title:
Abstract: We will discuss the existence and parametrization of determinantal representations for a given homogeneous polynomial (or a hypersurface it defines). Our special interest is in general and in self-adjoint determinantal representations of smooth cubic surfaces. ---- Speaker: Olivier Ruatta Faculté des Sciences et Techniques, Université de Limoges, France Title: On LMI arising in some real semi-algebraic geometry problems Abstract: Some matrices widely used in elimination theory allow to give "determinantal or matricial" representation of algebraic or semi-algebraic sets. Those matrices are characterized by the fact that the determinant is, up to a invertible constant, the resultant in some cases of interest. For instance, some problems in semi-algebraic geometry can be rephrased in terms of LMI using this matricial formulations of resultant. We will give some example of how this principle can be used to express typical real semi-algebraic problems in terms of LMI. ---- Speaker: Mark Spivakovsky Institut de Mathématiques de Toulouse, Université de Toulouse, France Title: On the Pierce-Birkhoff conjecture Abstract: A continuous function $f:R^n --> R$ is said to be piecewise-polynomial if $R^n$ can be expressed as a finite union of closed semi-algebraic sets, on each of which $f$ is given by a polynomial in $n$ variables. The Pierce-Birkhoff conjecture asserts that every piecewise-polynomial function can be obtained from a finite collection of polynomials by iterating the operations of maximum and minimum. In this talk we will describe our recent work on the Pierce-Birkhoff conjecture (with F.Lucas, D.Schaub and J.J.Madden). We will explain our approach using the real spectrum of a ring and give some partial results towards the proof of the conjecture. ---- Speaker: Victor Vinnikov Department of Mathematics, Ben Gurion University of the Negev, Beer Sheva, Israel Title: Determinantal representations of singular curves Abstract: I will discuss recent joint work with Dmitry Kerner on determinantal representations of singular plane curves. While one can construct some positive determinantal representations (and hence LMI representations of a rigidly convex algebraic interior in dimension 2) essentially ignoring the singularities, including the singularities in the picture can yield additional determinantal representations. This is interesting by itself, but especially in relation to looking for determinantal representations of a non-minimal defining polynomial --- a necessary step in trying to construct LMI representations in dimension greater than 2.