Collaborative Proposal: Hierarchical programs under uncertainty: Risk, Discreteness, and Distributed
Abstract
Project SummaryApproved for Public ReleaseThe goal of this project lies in devising provably convergent randomized methods equipped,with performance guarantees for computing approximate solutions to stochastic and risk-averse mathematical programs with equilibrium, constraints (MPECs) and their myriad extensions. MPECs subsume bilevel programs with convex lower-level problems and find broad app,licability in engineering and economics; of particular relevance are network interdiction games arising in military logistics, suppl,y chain interdiction, and nuclear weapon smuggling prevention, to name a few. Despite nearly three decades of research, there are no, efficient first/zeroth-order schemes equipped with non-asymptotic rate guarantees for resolving deterministic or risk-averse varian,ts of MPECs. Similar gaps exist in terms of distributed algorithms as well as schemes for mixed-integer MPECs. Motivated by these la,cunae, our proposed research is built around presenting amongst the first rate and complexity guarantees for a breadth of stochastic, and risk-averse MPECs with possible discreteness and extensions to large-scale block-based and privacy-constrained settings. In add,ition, we propose the development of amongst the first asynchronous and possibly delay-afflicted schemes for computing equilibria to, hierarchical noncooperative games. The project is divided in four integrated research thrusts: Thrust I. Implicit Quasi-Newton Meth,ods for Risk-Averse MPECs; Thrust II. Distributed and Block-Based Methods for Large-Scale SMPECs; Thrust III. Implicit Schemes for c,omputing Risk-Averse Nash-Stackelberg Equilibria; Thrust IV. Probabilistic Branching Schemes for Mixed-Integer MPECs. The performanc,e of these algorithms will be illustrated on realistic large-scale networked applications relevant to naval research. If successful,, the project will lead to outcomes that will advance the theory and algorithms for addressing large-scale hierarchical decision maki,ng programs by the following: (a) Design and analysis of a suite of randomized implicit algorithms for addressing risk-averse stocha,stic MPECs; (b) Design and analysis of distributed and parallel randomized algorithms for addressing large-scale and stochastic MPEC,s in regimes where there is a lack of access to the data in a centralized fashion; (c) Development of asynchronous convergent scheme,s for computing Nash-Stackelberg equilibria in risk-averse regimes; (d) Development of implicit algorithms reliant on a probabilisti,c branching scheme for addressing discretely-valued MPECs. Theoretically, new performance guarantees will be provided for each class, of the proposed algorithms. This will allow for addressing a broad range of currently intractable hierarchical optimization problem,s arising in naval research. Preliminary theoretical and numerical results obtained by the PIs display promise and provide support f,or the proposed expansive research plan.This project has the potential to substantially advancethe tractability in applications in t,he areas of network interdiction and design that are of particular interest to homeland security and the US navy. This includes crit,ical problems such as counter-drug operations, nuclear weapon smuggling prevention, cybersecurity enhancement, and inspection in ter,ror networks. The resolution of such questions will significantly contribute to the ONR s mission in preserving national security.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Oct 07, 2022
- Source ID
- N000142212757
Entities
People
- Farzad Yousefian
Organizations
- Office of Naval Research
- Rutgers University
- United States Navy