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

• 成果类型: Article
• 署名作者: Cui, Shisheng; Shanbhag, Uday, V; Yousefian, Farzad
• 署名单位: Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Rutgers University System; Rutgers University New Brunswick
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01893-6
• 发表日期: 2023
• 页码: 1153-1225
• 关键词: mathematical programs; equilibrium constraints; optimization problems; complementarity constraints; sqp methods; approximation; CONVERGENCE; nonsmooth; gradient

摘要

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/epsilon(2)), and O(1/epsilon(2) ln(1/epsilon)), respectively. Analogous bounds for the nonconvex regime are O(1/epsilon), O(1/epsilon(2)), and O(1/epsilon(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/epsilon(2)), and O(1/epsilon(2) ln(1/epsilon)) while the corresponding bounds in the nonconvex regime are O(1/epsilon), O(1/epsilon(2)), and O(1/epsilon(2) ln (1/epsilon)), 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).