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)
Introductory comments
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
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 occuring 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)
Quadratic approximation of some convex optimization problems using the arithmetic-geometric mean iteration
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
Registration before Tuesday, November 10th, 2009
There is no registration fee, but please register by contacting Ms Christèle Soler at <csoler@laas.fr> before Tuesday, November 10th, 2009.
Please note that the number of participants is limited, and registration is managed on the basis of first come, first served.
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:
Francois 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:
Determinantal representations of cubic surfaces
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.