---
abstract: 'This paper addresses a particular instance of probability maximization problems with random linear inequalities. We consider a novel approach that relies on recent findings in the context of non-Gaussian integrals of positively homogeneous functions. This allows for showing that such a maximization problem can be recast as a convex stochastic optimization problem. While standard stochastic approximation schemes cannot be directly employed, we notice that a modified variant of such schemes is provably convergent and displays optimal rates of convergence. This allows for stating a variable sample-size stochastic approximation (SA) scheme which uses an increasing sample-size of gradients at each step. This scheme is seen to provide accurate solutions at a fraction of the time compared to standard SA schemes.'
author:
- 'I. E. Bardakci'
- 'C. Lagoa'
- 'U. V. Shanbhag [^1][^2]'
bibliography:
- 'references.bib'
title: '**Probability Maximization with Random Linear Inequalities: Alternative Formulations and Stochastic Approximation Schemes** '
---

at (current page.south) ;

Introduction
============

In this paper, we consider the maximization of a function defined as the probability of a random variable prescribed by a set defined by inequalities. In particular, the aim of this paper is to provide novel avenue for resolving problems of the form: $$\begin{aligned}
\max_{x \in X} \ f(x) \ \triangleq \  \text{Prob} \{\xi \colon
\xi^{\intercal}x \leq a\},
    \label{main_prob}\end{aligned}$$ where $x \in \mathbb{R}^n$ is the decision variable, $\xi : \Omega \to
\mathbb{R}^d$ is a $d-$dimensional random vector, [[and]{}]{} $f:
\mathbb{R}^n \to \mathbb{R}$ is a real-valued function. [[Furthermore, suppose $\xi$ is assumed to be uniformly distributed on a convex set $\mathcal{K} \subset \mathbb{R}^m$ as per the known distribution]{}]{} $\text{Prob}(\cdot). $

[[Problems of the form (\[main\_prob\]) fall within the umbrella of chance-constrained optimization problems and find applicability in a breadth of settings including financial risk management [@rockafellar2002], reservoir system design [@andrieu2010], and optimal power flow [@bienstock2014]. Optimization problems with probabilistic or chance constraints were first studied in the seminal work by Charnes and Cooper [@charnes59chance]. Much of the early research in this area examined continuity [@raik1972; @wang1989], differentiability [@raik1975; @simon1989; @uryasev1989], log-concavity [@prekopa1970; @prekopa1971], quasi-concavity [@brascamp1976; @gupta1980; @tamm1977], and $\alpha-$concavity [@borrell1975; @gupta1976; @norkin1991] of probability distributions. Although, there are instances of convex chance-contrained problems (cf. [@lagoa2005; @prekopa2013]), generally such problems are not convex [@prekopa2013; @pinter1989]. In particular, convexity of (\[main\_prob\]) can be claimed when density function of the random vector is log-concave and symmetric. For instance, in [@ball1988; @bobkov2010] it has been shown that problem (\[main\_prob\]) can be reformulated as a convex program when $\xi$ has a logarithmically concave probability density function.]{}]{}

[[: Despite the theoretical progress over the years, problems of the form (\[main\_prob\]) remain challenging to solve, barring a few special cases. The main difficulty in applying standard optimization techniques arises in evaluating a multi-dimensional integral (and its derivatives), and in high dimensions, numerical computation of such integrals with high accuracy remains challenging [@nemirovski2009]. To this end, there have been several avenues that have emerged in addressing this class of problems:\
[*Approximations.*]{} When the problem is nonconvex, quadratic [@bental00robust] and Bernstein [@nemirovski2006] approximations allow for tractable computation of feasible solutions to .\
[*Mixed-integer approaches.*]{} There has been a significant effort in resolving such problems when the distribution is over a finite sample-space (or require a set of points from a continuous sample-space) via mixed-integer programming approaches [@luedtke08sample; @ahmed17nonanticipative].\
[*Monte-Carlo sampling techniques.*]{} A somewhat different tack was considered by Norkin [@norkin1993] where the probability maximization problem was recast as the expectation of the characteristic function. Then by utilizing a convolution-based (or Steklov-Sobolev) smoothing (with a fixed parameter), a stochastic approximation framework was employed for computing an approximate solution. A sample-average approximation has also been utilized for obtaining approximate solutions to chance-constrained problems [@luedtke08sample; @ahmed09sample]. An alternate approach is proposed in [@campi11sampling] which uses a sampling and rejection framework. More recently, in [@hong2011], the authors develop a technique that recognizes that difference-of-convex (DC) programming within a simulation framework to address such settings.]{}]{}

[**Contributions.**]{} We also consider a stochastic approximation framework but rather than utilizing characteristic functions, we employ recent findings non-Gaussian integrals of positively homogeneous functions (PHFs) (see [@lassere2015; @morozov2009]) to derive an alternative formulation. In particular, the resulting problem is an expectation of a random integrand that is continuous for every $\xi$ but is nonsmooth. This then allows us to employ stochastic approximation techniques on the original problem (rather than a smoothed variant). However, through a deterministic smoothing, we may also develop variable sample-size schemes for a smoothed counterpart with Lipschitz continuous gradients, which produces solutions with far less effort.\
[**Organization of paper.**]{} The outline of the paper is [[organized]{}]{} as follows. In section II, [[we present]{}]{} some of the preliminary results that play [[an]{}]{} important role in our formulation [[and briefly review the notation of relevance.]{}]{} Section III is dedicated to [[stating the problem and providing an alternative formulation]{}]{}. In section IV, [[we present a stochastic approximation scheme and provide convergence theory and rate statements.]{}]{} [[A numerical example is provided]{}]{} in section V and [[we conclude the paper]{}]{} in section VI.

Notation and Preliminary Results
================================

Notation and Basic Definitions
------------------------------

