2018/02/27 by I. E. Bardakci, Afrooz Jalilzadeh, Bardakci, Ibrahim E. +5
Decision Sciences · Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.1802.09682
openalex publication_date 2018/02/27 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
In this paper, we consider the maximization of a probability ℙ\ ζ| ζ∈ K(\mathbf x)\ over a closed and convex set \mathcal X, a special case of the chance-constrained optimization problem. We define K(\mathbf x) as K(\mathbf x) \triangleq \ ζ∈ K | c(x,ζ) ≥ 0 \ where ζ is uniformly distributed on a convex and compact set K and c(x,ζ) is defined as either c(x,ζ) \triangleq 1-|ζTx|m, m≥ 0 (Setting A) or c(x,ζ) \triangleq Tx -ζ (Setting B). We show that in either setting, ℙ\ ζ| ζ∈ K(x)\ can be expressed as the expectation of a suitably defined function F(x,ξ) with respect to an appropriately defined Gaussian density (or its variant), i.e. 𝔼 p [F(\mathbf x,ξ)]. We then develop a convex representation of the original problem requiring the minimization of g(𝔼[F(x,ξ)]) over \mathcal X where g is an appropriately defined smooth convex function. Traditional stochastic approximation schemes cannot contend with the minimization of g(𝔼[F(⋅,ξ)]) over \mathcal X, since conditionally unbiased sampled gradients are unavailable. We then develop a regularized variance-reduced stochastic approximation (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.