**GOAL** led by *Bernd Sturmfels* (UC Berkeley) and *Jean-charles* Faugere (POLSYS, Inria Paris) on

## “

Geometry and Optimization with ALgebraic method"

The goal of this project is to develop algorithms and mathematical tools to solve geometric and optimization problems through algebraic techniques. As a long-term goal, the joint team plans to develop new software to solve these problems more efficiently. These objectives encompass the challenge of identifying instances of these problems that can be solved in polynomial time with respect to the number of solutions and modeling these problems with polynomial equations. .

- Berkeley Bernd Sturmfels - Dept. of Mathematics - University of California - Professor of Mathematics, Statistics and Computer Science
- Rekha R. Thomas is Professor of Mathematics at the University of Washington.
- Jean-Charles Faugere (Senior Researcher INRIA)
- Mohab Safey El Din (Prof. Univ. Pierre and Marie Curie and IUF)
- Elias Tsigaridas (Researcher INRIA)

The goal is to develop algorithms and mathematical tools to solve geometric and optimization problems through algebraic techniques. As a long-term goal, we plan to develop new software to solve these problems more efficiently. These objectives encompass the challenge of identifying instances of these problems that can be solved in polynomial time with respect to the number of solutions and modeling these problems with polynomial equations.

**Geometry of polynomial optimization. **Most of the recent numerical techniques in this context (e.g. those based on semi-definite programming) consist of tracking a path, called the central curve, that is an algebraic curve. The modeling plays an important role since, most of the time, problems can be expressed in a primal or a dual form. Understanding the geometry and the algebraic degree of these curves can allow us to predict which model (primal or dual) should be used. We will also focus on important optimization problems that have an intrinsic geometric description [Baj88]; this is the case for example of the famous Fermat-Weber problem [WF29] that is described in the next section. For both problems numerical methods are available [HRVW96, KK62] but their bit complexity is unknown (the needed precision for the basic arithmetic operations). One can consider exact methods as an alternative. To solve these problems exactly, one can compute a set of univariate polynomials equations whose degree is the algebraic degree. The algebraic degree is usually very big, even for instances of small input size1. The algebraic degree is also useful to estimate the number of digits required to obtain reliable numerical routines. Our goal is to exploit the geometric structure of these problems, to improve numerical techniques, and to obtain dedicated algebraic algorithms for solving them.

**Matrix factorizations.** Matrix factorizations are a classical and important topic in applied mathematics. In the standard low-rank matrix factorization problem, the goal is to write a given matrix M as a product M = A B where the intermediate dimension of A and B is as small as possible. In many situations, additional conditions on the factors are required. We will consider the non-negative factorization problem (see [CR93]) and the positive semi-definite factorization problem (see [FGP+14]). Describing the sets of matrices A and B that yield the best factorizations requires considering highly structured systems of polynomial equations and inequalities. In many cases these inequalities imply additional polynomial equations that are hard to discover. A well defined procedure for finding these equations (which is a modeling task) and analyzing the algebraic degree of the sets of equations would yield significant

improvements to the state-of-the-art

Moment Varieties of Gaussian Mixtures (arxiv) (C. Améndola, J-C. Faugère and B. Sturmfels), submitted to Journal of Algebraic Statistics.

- GOAL meeting
*Geometry and Optimization with ALgebraic methods***Paris (France)**(May, 20-21, 2016)

- GOAL meeting
*Geometry and Optimization with ALgebraic methods***BERKELEY USA**(May, 17-19, 2015) -- Kick-off meeting- Schedule of Talks
- Monday, May 18

9:00-9:45 Mohab Safey El Din (INRIA Paris) Polynomial optimization and solving real polynomial systems

10:00-10:45 Rekha Thomas (U of Washington, Seattle) Polynomial systems in two view geometry

11:00-11:30 Serkan Hosten (San Francisco State U) The central curve in quadratic programming

11:35-12:05 Elias Tsigaridas (INRIA Paris) Bounds for the central curve in semidefinite programming

12:10-12:40 Elina Robeva (UC Berkeley) Geometry of the positive semidefinite rank

Lunch

14:30-15:00 Joe Kileel (UC Berkeley) Real slice experiments for the calibrated trifocal variety

15:05-15:35 Hon Lee (U of Washington, Seattle) Orthogonally invariant matrix varieties

Coffee Break

16:15-16:45 Emil Horobet (TU Eindhoven, Netherlands) Data singular locus of affine cones

16:50-17:35 Jean-Charles Faugere (INRIA Paris) Solving quadratic fewnomial systems using sparse Gröbner bases

Dinner

- Tuesday, May 19
- 9:00-9:30 Jose Rodriguez (Notre Dame U) The maximum likelihood degree for rank 2 matrices via Euler characteristics

9:35-10:05 Bernd Sturmfels (UC Berkeley) The Hurwitz form of a projective variety

Informal Discussions

- 9:00-9:30 Jose Rodriguez (Notre Dame U) The maximum likelihood degree for rank 2 matrices via Euler characteristics

- Schedule of Talks
- Visit of C. Améndola in Paris
**1 month**(Sep. 2015) - Visit of K Kubjas in Paris
**1 month**(Oct. 2015)