The sets of real numbers, nonnegative integers, and positive integers are denoted by $\mathbb{R}$, $\mathbb{N}$, and $\mathbb{Z}$, respectively. The Euclidean norm of column vectors $\mathbf{x} \in
    \mathbb{R}^n$ is denoted by $\|\mathbf{x}\|$, [[while]{}]{} the spectral norm of $\mathbf{A} \in \mathbb{R}^{m\times n}$ is given by $\| \mathbf{A} \| = \text{max}\{ \|\mathbf{Ax} \| \colon \|\mathbf{x}\| \leq 1 \}$. The $n$-by-$n$ identity matrix is written as $\mathbf{I}_n$, and the $m$-by-$n$ zero matrix as $\mathbf{0}_{m \times n}$. The projection onto the set $X$ is denoted by $\Pi_{X}$, that is, $\Pi_{X}(y) = \text{argmin}_{x \in X} \| x - y \| $.\

The function $f(\cdot)$ is said to be Lipschitz continuous on [[the]{}]{} domain of $f$ with constant $L > 0$ if $$\begin{aligned}
\| f(x)- f(y)\| \leq L \|x-y\| \ \text{for all} \ x, y \in \text{dom}(f).\end{aligned}$$

\[Log-concavity\] A function $f : \mathbb{R}^d \rightarrow [0, \infty)$ is said to be log-concave if the following holds: Given any $x, y \in \mathbb{R}^d $ and $\lambda \in [0,1]$, it follows that $$\begin{aligned}
 f((1-\lambda)x + \lambda y) \geq [f(x)]^{1-\lambda} [f(y)]^{\lambda}.\end{aligned}$$

\[Minkowski Functional\] Let the set $K \subset \mathbb{R}^n$. Then, Minkowski functional associated with the set $K$, denoted by $\|\xi\|_K$, is given by $$\begin{aligned}
\|\xi\|_K \triangleq \text{inf} \{t>0 : \xi/t \in K\}\end{aligned}$$ for all $\xi \in \mathbb{R}^n $. Note that the expression above defines a norm when the set $K$ is compact, convex and symmetric.

[[Throughout this paper, we define $K(x)$ as follows. $$K{{\color{black}(x)}} \triangleq \{\xi \in \mathbb{R}^n \colon |\xi^{\intercal}x| \leq    1  \}$$]{}]{}where $x \in \mathbb{R}^n$. [[Further the function $f$ in can be restated as]{}]{} $f(x) =
    \text{Prob}\{K{{\color{black}(x)}}\}$. Note $f(0) = 1$ and $f(x) \rightarrow 0$ as $|x| \rightarrow + \infty$.

Preliminary Results
-------------------

[[We now]{}]{} present some results that play [[an]{}]{} important role in our formulation. Throughout this paper, we [[assume that the random variable is defined by a ]{}]{}symmetric log-concave probability density function. Moreover, we assume the support $\mathcal{K} \in \mathbb{R}^m$ of the random variable $\xi$ is centrally symmetric, i.e. the center of symmetry is the origin. First, we have the convexity of the objective function of the reformulated problem; see Section \[Prob\_State\] for detailed description of the problem.\

\[lem\_bobkov\] [[Consider problem .]{}]{} Suppose $\xi$ has a log-concave density. Then $h(x) \triangleq 1/f(x)$ is convex in $\mathbb{R}^n$.

See Lemma 6.2 in [@bobkov2010].

The following result is needed for [[developing an]{}]{} alternative formulation of problem ; see Section \[Alt\_form\] for details.

Let $g_1,\hdots,g_l$ be [[positively homogenous functions (PHFs)]{}]{} of degree $m \neq 0$, $m \in \mathbb{R}$ [[and]{}]{} let $\Omega {{\color{black}\
    \triangleq \ }}  \{\xi: g_k(\xi) \leq 1, k=1,{{\color{black}\hdots}}, l\}.$ Assume that the set $\Omega$ is bounded. Notice that $g(\xi) =
    \max\{g_1(\xi),{{\color{black}\hdots}}, g_l(\xi)\}$ is [[a]{}]{} PHF of degree m. Then, [[the following holds.]{}]{} $$\begin{aligned}
\int_{\Omega} 1 \ d\xi = \frac{1}{\Gamma(1+n/m)} \int_{\mathbb{R}^n} e^{-g(\xi)} \ d\xi.\end{aligned}$$

See *Corollary 1* in [@lassere2015].

