20 Nov. |
Ming Zhao (U. Houston) "Mixing sets: Complexity and Applications"
|
| Abstract. |
Mixing sets arise as an important substructure in
general mixed-integer programming. In this talk, I
will present two mixing sets. For the first one, I
will give an algebraic characterization of all the
extreme points. Although the number of extreme
points grows exponentially in the worst case, we
can still find the optimal solution within
polynomial time. The other mixing set is an
essential substructure underlying
chance-constrained programming problems with
finite discrete distributions. I will show
families of strong inequalities that can tighten
the formulation and improve the computational time
in branch-and-cut algorithm.
|
13 Nov. |
James Staff "The Compact Lie Groups \(SU(3)\) and \(G_2\)"
|
| Abstract. |
The group of automorphisms of the real octonion
algebra \(\mathbb{O}\) is the compact form of the
exceptional Lie group \(G_2\). We can view the group
\(SU(3)\) as the stabilizer of a point in the sphere
\(S^6\) of imaginary units in \(\mathbb{O}\), which
exhibits \(G_2\) as an \(SU(3)\)-principal bundle over
\(S^6\). These well-known facts already paint a nice
picture of the structure of \(G_2\), and the
explicit embeddings obtained in this way should be
useful to describe the moduli space of flat
principal connections on a \(G_2\)-principal bundle
over a standard torus \(\Sigma \cong S^1 \times
S^1\). Such moduli spaces appear prominently in
Chern-Simons theory. It is a work in progress to
explicitly compute the Weyl quantization of this
moduli space for the gauge group \(SU(3)\). If time
permits, we will discuss how these results can be
used to obtain the quantization for the gauge
group \(G_2\).
|
6 Nov. |
Odin Jesse "Real Radical Ideals with Singular"
|
| Abstract. |
This talk will serve as a casual follow-up to some
of the questions that arose during Dr. de Farias'
talk last week. We'll discuss the moment matrix
approach to the computation of real radical ideals
based on Lasserre and Laurent's 2009 work. We'll
do some small examples by hand then turn to
software for more interesting cases. We'll talk
about the "realrad" package in Singular and use it
to compute the real radicals of ideals that can
assist in optimization problems. We'll also take
a look at some seemingly small ideals for which
the real radical algorithm can't produce a result
in a realistic amount of time on average desktop
hardware.
|
30 Oct. |
Ismael Regis de Farias Jr. "Challenging problems in computational polynomial optimization"
|
| Abstract. |
The problem of minimizing a polynomial function
over a semi-algebraic set is one of the most
important in optimization, both in theory as well
as in practice. It turns out that polynomial
optimization is a robust model, and it includes as
a special case, such problems as 0-1 mixed-integer
quadratic programming. The use of algebraic
methods, both theory and computational, is clearly
possible. However, this is a largely unexplored
approach. I will present a few of these problems
and thoughts as to how they can benefit from
theory and computational methods from algebraic
geometry.
|
23 Oct. |
No seminar
|
16 Oct. |
No seminar
|
9 Oct. |
Odin Jesse "Theta Bodies and Classification of SOS Ideals"
|
| Abstract. |
If a polynomial can be written as the sum of
squares of other polynomials then it is certainly
non-negative over the reals. More generally, if a
polynomial is congruent to a sum of squares in a
quotient ring for an ideal then it is non-negative
over the real variety of the ideal. It turns out
that the converse is true in certain nice cases.
In this talk we'll motivate this study of
non-negativity with some applications in
optimization. We'll introduce some tools from
real algebraic geometry including the Real Radical
of an ideal, a real version of the
Nullstellensatz, and the Theta Body hierarchy of
an ideal. These can be used to study the SOS
structure of polynomial ideals. An ideal is
called \((d,k)\)-SOS if every polynomial of degree
\(\leq d\) that is non-negative over the variety of the
ideal can be written not only as a sum of squares,
but as a sum of squares of polynomials of degree
\(\leq k\). Ideals with this property, especially the
\((1,1)\)-SOS ideals, are cooperative with a number of
optimization techniques that use Semi-Definite
Programming algorithms. A classification of
ideals by \((d,k)\)-SOS properties is an open problem.
We'll look at some applications that demonstrate
why the classification is interesting and we'll
conclude with a discussion of the situations in
which a classification is known.
|
2 Oct. |
Ismael Regis de Farias Jr. "Theta bodies for polynomial ideals"
|
| Abstract. |
I will review the recent work of Gouveia, Parrilo,
and Thomas on a semidefinite programming hierarchy
of relaxations for polynomial optimization. I will
define and motivate Theta bodies, and give some of
its main properties. In the end I will present a
few open problems on polynomial optimization
related to Theta bodies.
|
25 Sep. |
Ismael Regis de Farias Jr. "Connections between algebra and optimization"
|
| Abstract. |
This is the first of n (where n is a positive
integer) presentations that will explore the
virtually unexplored synergism between algebra and
optimization. In this one, I will give a gentle
introduction to the field of optimization and will
hint a few possibilities of interaction with
algebra.
|
18 Sep. |
Chris Monico "Root-finding over finite fields"
|
| Abstract. |
In this elementary talk, aimed at graduate
students, we will present a well-known technique
for finding roots of univariate polynomials over
finite fields.
|
11 Sep. |
No seminar
|
4 Sep. |
Lars Winther Christensen "A variation on Baer's criterion II"
|
| Abstract. |
Baer's criterion says, when one phrases it in
cohomological terms, that injectivity of a module can be
detected by vanishing of Ext against cyclic modules. I
will discuss a recent result that says that one can
replace cyclic modules with fields; it comes out of joint
work with Srikanth Iyengar.
|
28 Aug. |
Lars Winther Christensen "A variation on Baer's criterion I"
|
| Abstract. |
Baer's criterion says, when one phrases it in
cohomological terms, that injectivity of a module can be
detected by vanishing of Ext against cyclic modules. I
will discuss a recent result that says that one can
replace cyclic modules with fields; it comes out of joint
work with Srikanth Iyengar.
|
