Prof. Sharad Bhartiya Research Group IIT Bombay

Implicit active set enumeration approach to mp-QP

 Implicit active set enumeration approach to mp-QP

Multiparametric (mp) programming pre-computes optimal solutions offline which are functions of parameters whose values become apparent online. This makes it particularly well suited for applications that need a rapid solution of online optimization problems. In this work, a novel approach for solving a strictly convex mp-QP problem is presented, which eliminates the need for a parameter exploration step. The main advantage of the proposed technique is that it guarantees arriving at the minimum number of partitions of the parameter space while ensuring that the parameter space is fully explored, thereby remaining free of the issues in the previously reported algorithms. The approach is based on an implicit enumeration of the set of active constraints. Further, it uses a pruning criterion that facilitates a significant reduction in the number of active sets that need be enumerated, thus avoiding the combinatorial complexity in the enumeration-based approach. The proposed approach also inherently identifies degeneracies arising out of violations of Strict Complementary Slackness (SCS) and Linear Independence Constraint Qualification (LICQ) conditions, which are commonly encountered in real problems.