Problem Statement {#Prob_State}
=================

In this section, we first state the problem of interest and present the equivalent convex problem by using *Lemma \[lem\_bobkov\]*.

**Problem 1:** Consider the optimization problem given by $$\begin{aligned}
\max_{x \in X} f(x) = \text{Prob} \{ {{\color{black}K(x)}}\}, \label{fx}\end{aligned}$$ where $f \colon X \rightarrow \mathbb{R}$ [[can be shown to be]{}]{} continuously differentiable function with Lipschitz continuous gradients. The set $K{{\color{black}(x)}} =\{\xi \in
\mathcal{K}: |\xi^{\intercal}x | \leq 1 \}$, [[where]{}]{} $x$ denotes the decision variable and $ x \in X$, [[the random variable]{}]{} $\xi$ [[is uniformly distributed over the set $\mathcal{K}$]{}]{}. The set ${{\color{black}\mathcal{K}}} \subset \mathbb{R}^m$ is assumed to be compact, convex and symmetric, and the set $X \subset
\mathbb{R}^n$ is closed and convex. [[We further assume]{}]{} that $f(x) \in [\epsilon,1]$ on $X$ with $0 <\epsilon < 1$.

Although the setup above seems rather restrictive, the proposed algorithms can be applied to solve more general probability maximization problems of the form $$\max_{x\in X} \ \text{Prob}\{ x: (\zeta + a)^T (x+b) \leq 1\}.$$ In other words, the approach proposed can be used to maximize probability of sets involving general linear constraints. This can be done by exploiting the symmetric [[nature]{}]{} of the distribution of the uncertainty. [[To keep the paper concise and the discussion focused]{}]{}, this question will be discussed in future work.

We now formally define the Problem 2, which forms the basis of our computation.

**Problem 2:** Consider the alternative problem defined as follows: $$\begin{aligned}
\min_{x \in X} \ h(x) {{\color{black} \  \triangleq \ }}  \frac{1}{f(x)}. \label{hx}\end{aligned}$$ [[We proceed to show that is a convex optimization problem with $h$ being continuously differentiable with Lipschitzian gradients.]{}]{}

(*Convexity and Lipschitzian properties of* ) \[prop-1\] [[Consider the problem . Then the following hold: (i) The function $h(x)$ is convex over $X$; and (ii) The function $h(x)$]{}]{} is continuously differentiable with Lipschitz continuous gradients.

\(i) [[Since]{}]{} uniform distributions over a compact convex symmetric sets are log-concave and symmetric, by the assumption on the set $\mathcal{K}$, $\xi$ has a symmetric log-concave density. Hence by *Lemma 1*, $h(x)\triangleq 1/f(x)$ is convex; (ii) See Appendix.

We now prove the relatively simple result that allows us to claim that a global minimizer of Problem 2 (a convex program) is a global maximizer of Problem 1.

\[lem2\] Consider [[Problems 1 and 2]{}]{} where $f(x)$ is a continuously differentiable function and $f(x) \in [\epsilon,1]$ on $X$ with $1 >\epsilon > 0$. Suppose $h(x) = 1/f(x)$ is a convex function over $X\subseteq \mathbb{R}^n$, a closed and convex [[set]{}]{}. Then, a global minimizer of is a global maximizer of .

See Appendix.

[[The mere convexity of does not suffice in developing efficient first-order algorithms. To this end]{}]{}, we still need to compute the gradient of the function $h(x)$, [[which is given by the following.]{}]{} $$\begin{aligned}
\nabla_{x} h(x) = -\frac{1}{f^2(x)} \nabla_{x} f(x).\end{aligned}$$

Here, note that $X$ is bounded which implies that $0 < \epsilon \leq f(x)\leq 1$, and in turn, $1/f^2(x)$ is bounded and deterministic. Thus, in order to compute the gradient of $h(x)$, it is enough to compute the gradient of $f(x)$. The function $f(x)$ can be written as $$\begin{aligned}
f(x) =  \text{Prob} \{K{{\color{black}(x)}}\} = \int_{ K{{\color{black}(x)}}} p_{\xi}(\xi) \ d\xi \label{f_prob}\end{aligned}$$ where $p_\xi{(\xi)}$ is probability density function of the random variable $\xi$. Since ${{\color{black}\xi}}$ is uniformly distributed over the set $\mathcal{K}$, we may rewrite $f$ as follows $$\begin{aligned}
f(x) =  \frac{1}{\text{Vol}({{\color{black}\mathcal{K}}})} \int_{K{{\color{black}(x)}}}
\mathbf{1}_{\mathcal{K}} (\xi) \ d\xi, \label{uni}\end{aligned}$$ where $\text{Vol}({{\color{black}\mathcal{K}}})$ denotes [[the]{}]{} volume of the set $\mathcal{K}$. However, as mentioned earlier, [[computing the above multivariate integral ($\ref{uni}$) is computationally demanding, a concern that is addressed next.]{}]{}

Alternative formulation {#Alt_form}
-----------------------

In this section, we [[discuss how the]{}]{} integral (\[uni\]) [[may be expressed as an]{}]{} expectation of [[a suitably defined]{}]{} function, i.e., $f(x) = \mathbb{E}[F(x,\xi)]$. [[Then under suitable assumptions, we may then utilize]{}]{} stochastic approximation tools to compute a solution to . In this setup, we use some important properties of Minkowski functionals and the result given by *Corollary 1*.

Consider the function $f(x)$ in Problem 1. Suppose $X$, $\mathcal{K}$ and $K(x)$ are defined as in Problem 1 and $\xi$ is uniformly distributed over $\mathcal{K}$. Then $$f(x) = \mathcal{C} \ \mathbb{E}[F(x,\xi)],$$ where $F \colon \mathbb{R}^n \times \mathbb{R}^d \rightarrow
\mathbb{R}$, and $\mathbb{E}[\cdot]$ denotes the expectation with respect to $p_{\xi}$, $p_\xi$ denotes the probability density function of independent and identically distributed random variables $\xi \sim \mathcal{N}(0,1)$ with zero mean and unit variance.

First, the indicator function in (\[uni\]) can be expressed as a PHF by exploiting the relation between convex sets and Minkowski functionals. Since the set $\mathcal{K}$ is compact, convex and symmetric, [[the]{}]{} Minkowski functional of $\mathcal{K}$ defines a norm, and hence, it is [[a]{}]{} PHF. Moreover, by the definition of [[the]{}]{} Minkowski functional, $\xi \in \mathcal{K}$ if and only if $ \|\xi\|_\mathcal{K} \leq 1$. Now, in order to use *Corollary 1*, define $\Omega$ as follows. $$\begin{aligned}
\Omega \triangleq  \{\xi: |\xi^{\intercal} x | \leq 1\} \cap \{\xi
\colon \|\xi\|_\mathcal{K} \leq 1\},\end{aligned}$$ which can equivalently be written as $$\begin{aligned}
\Omega =  \left\{\xi: \text{max}(|\xi^{\intercal} x |, \|\xi\|_K) \leq 1
\right\}.\end{aligned}$$ Hence, we have $$\begin{aligned}
f(x)= \frac{1}{\text{Vol}({{\color{black}\mathcal{K}}})} \int_{\Omega} 1 \  d\xi.\end{aligned}$$ Now, define $g(\xi)$ as follows: $$\begin{aligned}
g(\xi) \triangleq \text{max}\{|\xi^\intercal x |^m,
{\|\xi\|^m_{{\color{black}\mathcal{K}}}}\}. \end{aligned}$$ Since $|\xi^\intercal x |^m$ and $ \|\xi\|^{m}_{{{\color{black}\mathcal{K}}}}$ are both PHFs of degree $m$, $g(\xi)$ is also a PHF of degree $m$. Thus, it follows from *Corollary 1* that $$\begin{aligned}
f(x) = \frac{1}{\text{Vol}({{\color{black}\mathcal{K}}})} \frac{1}{\Gamma(1+n/m)} \int_{\mathbb{R}^n} e^{-g(\xi)} \ d\xi, \label{Las}\end{aligned}$$ whenever $\int_{\mathbb{R}^n} e^{-g(\xi)} \ d\xi$ is finite. In fact, the expression (\[Las\]) can be written as $$\begin{aligned}
f(x)  \ & = \mathcal{C} \int_{\mathbb{R}^n} \left[ 2\pi^{n/2}
e^{-\max\{|\xi^{\intercal} x |^m, {\|\xi\|^m_{{\color{black}\mathcal{K}}}}\}+\frac{\xi^{\intercal}
    \xi}{2}}\right] \\
    & \times \left[ {2\pi}^{-n/2} e^{\frac{-\xi^{\intercal} \xi}{2}}
    \right]  \ d\xi\\
 & =  \mathcal{C} \int_{\mathbb{R}^n} F(x,\xi) \ p_\xi(\xi) \ d\xi  =
 \mathcal{C} \ \mathbb{E}[F(x,\xi)],  \end{aligned}$$ where $F(x,\xi)$ is defined as $$F(x,\xi) \triangleq \left[ 2\pi^{n/2}
e^{-\max(|\xi^{\intercal} x |^m, {\|\xi\|^m_{{\color{black}\mathcal{K}}}})+\frac{\xi^{\intercal}
    \xi}{2}}\right],$$ and $ \mathcal{C} = 1/ (\text{Vol}(K) \ \Gamma(1+n/m)) $.

However, $F(x,\xi)$ is not a differentiable function for every $x,\xi$ but it can be shown to be a subdifferentiable convex function. In fact, under the boundedness of $X$, we may further show that under suitable boundedness requirements of the subdifferential, we may apply the robust stochastic approximation framework [@nemirovski2009] to obtain asymptotic convergence as well as rate statements. However, such an avenue necessitates taking as many projection steps as the simulation budget, which makes large-scale implementations challenging if $X$ is a complicated set. An alternative is variable sample-size stochastic approximation (VSSA) [@jalilzadeh2017]. However, such a scheme necessitates that $F(x,\xi)$ be differentiable for almost every $\xi$, a property that may be recovered by introducing a deterministic smoothing.

Smoothing of nonsmooth integrands
---------------------------------

The integrand $F(x,\xi)$ has two sources of nonsmoothness; the first of these is the the max function while the second is the absolute value function. [*Smoothing the max function.*]{} Consider the relatively simple convex function $g(u_1,u_2) =
\max\{u_1,u_2\}$ which can be smoothed via a logarithmic smoothing function $g(u_1,u_2;s) \triangleq
s\ln(\mbox{exp}(u_1/s)+ \mbox{exp}(u_2/s))$ where $s > 0$. In fact, we have that for $i \in \{1,2\}$, $$\nabla_{u_i} g(u_1,u_2;s) =
\frac{\mbox{exp}(u_i/s)}{\mbox{exp}(u_1/s)+\mbox{exp}(u_2/s)},$$ where $0 < \nabla_{u_i} g_i(u_1,u_2;s) < 1$. Furthermore, $$\begin{aligned}
\label{smooth-diff}
0 \leq g(u_1,u_2;s)-g(u_1,u_2) \leq s\ln 2 \end{aligned}$$ for all $u_1, u_2 \in \mathbb{R}$. In fact, the absolute value function $\ell(u) = |u|$ can be smoothed in a similar way by noting that $|u| = \max\{u, -u\}$ and therefore $\ell(u;s)$ is constructed in a fashion similar to $g(u_1,u_2;s)$. By employing this form of smoothing, we may constructed a smoothed variant of $F(x,\xi)$ defined as follows: $$\begin{aligned}
\label{smooth-F}
F(x,\xi;s) \triangleq \left[ -2\pi^{n/2}
e^{-g(\ell(\xi^{\intercal}x;s)^m, {\|\xi\|^m_K}\};s)-\frac{\xi^{\intercal} \xi}{2}}\right].\end{aligned}$$ The continuous differentiability of $\nabla_x F(x,\xi;s)$ can be shown with relative ease and under suitable conditions, for every $\xi$ and $s>0$, we may further show that the $\nabla_x F(\cdot,\xi;s)$ is Lipschitz continuous in $(.)$. We now focus on the solution of the smoothed problem: $$\begin{aligned}
\label{main_prob_s}
\min_{x \in X} \ f(x;s) \triangleq \mathbb{E}[F(x,\xi;s)],\end{aligned}$$ where $F(x,\xi;s)$ is defined in . In future work, we intend to derive the bounds of $f(x;s)-f(x)$. In the rest of the paper, we will focus on .

Stochastic Approximation Schemes
================================

In the prior section, we observed that the function $f(x;s)$ could be recast as an expectation of $F(x,\xi)$. This paves the way for the development of stochastic approximation schemes for computing a solution of such problems. Note that such schemes can handle both smooth and nonsmooth objectives. It may be recalled that stochastic approximation has its roots in the seminal paper by Robbins and Monro [@robbins1951]. In the last several decades, there has been a tremendous amount of research in stochastic approximation, noteworthy amongst these being the long-step averaging framework by Polyak [@polyak1990] and Polyak and Juditsky [@polyak1992] as well as the robust stochastic approximation framework by Nemirovski, Juditsky, Lan, and Shapiro [@nemirovski2009] (which can contend with nonsmooth stochastic convex optimization). In the next subsection, we present a modified stochastic approximation scheme for computing a solution to for which we derive asymptotic convergence and develop rate statements. However, a key shortcoming of this approach is the need for projections on a given convex set at every step, a problem that can prove quite onerous when the simulation lengths are long. To ameliorate this burden, we consider a variable sample-size stochastic approximation scheme [@jalilzadeh2017] and propose variable sample-size counterparts of the proposed techniques.

A modified stochastic approximation scheme
------------------------------------------

Consider the optimization problem $$\begin{aligned}
 \label{opt_prob}
\min_{x \in X} \ h(x;s) =  \frac{1}{f(x;s)},\end{aligned}$$ where $f(x;s) \triangleq \mathbb{E}[F(x,\xi;s)]$ and $h(x;s)$ is convex and continuously differentiable on $X$ for every $s>0$. We further assume that $f(x;s) \in [\epsilon,1]$ on $X$. The derivative of $h$ is given by the following: $$\begin{aligned}
\nabla_x h(x;s) &= -\frac{1}{f^2(x;s)} \nabla_x f(x;s)\\
 &= -\frac{1}{f^2(x;s)}\mathbb{E}[ \nabla_x F(x,\xi;s)],\end{aligned}$$ where the second equality follows from interchanging derivatives and expectations [@shapiro2009]. Unfortunately, the expectation of $F(x,\xi;s)$ and its derivative are unavailable in closed form. But we do make the following assumption on the existence of a [*stochastic oracle*]{} and the parameter sequences employed in the scheme to be defined.

\[ass-1\] There exists a stochastic oracle that produces unbiased (but possibly noise corrupted) estimate of the gradient $\nabla_x F(x,\xi;s)$. Specifically, $w_k = \nabla_x F(x_k,\xi_k;s) - F(x_k;s)$ and satisfy the following for all $k$: (i) The random variables $w_k$ satisfy the following for all $k \geq 0$: $\mathbb{E}[w_k \mid \mathcal{F}_k] = 0$ and $\mathbb{E}[\|w_k\|^2 \mid
\mathcal{F}_k] \leq \nu^2$ almost surely, where $\mathcal{F}_k \triangleq \{x_0,\xi_1,  \hdots, \xi_k\}$. (ii) Furthermore, $\frac{\gamma_k}{\beta_k}$ are positive sequences defined such that $\sum_{k} \gamma_k/\beta_k = \infty$, $\sum_k \gamma_k^2/\beta_k^2 < \infty$, and $0 < \beta_k^2 \leq \epsilon^2$.

[[Consider a traditional stochastic approximation scheme, defined as follows for $k \geq 1$ given an $x_1 \in X$: $$\begin{aligned}
 \tag{t-SA}
x_{k+1} := \Pi_X \left(x_k +
        \frac{\gamma_k\nabla_x
        F(x_k,\xi_k;s) }{\left(\mathbb{E}[F(x_k,\xi;s)]\right)^2} \right).\end{aligned}$$ However, $\mathbb{E}[F(x,\xi;s)]$ is unavailable and consequence ( t-SA) is unimplementable. Consequently, we consider a modified stochastic approximation scheme in which we assume that $\beta_k$ replaces $(\mathbb{E}[F(x,\xi;s)])^2$ and show that this is scheme is indeed convergent. $$\begin{aligned}
 \tag{m-SA}
x_{k+1} := \Pi_X \left(x_k +
        \frac{\gamma_k\nabla_x
        F(x_k,\xi_k;s)}{\beta_k}  \right).\end{aligned}$$ ]{}]{}

\[prop-2\] Consider the problem (\[opt\_prob\]) and suppose Assumption \[ass-1\] [[holds]{}]{}. Given a randomly generated $x_1 \in X$, consider a sequence generated by scheme (m-SA). Then the following hold:

1.  The sequence $\{x_k\}$ converges to the solution set $X_s^*$ of as $k \to \infty$ in an almost surely sense.

2.  The sequence $\mathbb{E}[f(\bar{x}_k;s)-f^*(s)]$ converges to $0$ as $k \to \infty.$

See Appendix.

Accelerated variable sample-size SA (ac-VSSA) scheme
----------------------------------------------------

One of the key shortcomings of the ([m-SA]{}), ([t-SA]{}), and essentially all SA schemes is that given a simulation budget of $M$, the scheme requires taking $M$ projection steps for generating a single simulation run. If $X$ is a complicated set, then this projection operation, albeit a convex programming problem, can significantly slow down practical implementations. To obviate this challenge, there has been some recent effort in developing variable sample-size generalizations which employ a batch-size or sample-size of $N_k$ at iteration $k$ and terminate the scheme when $M$ samples have been consumed [@jalilzadeh2017].

We now consider the following scheme which represents a stochastic generalization of Nesterov’s accelerated gradient scheme [@nesterov1998] which is introduced in [@jalilzadeh2017]. Recall that in [@nesterov1998], for a convex differentiable problem, Nesterov showed that a suitably defined method achieves the optimal rate, i.e. $f(x_k) - f^* \leq \mathcal{O}(1/k^2)$ where $k$ denotes the iteration. As part of the ([m-ac-VSSA]{}) framework, given budget M, $x_1 \in X$, $x_1 = y_1$ and positive sequences $\{\eta_k, N_k\}$; set $\lambda_{0} \triangleq 0$, $k=1$. Then $\{y_k\}$, $\{\lambda_k\}$ and $\{x_k\}$ are defined as follows: $$\begin{aligned}
 \tag{m-ac-VSSA}
\begin{aligned}
y_{k+1} &:= \Pi_X \left(x_k +
        \frac{\eta_k \bar{F}_k}{\beta_k}  \right), \\
\lambda_{k+1} &:= \frac{1+\sqrt{1+4\lambda_{k}^2}}{2},\\
x_{k+1} &:= y_{k+1} + \frac{(\lambda_k - 1)}{\lambda_{k+1}} (y_{k+1} - y_k). 
\end{aligned}\end{aligned}$$ where $\bar{F}_k \triangleq \frac{\sum_{j=1}^{N_k}\nabla_x
    F(x_k,\xi_{j,k};s)}{N_k}$.\

\[ass-2\]

i)  $X$ is closed and convex set.

