STOCHASTIC VARIATIONAL & HIERARCHICAL PROBLEMS: MODELS, ALGORITHMS, AND APPLICATIONS TO TRANSMISSION EXPANSION PROBLEMS
Open Access
- Author:
- Cui, Shisheng
- Graduate Program:
- Industrial Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- June 03, 2019
- Committee Members:
- Uday V. Shanbhag, Dissertation Advisor/Co-Advisor
Uday V. Shanbhag, Committee Chair/Co-Chair
Mort D. Webster, Committee Member
Huanan Zhang, Committee Member
Constantino Lagoa, Outside Member
Benjamin F. Hobbs, Special Member - Keywords:
- variational inequality
generalized equations
transmission expansion
stochastic optimization - Abstract:
- This dissertation comprises of three main essays, all of which fall under the umbrella of models and algorithms for stochastic variational and hierarchical problems. (i). Extragradient-type schemes for stochastic variational inequality problems. When solving stochastic variational inequality problems, the classical extragradient method for merely monotone problems is complicated by a key challenge: the scheme requires two projections on what could be a complicated convex set and two evaluations of the map for every major iteration. We consider two related avenues where every iteration requires only a single projection: (i) A stochastic projected reflected gradient (SPRG) method requiring a single evaluation of the map and a single projection; and (ii) A stochastic subgradient extragradient (SSE) method that requires two evaluations of the map and a single projection. We prove the almost-sure convergence of the iterates to a random point in the solution set for both schemes under suitable requirements and prove that variance-reduced counterparts achieve the canonical deterministic rates of convergence. To contend with complex feasibility sets given by an intersection of a large number of convex sets, we provide rate statements for a variant of our scheme where the projection is replaced by a random projections. (ii). Sampling-based Proximal and splitting schemes for monotone stochastic inclusion problems. Next, we consider a stochastic generalized equation with monotone operators, a class of problems that subsumes convex stochastic optimization problems as well as subclasses of convex Nash games and variational inequality problems. A direct application of proximal and splitting schemes are complicated by the need to resolve problems with expectation-valued maps at each step, a concern that is addressed by using sampling. Accordingly, we propose two avenues for addressing uncertainty in the mapping. (i) Stochastic proximal point methods (SPP}). We develop amongst the first variance-reduced stochastic proximal point scheme that achieves deterministic rates of convergence in terms of solving proximal-point problems. Notably, the presented schemes achieve deterministic rates of convergence and oracle complexity bounds are provided; (ii) Stochastic modified forward-backward splitting scheme (SMFBS). In settings, where the map is a sum of two maps, of which the first is an expectation-valued map and the second has a cheap resolvent. In such cases, we prove that variance-reduced splitting schemes display deterministic rates of convergence under maximal monotonicity and optimal oracle complexities. We proceed to show that both schemes achieve the optimal (deterministic) rates of convergence and provide oracle complexity guarantees. (iii). Competitive transmission expansion under uncertainty. Finally, we consider a problem of competitive transmission expansion framework under uncertainty in the context of power systems planning. This work is motivated by the need to consider transmission charges and their impact on subsequent generation expansion decisions and the resulting social welfare in a competitive environment, as captured by a market equilibrium problem. We model this hierarchical problem as a mathematical program with equilibrium constraints complicated by the presence of first-stage binary expansion decisions. Empirical studies suggest that by smoothing the problem allows for improving the efficiency of computing near-global solutions in a fraction of the time taken by standard branching schemes. Preliminary insights from the model show that using charges such as MW-miles leads to lower social welfare compared to that obtained from either the flat rate charge or no charge.