The adaptive convexification algorithm for semi-infinite programming with arbitrary index sets

Oliver Stein and Paul Steuermann

Abstract. A numerical solution method for semi-infinite optimization problems with arbitrary, not necessarily box-shaped, index sets is presented. Following the ideas of C. A. Floudas, O. Stein, The adaptive convexification algorithm: a feasible point method for semi-infinite programming (SIAM Journal on Optimization, Vol. 18, 2007, 1187-1208), convex relaxations of the lower level problem are adaptively constructed and then reformulated as MPCCs and solved. Although the index set is arbitrary, this approximation produces feasible iterates for the original problem. The convex relaxations and needed parameters are constructed with ideas of the alphaBB method of global optimization and interval methods. It is shown that after finitely many steps an epsilon-stationary point of the original semi-infinite problem is reached. A numerical example illustrates the performance of the proposed method.

Software. Note that an implementation of this method is freely available here.

Full text.