ii) $h(x)$ is continuously differentiable with Lipschitz continuous gradients.

iii) There exists $v>0$ such that $\mathbb{E}\|w_k\|^2\leq v^2 \ | \mathcal{F}_k]$ holds a.s. for all $k$, where $\mathcal{F}_k\triangleq \sigma\{x_0, x_1, ..., x_n\}$.

iv) $h(x)$ is convex in $x$.

v)  There exists $C$, $D$ such that $\max_{y \in X} \mathbb{E}[\|y-x^*\|] \leq C$ and $\mathbb{E}[\|h(x_1) - h^*\|] \leq D$.

(*Error bound in terms of number of projections $K$ for m-ac-VSSA*) Suppose $h(x; s)$ is a smooth function and *Assumption* \[ass-2\] holds. Let $K$ be the largest integer such that $\sum_{k=1}^{K}N_k \leq M$. Furthermore, suppose $\eta_k = \eta \leq 1/2L$ for all $k$. Let $N_k=\lfloor k^a \rfloor$ where $a = a + \delta$ for $a > 3$ and $\widehat{C} \triangleq \frac{2v^2\eta(a-2)}{a-3}+ \frac{4C^2}{\eta}$. Then the following holds for all $K$. $$\begin{aligned}
\mathbb{E}[h(y_{K+1}; s)-h(x^*; s)] &\leq \frac{\widehat{C}}{K^2} \ \text{and} \ \leq \mathcal{O}\left(\frac{1}{\epsilon^{2+\delta/2}}\right).\end{aligned}$$

