COMPLETELY POSITIVE AND CO-POSITIVE PROGRAMMING: APPLICATIONS IN DISRUPTION RISK MANAGEMENT, POST DISASTER HUMANITARIAN LOGISTICS AND HOMELAND SECURITY GAMES

GAO YINI

Publication

COMPLETELY POSITIVE AND CO-POSITIVE PROGRAMMING: APPLICATIONS IN DISRUPTION RISK MANAGEMENT, POST DISASTER HUMANITARIAN LOGISTICS AND HOMELAND SECURITY GAMES

GAO YINI

Abstract

This thesis is motivated by recent advancements in applying completely positive and co-positive programs to obtaining bounds to $\mathcal{NP}$-hard problems as well as stochastic optimization problem. There are literature establishing the equivalence between completely/co-positive programs and several classic NP-hard problems, such as nonconvex quadratic problem, maximum stable set problem, and nonconvex mixed 0-1 quadratic problem . Following their work, Natarajan et al. extended the application of completely positive program to stochastic optimization problem. Specifically, by adopting the concept of distributional robustness and assuming the first-two moments of the underlying distribution are known, they showed the moment-based bound of a mixed 0-1 linear problem with random objective coefficients can be obtained by solving a completely positive program. Inspired by their works, in this thesis, we establish a framework showing that a more general form of distributionally robust stochastic problem admits an equivalent completely positive reformulation. The framework also incorporates different types of uncertainty sets and constructs equivalent completely positive formulations to characterize feasible moments. We apply this general framework to three applications in disaster management.