A constructive algorithm for determination of immobile indices in convex SIP problems with polyhedral index sets

Abstract

We consider convex Semi-Infinite Programming (SIP) problems with polyhedral index sets. For these problems, we generalize the concepts of immobile indices and their immobility orders (that are objective and important characteristics of the feasible sets permitting to formulate new efficient optimality conditions.

We describe and justify a finite constructive algorithm (DIIPS algorithm) that determines immobile indices and their immobility orders along the feasible directions. This algorithm is based on a representation of the cones of feasible directions of polyhedral index sets in the form of linear combinations of the extremal rays {and on the approach described in our previous papers for the cases of multidimensional immobile sets of more simple structure. A constructive procedure of determination of the extremal rays is described and an example illustrating the application of the DIIPS algorithm is provided.