See [@jalilzadeh2017].

Numerical Example
=================

In our formulation, these assumptions are satisfied. In particular, *Assumption 2 (i, v)* are satisfied since we assumed the set $X$ is closed and convex, and the function $h(x)$ is bounded. For *Assumption 2 (ii)* see Appendix. *Assumption 2 (iii)* imposes a bound on moments of the function $F(x,\xi)$. By letting $g(\xi) = \text{max}(|\xi^\intercal x |^m, {\|\xi\|^m_K}) $, for $m \geq 2$, one can prove that all moments of $F(x,\xi)$ are bounded. The convexity of $h(x)$ is shown in Section \[Prob\_State\]. In our simulations, $M=10000$ with $20$ replications.

*Example 1:* Consider a problem $$\begin{aligned}
\max_{x \in X} f(x) = \text{Prob} \{ K(x)\}. \end{aligned}$$ where $K(x) =\{\xi \in \mathcal{K} \colon |\xi^{\intercal}x | \leq 1 \}$. Let $X$ and $\mathcal{K}$ be defined as $X =  \{ x \in \mathbb{R}^3 : A x \leq b \}$, $\mathcal{K} =  \{ \xi \in \mathbb{R}^3 : \|\xi\| \leq 1 \}$, and the parameters $A$ and $b$ are given as $$A= 
\begin{bmatrix}
    1 & 1 & 1  \\
    -1 & 0 & 0 \\
    -1 & 1 & 0 \\
     0 & -1 & 0 \\
      0 & -1 & 1 \\
      0 &0 & -1
