Duality, Complementarity, and Regularization, in Conic Convex Optimization
Speaker: | Henry Wolkowicz |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
The
elegant
results
for
strong
duality
and
strict
complementarity
for
linear
programming
(LP)
can
fail
for
cone
programming
over
nonpolyhedral
cones.
One
can
have:
unattained
optimal
values;
nonzero
duality
gaps;
and
no
primal-dual
optimal
pair
that
satisfies
strict
complementarity.
We
take
a
fresh
look
at
known
and
new
results
for
duality,
optimality,
constraint
qualifications,
and
complementarity,
for
linear
cone
optimization
problems
in
finite
dimensions.
These
results
include:
weakest
and
universal
constraint
qualifications
(CQs);
duality
and
characterizations
of
optimality
that
hold
without
any
CQ;
geometry
of
nice
and
devious
cones;
the
geometric
relationships
between
zero
duality
gaps,
complementarity,
and
the
facial
structure
of
cones;
and,
the
connection
between
theory
and
empirical
evidence
for
lack
of
a
CQ
and
failure
of
strict
complementarity.
One
theme
is
the
notion
of
minimal
representation
of
the
cone
and
the
constraints
in
order
to
regularize
the
problem
and
avoid
both
the
theoretical
and
numerical
difficulties
that
arise
due
to
(near)
loss
of
a
CQ.
We
include
a
discussion
on
obtaining
these
representations
efficiently.
A
parallel
theme
is
the
loss
of
strict
complementarity
and
the
corresponding
theoretical
and
numerical
difficulties
that
arise;
a
discussion
on
avoiding
these
difficulties
is
included.
We
then
discuss
the
surprising
connections
between
the
duality
theory
and
complementarity.
Our
emphasis
is
on
results
that
deal
with
Semidefinite
Programming
(SDP).
Joint work with Simon Schurr and Levent Tuncel.