Henry Wolkowicz, University of Waterloo
Slater's condition -- existence of a ``strictly feasible solution'' --
is at the heart of convex optimization. It is enough to look at the basics:
without strict feasibility, first-order optimality conditions may be
meaningless, the dual problem may yield little information about the primal,
and small changes in the data may render the problem infeasible.
In consequence, many off-the-shelf numerical methods can perform poorly;
primal-dual interior point methods, in particular.
New optimization modelling techniques and convex relaxations for hard nonconvex
problems have shown that the loss of strict feasibility is a much
more pronounced phenomenon than has previously been realized.
Such new developments suggest a reappraisal.
In this talk we describe the various reasons for the loss of strict
feasibility, whether due to poor modelling choices or (more interestingly)
rich underlying structure, and describe ways to cope with it.
In particular, we look at three different views:
(i) from the ground set of the application;
(ii) from the lifted space of semidefinite matrices in the relaxation;
(iii) from the image space of the relaxation.
We consider applications to Euclidean matrix completions for sensor network localization and
molecular conformation problems.
(talk based on a survey paper, in progress, with Dmitriy Drusvyatskiy, University of Washington, Seattle WA.)