\end{bmatrix}
, b=
\begin{bmatrix}
    3\\
    -0.1\\
    2\\
    -0.2\\
    1 \\
    -0.1
\end{bmatrix}.$$ In this example, we assume the random vector $\xi$ is uniformly distributed on $\mathcal{K}$.

The stochastic approximation schemes prescribed in Section IV are applied and Table 1 shows the comparison of m-ac-VSSA scheme with standard SA scheme. As seen in Table \[table1\] that the standard SA requires 10000 projection steps with 8.9e-3 empirical error. In contrast, when $a=7$ the empirical error reduces to 1.3e-3 and requires 5 projection steps for m-ac-VSSA scheme. Figure 1 gives a graphical comparison schemes in terms of trajectories.

     *Scheme*      *a*   *No of iter.*   *Emp. error*
  --------------- ----- --------------- --------------
                    4          9            4.4e-3
                    5          7            3.7e-3
   [m-ac-VSSA]{}    6          6            2.1e-3
                    7          5            1.3e-3
                    8          4            1.8e-3
     [ m-SA]{}               10000          8.9e-3

  : Comparison of schemes[]{data-label="table1"}

![Trajectory comparison of SA schemes: Empirical error vs number of iterations](Figures/traject.eps){width="\columnwidth"}

*Example 2:* Consider the previous example and now let $X$ be defined on the non-negative orthant as $X =  \{ x \in \mathbb{R}^n : \|x - x_0 \| \leq r \},$ where $x_0 = 1.2 \mathbf{e}^\intercal $ ($\mathbf{e}\triangleq [1,1,\cdots, 1]$) and $r=1$ for each $n$. In this example, we consider the m-ac-VSSA scheme with $a = 7$.

     *Scheme*      *n*   *Emp. error*
  --------------- ----- --------------
                    4       3.0e-4
                    5       2.0e-3
   [m-ac-VSSA]{}    6       2.2e-3
                    7       4.3e-3
                    8       6.2e-3

  : ac-VSSA scheme for different dimensions[]{data-label="table2"}

Table \[table2\] shows the performance of m-ac-VSSA scheme in different dimensions. The numerical results suggest that m-ac-VSSA scheme perform reasonably well in higher dimensions. It produces accurate solutions with significantly less computational effort (which is almost two-thousandth of the computational effort required by standard SA schemes). Moreover, it can be seen from Table \[table2\] that as the dimension gets higher, the increase in empirical error is modest.

Conclusion
==========

In this paper, a novel approach is developed to the solution of a subclass of chance constrained optimization. By exploiting results on the integration of homogeneous functions, the problem of maximization of probability of sets defined by a linear inequality is recast into a form amenable to the use of stochastic approximation algorithms. Examples show the effectiveness of the proposed approach.

Future work will consider extending the class of chance constrained problems that can be addressed by this approach with a focus on examining uncertainties with general log-concave distributions as well as regimes complicated by probabilistic constraints.

