## Active-set prediction for interior point methods

##### Abstract

This research studies how to efficiently predict optimal active constraints of an inequality
constrained optimization problem, in the context of Interior Point Methods (IPMs).
We propose a framework based on shifting/perturbing the inequality constraints of the
problem.
Despite being a class of powerful tools for solving Linear Programming (LP) problems,
IPMs are well-known to encounter difficulties with active-set prediction due essentially
to their construction. When applied to an inequality constrained optimization
problem, IPMs generate iterates that belong to the interior of the set determined by
the constraints, thus avoiding/ignoring the combinatorial aspect of the solution. This
comes at the cost of difficulty in predicting the optimal active constraints that would
enable termination, as well as increasing ill-conditioning of the solution process. We
show that, existing techniques for active-set prediction, however, suffer from difficulties
in making an accurate prediction at the early stage of the iterative process of IPMs;
when these techniques are ready to yield an accurate prediction towards the end of
a run, as the iterates approach the solution set, the IPMs have to solve increasingly
ill-conditioned and hence difficult, subproblems.
To address this challenging question, we propose the use of controlled perturbations.
Namely, in the context of LP problems, we consider perturbing the inequality constraints
(by a small amount) so as to enlarge the feasible set. We show that if the perturbations
are chosen judiciously, the solution of the original problem lies on or close to the central
path of the perturbed problem. We solve the resulting perturbed problem(s) using a
path-following IPM while predicting on the way the active set of the original LP problem;
we find that our approach is able to accurately predict the optimal active set of the
original problem before the duality gap for the perturbed problem gets too small.
Furthermore, depending on problem conditioning, this prediction can happen sooner
than predicting the active set for the perturbed problem or for the original one if no
perturbations are used. Proof-of-concept algorithms are presented and encouraging
preliminary numerical experience is also reported when comparing activity prediction
for the perturbed and unperturbed problem formulations.
We also extend the idea of using controlled perturbations to enhance the capabilities
of optimal active-set prediction for IPMs for convex Quadratic Programming (QP) problems.
QP problems share many properties of LP, and based on these properties, some
results require more care; furthermore, encouraging preliminary numerical experience
is also presented for the QP case.