Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs
Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs
复制标题
DOI：
10.1007/s10107-022-01893-6
复制
发表时间：
2021-04
影响因子：
2.7
通讯作者：
Shisheng Cui;U. Shanbhag;Farzad Yousefian
中科院分区：
文献类型：
--
作者：
Shisheng Cui;U. Shanbhag;Farzad Yousefian
具有平衡约束的数学规划（MPEC）代表了一类分层规划，允许对工程，经济，金融和统计中的问题进行建模。虽然随机概括一直假设越来越多的相关性，有一个明显的缺乏有效的一阶/零阶计划与非渐近率保证解决甚至确定性的变种，这样的问题。我们考虑一类随机MPEC（SMPEC），其中参数化的下层平衡问题是由确定性/随机变分不等式问题，其映射是强单调的，一致的上层决策。在适当的假设下，这为通过利用局部随机球面平滑框架的无梯度零阶方法解决具有Lipschitz连续目标的隐式问题铺平了道路。求解隐式问题的有效算法允许利用隐式问题所具有的任何凸性属性，这反过来又有利于近似全局极小值的计算。在这种情况下，我们提出了单阶段和两阶段的随机MPEC计划时，上层问题是凸或非凸的隐式意义。（一）.单阶段SMPEC。在单阶段SMPEC中，在凸区域中，我们提出的不精确方案的特征在于分别在、和的上层投影、上层样本和下层投影中的复杂性。非凸区域的类似边界分别为、和。（二）.两阶段SMPEC。在两阶段SMPEC中，在凸区域中，我们提出的不精确方案在上层投影、上层样本和下层投影方面的复杂性分别为，，和，而在非凸区域中相应的边界分别为，，和，。此外，我们得出的声明，加速计划的设置，低级别的问题的确切解决方案是可用的。初步的数值计算表明，该计划规模与问题的大小，是相对稳健的算法参数的修改，显示出明显的优势，在获得近全球的凸隐式问题的最小值与竞争的求解器相比，并提供类似的精度的解决方案，在一小部分的时间所采取的样本平均近似（SAA）。
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,, and, respectively. Analogous bounds for the nonconvex regime are,, and, 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,, andwhile the corresponding bounds in the nonconvex regime are,, and, 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).