APPENDIX {#appendix .unnumbered}
========

(*Lemma \[lem2\]*) Since is a convex program, any solution $x^*$ of it satisfies $$h(x^*) \leq h(y), \qquad \forall y \in X.$$ It follows from the positivity of $f$ over $X$ that $$\frac{1}{f(x^*)} \leq \frac{1}{f(x)} \quad \forall y \in X \implies
f(x^*) \geq f(x), \quad \forall y \in X.$$ Consequently, $x^*$ is a global maximizer of .

(*Proposition \[prop-1\]*) First note that, since $x \in X$ is bounded, it implies that $0 < \epsilon \leq f(x)\leq 1$, and in turn, $1/f^2(x)$ is bounded and independent from expectation samples. Then, the gradient of $h(x)$ with respect to $x$ is given by $$\begin{aligned}
\nabla h(x) = \frac{-1}{f^2(x)} \nabla_{x} f(x) &= \frac{-1}{f^2(x)} \nabla_{x} \mathbb{E}[F(x,{\xi}_k)]\\
&=\frac{-1}{f^2(x)} \mathbb{E}[\nabla_{x} F(x,{\xi}_k)].\end{aligned}$$ where the last equality follows by the differentiability and Lipschitz continuity of $F(\cdot,\xi)$ with probability 1 [@shapiro2009]. First note that the function $F(x,\xi)$ is differentiable almost everywhere, that is, differentiable at every point outside a set of Lebesgue measure zero. Moreover, one can prove that the partial derivatives of $F(x,\xi)$ is bounded for all $x \in X$ which implies the function $F(x,\xi)$ is Lipschitz continuous on the set $X$. Let the bound on $f(x)$ be $U_f$. Since $F(x,\xi)$ is Lipschitz continuous with constant, say $L_{F}(\xi)$, we have $$\begin{aligned}
\| \nabla_{x} F(x_1,\xi_k) - \nabla_{x} F(x_2,\xi_k) \| \leq& L_{F}(\xi) \|x_1 - x_2 \|\\
\mathbb{E}[\| \nabla_{x} F(x_1,\xi_k) - \nabla_{x} F(x_2,\xi_k) \|] \leq& \mathbb{E}[L_{F}(\xi)] \|x_1 - x_2 \|\\
\| \mathbb{E}[\nabla_{x} F(x_1,\xi_k)] - \mathbb{E}[\nabla_{x} F(x_2,\xi_k)] \| \leq& \mathbb{E}[L_{F}(\xi)] \|x_1 - x_2 \|\end{aligned}$$ which implies $$\begin{aligned}
\| \nabla_{x} f(x_1) - \nabla_{x} f(x_2) \| \leq& C \ \mathbb{E}[L_{F}(\xi)] \|x_1 - x_2 \|\\
\| \nabla_{x} h(x_1) - \nabla_{x} h(x_2) \| \leq& \frac{1}{U^2_{f}} C \ \mathbb{E}[L_{F}(\xi)] \|x_1 - x_2 \|.\end{aligned}$$ Hence, letting $L_F \triangleq \mathbb{E}[L_{F}(\xi)]$ implies that $\nabla_{x} h(x)$ is Lipschitz continuous with Lipschitz constant $L=\frac{C}{U^2_{f}} L_F$.

(*Proposition* \[prop-2\]) $$\begin{aligned}
(1) \quad &\|x_{k+1} - x^*\|^2\\
& \leq \| x_k + \frac{\gamma_k}{\beta_k} (w_k + \nabla_x f(x_k)) - x^* -\frac{\gamma_k}{\beta_k} \nabla_x   f(x^*) \|^2 \\
&  = \|x_k-x^*\|^2 +\frac{2\gamma_k}{\beta_k}(\nabla_x f(x_k) + w_k)^T(x_k-x^*)\\ 
& + \frac{\gamma_k^2}{\beta_k^2}\|\nabla_x f(x_k) + w_k\|^2.\end{aligned}$$ From the convexity of $h(x)$ we have that $$\begin{aligned}
h(x^*) & \geq h(x_k) + \nabla_x h(x_k)^T(x^*-x_k) \\
& = h(x_k) - \frac{1}{f^2(x_k)}\nabla_x f(x_k)^T(x_k-x^*).\end{aligned}$$ This implies $$-\frac{1}{f^2(x_k)}\underbrace{\nabla_x f(x_k)^T(x_k-x^*)}_{\ \geq \ 0} \leq -\underbrace{(h(x_k)-h(x^*))}_{\ \geq \ 0} \leq 0.$$ If $1 \geq f^2(x) \geq \epsilon^2 \geq \beta^2_k$ for all $k$, this implies that $$\begin{aligned}
-\frac{1}{\beta_k^2}\nabla_x f(x_k)^T(x_k-x^*) &\leq -\frac{1}{\epsilon^2}\nabla_x f(x_k)^T(x_k-x^*)\\
&\leq  -\frac{1}{f^2(x_k)}\nabla_x f(x_k)^T(x_k-x^*)\\
& \leq -(h(x_k)-h(x^*)) \leq 0.\end{aligned}$$ As a consequence, we have the following expression: $$\begin{aligned}
&\|x_{k+1} - x^*\|^2\\
& \leq \|x_k-x^*\|^2 - \frac{2\gamma_k}{\beta_k} (-\nabla_x f(x_k))^T(x_k-x^*)\\
&-w_k^T(x_k-x^*)+ \frac{\gamma_k^2}{\beta_k^2}\|\nabla_x f(x_k) + w_k\|^2\\
& \leq \|x_k-x^*\|^2 - \frac{2\gamma_k}{\beta_k}(h(x_k)-h(x^*))-2w_k^T(x_k-x^*)\\
&+\frac{\gamma_k^2}{\beta_k^2}\|\nabla_x f(x_k) + w_k\|^2\\
& \leq \|x_k-x^*\|^2 - \frac{2\gamma_k}{\beta_k}(h(x_k)-h(x^*)) -w_k^T(x_k-x^*)\\
& +\frac{2\gamma_k^2}{\beta_k^2}\|\nabla_x f(x_k) - \nabla_x f(x^*)\|^2 + \frac{2\gamma_k^2}{\beta_k^2}\|\nabla_x f(x^*) +  w_k\|^2 \\
& \leq \|x_k-x^*\|^2 - \frac{2\gamma_k}{\beta_k}(h(x_k)-h(x^*)) -w_k^T(x_k-x^*)\\
& +\frac{2\gamma_k^2}{\beta_k^2}L^2 \|x_k - x^*\|^2 + \frac{2\gamma_k^2}{\beta_k^2}\|\nabla_x f(x^*) + w_k\|^2. \end{aligned}$$ Taking expectations conditional on the history $\mathcal{F}_k$, we obtain the following inequality. $$\begin{aligned}
&\mathbb{E}[\|x_{k+1} - x^*\|^2 \mid \mathcal{F}_k]\\
& \leq \|x_k-x^*\|^2 - \frac{2\gamma_k}{\beta_k}(h(x_k)-h(x^*))\\
& -\mathbb{E}[w_k\mid \mathcal{F}_k]^T(x_k-x^*)+
\frac{2\gamma_k^2}{\beta_k^2}L^2 \|x_k - x^*\|^2 \\
& + \frac{4\gamma_k^2}{\beta_k^2}\|\nabla_x f(x^*)\|+
\frac{4\gamma_k^2}{\beta_k^2}\mathbb{E}[\|w_k\|^2 \mid \mathcal{F}_k]\\
& \leq \|x_k-x^*\|^2 - (h(x_k)-h(x^*))\\
& + \frac{2\gamma_k^2}{\beta_k^2}L^2 \|x_k - x^*\|^2 +\frac{4\gamma_k^2}{\beta_k^2}\|\nabla_x f(x^*)\|+
\frac{4\gamma_k^2}{\beta_k^2} \nu^2. \end{aligned}$$ By the super-martingale convergence theorem and by the square summability of $\gamma_k/\beta_k$, we have that $ \{x_k-x^*\}$ is a convergent sequence and $\sum_{k=1}^{\infty} {\gamma_k}/{\beta_k} (h(x_k)-h(x^*)) < \infty$ in an a.s. sense. Since $\sum_{k=1}^{\infty} {\gamma_k}/{\beta_k} = \infty$, it follows that $\lim \inf_{k \to \infty} h(x_k) = h(x^*)$ in an a.s. sense. But $X$ is closed implying that it contains all the accumulation points of $\{x_k\}$. Since $h(x_k) \to h(x^*)$ along a subsequence in an a.s. sense, by continuity, it follows that $\{x_k\}$ has a subsequence converging to an $x^*$ in $X$ a.s. However, $\{x_k\}$ is a convergent sequence in an a.s. sense, implying that entire sequence converges to a point in $X^* \subseteq X$.

\(2) We note from the above proof that by taking unconditional expectations, the following holds: $$\begin{aligned}
&\mathbb{E}[\|x_{k+1} - x^*\|^2]\\
 & \leq \mathbb{E}[\|x_k-x^*\|^2] -
    \frac{2\gamma_k}{\beta_k}\mathbb{E}[(h(x_k)-h(x^*))] \\
    &+ \frac{2\gamma_k^2}{\beta_k^2}L^2 \mathbb{E}[\|x_k - x^*\|^2] + \frac{4\gamma_k^2}{\beta_k^2}\|\nabla_x f(x^*)\|+
\frac{4\gamma_k^2}{\beta_k^2} \nu^2 \\
\implies &  \frac{2\gamma_k}{\beta_k}\mathbb{E}[(h(x_k)-h(x^*))] \\
 & \leq \mathbb{E}[\|x_k-x^*\|^2 - \|x_{k+1}-x^*\|^2]\\ &+ \frac{4\gamma_k^2}{\beta_k^2}\|\nabla_x f(x^*)\|+
\frac{4\gamma_k^2}{\beta_k^2} \nu^2. \end{aligned}$$ It follows that by summing from $k=0$ to $K-1$, we have the following: $$\begin{aligned}
&\sum_{k=0}^{K-1}   \frac{2\gamma_k}{\beta_k}\mathbb{E}[(h(x_k)-h(x^*))]\\
  & \leq \mathbb{E}[\|x_0-x^*\|^2 - \|x_{K}-x^*\|^2]\\
  & + \sum_{k=0}^{K-1}\left(\frac{4\gamma_k^2}{\beta_k^2}\|\nabla_x f(x^*)\|+
\frac{4\gamma_k^2}{\beta_k^2} \nu^2\right). \end{aligned}$$ By convexity of $h$ and by defining $v_k = \frac{2\gamma_k}{\beta_k}$ and dividing both sides by $\sum_{k=0}^{K-1} v_k$, we have the following: $$\begin{aligned}
& \mathbb{E} [ h(\bar{x}_{k})-h(x^*)]\\
&  \leq
\frac{\mathbb{E}[\|x_0-x^*\|^2 ] + \sum_{k=0}^{K-1}\left( \frac{4 \gamma_k^2}{\beta_k^2}(M^2 +\nu^2) \right)}{\sum_{k=0}^{K-1} v_k}, \end{aligned}$$ where $\bar{x}_k = \frac{\sum_{j=0}^k v_j x_j}{\sum_{j=0}^k v_j}.$

[^1]: This research is partially funded by the NSF Grant CNS-1329422 (C. Lagoa) and CMMI-1246887 (CAREER, Shanbhag)

[^2]: U. V. Shanbhag is in the Department of Industrial and Manuf. Engineering, `udaybag@psu.edu`, while I. E. Bardakci and C. Lagoa are in the Department of Electrical Engineering, the Pennsylvania State University, University Park, PA 16802, USA `bardakci@psu.edu`; `Lagoa@engr.psu.edu`.
