SemiDefinite Programming Relaxation for Polynomial Optimization Problems
Speaker: | Hayato Waki |
---|---|
Affiliation: | The University of Electro-Communications |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
Polynomial Optimization Problem (POP) is the problem of minimizing a polynomial objective function over a set defined by finite many polynomial equalities and/or inequalities. Lasserre proposed an approach via SemiDefinite Programming (SDP) to find a tighter lower bound or the exact optimal value of a given POP. However, it is known that the resulting SDP problems by Lasserre's approach often become large-scale and/or highly degenerate. As a result, we need to overcome these difficulties to find a lower bound or the exact optimal value of a given POP.
This
talk
consists
of
two
parts.
In
part
I,
we
deal
with
POPs
with
a
sparse
structure.
For
such
POPs,
we
propose
a
sparse
SDP
relaxation.
We
present
some
numerical
results
and
observe
that
the
resulting
SDP
relaxation
problems
become
small
enough
to
be
solved
effectively.
In
part
II,
we
show
that
for
simple
POPs,
the
'optimal'
values
of
SDP
relaxation
problems
reported
by
the
standard
SDP
solvers
converge
to
the
optimal
values
of
those
POPs,
while
the
true
optimal
values
of
SDP
relaxation
problems
are
strictly
and
significantly
less
than
those
values.
One
of
this
reason
is
that
the
SDP
relaxation
problems
are
highly
degenerate.
We
also
demonstrate
how
SDPA-GMP,
a
multiple
precision
SDP
solver
developed
by
one
of
the
authors,
can
deal
with
this
situation
correctly.
This
is
joint
work
with
Masakazu
Kojima,
Sunyoung
Kim,
Masakazu
Muramatsu
and
Maho
Nakata.