Title: Structured Bilinear Mixed-Integer Programming
| Speaker: | Billy Jin |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
We
consider
those
optimization
problems
that
can
be
formulated
as
the
minimization
or
maximization
of
a
bilinear
function
of
finitely
many
real
variables
subject
to
finitely
many
bilinear
inequalities
on
these
variables.
We
further
assume
that
a
subset
of
the
variables
are
required
to
take
only
0,1
values
and
the
remaining
variables
may
take
on
any
real
value.
This
model
is
incredibly
versatile
and
covers
a
wide
swath
of
applications,
but
is
very
difficult
to
solve
in
general.
As
such,
our
goal
is
to
develop
heuristic
algorithms
to
solve
some
special
classes
of
these
problems
efficiently.
In
this
talk,
we
will
illustrate
some
of
the
theory
and
algorithms
of
bilinear
mixed-integer
programs
through
an
application:
the
Stackelberg
shortest
path
game.
Title: Facial Reduction for Low-Rank Matrix Completion
| Speaker: | Shimeng Huang |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: Strict feasibility, the Slater condition, is a crucial element in convex optimization. If Slater condition does not hold, many numerical methods can perform poorly. In this case, facial reduction -- a regularization technique -- can be used to reduce the problem to a lower dimension where the Slater condition can hold, so that the problem can be solved fast and efficiently.
We form the rank minimization matrix completion problem with an SDP embedding and employ nuclear norm as a surrogate of the rank function. The nuclear norm is known to be the convex envelope of the rank function, and it is widely used in rank minimization problems. Although Slater condition holds in this setting, the solution is highly degenerate at optimality so that facial reduction can be effectively applied.
In
this
talk,
we
will
cover
the
idea
of
facial
reduction
and
it's
applications
with
emphasis
on
the
low-rank
matrix
completion
problem.