Probability Maximization via Minkowski Functionals: Convex Representations and Tractable Resolution

Dr. Uday V. Shanbhag, The Gary and Sheila Bello Chaired professor, Department of Industrial and Manufacturing Engineering, Penn State University
Zoom Meeting ID: 970 7656 5407 Password: 477211

In this talk, we consider the maximization of a probability ℙ{ζ∣ζ∈K(x)} over a closed and convex set  χ, a special case of the chance-constrained optimization problem. We define K(x) as K(x)≜{ζ∈к ∣c(x,ζ)≥0} where ζ is uniformly distributed on a convex and compact set к and c(x,ζ) is defined as either {c(x,ζ)≜1−|ζTx|m, m≥0} (Setting A) or c(x,ζ)≜Tx−ζ (Setting B). We show that in either setting, ℙ{ζ∣ζ∈K(x)} can be expressed as the expectation of a suitably defined function F(x,ξ) w. r. t. an appropriately defined Gaussian density, i.e. 𝔼p̃ [F(x,ξ)]. We then develop a convex representation of the original problem requiring the minimization of g(𝔼[F(x,ξ)]) over χ where g is an appropriately defined smooth convex function. Traditional stochastic approximation schemes cannot contend with the minimization of g(𝔼[F(⋅,ξ)]) over χ, since conditionally unbiased sampled gradients are unavailable. We then develop a regularized variance-reduced stochastic approximation ({\textbf{r-VRSA}}) scheme that obviates the need for such unbiasedness by combining iterative {regularization} with variance-reduction. Notably, (r-VRSA) is characterized by both almost-sure convergence guarantees, a convergence rate of O(1/k1/2−a)  in expected sub-optimality where a>0, and a sample complexity of O(1/ϵ6+δ) where δ>0. This is joint work with I. Bardakci, A. Jalilzadeh, and C. Lagoa. 


Uday V. Shanbhag has held the Gary and Sheila Bello Chaired professorship in Ind. & Manuf. Engr. at Penn State University (PSU) since Nov. 2017 and has been at PSU since Fall 2012, prior to which he was at University of Illinois at Urbana- Champaign (between 2006–2012, both as an assistant and a tenured associate professor). His interests lie in the analysis and solution of optimization probems, variational inequality problems, and noncooperative games complicated by nonsmoothness and uncertainty. He holds undergraduate and Masters degrees from IIT, Mumbai (1993) and MIT, Cambridge (1998) respectively and a Ph.D. in management science and engineering (Operations Research) from Stanford University (2006).