Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs

Mathematical programs with equilibrium constraints (MPECs) represent a class of hierarchical programs that allow for modeling problems in engineering, economics, finance, and statistics. While stochastic generalizations have been assuming increasing relevance, there is a pronounced absence of efficient first/zeroth-order schemes with non-asymptotic rate guarantees for resolving even deterministic variants of such problems. We consider a subclass of stochastic MPECs (SMPECs) where the parametrized lower-level equilibrium problem is given by a deterministic/stochastic variational inequality problem whose mapping is strongly monotone, uniformly in upper-level decisions. Under suitable assumptions, this paves the way for resolving the implicit problem with a Lipschitz continuous objective via a gradient-free zeroth-order method by leveraging a locally randomized spherical smoothing framework. Efficient algorithms for resolving the implicit problem allow for leveraging any convexity property possessed by the implicit problem, which in turn facilitates the computation of approximate global minimizers. In this setting, we present schemes for single-stage and two-stage stochastic MPECs when the upper-level problem is either convex or nonconvex in an implicit sense. (I). Single-stage SMPECs. In single-stage SMPECs, in convex regimes, our proposed inexact schemes are characterized by a complexity in upper-level projections, upper-level samples, and lower-level projections of O(1ϵ2), O(1ϵ2), and O(1ϵ2ln(1ϵ)), respectively. Analogous bounds for the nonconvex regime are O(1ϵ), O(1ϵ2), and O(1ϵ3), respectively. (II). Two-stage SMPECs. In two-stage SMPECs, in convex regimes, our proposed inexact schemes have a complexity in upper-level projections, upper-level samples, and lower-level projections of O(1ϵ2), O(1ϵ2), and O(1ϵ2ln(1ϵ)) while the corresponding bounds in the nonconvex regime are O(1ϵ), O(1ϵ2), and O(1ϵ2ln(1ϵ)), respectively. In addition, we derive statements for accelerated schemes in settings where the exact solution of the lower-level problem is available. Preliminary numerics suggest that the schemes scale with problem size, are relatively robust to modification of algorithm parameters, show distinct benefits in obtaining near-global minimizers for convex implicit problems in contrast with competing solvers, and provide solutions of similar accuracy in a fraction of the time taken by sample-average approximation (SAA).