Collaborative Proposal: Hierarchical programs under uncertainty: Risk, Discreteness, and Distributed

The goal of this project lies in devising provably convergent randomized methods equipped withperformance guarantees for computing a,pproximate solutions to stochastic and risk-averse mathematicalprograms with equilibrium constraints (MPECs) and their myriad extens,ions. MPECssubsume bilevel programs with convex lower-level problems and find broad applicability in engineeringand economics; of pa,rticular relevance are network interdiction games arising in militarylogistics, supply chain interdiction, and nuclear weapon smuggl,ing prevention, to name a few. Despitenearly three decades of research, there are no efficient first/zeroth-order schemes equippedwi,th non-asymptotic rate guarantees for resolving deterministic or risk-averse variants of MPECs.Similar gaps exist in terms of distri,buted algorithms as well as schemes for mixed-integer MPECs.Motivated by these lacunae, our proposed research is built around presen,ting amongst the firstrate and complexity guarantees for a breadth of stochastic and risk-averse MPECs with possiblediscreteness and, extensions to large-scale block-based and privacy-constrained settings. In addition,we propose the development of amongst the first, asynchronous and possibly delay-afflictedschemes for computing equilibria to hierarchical noncooperative games. The project is divi,dedin four integrated research thrusts: Thrust I. Implicit Quasi-Newton Methods for Risk-AverseMPECs; Thrust II. Distributed and Blo,ck-Based Methods for Large-Scale SMPECs; Thrust III.Implicit Schemes for computing Risk-Averse Nash-Stackelberg Equilibria; Thrust I,V. ProbabilisticBranching Schemes for Mixed-Integer MPECs. The performance of these algorithms will beillustrated on realistic large,-scale networked applications relevant to naval research.If successful, the project will lead to outcomes that will advance the theo,ry and algorithms foraddressing large-scale hierarchical decision making programs by the following: (a) Design andanalysis of a suit,e of randomized implicit algorithms for addressing risk-averse stochastic MPECs;(b) Design and analysis of distributed and parallel,randomized algorithms for addressing largescaleand stochastic MPECs in regimes where there is a lack of access to the data in a cent,ralizedfashion; (c) Development of asynchronous convergent schemes for computing Nash-Stackelbergequilibria in risk-averse regimes;,(d) Development of implicit algorithms reliant on a probabilisticbranching scheme for addressing discretely-valued MPECs. Theoretica,lly, new performanceguarantees will be provided for each class of the proposed algorithms. This will allow for addressinga broad ran,ge of currently intractable hierarchical optimization problems arising in navalresearch. Preliminary theoretical and numerical resul,ts obtained by the PIs display promise andprovide support for the proposed expansive research plan.This project has the potential to, substantially advance the tractability in applications in the areasof network interdiction anddesign that are of particular interes,t to homeland security and the USnavy. This includes critical problems such as counter-drug operations, nuclear weapon smugglingprev,ention, cybersecurity enhancement, and inspection in terror networks. The resolution of suchquestions will significantly contribute,to the ONR?s mission in preserving national security.Approved for Public Release.