**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. Pragu**e **(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.