Saugata Basu
Toda's theorem -- real and complex.
We study the relationship between the computational hardness of two
well-studied problems in algorithmic semi-algebraic as well as complex
geometry -- namely the problem of deciding sentences in the first
order theory of reals/complex numbers with a constant number of
quantifier alternations, and that of computing Betti numbers of
semi-algebraic/constructible sets. We obtain a polynomial time
reduction of the compact version of the first problem to the
second. As a consequence we obtain analogues of Toda's theorem from
discrete complexity theory over the reals as well as complex
numbers. (Part of this work is joint with Thierry Zell).
---------------------------------------------------------
Greg Blekherman
Convex Forms and Faces of the Cone of Sums of Squares
We will describe a simple proof based on volumes that there exist
convex forms that are not sums of squares. A convex form has to be
nonnegative and there are currently no explicit examples of such
forms. A prerequisite for constructing such an example would be
building strictly positive forms that are not sums of squares. We will
describe the facial structure of the cone of nonnegative forms and
build explicit faces of the cone of sums of squares that contain
strictly positive forms, which leads to strictly positive polynomials
that are not sums of squares.
------------------------------------------------------
Petter Braenden
Title: Tropicalization of hyperbolic polynomials
Abstract: We study the tropicalization of a class of hyperbolic
polynomials, namely the stable polynomials. We prove that the
tropicalization of stable polynomials is a proper subspace of the
space of $M$-concave functions studied by Murota. We also describe the
relationship with the tropical Grassmannian and the Dressian. Finally
we provide a short proof of Speyer's hive theorem.
--------------------------------------------------------
Harm Derksen
(Poly)Matroid Polytopes
To a matroid, or more generally, a polymatroid one can associate its
base polytope. Many interesting invariants, such as the Tutte
polynomial, the Billera-Jia-Reiner quasi-symmetric function F, and the
quasi-symmetric function G introduced by the speaker, are
valuative. Valuative functions are functions which can be described as
integrating a function over the polymatroid polytope with respect to
some measure. In this talk, we will explicitly describe explicitly
all valuative functions and all valuative invariants. In particular,
this shows that G is universal with respect to all valuative
invariants. This is joint work with Alex Fink.
-------------------------------------------------------
Jonathan Hauenstein
Numerical algebraic geometry
The field of numerical algebraic geometry consists of numerical-based
algorithms for solving polynomial systems and manipulation
positive-dimensional solution components. Such algorithms have many
applications in convex algebraic geometry and optimization as well as
science and engineering in general. The first part of this talk will
review two fundamental ideas of numerical algebraic geometry, namely
homotopy continuation and the numerical irreducible decomposition.
This talk will conclude by describing regeneration and computing
rank-deficiency sets of a matrix with multivariate polynomial entries.
---------------------------------------------
Martin Henk
Representing Polyhedra by Few Polynomials
By a theorem of Br"ocker and Scheiderer, every basic closed
semi-algebraic set in R^n can be described by at most n(n+1)/2
polynomial inequalities. All known proofs of this result are highly
non-constructive. Here we are interested in algorithmic constructions
of such a representation by few polynomials for the very special class
of semi-algebraic sets consisting of polyhedra. The talk reviews
recent results on this problem.
--------------------------------------------------------
Erich Kaltofen
Certifying the Radius of Positive Semidefiniteness
Via Our ArtinProver Package
We give a stability criterion for real polynomial inequalities with
floating point or inexact scalars by estimating from below or
computing the radius of positive semidefiniteness. The stability
radius is the maximum deformation of the polynomial coefficient vector
measured in a weighted Euclidean vector norm within which the
inequality remains true. A large radius means that the inequalities
are numerically stable.
The stability radius is the distance to the nearest polynomial with a
real root. We solve this problem by parameterized Lagrangian
multipliers and Karush-Kuhn-Tucker conditions. Our algorithms can
compute the stability radius for several simultaneous inequalities and
with additional linear coefficient constraints.
The computation of the nearest polynomial with a real root can be
interpreted as a dual of Seidenberg's method that decides if a real
hypersurface contains a real point. Sums of squares rational lower
bound certificates for the radius of positive semidefiniteness provide
a new approach to solving Seidenberg's problem, especially when the
coefficients are numeric.
Joint work with Sharon Hutton and Lihong Zhi.
-------------------------------------------------------------
Oliver Labs
Towards Visualization Tools for Convex Algebraic Geometry
We present some preliminary tools to visualize convex algebraic
geometry. Some are based on our software SURFEX which is a software
for visualizing real algebraic varieties in three-space. Some others
are based on MATLAB and its SDP computation features. Together with
Ph. Rostalski, we plan to provide a set of tools using these two
approaches. Feel free to contact us for preliminary versions.
---------------------------------------------------------
Monique Laurent (CWI, Amsterdam, and Tilburg University)
Error and degree bounds for positivity certificates on the hypercube
We consider the problem of testing whether a polynomial is positive on
a compact basic closed semi-algebraic set $K$, and of approximating
its minimum over $K$. As is well known, positivity certificates have
been given by Schm\"udgen [1991] and by Putinar [1993], involving
respectively the preordering and the quadratic module generated by the
polynomials inequalities defining $K$. Degree bounds and error
estimates have been proved for these two types of representations by
Schweighofer [2004] and by Nie and Schweighofer [2007]. These results
involve some unknown constants depending only on the set $K$. In this
talk we give explicit degree and error bounds for representations in
the preordering in the case when $K$ is the hypercube $[0,1]^n$, which
imply in particular that the unknown constants can be chosen equal to
1. Our results are elementary and rely on using Bernstein
approximations. This is joint work with Etienne de Klerk (Tilburg
University).
-----------------------------------------------------
Murray Marshall
Lower bounds for a polynomial in terms of its coefficients
We determine new sufficient conditions in terms of the coefficients
for a polynomial $f$ of degree $2d$ in $n$ variables to be a sum of
squares of polynomials, thereby strengthening results of Fidalgo and
Kovacec and of Lasserre. Exploiting these results, we determine, for
any polynomial $f$ of degree $2d$ whose highest degree term is an
interior point in the cone of sums of squares of forms of degree $d$,
a real number $r$ such that $f-r$ is a sum of squares of
polynomials. The existence of such a number $r$ was proved earlier,
but no estimates for $r$ were given. We also determine a lower bound
for any polynomial $f$ whose highest degree term is positive
definite. This is joint work with Mehdi Ghasemi.
------------------------------------------------------
Tim Netzer
Spectrahedra and their projections
Spectrahedra are sets defined by linear matrix inequalities. Both
spectrahedra and their projections are feasible sets for semidefinite
programming. The question which sets are spectrahedra or arise as
their projections has recently gained a lot of interest. I will
explain some of the most important results and present some new.
------------------------------------------------------
Daniel Plaumann
Exposed faces and projections of spectrahedra
A spectrahedron is a convex set defined by a linear matrix
inequality. It is known that every face of a spectrahedron is
exposed. This is true more generally of rigidly convex sets. We study
the same question for projections of spectrahedra. Our main result is
that Lasserre's moment matrix method can only work for a convex set if
all its faces are exposed. This necessary condition complements
sufficient conditions recently proved by Lasserre, Helton and
Nie. (joint work with Tim Netzer and Markus Schweighofer)
----------------------------------------------------
Mihai Putinar
Optimization of non-polynomial functions and applications
When trying to apply to Borel measurable functions the optimization
scheme advocated by Jean-Bernard Lasserre in the last decade in the
case of polynomials, one encounters a series of natural, but far from
trivial questions. The first is to characterize the moments of
positive Borel measures with respect to various bases of functions,
such as exponentials, Haar systems, wavelets, trigonometric functions
or fractional powers of the coordinates. Second, it is necessary to
saturate Archimedean quadratic modules of such functions, so that the
solvability of the moment problem with prescribed supports can be
achieved effectively, buy a sequence of positivity assumptions. Last,
after passing to the moment coordinate framework, a filtration given
by the degree should converge (fast enough) to the solution of the
original optimization problem. Applications to systems of difference
and differential equations with delays in the argument will be
discussed. Based on joint work in progress with Jean- Bernard Lasserre
and Silviu Niculescu.
--------------------------------------------------------------------
Kristian Ranestad
The convex hull of a space curve
The boundary of the convex hull of a compact algebraic curve in real
3-space defines a real algebraic surface. For general curves, that
boundary surface is reducible, consisting of tritangent planes and a
scroll of stationary bisecants. In recent work with Sturmfels we
extend classical formulas to express the degree of this surface in
terms of the degree, genus and singularities of the curve. For
rational curves we present methods for computing their defining
polynomials, and exhibit a range of examples.
---------------------------------------------
Jim Renegar
Optimization Over Hyperbolicity Cones
After a brief survey of basic results on multivariate hyperbolic
polynomials, and on the derivative relaxations of hyperbolic programs
(= linear optimization over hyperbolicity cones), we introduce the
notion of central swaths, which although not immediately obvious,
happen to be (substantial) generalizations of the central path
ubiquitous in the interior-point method literature. We display a
simple and natural dynamics for generating paths in the swaths, paths
guaranteed to lead to optimality. Finally, we present some key
ingredients for a mathematical analysis of algorithms in following
these paths (but a complete analysis has yet to be accomplished).
---------------------------------------------
Bruce Reznick
The cones of real convex forms
For each (n,m), let K_{n,m} denote the set of real forms
p(x_1,...,x_n) of degree m which are convex as functions. Then K_{n,m}
is a closed convex cone. The extremal elements for m=2 and n=2 will be
discussed, and completely described for K_{2,4} and K_{2,6}. One
extremal form is x^6 + 5(3/2)^(2/3) x^2 y^4 + y^6. Each K_{n,m} is an
example of a blender, as defined by the speaker 20 years ago. Under
the natural inner product, the dual cone is generated by all products
L_1^2*L_2^{m-2}, where the L_i's are real linear forms. Let
f(x_1,...,x_{n-1}) = p(x_1,...,x_n) be a dehomogenization of p. It is
apparently well-known to some analysts that p is convex iff f^{1/m} is
convex as a function in n-1 variables. Blekherman has proved that for
fixed m, the probability that a convex form is a sum of squares of
forms goes to zero as n goes to infinity, but he's been unable to find
a single example of a convex form which is not a sum of squares. Alas,
neither has the speaker.
---------------------------------------------------------
Philipp Rostalski
SDP Relaxations for the Grassmann Orbitope
The Grassmann orbitope is the convex hull over the Grassmann variety
of decomposable skew-symmetric tensors of unit length. This variety
parametrizes k-dimensional linear subspaces of R^n, and it is the
highest weight orbit under the k-th exterior power representation of
the group SO(n). In this talk we discuss semidefinite relaxations of
the Grassmann orbitope. That convex body can be approximated and
represented surprisingly well by projections of spectrahedra (using
Lasserre's moment matrices). We show that the first relaxation is
exact for k=2, we present numerical evidence that this result extends
to higher k, and we discuss relations to a longstanding conjecture on
calibrations by Harvey and Lawson. If time permits, we discuss three
additional classes of orbitopes and explain why the relaxation order
is related to a certain polytope. This is a joint project with Raman
Sanyal and Bernd Sturmfels.
------------------------------------------------------
Claus Scheiderer
Bounded polynomials and stability of preorderings
Given a semi-algebraic set S, we study the ring B(S) of polynomials
bounded on S, and we discuss some results on the structure of B(S) from
the last years (joint work with D. Plaumann). We review the concepts
of stability and strict stability for preorderings and quadratic
modules, and we point to some open questions relating those to bounded
polynomials. We finally show that the use of toric completions can greatly
simplify the study of bounded polynomials and of stability for certain
classes of semi-algebraic sets.
-------------------------------------------------
Gregory G Smith
Determinantal Equations
We prove that every projective embedding of a connected scheme
determined by the complete linear series of a sufficiently ample line
bundle is defined by the (2×2)-minors of a 1-generic matrix of linear
forms. Extending the work of Eisenbud-Koh-Stillman for integral
curves, we also provide effective descriptions for such
determinantally presented ample line bundles on products of projective
spaces, Gorenstein toric varieties, and smooth n-folds.
---------------------------------------------------------
Frank Sottile
Orbitopes
An orbitope is the convex hull of an orbit of a compact group acting
linearly on a vector space. Instances of these highly symmetric conex
bodies have appeared in many areas of mathematics and its
applications, including protein reconstruction, symplectic geometry,
and calibrations in differential geometry. In this talk, I will
discuss Orbitopes from the perpectives of classical convexity,
algebraic geometry, and optimization with an emphasis on ten
motivating problems and concrete examples. This is joint work with
Raman Sanyal and Bernd Sturmfels.
----------------------------------------------------
Thorsten Theobald (Goethe-Universität Frankfurt):
Amoebas of genus at most 1
The amoeba $\mathcal{A}(f)$ of a polynomial $f \in \mathbb{C}[x_1,
\ldots, x_n]$ is the image of the variety $V(f) \subset
(\mathbb{C}^*)^n$ under the map $\Log z := (\log |z_1|, \ldots, \log
|z_n|)$. It is well-known that the complement of \mathcal{A}(f)
consists of finitely many convex components.
In general, understanding the configuration space of amoebas is widely
open. In this talk, we study a subclass of amoebas where the Newton
polytope of $f$ is a simplex with one inner support point. Thus there
are only two possible homotopy types. We give bounds on the inner
coefficients for either of the two genera and give characterizations
for the two genera in terms of lopsidedness and in terms of the
$A$-discriminant. (Joint work with Timo de Wolff.)
--------------------------------------------------
Frank Vallentin
Approximation algorithms for SDPs with rank constraints
Abstract:
Finding a sparse/low rank solution in linear/semidefinite programming
has many important applications, e.g. combinatorial optimization,
compressed sensing, geometric embedding, sensor network
localization. In this talk we will consider one of the most basic
problems involving semidefinite programs with rank constraints: the
Grothendieck problem with rank-k-constraint. It contains the MAX CUT
problem as a special case when k = 1 and it is closely related to
Grothendieck inequalities which have been studied in optimization,
functional analysis, combinatorics, quantum information theory, and
complexity theory. We will perform a complete complexity analysis of
the the positive semidefinite version problem by designing an
approximation algorithm and by proving that the algorithm is optimal
if one assumes the unique games conjecture.
joint work with Jop Briët and Fernando de Oliveira Filho
(http://arxiv.org/abs/0910.5765).
-------------------------------------------------------------
Cynthia Vinzant (University of California, Berkeley)
Faces of the Barvinok-Novik orbitope
In 2008, Barvinok and Novik studied faces of the convex hull of the
odd trigonometric moment curve. They show that this convex body is
locally k-neighborly and use this to construct centrally symmetric
polytopes with high face numbers. We will review these results and
resolve one the conjectures from their paper, which leads to a
complete characterization of the edges of this orbitope. In small
dimensions we'll be able to see many other faces as well.
-----------------------------------------------------