Workshop GeoLMI on the geometry and algebra of linear matrix inequalities


19-20 November 2009


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).





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)




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 (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)

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




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.



Anita Buckley

Department of Mathematics, University of Ljubljana, Slovenia


Pfaffian representations of plane curves


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.



Luca Chiantini

Dipartimento di Scienze Matematiche e Infromatiche,

Università Degli Studi di Siena, Italy


On the pfaffian representation of general homogeneous polynomials


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.



Aris Daniilidis

Universitat Autonoma de Barcelona, Spain


Generic optimality conditions for semialgebraic convex programs


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)



François Glineur

Center for Operations Research and Econometrics, Universite Catholique de Louvain,

Louvain-la-Neuve, Belgium


Quadratic approximation of some convex optimization problems

using the arithmetic-geometric mean iteration


We describe a general method to approximate non-semialgebraic sets

(defined by trigonometric and hyperbolic constraints) with

semialgebraic sets (defined by quadratic constraints).



Tomaz Kosir

Department of Mathematics, University of Ljubljana, Slovenia



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.



Olivier Ruatta

Faculté des Sciences et Techniques, Université de Limoges, France


On LMI arising in some real semi-algebraic geometry problems


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.



Mark Spivakovsky

Institut de Mathématiques de Toulouse, Université de Toulouse, France


On the Pierce-Birkhoff conjecture


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.



Victor Vinnikov

Department of Mathematics, Ben Gurion University of the Negev,

Beer Sheva, Israel


Determinantal representations of singular curves


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.