remarkRemark hypothesisHypothesis claimClaim Stochastic optimization for
problems with upper-$\mathcal{C}^{2}$ objectivesJ. Wang, I. Aravena and C. G.
Petra

# An adaptive sampling sequential quadratic programming method for nonsmooth
stochastic optimization with upper-$\mathcal{C}^{2}$ objective ††thanks:
Submitted to the editors. LLNL release number LLNL-JRNL-846514. Prepared by
Lawrence Livermore National Laboratory (LLNL) under Contract DE-
AC52-07NA27344.

Jingyi Wang Center for Applied Scientific Computing, Lawrence Livermore
National Laboratory, Livermore, CA<EMAIL_ADDRESS><EMAIL_ADDRESS>Ignacio Aravena Computational Engineering Division, Lawrence Livermore
National Laboratory, Livermore, CA<EMAIL_ADDRESS>Cosmin G.
Petra22footnotemark: 2

###### Abstract

We propose an optimization algorithm that incorporates adaptive sampling for
stochastic nonsmooth nonconvex optimization problems with
upper-$\mathcal{C}^{2}$ objective functions. Upper-$\mathcal{C}^{2}$ is a
weakly concave property that exists naturally in many applications,
particularly certain classes of solutions to parametric optimization problems,
e.g., recourse of stochastic programming and projection into closed sets [37].
Our algorithm is a stochastic sequential quadratic programming (SQP) method
extended to nonsmooth problems with upper-$\mathcal{C}^{2}$ objectives and is
globally convergent in expectation with bounded algorithmic parameters. The
capabilities of our algorithm are demonstrated by solving a joint production,
pricing and shipment problem, as well as a realistic optimal power flow
problem as used in current power grid industry practice.

###### keywords:

optimization, stochastic, nonsmooth, nonconvex, sampling,
upper-$\mathcal{C}^{2}$

49M37, 65K05, 90C26, 90C30, 90C55 90C15, 62P30, 35Q93, 49Q10

##  1 Introduction

In this paper, we consider the class of nonsmooth nonconvex optimization
problems in the form of

(1) $\displaystyle\underset{\begin{subarray}{c}x\end{subarray}\in
C}{\text{minimize}}$ $\displaystyle f(x)+r(x),$ subject to $\displaystyle
c(x)=0,$

where the objective function $f:\mathbb{R}^{n}\to\mathbb{R}$ and equality
constraint function $c:\mathbb{R}^{n}\to\mathbb{R}^{m}$, are continuously
differentiable with Lipschitz gradients and $C\subset\mathbb{R}^{n}$ is a
convex compact set. The stochastic part of the objective is given as
$r(x)=\mathbb{E}_{\xi}\left[R(x,\xi)\right]$, where the expectation
$\mathbb{E}_{\xi}$ is the expected value of the function $R(x,\xi)$ with
respect to $\xi$. The random vector $\xi$ is defined over a probability space
$(\Omega,\mathcal{F},\mathbb{P})$, where $\Omega$ is the sample space,
$\mathcal{F}$ the $\sigma$-algebra generated by the subspace of $\Omega$ and
$\mathbb{P}$ a probability measure on $\mathcal{F}$. In this work, we focus on
$r:\mathbb{R}^{n}\to\mathbb{R}$ that is Lipschitz continuous and
upper-$\mathcal{C}^{2}$ (see monograph [37] and Section 2), but potentially
nonsmooth.

Upper-$\mathcal{C}^{2}$ functions are a subset of difference of convex (DC)
functions, and is equivalent to weakly concave functions on compact set in
$\mathbb{R}^{n}$ [11]. Any finite, concave function is upper-$\mathcal{C}^{2}$
[37, Theorem 10.33], as are all continuously differentiable functions [37,
Proposition 13.34]. Moreover, a squared distance function to a closed set,
which is the value function of a minimization problem, is
upper-$\mathcal{C}^{2}$ [37, Example 10.57]. The property exists in many
important two-stage (stochastic) programming problems with recourse of the
form of (1) [39, 4, 17], whose first-stage objective includes an
upper-$\mathcal{C}^{2}$ value function $r(\cdot)$ of the second-stage problem.
The application that motivated us to look into such concavity-related property
is the security-constrained alternating current optimal power flow (SCACOPF)
problem [9, 34, 33, 32, 31], which can be stated as a stochastic two-stage
problem. In this case, the nonsmooth part of the first-stage objective
$r(\cdot)$ becomes upper-$\mathcal{C}^{2}$ through regularization of the
second-stage problems, if it is not already so [43]. We add that
upper-$\mathcal{C}^{2}$ does not guarantee differentiability, or (lower)
regularity (see Section 2).

The most successful nonsmooth optimization methods include subgradient methods
[40], bundle methods [25, 18], and DC algorithms [1]. In particular, many
bundle methods have been shown to enjoy subsequent global convergence with
lower-$\mathcal{C}^{1}$ or upper-$\mathcal{C}^{1}$ objectives [21, 20, 38, 28,
16, 29]. For constrained problems, bundle methods typically incorporate
constraints into the objective through penalty or filter methods so that the
bundle approximation is constructed for the new objective [15, 13]. The
extension to stochastic optimization is challenging as the piecewise-linear
cutting planes are not exact in the stochastic setting. However, if the error
from the finite approximation to the stochastic objective is bounded, bundle
methods have been proven to converge to proximity of certain optimality points
with inexact information [30, 15, 29].

A significant body of literature has been dedicated to research of (nonsmooth)
stochastic optimization methods, where prominent algorithms include stochastic
gradient descent [6] and stochastic subgradient descent [14, 35, 26]. For
constrained nonsmooth stochastic problems, sequential quadratic programming
(SQP) has been applied to stochastic objective and deterministic, smooth
constraints, including both equality and inequality constraints [3]. DC
algorithms with sample average approximation has also been applied to
stochastic optimization with both theoretical and practical success [23]. The
smoothing of the objective is explored in [19], where a primal-dual
regularization of the objective combined with sample average approximation
(SAA) provides a solution problems with certain nonsmooth risk measures.

Adaptive sampling, which aims to provide sample size selection criteria, is an
active topic in recent years for projected gradient descent, augmented
Lagrangian, and SQP methods [7, 2]. The sample size is commonly controlled via
variance in the stochastic approximation of quantities such as the gradient to
improve efficiency of the algorithm. In the unconstrained setting, a well-
established ‘norm test’ [7, 8] exists. Its theory and application to smooth
objectives on convex feasible regions has been shown in [2]. To the best of
our knowledge, effort to extend adaptive sampling to stochastic nonsmooth
objectives with constraints has been limited. In [43], we described a
simplified bundle method, which bears similarity to SQP, for
upper-$\mathcal{C}^{2}$ objective with smooth constraints. The method uses
line search on the constraints and trust-region curvature search to achieve
convergence with practical success in solving SCACOPF [42]. In this paper, we
extend the effort to stochastic optimization problems. Since the curvature
search and serious step criterion are no longer available without exact
function values, the algorithm is now referred to as an extension of SQP.

This paper is organized as follows. In Section 2, we describe the
upper-$\mathcal{C}^{2}$ properties of $r(\cdot)$ and mathematical notations
necessary for the stochastic optimization algorithm. In Section 3, we propose
an algorithm for a simplified version of problem (1) where the equality
constraints $c(x)=0$ are neglected, making line search unnecessary. We provide
global convergence analysis for the algorithm with respect to expectation,
under assumptions typically made for stochastic and nonsmooth optimization. In
Section 4, we expand the algorithm to the full problem (1) based on a line
search algorithm the authors previously developed [43]. We show almost sure
subsequent convergence of the algorithm to Karush–Kuhn–Tucker (KKT) points
(points that satisfy KKT conditions) under proper assumptions. Implementation
details and numerical experiments are shown in Section 5 to illustrate both
the theoretical and practical capabilities of the proposed algorithm. Finally,
Section 6 concludes the paper and suggests directions for further research.

##  2 Background and notations

In this section, we provide the concepts and notations necessary for the
analysis in this paper. First, the lower regular subdifferential of a function
$r:\mathbb{R}^{n}\to\mathbb{R}$ at point $\bar{x}$, denoted as
$\hat{\partial}r(\bar{x})$, is defined by

(2)
$\displaystyle\hat{\partial}r(\bar{x})=\left\\{g\in\mathbb{R}^{n}|\liminf_{\begin{subarray}{c}x\to\bar{x}\\\
x\neq\bar{x}\end{subarray}}\frac{r(x)-r(\bar{x})-\langle
g,x-\bar{x}\rangle}{\left\lVert{x-\bar{x}}\right\rVert}\geq 0\right\\},$

where $\left\lVert{\cdot}\right\rVert$ is the 2-norm and $\langle\cdot\rangle$
is the inner product in $\mathbb{R}^{n}$ [37]. For a sequence $\\{x^{\nu}\\}$,
the notation $x^{\nu}\to x$ refers to $\left\lVert{x^{\nu}-x}\right\rVert\to
0$ as $\nu\to\infty$. If there exists a sequence $\\{x^{\nu}\\}$ such that
$x^{\nu}\xrightarrow[r]{}\bar{x}$ and $g^{\nu}\in\hat{\partial}r(x^{\nu})$
with $\\{g^{\nu}\\}$ converging $g^{\nu}\to\bar{g}\in\mathbb{R}^{n}$, then
$\bar{g}$ is a lower general subgradient of $r(\bar{x})$. The notation
$x^{\nu}\xrightarrow[r]{}\bar{x}$ is the f-attentive convergence where

(3) $\displaystyle
x^{\nu}\xrightarrow[r]{}\bar{x}\quad\ratio\Leftrightarrow\quad
x^{\nu}\to\bar{x}\quad\text{with}\quad r(x^{\nu})\to r(\bar{x}),$

and is trivially satisfied for $x^{\nu}\to\bar{x}$ when $r$ is Lipschitz (see
8(2), [37] for details). The lower general subdifferential at $\bar{x}$ is
denoted as $\partial r(\bar{x})$.

A Lipschitz function $r$ is lower regular (or subdifferentially regular) if
and only if $\partial r(\bar{x})=\hat{\partial}r(\bar{x})$ [37, Corollary
8.11]. Due to its importance, lower general subgradient is often simply called
general subgradient, while a lower regular function is called regular. On the
other hand, upper regular subdifferential [37, 24] is defined as

(4) $\displaystyle\hat{\partial}^{+}r(\bar{x})=$
$\displaystyle-\hat{\partial}(-r)(\bar{x})=\left\\{g\in\mathbb{R}^{n}|\limsup_{\begin{subarray}{c}x\to\bar{x}\\\
x\neq\bar{x}\end{subarray}}\frac{r(x)-r(\bar{x})-\langle
g,x-\bar{x}\rangle}{\left\lVert{x-\bar{x}}\right\rVert}\leq 0\right\\}.$

The upper general subdifferential is
$\partial^{+}r(\bar{x})=-\partial(-r)(\bar{x})$. A function $r$ is called
upper regular if $-r$ is lower regular.

In nonsmooth nonconvex optimization literature, both Clarke subdifferential
[10], denoted as $\bar{\partial}r{(\bar{x})}$ of $r$ at $\bar{x}$, and
$\partial r(\bar{x})$ have been widely adopted. If $r$ is lower regular, given
the convexity of $\hat{\partial}r(\bar{x})$, $\partial
r(\bar{x})=\bar{\partial}r{(\bar{x})}$ [37, Theorem 8.6, 8.49, 9.61]. The same
holds for an upper regular $r$ as well (for proof see [43]) and allows us to
use its Clarke subgradient and upper general subgradient interchangeably.
Therefore, in the remainder of the paper, we simply refer to Clarke
subgradient as subgradient. Clarke subdifferential is outer/upper-
semicontinuous, which is necessary in establishing subsequent convergence [37,
Proposition 6.6]. In addition, for a Lipschitz $r$, $\bar{\partial}r(\bar{x})$
is locally bounded [37, Theorem 9.13].

Next, we discuss lower-$\mathcal{C}^{k}$, introduced in [41, 37] with
equivalent definitions in [12]. A function $r:O\to\mathbb{R}$, where
$O\subset\mathbb{R}^{n}$ is open, is said to be lower-$\mathcal{C}^{k}$ on
$O$, if on some neighborhood $V$ of each $\bar{x}\in O$ there is a
representation

(5) $\displaystyle r(x)=\underset{\begin{subarray}{c}t\in
T\end{subarray}}{\text{max}}\ r_{t}(x),$

where $r_{t}:\mathbb{R}^{n}\to\mathbb{R}$ is of class $\mathcal{C}^{k}$ on $V$
and the index set $T$ is a compact space such that $r_{t}$ and all of its
partial derivatives through order $k$ are continuous on $(t,x)\in T\times V$.
A function is upper-$\mathcal{C}^{k}$ if we replace the $max$ with $min$ in
(5). Let $T\subset\mathbb{R}^{p}$ be compact, the function $r$ is
upper-$\mathcal{C}^{2}$ if it can be expressed as

(6) $\displaystyle r(x)=\underset{\begin{subarray}{c}t\in
T\end{subarray}}{\text{min}}\ p(t,x)$

for all $x\in O$, such that
$p(\cdot,\cdot):\mathbb{R}^{p}\times\mathbb{R}^{n}\to\mathbb{R}$ and its
first- and second-order partial derivatives in $x$ are continuous on $(t,x)$.
Clearly, upper-/lower-$\mathcal{C}^{k}$ imply upper-/lower-regularity.

Further, lower- and upper-type properties have equivalent definitions based on
function and subgradient values. The finite-valued function $r$ is
lower-$\mathcal{C}^{2}$ on $O\subset\mathbb{R}^{n}$ if and only if there
exists $\rho>0$ such that
$r(\cdot)+\frac{1}{2}\rho\left\lVert{\cdot}\right\rVert^{2}$ is convex. Notice
that this definition is already given on $O$ with a uniform $\rho$. Through
simple arithmetic and convexity with subgradients, if $r$ is
lower-$\mathcal{C}^{2}$, for all $x\in O$,

(7) $\displaystyle r(x)-r(\bar{x})-\langle
g,x-\bar{x}\rangle+\frac{\rho}{2}\left\lVert{x-\bar{x}}\right\rVert^{2}\geq
0,$

where $g\in\bar{\partial}r(\bar{x})$. By the symmetry property of Clarke
subgradient [10, Proposition 2.3.1], if $g\in\bar{\partial}r(\bar{x})$, then
$-g\in\bar{\partial}(-r)(\bar{x})$. Hence, if $r$ is upper-$\mathcal{C}^{2}$,
e.g., $r(x)=-|x|,x\in\mathbb{R}$, by definition, $-r$ is
lower-$\mathcal{C}^{2}$. Thus, we have

(8) $\displaystyle r(x)-r(\bar{x})-\langle
g,x-\bar{x}\rangle\leq\frac{\rho}{2}\left\lVert{x-\bar{x}}\right\rVert^{2},$

where $g\in\bar{\partial}r(\bar{x})$. We refer to (8) as the _upper-
$\mathcal{C}^{2}$ inequality_.

Without loss of generality, (1) is simplified to

(9) $\displaystyle\underset{\begin{subarray}{c}x\in
C\end{subarray}}{\text{minimize}}$ $\displaystyle
r(x)=\mathbb{E}\left[R(x,\xi)\right],$ subject to $\displaystyle c(x)=0.$

There are multiple optimality conditions used for nonsmooth constrained
problems, e.g., stationary point, KKT point, critical point. In this paper, we
assume linear independent constraint qualification (LICQ, Section 4) at local
minima and accumulation points of the proposed algorithms for (9), due to
presence of both equality and inequality constraints. This enables us to
establish the necessary optimality condition in terms of subgradient [10,
Section 6.4]. For problem (9), at a local minimum $\bar{x}$, there exists
$\bar{\lambda}\in\mathbb{R}^{m}$ such that

(10) $\displaystyle 0\in\bar{\partial}r(\bar{x})+\nabla
c(\bar{x})\bar{\lambda}+\partial i_{C}(\bar{x})$ , $\displaystyle
c_{j}(\bar{x})=0,j=1,\dots,m,\ \bar{x}\in C$ ,

where the matrix $\nabla c(\bar{x})$ is of dimension $n\times m$, and
$\partial i_{C}(\cdot)$ is the subdifferential of the indicator function
$i_{C}(\cdot)$ defined as

(11) $\displaystyle i_{C}(x)=\begin{cases}0,&\text{if}\ x\in C,\\\
+\infty,&\text{otherwise.}\end{cases}$

Note that because $C$ is convex, so is $i_{C}(\cdot)$.

##  3 Stochastic optimization with convex set constraint

In this section, we focus on a simplified problem

(12) $\displaystyle\underset{\begin{subarray}{c}x\in
C\end{subarray}}{\text{minimize}}$ $\displaystyle
r(x)=\mathbb{E}\left[R(x,\xi)\right],$

which permits a simpler algorithm as well. Motivated by the discussion in
Section 2, the assumptions are formalized below.

######  Assumption .

The Lipschitz continuous objective $r(\cdot)$ in (12) is
upper-$\mathcal{C}^{2}$.

In particular, inequality (8) is satisfied.

######  Assumption .

The feasible region $C$ is convex and compact.

Here, we opt for a compact $C$ instead of a closed $C$ with bounded iterates
$\\{x_{k}\\}$ as an assumption for ease of presentation. A bounded $C$ would
ensure bounded $\\{x_{k}\\}$ and given Assumption 3 guarantee bounded $r(x)$
as well. Therefore, there exists $r_{\min}$ such that $r_{\min}\leq
r(x),\forall x\in C$. It is assumed that $x\in C$ can be enforced efficiently
in the optimization subproblems, e.g., through projection onto $C$.

###  3.1 Algorithm description

We propose an iterative algorithm with locally approximated convex quadratic
objective at each iteration that bears similarity to SQP while the convex set
$C$ is maintained as it is. At iteration $k$ and its iterate $x_{k}$, the
approximation model with a true subgradient $g_{k}\in\bar{\partial}r(x_{k})$
is

(13)
$\displaystyle\phi_{k}(x)=r(x_{k})+g_{k}^{T}(x-x_{k})+\frac{1}{2}\alpha_{k}\left\lVert{x-x_{k}}\right\rVert^{2},$

where $\alpha_{k}>0$ is a scalar quadratic coefficient. In the stochastic
setting, however, we rely on a stochastic subgradient estimate $\bar{g}_{k}$
of $g_{k}\in\bar{\partial}r(x_{k})$ and the local model
$\bar{\phi}_{k}(\cdot)$ is

(14)
$\displaystyle\bar{\phi}_{k}(x)=\bar{r}(x_{k})+\bar{g}_{k}^{T}(x-x_{k})+\frac{1}{2}\alpha_{k}\left\lVert{x-x_{k}}\right\rVert^{2}.$

The stochastic estimate of function value $\bar{r}(x_{k})$ does not affect the
optimization subproblem and its solution. Hence, we hereby use it
interchangeably with $r(x_{k})$. Denoting $d=x-x_{k}$, $\bar{\phi}_{k}(x)$ and
$\phi_{k}(x)$ can be rewritten as $\bar{\Phi}_{k}(d)$ and $\Phi_{k}(d)$,
respectively, such that

(15) $\displaystyle\bar{\Phi}_{k}(d)$
$\displaystyle=r(x_{k})+\bar{g}_{k}^{T}d+\frac{1}{2}\alpha_{k}\left\lVert
d\right\rVert^{2},$ $\displaystyle\Phi_{k}(d)$
$\displaystyle=r(x_{k})+g_{k}^{T}d+\frac{1}{2}\alpha_{k}\left\lVert{d}\right\rVert^{2}.$

The subproblem to be solved at iteration $k$ and $x_{k}$ is thus

(16) $\displaystyle\underset{\begin{subarray}{c}x_{k}+d\in
C\end{subarray}}{\text{minimize}}$ $\displaystyle\bar{\Phi}_{k}(d).$

Meanwhile, the corresponding subproblem with true subgradient is

(17) $\displaystyle\underset{\begin{subarray}{c}x_{k}+d\in
C\end{subarray}}{\text{minimize}}$ $\displaystyle\Phi_{k}(d).$

Let $\bar{d}_{k}$ be the solution to (16) and $d_{k}$ the solution to (17).
The predicted change on the objective is defined as

(18) $\displaystyle\bar{\delta}_{k}=$
$\displaystyle\bar{\Phi}_{k}(0)-\bar{\Phi}_{k}(\bar{d}_{k})=-\bar{g}_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}.$

Similarly,
$\delta_{k}=-g_{k}^{T}d_{k}-\frac{1}{2}\alpha_{k}\left\lVert{d_{k}}\right\rVert^{2}$.
The choice of $\alpha_{k}$ is independent of the stochastic subgradient. The
trust-region update rule for $\alpha_{k}$ in [43] unfortunately is no longer
valid since the true values $r(x_{k})$ and $r(x_{k}+\bar{d}_{k})$ are not
available. Consequently, we rely on knowledge of $r(\cdot)$ such as its
Lipschitz constant to select $\alpha_{k}$ such that $\alpha_{k}$ is large
enough to ensure convergence in expectation, in line with stochastic
optimization literature [3].

The first-order optimality conditions of subproblem (16) are

(19) $\displaystyle\bar{g}_{k}+\alpha_{k}\bar{d}_{k}+\bar{v}_{k}=0,$
$\displaystyle x_{k}+\bar{d}_{k}\in C,\bar{v}_{k}\in\partial
i_{C}(x_{k}+\bar{d}_{k}).$

The first-order optimality conditions of subproblem (17) are

(20) $\displaystyle g_{k}+\alpha_{k}d_{k}+v_{k}=0,$ $\displaystyle
x_{k}+d_{k}\in C,v_{k}\in\partial i_{C}(x_{k}+d_{k}).$

Since $C$ is convex, so is $i_{C}(\cdot)$. We can now state our adaptive
sampling conditions on expectation and variance of the subgradient estimate.

######  Assumption .

For all iterations $k\in\mathbb{N}$, the stochastic subgradient approximation
$\bar{g}_{k}$ is an unbiased estimate of $g_{k}\in\bar{\partial}r(x_{k})$,
i.e., $\mathbb{E}_{k}[\bar{g}_{k}]=g_{k}$. Furthermore, $\bar{g}_{k}$
satisfies

(21)
$\displaystyle\mathbb{E}_{k}\left[\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert^{2}\right]\leq\eta\alpha_{k}\left\lVert{d_{k}}\right\rVert^{2},$

where $\eta>0$ is a parameter of the algorithm. Here, $\mathbb{E}_{k}$ denotes
the expectation over $\xi$ conditioned on iterate $x_{k}$ at the $k$-th
iteration, generated by the random vectors $\\{\xi_{t}\\}_{t=1}^{k}$.

######  Remark 3.1.

Assumption 3.1 reduces to the well-known ‘norm’ condition for unconstrained
optimization problems. Similar conditions on constrained optimization can be
found in [2].

The proposed SQP with adaptive sampling algorithm is presented in Algorithm 1.
The sample set at iteration $k$ is denoted by $S_{k}$. We note that the
adaptive sampling test in step $5$ based directly on (21) is not practical as
$g_{k}$ is unknown. A practical implementation of the sampling size selection
is given in Section 5. Further, while we require $\\{\alpha_{k}\\}$ to be
monotonically non-decreasing, in step $7$ for a simpler analysis, it is
possible to relax this requirement as long as
$\rho\leq\alpha_{k}\leq\eta_{\alpha}\rho$ is maintained. Additionally, we
leave the exact update rule for $\alpha_{k}$ to be specified for each
application.

Algorithm 1 Upper-$\mathcal{C}^{2}$ stochastic SQP with adaptive sampling

1: Choose scalars $0<\eta\leq 1$ and $\eta_{\alpha}>1$. Initialize $x_{0}$,
$\rho\leq\alpha_{0}\leq\eta_{\alpha}\rho$ and $k=0$. Choose initial sampling
set $\\{S_{0}\\}$.

2: for $k=0,1,2,...$ do

3: Evaluate the function value $\bar{r}(x_{k})$ and stochastic subgradient
estimate $\bar{g}_{k}$.

4: Form the objective $\bar{\Phi}_{k}$ in (15) and solve subproblem (16) to
obtain $\bar{d}_{k}$.

5: Compute $\bar{\delta}_{k}$ in (18). Select and test to ensure the samples
$S_{k}$ satisfies Assumption 3.1.

6: Take the step $x_{k+1}=x_{k}+\bar{d}_{k}$.

7: Call the chosen $\alpha_{k}$ update rules to obtain
$\alpha_{k}\leq\alpha_{k+1}\leq\eta_{\alpha}\rho$.

###  3.2 Convergence analysis

In this section, we assume Assumption 3, 3 and 3.1 are valid. The choice of
$\alpha_{k}$ in step 7 of Algorithm 1 leads to the following Lemma.

######  Lemma 3.2.

The iterate $x_{k+1}$ from Algorithm 1 satisfies
$r(x_{k})-r(x_{k+1})\geq\Phi_{k}(0)-\Phi_{k}(\bar{d}_{k})$.

######  Proof 3.3.

From the upper-$\mathcal{C}^{2}$ inequality (8), we have

(22) $\displaystyle
r(x_{k}+d)-r(x_{k})-g_{k}^{T}d\leq\frac{\rho}{2}\left\lVert{d}\right\rVert^{2},$

for $g_{k}\in\bar{\partial}r(x_{k})$, $\rho>0$ and $x\in C$. Since
$\alpha_{k}$ is monotonically non-decreasing and $\alpha_{0}>\rho$, we have

(23) $\displaystyle\alpha_{k}>\rho,\ \text{for all}\ k\in\mathbb{N}.$

The inequalities (22) and (23) imply that at $d=\bar{d}_{k}$

(24) $\displaystyle r(x_{k})-r(x_{k}+\bar{d}_{k})\geq$ $\displaystyle-
g_{k}^{T}\bar{d}_{k}-\frac{1}{2}\rho\left\lVert{\bar{d}_{k}}\right\rVert^{2}$
$\displaystyle>$ $\displaystyle-
g_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}=\Phi_{k}(0)-\Phi_{k}(\bar{d}_{k}).$

The following Lemma holds for the solution $d_{k}$ to (17).

######  Lemma 3.4.

For all $k\in\mathbb{N}$, it follows that

(25) $\displaystyle
r(x_{k})-r(x_{k}+d_{k})\geq\frac{1}{2}\alpha_{k}\left\lVert{d_{k}}\right\rVert^{2}.$

######  Proof 3.5.

As discussed in Lemma 3.2, $\alpha_{k}>\rho$. As shown in (24), we have

(26) $\displaystyle r(x_{k})-r(x_{k}+d_{k})>$ $\displaystyle-
g_{k}^{T}d_{k}-\frac{1}{2}\alpha_{k}\left\lVert{d_{k}}\right\rVert^{2}.$

Rearranging the first equation in optimality conditions (20), we have

(27) $g_{k}+\alpha_{k}d_{k}=-v_{k}.$

By taking the inner product with $-d_{k}$ and using the convexity of
$i_{C}(\cdot)$, we obtain

(28) $\displaystyle-
g_{k}^{T}d_{k}-\alpha_{k}\left\lVert{d_{k}}\right\rVert^{2}$
$\displaystyle=v_{k}^{T}d_{k}$
$\displaystyle=i_{C}(x_{k})-i_{C}(x_{k}+d_{k})-v_{k}^{T}(-d_{k})\geq 0.$

Adding $\frac{1}{2}\alpha_{k}\left\lVert{d_{k}}\right\rVert^{2}$ to both sides
of (28) gives us

(29) $\displaystyle-
g_{k}^{T}d_{k}-\frac{1}{2}\alpha_{k}\left\lVert{d_{k}}\right\rVert^{2}$
$\displaystyle\geq\frac{1}{2}\alpha_{k}\left\lVert{d_{k}}\right\rVert^{2}.$

Combining (26) and (29) finishes the proof.

######  Remark 3.6.

We recognize that the constant $\rho$ might not be known. Therefore, in
practical applications, an estimate of $\rho$ is often needed for the choice
of $\alpha_{k}$ such that $\alpha_{k}>\rho$ can be maintained.

An immediate result of Assumption 3.1 is given in the next Lemma.

######  Lemma 3.7.

For all $k\in\mathbb{N}$ of Algorithm 1,
$\mathbb{E}_{k}\left[\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert\right]\leq\sqrt{\eta\alpha_{k}}\left\lVert{d_{k}}\right\rVert$.

######  Proof 3.8.

From Assumption 3.1 and Jensen’s inequality (with square function), we have

(30)
$\displaystyle\mathbb{E}_{k}[\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert]\leq\left(\mathbb{E}_{k}\left[\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert^{2}\right]\right)^{\frac{1}{2}}\leq\sqrt{\eta\alpha_{k}}\left\lVert{d_{k}}\right\rVert.$

Assumption 3.1 leads to the bounds on the variance of the stochastic search
directions.

######  Lemma 3.9.

For all $k\in\mathbb{N}$ of Algorithm 1,
$\mathbb{E}_{k}[\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert]\leq\sqrt{\frac{\eta}{\alpha_{k}}}\left\lVert{d_{k}}\right\rVert$,
and
$\mathbb{E}_{k}[\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert^{2}]\leq\frac{\eta}{\alpha_{k}}\left\lVert{d_{k}}\right\rVert^{2}$.

######  Proof 3.10.

From the definition, $d_{k}$ and $\bar{d}_{k}$ are the solutions to (17) and
(16), respectively. Subtracting the optimality conditions (20) from (19) leads
to

(31)
$\displaystyle\bar{g}_{k}-g_{k}+\alpha_{k}(\bar{d}_{k}-d_{k})+\bar{v}_{k}-v_{k}=0.$

Multiply both sides of (32) by $\bar{d}_{k}-d_{k}$ and we obtain

(32)
$\displaystyle(\bar{g}_{k}-g_{k})^{T}(\bar{d}_{k}-d_{k})+\alpha_{k}\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert^{2}+(\bar{v}_{k}-v_{k})^{T}(\bar{d}_{k}-d_{k})=0,$

where $\bar{v}_{k}\in\partial i_{C}(x_{k}+\bar{d}_{k})$ and $v_{k}\in\partial
i_{C}(x_{k}+d_{k})$. Given that $x_{k}+d_{k}\in C$ and $x_{k}+\bar{d}_{k}\in
C$, the convexity of $i_{C}(\cdot)$ implies

(33) $\displaystyle\left(\bar{v}_{k}-v_{k}\right)^{T}(\bar{d}_{k}-d_{k})\geq
0.$

Applying (33) to (32) leads to

(34) $\displaystyle\alpha_{k}\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert^{2}$
$\displaystyle\leq-(\bar{g}_{k}-g_{k})^{T}(\bar{d}_{k}-d_{k})\leq\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert.$

Notice that $(\bar{g}_{k}-g_{k})^{T}(\bar{d}_{k}-d_{k})\leq 0$ from (34) and

(35)
$\displaystyle\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert\leq\frac{1}{\alpha_{k}}\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert.$

Taking $\mathbb{E}_{k}$ on (35) as well as (34) and applying Lemma 3.7
completes the proof.

The expectation of change in the objective $r(\cdot)$ observes the following
Lemma.

######  Lemma 3.11.

The step $x_{k+1}=x_{k}+\bar{d}_{k}$ satisfies
$\mathbb{E}_{k}[r(x_{k})-r(x_{k+1})]\geq\zeta_{k}\left\lVert{d_{k}}\right\rVert^{2}$,
where
$\zeta_{k}=\frac{1}{2}\alpha_{k}-\left(\sqrt{\eta\alpha_{k}}+\eta\right)$.

######  Proof 3.12.

From Lemma 3.2 and (24), we have

(36) $\displaystyle r(x_{k})-r(x_{k+1})\geq$ $\displaystyle-
g_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}.$

Similar to the proof of Lemma 3.4, by the optimality conditions (19), we have

(37) $\bar{g}_{k}+\alpha_{k}\bar{d}_{k}=-\bar{v}_{k},\
\bar{v}_{k}\in\bar{\partial}i_{C}(x_{k}+\bar{d}_{k}).$

Taking the inner product with $-\bar{d}_{k}$ in (37) and using the convexity
of $i_{C}(\cdot)$, we have

(38)
$\displaystyle-\bar{g}_{k}^{T}\bar{d}_{k}-\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}$
$\displaystyle=\bar{v}_{k}^{T}\bar{d}_{k}=i_{C}(x_{k})-i_{C}(x_{k}+\bar{d}_{k})-\bar{v}_{k}^{T}(-\bar{d}_{k})\geq
0.$

Thus,

(39)
$\displaystyle-\bar{g}_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}\geq\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}.$

The right-hand side of (36) can be rewritten based on (39) as

(40) $\displaystyle-
g_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}$
$\displaystyle=-g_{k}^{T}\bar{d}_{k}+\bar{g}_{k}^{T}\bar{d}_{k}-\bar{g}_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}$
$\displaystyle\geq\left(\bar{g}_{k}-g_{k}\right)^{T}d_{k}+\left(\bar{g}_{k}-g_{k}\right)^{T}\left(\bar{d}_{k}-d_{k}\right)+\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}$
$\displaystyle\geq\left(\bar{g}_{k}-g_{k}\right)^{T}d_{k}-\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert+\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}.$

The term $\left\lVert{\bar{d}_{k}}\right\rVert^{2}$ can be rewritten as

(41) $\displaystyle\left\lVert{\bar{d}_{k}}\right\rVert^{2}=$
$\displaystyle\left\lVert{\bar{d}_{k}-d_{k}+d_{k}}\right\rVert^{2}=\left\lVert{d_{k}}\right\rVert^{2}+\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert^{2}+2\left[\bar{d}_{k}-d_{k}\right]^{T}d_{k}$
$\displaystyle\geq$
$\displaystyle\left\lVert{d_{k}}\right\rVert^{2}+\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert^{2}-2\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert\left\lVert{d_{k}}\right\rVert.$

Taking the expectation $\mathbb{E}_{k}$ on (41), we have from Lemma 3.9

(42)
$\displaystyle\mathbb{E}_{k}[\left\lVert{\bar{d}_{k}}\right\rVert^{2}]\geq$
$\displaystyle\left\lVert{d_{k}}\right\rVert^{2}+\mathbb{E}_{k}\left[\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert^{2}\right]-2\mathbb{E}_{k}\left[\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert\right]\left\lVert{d_{k}}\right\rVert$
$\displaystyle\geq$
$\displaystyle\left\lVert{d_{k}}\right\rVert^{2}-2\sqrt{\frac{\eta}{\alpha_{k}}}\left\lVert{d_{k}}\right\rVert^{2}.$

By Lemma 3.7 and Lemma 3.9, the expectation $\mathbb{E}_{k}$ of (40) is

(43)
$\displaystyle\mathbb{E}_{k}\left[-g_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}\right]\geq$
$\displaystyle-\eta\left\lVert{d_{k}}\right\rVert^{2}+\mathbb{E}_{k}\left[\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}\right].$

Applying (42) to (43), we have

(44)
$\displaystyle\mathbb{E}_{k}\left[-g_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}\right]$
$\displaystyle\geq-\eta\left\lVert{d_{k}}\right\rVert^{2}+\frac{1}{2}\alpha_{k}\left\lVert{d_{k}}\right\rVert^{2}-\sqrt{\eta\alpha_{k}}\left\lVert{d_{k}}\right\rVert^{2}.$

Let $\zeta_{k}=\frac{1}{2}\alpha_{k}-\left(\sqrt{\eta\alpha_{k}}+\eta\right)$,
then

(45)
$\displaystyle\mathbb{E}_{k}\left[-g_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}\right]\geq\zeta_{k}\left\lVert{d_{k}}\right\rVert^{2}.$

From (36) and (45), we have

(46)
$\displaystyle\mathbb{E}_{k}[r(x_{k})-r(x_{k+1})]\geq\zeta_{k}\left\lVert{d_{k}}\right\rVert^{2}.$

We can prove the convergence of the expected reduction of the objective in the
following theorem.

######  Theorem 3.13.

Let $\eta,\alpha_{k},\eta_{\alpha}$ be chosen such that $\zeta_{k}>0$ for all
$k\in\mathbb{N}$, then

(47)
$\displaystyle\lim_{k\to\infty}\mathbb{E}\left[\sum_{i=0}^{k-1}\left\lVert{d_{i}}\right\rVert^{2}\right]<\infty.$

It follows that
$\lim_{k\to\infty}\mathbb{E}\left[\left\lVert{d_{k}}\right\rVert\right]=0$ and
$\lim_{k\to\infty}\mathbb{E}\left[\left\lVert{g_{k}+v_{k}}\right\rVert\right]=0$.

######  Proof 3.14.

Taking the total expectation of (46) in Lemma 3.11, for all $k\in\mathbb{N}$,

(48)
$\displaystyle\mathbb{E}[r(x_{k+1})-r(x_{k})]\leq-\mathbb{E}[\zeta_{k}\left\lVert{d_{k}}\right\rVert^{2}].$

Summing up $j=0,1,\dots,k-1$ of $r(x_{j+1})-r(x_{j})$ and taking the total
expectation, we have

(49) $\displaystyle-\infty<r_{\min}-r(x_{0})\leq$
$\displaystyle\mathbb{E}\left[r(x_{k})-r(x_{0})\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{i=0}^{k-1}\left(r(x_{i+1})-r(x_{i})\right)\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left[-\sum_{i=0}^{k-1}\zeta_{i}\left\lVert{d_{i}}\right\rVert^{2}\right]$

Choose $\eta,\alpha_{k},\eta_{\alpha}$ so that $\zeta_{k}>0$. Since
$\rho\leq\alpha_{k}\leq\eta_{\alpha}\rho$ and $\alpha_{k}$ is monotonically
non-decreasing and bounded, there exists $\zeta_{l}>0$ such that
$\zeta_{k}\geq\zeta_{l}$ for all $k\in\mathbb{N}$. Thus,

(50)
$\displaystyle-\infty<\mathbb{E}\left[-\sum_{i=0}^{k-1}\zeta_{i}\left\lVert{d_{i}}\right\rVert^{2}\right]\leq-\zeta_{l}\mathbb{E}\left[\sum_{i=0}^{k-1}\left\lVert{d_{i}}\right\rVert^{2}\right]=-\zeta_{l}\sum_{i=0}^{k-1}\mathbb{E}[\left\lVert{d_{i}}\right\rVert^{2}].$

Let $k\to\infty$, the first part of the Theorem is proven. Further,
$\lim_{k\to\infty}\mathbb{E}[\left\lVert{d_{k}}\right\rVert^{2}]=0$. By
Jensen’s inequality,
$\lim_{k\to\infty}\mathbb{E}[\left\lVert{d_{k}}\right\rVert]=0$. By first
equation in (20), the last result is proved.

We remark that Theorem 3.13 does not guarantee convergence of $\\{x_{k}\\}$.
However, it is possible to further show subsequence convergence of
accumulation points of $\\{x_{k}\\}$.

######  Theorem 3.15.

Under the assumptions in Theorem 3.13, every accumulation point of the
sequence $\\{x_{k}\\}$ produced by Algorithm 1 is a KKT point of (12) with
probability 1.

######  Proof 3.16.

We first show that $\lim_{k\to\infty}d_{k}=0$ with probability 1. From the
proof of Theorem 3.13 and (49), since $\zeta_{i}$ is finite, we have

(51)
$\displaystyle\sum_{k=0}^{\infty}\mathbb{E}[\left\lVert{d_{k}}\right\rVert^{2}]=\lim_{p\to\infty}\sum_{k=0}^{p}\mathbb{E}[\left\lVert{d_{k}}\right\rVert^{2}]<\infty.$

Now we proceed by contradiction. Suppose there exists $\epsilon>0$ and $a>0$
such that

(52)
$\displaystyle\mathbb{P}(\limsup_{k\to\infty}\left\lVert{d_{k}}\right\rVert\geq\epsilon)\geq
a.$

By Chebyshev’s inequality, we have
$\mathbb{P}(\left\lVert{d_{k}}\right\rVert\geq\epsilon)\leq\frac{\mathbb{E}[\left\lVert{d_{k}}\right\rVert^{2}]}{\epsilon^{2}}$.
Since $\mathbb{E}[\left\lVert{d_{k}}\right\rVert^{2}]$ is finitely summable,
there exists $N>0$ such that
$\sum_{k=N}^{\infty}\mathbb{P}(\left\lVert{d_{k}}\right\rVert\geq\epsilon)\leq\sum_{k=N}^{\infty}\frac{\mathbb{E}[\left\lVert{d_{k}}\right\rVert^{2}]}{\epsilon^{2}}<a$.
Therefore,

(53)
$\displaystyle\mathbb{P}\left(\limsup_{k\to\infty}\left\lVert{d_{k}}\right\rVert\geq\epsilon\right)=\mathbb{P}\left(\limsup_{k\to\infty:k\geq
N}\left\lVert{d_{k}}\right\rVert\geq\epsilon\right)\leq\sum_{k=N}^{\infty}\mathbb{P}(\left\lVert{d_{k}}\right\rVert\geq\epsilon)<a.$

This is a contradiction against (52). Hence, we have with probability 1
$\lim_{k\to\infty}d_{k}=0$. Let $\bar{x}$ be an accumulation point of
$\\{x_{k}\\}$. Then, passing on to a subsequence if necessary, we can assume
$\lim_{k\to\infty}x_{k}=\bar{x}$ where $\bar{x}\in C$. Since
$g_{k}\in\bar{\partial}r(x_{k})$ is bounded, there exists at least one
accumulation point for $\\{g_{k}\\}$ as well. Passing on to a subsequence if
necessary, we have $g_{k}\to\bar{g}$ . By the outer semicontinuity of Clark
subdifferential, we have $\bar{g}\in\bar{\partial}r(\bar{x})$. Then, the
quadratic subproblem (17) leads to the equations in (20). With probability 1,
$\lim_{k\to\infty}v_{k}=-\bar{g}$. Given that $v_{k}\in\partial i_{C}(x_{k})$,
the outer semicontinuity of subdifferential of $i_{C}$ leads to
$\lim_{k\to\infty}v_{k}\in\partial i_{C}(\bar{x})$ with probability 1.
Therefore,

(54) $\displaystyle 0\in\bar{\partial}r(\bar{x})+\partial i_{C}(\bar{x}),$

and $\bar{x}$ is a KKT point with probability 1.

Similar convergence results can be found in [22, 5]. Theorems 3.13 and 3.15
can also be partially obtained by the super-martingale convergence theorem
[36] in the form of the following Lemma.

######  Lemma 3.17.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and
$\mathcal{F}_{k-1}\subset\mathcal{F}_{k}$ a sequence of sub-$\sigma$-algebra
of $\mathcal{F}$. Let $\\{y_{k}\\}$,$\\{u_{k}\\}$,$\\{a_{k}\\}$,$\\{b_{k}\\}$
be sequences of nonnegative integrable random variables under
$\mathcal{F}_{k}$, such that for all $k\in\mathbb{N}$,
$\mathbb{E}[y_{k+1}|\mathcal{F}_{k}]\leq(1+a_{k})y_{k}-u_{k}+b_{k}$,
$\sum_{k=1}^{\infty}a_{k}<+\infty$, and $\sum_{k=1}^{\infty}b_{k}<+\infty$
almost surely. Then with probability 1, $\\{y_{k}\\}$ converges and
$\sum_{k=1}^{\infty}u_{k}<+\infty$.

In order to apply Lemma 3.17, we may consider $\mathcal{F}_{k}$ the
$\sigma$-algebra generated by random vectors $\\{\xi_{t}\\}_{t=1}^{k}$ and
apply the conditional expectation $\mathbb{E}_{k}$.

##  4 Stochastic optimization with equality constraint

We now turn to the full problem (9). In addition to Assumptions 3 and 3, the
constraints are assumed to be continuously differentiable with Lipschitz
continuous gradient in this section.

######  Assumption 4.1.

The function $c(\cdot)$ is continuously differentiable with Lipschitz
continuous gradient. This means that there exists a constant $H\geq 0$ such
that

(55) $\displaystyle|c_{j}(x^{\prime})-c_{j}(x)-\nabla
c_{j}(x)^{T}(x^{\prime}-x)|\leq$
$\displaystyle\frac{H}{2}\left\lVert{x-x^{\prime}}\right\rVert^{2},$

for all $x,x^{\prime}\in C$ and all $j\in\\{1,2,\ldots,m\\}$ [27].

###  4.1 Algorithm description

The algorithm remains an iterative method with locally approximated convex
quadratic objective. At iteration $k$ and its iterate $x_{k}$, the true model
$\phi_{k}(\cdot)$ is the same as given in (13) while the stochastic model
$\bar{\phi}_{k}(\cdot)$ is (14). Denoting $d=x-x_{k}$, $\phi_{k}(x)$ can be
rewritten as $\Phi_{k}(d)$, while its stochastic counterpart is
$\bar{\Phi}_{k}(d)$ in (15). Furthermore, the constraint $c(x)=0$ in (9) is
linearized. The subproblem to be solved at iteration $k$ is

(56) $\displaystyle\underset{\begin{subarray}{c}x_{k}+d\in
C\end{subarray}}{\text{minimize}}$ $\displaystyle
r(x_{k})+\bar{g}_{k}^{T}d+\frac{1}{2}\alpha_{k}\left\lVert{d}\right\rVert^{2}$
subject to $\displaystyle c(x_{k})+\nabla c(x_{k})^{T}d=0.$

The corresponding subproblem with the true subgradient is

(57) $\displaystyle\underset{\begin{subarray}{c}x_{k}+d\in
C\end{subarray}}{\text{minimize}}$ $\displaystyle
r(x_{k})+g_{k}^{T}d+\frac{1}{2}\alpha_{k}\left\lVert{d}\right\rVert^{2}$
subject to $\displaystyle c(x_{k})+\nabla c(x_{k})^{T}d=0.$

To measure progress in both the objective and constraints, a $l_{1}$ merit
function is adopted in the form of

(58)
$\displaystyle\phi_{1}(x,\theta_{k})=r(x)+\theta_{k}\left\lVert{c(x)}\right\rVert_{1},$

where $\left\lVert{\cdot}\right\rVert_{1}$ is the 1-norm and $\theta_{k}>0$ is
a penalty parameter. A line search step on the constraints is needed in order
to ensure progress in the merit function (58). The predicted change
$\bar{\delta}_{k}$ on the objective is again (18). Let the line search step
size for $\bar{d}_{k}$ be $\bar{\beta}_{k}\in(0,1]$. Then, the $(k+1)$-th step
taken is given as $x_{k+1}=x_{k}+\bar{\beta}_{k}\bar{d}_{k}$. By letting
$\bar{\delta}_{k}^{\beta}=\bar{\Phi}_{k}(0)-\bar{\Phi}_{k}(\bar{\beta}_{k}\bar{d}_{k})$,
we have

(59) $\displaystyle\bar{\delta}_{k}^{\beta}=$
$\displaystyle\bar{\Phi}_{k}(0)-\bar{\Phi}_{k}(\bar{\beta}_{k}\bar{d}_{k})=-\bar{\beta}_{k}\bar{g}_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\bar{\beta}_{k}^{2}\left\lVert{\bar{d}_{k}}\right\rVert^{2}.$

The first-order optimality conditions of subproblem (56) are

(60) $\displaystyle\bar{g}_{k}+\alpha_{k}\bar{d}_{k}+\nabla
c(x_{k})\bar{\lambda}^{k+1}+\bar{v}_{k}=0,$ $\displaystyle c(x_{k})+\nabla
c(x_{k})^{T}\bar{d}_{k}=0,$ $\displaystyle x_{k},x_{k}+\bar{d}_{k}\in
C,~{}\bar{v}_{k}\in\partial i_{C}(x_{k}+\bar{d}_{k}),$

where $\bar{\lambda}^{k+1}\in\mathbb{R}^{m}$ is the Lagrange multiplier for
the equality constraint. Similarly, the optimality conditions for (57) are

(61) $\displaystyle g_{k}+\alpha_{k}d_{k}+\nabla
c(x_{k})\lambda^{k+1}+v_{k}=0,$ $\displaystyle c(x_{k})+\nabla
c(x_{k})^{T}d_{k}=0,$ $\displaystyle x_{k},x_{k}+d_{k}\in
C,~{}v_{k}\in\partial i_{C}(x_{k}+d_{k})$

The line search condition on the stochastic step $\bar{d}_{k}$ and stochastic
penalty $\bar{\theta}_{k}$ is

(62)
$\displaystyle\bar{\theta}_{k}\left\lVert{c(x_{k})}\right\rVert_{1}-\bar{\beta}_{k}\left|(\bar{\lambda}^{k+1})^{T}c(x_{k})\right|$
$\displaystyle\geq\bar{\theta}_{k}\left\lVert{c(x_{k+1})}\right\rVert_{1}-\frac{1}{2}\eta_{\beta}\nu\alpha_{k}\bar{\beta}_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}.$

where $\eta_{\beta}\in(0,1)$ and $\nu\in(0,1)$ are parameters of the algorithm
that help control the step size and ensure decrease in the merit function
value in expectation. In addition, an user-defined upper bound $\nu\beta_{u}$,
where $\beta_{u}>0$ is a parameter, is enforced on $\bar{\beta}_{k}$.

Our proposed adaptive sampling stochastic optimization algorithm is presented
in Algorithm 2. As with Algorithm 1, the practical implementation of step 7 is
discussed in Section 5.

Algorithm 2 Upper-$C^{2}$ constrained stochastic SQP with adaptive sampling

1: Choose scalars $0<\eta\leq 1$, $\eta_{\alpha}>1$,
$0<\eta_{\beta}<1$,$\nu\in[1,2]$, $\eta_{\alpha}\geq 1$ and $\gamma>0$.
Initialize $x_{0}$, $\rho\leq\alpha_{0}\leq\eta_{\alpha}\rho$ and $k=0$.

2: for $k=0,1,2,...$ do

3: Call the approximation oracle to obtain $\bar{r}(x_{k})$ and subgradient
estimate $\bar{g}_{k}$.

4: Form the quadratic function $\bar{\Phi}_{k}$ in (15) and solve subproblem
(56) to obtain $\bar{d}_{k}$ and Lagrange multiplier $\bar{\lambda}^{k+1}$.

5: Set $\bar{\theta}_{k}$ in (58) with
$\bar{\theta}_{k}=\max{\\{\bar{\theta}_{k-1},\left\lVert{\bar{\lambda}^{k+1}}\right\rVert_{\infty}+\gamma\\}}$.

6: Set the initial line search step size $\bar{\beta}_{k}=1$. Using
backtracking, (reducing by half if too large), find $\bar{\beta}_{k}$ such
that the condition in (62) is satisfied.

7: Compute $\bar{\delta}_{k}^{\beta}$ in (59). Test to ensure the sampling
satisfies Assumption 3.1.

8: Set $\bar{\beta}_{k}=\min\\{\bar{\beta}_{k},\nu\beta_{u}\\}$.

9: Take the step $x_{k+1}=x_{k}+\bar{\beta}_{k}\bar{d}_{k}$.

10: Call the chosen $\alpha_{k}$ update rules to obtain
$\alpha_{k}\leq\alpha_{k+1}\leq\eta_{\alpha}\alpha_{k}$.

As in smooth SQP methods, it is possible that the linearized constraints in
(56) are infeasible. Addressing the inconsistency is beyond the scope of this
paper. Thus, we assume that the solution $\bar{d}_{k}$ to (56) can be found.
Together with LICQ, we make the following feasibility assumption for the
remainder of this section.

######  Assumption 4.2.

The subproblem with the linearized constraints (56) is feasible. Further, the
constraints $c(x)=0$ and $x\in C$ satisfy LICQ at every accumulation point of
$\\{x_{k}\\}$ generated by Algorithm 2.

For adaptive sampling criterion, we make the same assumption as in Assumption
3.1.

###  4.2 Convergence analysis

The analysis in this section is performed under the Assumptions 3, 3, 3.1, 4.1
and 4.2. Additional assumptions necessary for subsequent convergence analysis
are presented later in this section. Our choice of $\alpha_{k}$ in Algorithm 2
leads to the following Lemma.

######  Lemma 4.3.

The steps $x_{k+1}$ from Algorithm 2 satisfy
$r(x_{k})-r(x_{k+1})\geq\Phi(0)-\Phi(\bar{\beta}_{k}\bar{d}_{k})$.

The proof is similar to that of (3.2), and hence omitted.

######  Remark 4.4.

For simplicity, $\alpha_{k}$ is required to be monotonically non-decreasing in
the algorithm. In practice, we encourage that $\alpha_{k}$ be reduced when
possible to improve convergence behavior. In addition, one can use a diagonal
matrix instead of a scalar $\alpha_{k}$ to accelerate convergence without
compromising the sparse structure of the linear system [43].

Next, we show that the line search process is well-defined in the following
Lemma.

######  Lemma 4.5.

If the Lagrange multipliers $\bar{\lambda}^{k+1}$ of (56) are bounded, the
line search process of Algorithm 2 is well-defined. That is, there exists
$\bar{\beta}_{k}>0$ that satisfies the line search conditions in (62) and it
can be found in a finite number of backtracking iterations through step 6.

######  Proof 4.6.

From Assumption 4.1, we have

(63) $\displaystyle|c_{j}(x_{k+1})|\leq$
$\displaystyle|c_{j}(x_{k})+\bar{\beta}_{k}\nabla
c_{j}(x_{k})^{T}\bar{d}_{k}|+\frac{1}{2}\bar{\beta}_{k}^{2}H\left\lVert{\bar{d}_{k}}\right\rVert^{2},$

$j=1,\dots,m$ Given $\bar{d}_{k}$ as the solution to (56), we have that
$c_{j}(x_{k})+\nabla c_{j}(x_{k})^{T}\bar{d}_{k}=0$. As a consequence, we can
write based on (63) that

(64)
$\displaystyle\left|c_{j}(x_{k+1})\right|\leq\left|(1-\bar{\beta}_{k})c_{j}(x_{k})\right|+\frac{1}{2}\bar{\beta}_{k}^{2}H\left\lVert{\bar{d}_{k}}\right\rVert^{2},$

and thus

(65)
$\displaystyle\left\lVert{c(x_{k+1})}\right\rVert_{1}\leq(1-\bar{\beta}_{k})\left\lVert{c(x_{k})}\right\rVert_{1}+\frac{1}{2}m\bar{\beta}_{k}^{2}H\left\lVert{\bar{d}_{k}}\right\rVert^{2}.$

On the other hand, simple norm inequalities imply

(66)
$\displaystyle\bar{\beta}_{k}\left|(\bar{\lambda}^{k+1})^{T}c(x_{k})\right|\leq\bar{\beta}_{k}\left\lVert{\bar{\lambda}^{k+1}}\right\rVert_{\infty}\left\lVert{c(x_{k})}\right\rVert_{1}.$

Since
$\bar{\theta}_{k}\geq\left\lVert{\bar{\lambda}^{k+1}}\right\rVert_{\infty}+\gamma$
from step 5 in Algorithm 2, we can write based on (65) and (66) that

(67)
$\displaystyle\bar{\theta}_{k}\left\lVert{c(x_{k})}\right\rVert_{1}-\bar{\beta}_{k}\left|(\bar{\lambda}^{k+1})^{T}c(x_{k})\right|-\bar{\theta}_{k}\left\lVert{c(x_{k+1})}\right\rVert_{1}$
$\displaystyle\hskip
31.2982pt\geq(\bar{\theta}_{k}-\bar{\beta}_{k}\left\lVert{\bar{\lambda}^{k+1}}\right\rVert_{\infty})\left\lVert{c(x_{k})}\right\rVert_{1}-\bar{\theta}_{k}(1-\bar{\beta}_{k})\left\lVert{c(x_{k})}\right\rVert_{1}-\frac{1}{2}\bar{\theta}_{k}m\bar{\beta}_{k}^{2}H\left\lVert{\bar{d}_{k}}\right\rVert^{2}$
$\displaystyle\hskip
31.2982pt=(\bar{\theta}_{k}\bar{\beta}_{k}-\bar{\beta}_{k}\left\lVert{\bar{\lambda}^{k+1}}\right\rVert_{\infty})\left\lVert{c(x_{k})}\right\rVert_{1}-\frac{1}{2}\bar{\theta}_{k}m\bar{\beta}_{k}^{2}H\left\lVert{\bar{d}_{k}}\right\rVert^{2}$
$\displaystyle\hskip
31.2982pt\geq\bar{\beta}_{k}\gamma\left\lVert{c(x_{k})}\right\rVert_{1}-\frac{1}{2}\bar{\theta}_{k}m\bar{\beta}_{k}^{2}H\left\lVert{\bar{d}_{k}}\right\rVert^{2}.$

Therefore, if $\bar{\beta}_{k}$ is reduced through the backtracking of
Algorithm 2 to satisfy

(68) $\displaystyle
0<\bar{\beta}_{k}\leq\frac{\nu\eta_{\beta}\alpha_{k}}{H\bar{\theta}_{k}m},$

then (62) is satisfied. Both the denominator and numerator in (68) are
positive and independent of the line search. If $\bar{\lambda}^{k+1}$ is
bounded throughout the algorithm, then a finite and constant
$\bar{\theta}_{k}$ is guaranteed to exist for $k$ large enough based on how it
is chosen in Algorithm 2. Thus, all terms in (68) are finite. Therefore, step
6 of Algorithm 2 stops in finite iterations.

######  Lemma 4.7.

The sequence of Lagrange multipliers $\\{\lambda^{k+1}\\}$ for problem (56)
based on $\\{x_{k}\\}$ are bounded. In addition, there exists $\theta_{u}$
such that $\theta_{u}\geq\theta_{k}$ for all $k\in\mathbb{N}$.

######  Proof 4.8.

Note that $\\{x_{k}\\}$ is produced by Algorithm 2. We rewrite the first
equation in optimality condition in (61) as

(69) $\displaystyle
g_{k}+\alpha_{k}d_{k}=-\sum_{j=1}^{m}\lambda^{k+1}_{j}\nabla
c_{j}(x_{k})-v_{k}.$

Since $\\{x_{k}\\},\\{g_{k}\\}$ are bounded ($r$ being Lipschitz on a bounded
domain) and $\alpha_{k}$ is a finite parameter, the left-hand side of the
equation stays bounded for all $k\in\mathbb{N}$ and $d_{k}$. If $x_{k}+d_{k}$
is in the interior of $C$, then $v_{k}=0$. If $x_{k}+d_{k}$ is on the boundary
of $C$, then the constraints $x_{k}+d_{k}\in C$ is active. In either case,
from Assumption 4.2, $\nabla c_{j}(x_{k}),j=1,\dots,m$ and the non-zero
$v_{k}$ are linearly independent vectors of $\mathbb{R}^{n}$. Without losing
generality, suppose $\lambda^{k+1}_{j},j\in[1,m]$ is not bounded as
$k\to\infty$. Since $\\{x_{k}\\}$ is bounded, there exists a subsequence
$\\{x_{k_{u}}\\}$ such that $x_{k_{u}}\to\bar{x}$. Passing on to a subsequence
if necessary, $\lambda^{k_{u}}_{j}\to\infty$. Then, the right-hand side of
(69) $-\sum_{j=1}^{m}\lambda^{k_{u}+1}_{j}\nabla
c_{j}(x_{k_{u}})-v_{k_{u}}\to\infty$, by LICQ. This is a contradiction.
Therefore, there exists $\lambda^{u}\geq 0$, such that
$\left\lVert{\lambda^{k}}\right\rVert_{\infty}\leq\lambda^{u}$, for all $k$.
Since $\theta_{k}$ is determined by $\lambda^{k}$, there exists $k$ such that
$\theta_{t}=\theta_{k}$ for all $t\geq k$. Further, since $\theta_{k}$ is
monotonically non-decreasing, there exists $\theta_{u}>0$ such that
$\theta_{u}\geq\theta_{k}$ for all $k\in\mathbb{N}$.

From Assumption 3.1, Lemma 3.7 is preserved.

######  Lemma 4.9.

For all $k\in\mathbb{N}$ of Algorithm 2,
$\mathbb{E}_{k}\left[\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert\right]\leq\sqrt{\eta\alpha_{k}}\left\lVert{d_{k}}\right\rVert$.

The bound on the variance of $\bar{d}_{k}$ similarly follows Lemma 3.9 with
modified proofs.

######  Lemma 4.10.

For all $k\in\mathbb{N}$ of Algorithm 2,
$\mathbb{E}_{k}[\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert]\leq\sqrt{\frac{\eta}{\alpha_{k}}}\left\lVert{d_{k}}\right\rVert$,
and
$\mathbb{E}_{k}[\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert^{2}]\leq\frac{\eta}{\alpha_{k}}\left\lVert{d_{k}}\right\rVert^{2}$.

######  Proof 4.11.

From the definition, $d_{k}$ and $\bar{d}_{k}$ are the solutions to (57) and
(56), respectively. Subtracting the first optimality conditions in (61) from
(60) leads to

(70) $\displaystyle\bar{g}_{k}-g_{k}+\alpha_{k}(\bar{d}_{k}-d_{k})+\nabla
c(x_{k})(\bar{\lambda}^{k+1}-\lambda^{k+1})+\bar{v}_{k}-v_{k}=0.$

Multiply both sides of (70) by $\bar{d}_{k}-d_{k}$ and we obtain

(71)
$\displaystyle(\bar{g}_{k}-g_{k})^{T}(\bar{d}_{k}-d_{k})+\alpha_{k}\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert^{2}$
$\displaystyle+(\bar{\lambda}^{k+1}-\lambda^{k+1})^{T}\nabla
c(x_{k})^{T}(\bar{d}_{k}-d_{k})$
$\displaystyle+(\bar{v}_{k}-v_{k})^{T}(\bar{d}_{k}-d_{k})=0.$

Given that $x_{k}+d_{k}\in C$ and $x_{k}+\bar{d}_{k}\in C$, the convexity of
$i_{C}(\cdot)$ implies

(72) $\displaystyle(\bar{v}_{k}-v_{k})^{T}(\bar{d}_{k}-d_{k})\geq 0.$

Further, $\nabla c(x_{k})^{T}\bar{d}_{k}=\nabla c(x_{k})^{T}d_{k}=-c(x_{k})$,
i.e.,

(73) $\displaystyle(\bar{\lambda}^{k+1}-\lambda^{k+1})^{T}\nabla
c(x_{k})^{T}(\bar{d}_{k}-d_{k})=0.$

Applying (72) and (73) to (71) leads to

(74) $\displaystyle\alpha_{k}\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert^{2}$
$\displaystyle\leq-(\bar{g}_{k}-g_{k})^{T}(\bar{d}_{k}-d_{k})\leq\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert.$

Notice that $(\bar{g}_{k}-g_{k})^{T}(\bar{d}_{k}-d_{k})\leq 0$. Therefore,

(75)
$\displaystyle\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert\leq\frac{1}{\alpha_{k}}\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert.$

Taking $\mathbb{E}_{k}$ on (75) as well as (74) and applying Lemma 4.9
completes the proof.

From Lemma 4.7, $\\{\lambda^{k}\\}$ is bounded. To ensure convergence results
for the constrained problem, $\\{\bar{\lambda}^{k}\\}$ also needs to be
bounded. Unfortunately, this cannot be guaranteed without additional
assumptions. Choices of assumption in literature include direct boundedness of
$\bar{\lambda}^{k}$, boundedness on $\bar{g}_{k}$ [3] and boundedness on norm
of predicted decrease [2]. The stochastic subgradient estimate $\bar{g}_{k}$
is fully determined by the joint distribution of samples throughout iteration
$k$. By Chebyshev inequality, we know the probability of an unbounded
$\bar{g}_{k}$ can be represented by

(76)
$\displaystyle\mathbb{P}\left(\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert\geq
a\right)\leq\frac{\mathbb{E}[\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert^{2}]}{a^{2}},$

for any $a>0$. Taking the total expectation of Assumption 3.1 gives us
$\mathbb{E}[\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert^{2}]\leq\eta\mathbb{E}[\alpha_{k}\left\lVert{d_{k}}\right\rVert^{2}]$.
Thus,

(77)
$\displaystyle\mathbb{P}\left(\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert\geq
a\right)\leq\frac{\eta\alpha_{k}\mathbb{E}[\left\lVert{d_{k}}\right\rVert^{2}]}{a^{2}}.$

Since $\alpha_{k}$ and $d_{k}$ are bounded, the probability of an unbounded
$\bar{g}_{k}$ tends to zero as $a$ increases. Given this observation, we make
two different assumptions in the following sections, where the stronger
assumptions (Section 4.4) leads to subsequent convergence of accumulation
points similar to those in [22, 5] and the weaker assumption (Section 4.3)
shows convergence in expectation, similar to those in [2, 3].

###  4.3 Essentially bounded subgradient

In this subsection, we proceed with the following additional assumption.

######  Assumption 4.12.

For all $k\in\mathbb{N}$ of Algorithm 2, the stochastic subgradient
approximation $\bar{g}_{k}$ is essentially bounded, i.e.,

(78) $\displaystyle
essup(\bar{g}_{k})=\inf\left\\{a|\mathbb{P}\\{\bar{g}_{k}|\left\lVert{\bar{g}_{k}}\right\rVert>a\\}=0\right\\}$

is finite. Equivalently, for almost all realizations $\xi_{k}$ on the joint
distribution of samples $S_{0},S_{1},\dots,S_{k}$, $\bar{g}_{k}$ is bounded
with probability 1.

Assumption (4.12) leads to the following Lemma.

######  Lemma 4.13.

Given Assumption 4.12, the Lagrange multipliers $\\{\bar{\lambda}^{k}\\}$ of
(56) are bounded with probability 1. Further, there exists
$\bar{\theta}_{u}>0$ such that $\bar{\theta}_{u}\geq\theta_{k}$ for all
$k\in\mathbb{N}$ with probability 1.

######  Proof 4.14.

From the optimality condition (60),

(79)
$\displaystyle\bar{g}_{k}+\alpha_{k}\bar{d}_{k}=-\sum_{j=1}^{m}\bar{\lambda}^{k+1}_{j}\nabla
c_{j}(x_{k})-\bar{v}_{k}.$

The remaining proof is the same as in Lemma 4.7, where given Assumption 4.12,
the left-hand side of (79) is bounded with probability 1. LICQ thus guarantees
that $\\{\bar{\lambda}^{k}\\}$ and $\bar{\theta}_{k}$ are bounded with
probability 1.

Denote by $\bar{\theta}_{u}<\infty$ an upper bound on $\theta_{k}$, the
following Lemma on step size follows.

######  Lemma 4.15.

There exist $\bar{\beta}_{l}>0$ and $\bar{\beta}_{u}>0$ such that the step
size $\bar{\beta}_{k}$ satisfies
$\bar{\beta}_{l}\leq\bar{\beta}_{k}\leq\bar{\beta}_{u}$ for all
$k\in\mathbb{N}$ with probability 1.

######  Proof 4.16.

The step size $\bar{\beta}_{k}$ is chosen through backtracking with a user-
defined maximum value $\nu\beta_{u}$, as shown in step 6 and 8 in Algorithm 2.
From (68), using ceiling function $\lceil\cdot\rceil$, which returns the least
integer greater than the input, step 6 results in

(80)
$\displaystyle\bar{\beta}_{k}\geq\frac{1}{2}^{\lceil\log_{\frac{1}{2}}\frac{\nu\eta_{\beta}\alpha_{k}}{H\bar{\theta}_{k}m}\rceil}.$

Since $\alpha_{k}$ is monotonically non-decreasing and
$\bar{\theta}_{k}\leq\bar{\theta}_{u}$ by Lemma 4.13, we can define

(81)
$\displaystyle\beta_{l}=\frac{1}{2}^{\lceil\log_{\frac{1}{2}}\frac{\nu\eta_{\beta}\alpha_{0}}{H\bar{\theta}_{u}m}\rceil},\
\bar{\beta}_{l}=\min{\\{\beta_{l},1\\}}.$

From step 6 in Algorithm 2, $\bar{\beta}_{l}\leq\bar{\beta}_{k}$. From step 8
in Algorithm 2, we can set
$\bar{\beta}_{u}=\max\\{1,\nu\beta_{u},\bar{\beta}_{l}\\}$ to complete the
proof.

Note that both $\bar{\beta}_{l}$ and $\bar{\beta}_{u}$ depend on the choice of
parameter $\nu$. Next, an upper bound is provided for a term in the analysis
of the expectation of merit function.

######  Lemma 4.17.

With probability 1, there exists $c_{\beta}\geq 0$ such that

(82)
$\displaystyle\mathbb{E}_{k}\left[\bar{\beta}_{k}(g_{k}-\bar{g}_{k})^{T}d_{k}\right]\leq
c_{\beta}\sqrt{\eta\alpha_{k}}\left\lVert{d_{k}}\right\rVert^{2}.$

######  Proof 4.18.

Let $A_{k}$ be the event that $(g_{k}-\bar{g}_{k})^{T}d_{k}\geq 0$ and
$A_{k}^{c}$ the event that $(g_{k}-\bar{g}_{k})^{T}d_{k}<0$. Let
$\mathbb{P}_{k}[\cdot]$ denote the probability conditioned on the event of
$x_{k}$ at $k$th iteration. Using the Law of Total Expectation, by Lemma 4.15
we have

(83)
$\displaystyle\mathbb{E}_{k}\left[\bar{\beta}_{k}(g_{k}-\bar{g}_{k})^{T}d_{k}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{k}\left[\bar{\beta}_{k}(g_{k}-\bar{g}_{k})^{T}d_{k}|A_{k}\right]\mathbb{P}_{k}[A_{k}]+\mathbb{E}_{k}\left[\bar{\beta}_{k}(g_{k}-\bar{g}_{k})^{T}d_{k}|A_{k}^{c}\right]\mathbb{P}_{k}[A_{k}^{c}]$
$\displaystyle\leq$
$\displaystyle\bar{\beta}_{u}\mathbb{E}_{k}\left[(g_{k}-\bar{g}_{k})^{T}d_{k}|A_{k}\right]\mathbb{P}_{k}[A_{k}]+\bar{\beta}_{l}\mathbb{E}_{k}\left[(g_{k}-\bar{g}_{k})^{T}d_{k}|A_{k}^{c}\right]\mathbb{P}_{k}[A_{k}^{c}]$

Since $\mathbb{E}_{k}[\bar{g}_{k}]=g_{k}$, (83) implies

(84)
$\displaystyle\mathbb{E}_{k}[\bar{\beta}_{k}(g_{k}-\bar{g}_{k})^{T}d_{k}]\leq$
$\displaystyle\bar{\beta}_{l}\mathbb{E}_{k}\left[(g_{k}-\bar{g}_{k})^{T}d_{k}|A_{k}\right]\mathbb{P}_{k}[A_{k}]+$
$\displaystyle\bar{\beta}_{l}\mathbb{E}_{k}[(g_{k}$
$\displaystyle-\bar{g}_{k})^{T}d_{k}|A_{k}^{c}]\mathbb{P}_{k}[A_{k}^{c}]+(\bar{\beta}_{u}-\bar{\beta}_{l})\mathbb{E}_{k}\left[(g_{k}-\bar{g}_{k})^{T}d_{k}|A_{k}\right]\mathbb{P}_{k}[A_{k}]$
$\displaystyle=$
$\displaystyle(\bar{\beta}_{u}-\bar{\beta}_{l})\mathbb{E}_{k}\left[(g_{k}-\bar{g}_{k})^{T}d_{k}|A_{k}\right]\mathbb{P}_{k}[A_{k}].$

Similarly,

(85)
$\displaystyle\mathbb{E}_{k}\left[\bar{\beta}_{k}(g_{k}-\bar{g}_{k})^{T}d_{k}\right]\leq$
$\displaystyle(\bar{\beta}_{l}-\bar{\beta}_{u})\mathbb{E}_{k}\left[(g_{k}-\bar{g}_{k})^{T}d_{k}|A_{k}^{c}\right]\mathbb{P}_{k}[A_{k}^{c}].$

Summing (84) and (85) leads to

(86)
$\displaystyle\mathbb{E}_{k}\left[\bar{\beta}_{k}(g_{k}-\bar{g}_{k})^{T}d_{k}\right]$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}(\bar{\beta}_{u}-\bar{\beta}_{l})\left(\mathbb{E}_{k}\left[(g_{k}-\bar{g}_{k})^{T}d_{k}|A_{k}\right]\mathbb{P}_{k}[A_{k}]-\mathbb{E}_{k}\left[(g_{k}-\bar{g}_{k})^{T}d_{k}|A_{k}^{c}\right]\mathbb{P}_{k}[A_{k}^{c}]\right).$

Using the Law of Total Expectation again, we have

(87)
$\displaystyle\mathbb{E}_{k}\left[(g_{k}-\bar{g}_{k})^{T}d_{k}|A_{k}\right]\mathbb{P}_{k}[A_{k}]$
$\displaystyle\leq\mathbb{E}_{k}\left[\left\lVert{g_{k}-\bar{g}_{k}}\right\rVert\left\lVert{d_{k}}\right\rVert|A_{k}\right]\mathbb{P}_{k}[A_{k}]$
$\displaystyle=\mathbb{E}_{k}\left[\left\lVert{g_{k}-\bar{g}_{k}}\right\rVert\left\lVert{d_{k}}\right\rVert\right]-\mathbb{E}_{k}\left[\left\lVert{g_{k}-\bar{g}_{k}}\right\rVert\left\lVert{d_{k}}\right\rVert|A_{k}^{c}\right]\mathbb{P}_{k}[A_{k}^{c}]$
$\displaystyle\leq\mathbb{E}_{k}[\left\lVert{g_{k}-\bar{g}_{k}}\right\rVert]\left\lVert{d_{k}}\right\rVert.$

Similarly,

(88)
$\displaystyle-\mathbb{E}_{k}\left[(g_{k}-\bar{g}_{k})^{T}d_{k}|A_{k}^{c}\right]\mathbb{P}_{k}[A_{k}^{c}]$
$\displaystyle\leq\mathbb{E}_{k}\left[\left\lVert{g_{k}-\bar{g}_{k}}\right\rVert\left\lVert{d_{k}}\right\rVert|A_{k}^{c}\right]\mathbb{P}_{k}[A_{k}^{c}]$
$\displaystyle=\mathbb{E}_{k}\left[\left\lVert{g_{k}-\bar{g}_{k}}\right\rVert\left\lVert{d_{k}}\right\rVert\right]-\mathbb{E}_{k}\left[\left\lVert{g_{k}-\bar{g}_{k}}\right\rVert\left\lVert{d_{k}}\right\rVert|A_{k}\right]\mathbb{P}_{k}[A_{k}]$
$\displaystyle\leq\mathbb{E}_{k}[\left\lVert{g_{k}-\bar{g}_{k}}\right\rVert]\left\lVert{d_{k}}\right\rVert.$

Applying (87) and (88) to (86), we have

(89)
$\displaystyle\mathbb{E}_{k}\left[\bar{\beta}_{k}(g_{k}-\bar{g}_{k})^{T}d_{k}\right]\leq$
$\displaystyle(\bar{\beta}_{u}-\bar{\beta}_{l})\mathbb{E}_{k}[\left\lVert{g_{k}-\bar{g}_{k}}\right\rVert]\left\lVert{d_{k}}\right\rVert.$

By Lemma 4.9, let $c_{\beta}=\bar{\beta}_{u}-\bar{\beta}_{l}\geq 0$, (82) is
proven.

We proceed to examine the expectation $\mathbb{E}_{k}$ of consecutive merit
function values.

######  Lemma 4.19.

There exists constant $c^{\phi}_{k}$ so that the step
$x_{k+1}=x_{k}+\bar{\beta}_{k}\bar{d}_{k}$ leads to

(90)
$\displaystyle\mathbb{E}_{k}\left[\phi_{1}(x_{k},\bar{\theta}_{k})-\phi_{1}(x_{k+1},\bar{\theta}_{k})\right]>c^{\phi}_{k}\left\lVert{d_{k}}\right\rVert^{2}$

with probability 1.

######  Proof 4.20.

From Lemma 4.3, we have

(91) $\displaystyle r(x_{k})-r(x_{k+1})>$
$\displaystyle-\bar{\beta}_{k}g_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\bar{\beta}_{k}^{2}\left\lVert{\bar{d}_{k}}\right\rVert^{2}.$

Rearranging the first equation in optimality conditions (60), we have

(92) $\bar{g}_{k}+\alpha_{k}\bar{d}_{k}=-\nabla
c(x_{k})\bar{\lambda}^{k+1}-\bar{v}_{k}.$

Taking the inner product with $-\bar{d}_{k}$ in (92) and using (60), we have

(93)
$\displaystyle-\bar{g}_{k}^{T}\bar{d}_{k}-\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}$
$\displaystyle=(\bar{\lambda}^{k+1})^{T}\nabla
c(x_{k})^{T}\bar{d}_{k}+\bar{v}_{k}\bar{d}_{k}$
$\displaystyle=-(\bar{\lambda}^{k+1})^{T}c(x_{k})+i_{C}(x_{k})-i_{C}(x_{k}+\bar{d}_{k})-\bar{v}_{k}^{T}(-\bar{d}_{k})$
$\displaystyle\geq-(\bar{\lambda}^{k+1})^{T}c(x_{k}),$

where the convexity of $i_{C}(\cdot)$ is applied. Next, multiplying both sides
of (93) by $\bar{\beta}_{k}$ and then subtracting
$\frac{1}{2}\alpha_{k}\bar{\beta}_{k}^{2}\left\lVert{\bar{d}_{k}}\right\rVert^{2}$
leads to

(94)
$\displaystyle-\bar{\beta}_{k}\bar{g}_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\bar{\beta}_{k}^{2}\left\lVert{\bar{d}_{k}}\right\rVert^{2}$
$\displaystyle\geq\alpha_{k}\bar{\beta}_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}-\frac{1}{2}\alpha_{k}\bar{\beta}_{k}^{2}\left\lVert{\bar{d}_{k}}\right\rVert^{2}-\bar{\beta}_{k}(\bar{\lambda}^{k+1})^{T}c(x_{k})$
$\displaystyle\geq\frac{1}{2}\alpha_{k}\bar{\beta}_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}-\bar{\beta}_{k}(\bar{\lambda}^{k+1})^{T}c(x_{k}),$

where the second inequality makes use of $\bar{\beta}_{k}\in(0,1]$. The right-
hand side of (91) can be rewritten through that of (94) as

(95) $\displaystyle-$
$\displaystyle\bar{\beta}_{k}g_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\bar{\beta}_{k}^{2}\left\lVert{\bar{d}_{k}}\right\rVert^{2}=-\bar{\beta}_{k}g_{k}^{T}\bar{d}_{k}+\bar{\beta}_{k}\bar{g}_{k}^{T}\bar{d}_{k}-\bar{\beta}_{k}\bar{g}_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\bar{\beta}_{k}^{2}\left\lVert{\bar{d}_{k}}\right\rVert^{2}$
$\displaystyle\geq\bar{\beta}_{k}\left(\bar{g}_{k}-g_{k}\right)^{T}d_{k}+\bar{\beta}_{k}\left(\bar{g}_{k}-g_{k}\right)^{T}\left(\bar{d}_{k}-d_{k}\right)+\frac{1}{2}\alpha_{k}\bar{\beta}_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}-\bar{\beta}_{k}(\bar{\lambda}^{k+1})^{T}c(x_{k})$
$\displaystyle\geq\bar{\beta}_{k}\left(\bar{g}_{k}-g_{k}\right)^{T}d_{k}-\bar{\beta}_{k}\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert+\frac{1}{2}\alpha_{k}\bar{\beta}_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}-\bar{\beta}_{k}(\bar{\lambda}^{k+1})^{T}c(x_{k}).$

From Lemma 4.5 and (62), we have

(96)
$\displaystyle-\bar{\beta}_{k}(\bar{\lambda}^{k+1})^{T}c(x_{k})+\bar{\theta}_{k}\left\lVert{c(x_{k})}\right\rVert_{1}-\bar{\theta}_{k}\left\lVert{c(x_{k+1})}\right\rVert_{1}\geq-\frac{1}{2}\eta_{\beta}\nu\alpha_{k}\bar{\beta}_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}.$

Finally, combine the inequalities in (91), (95) and (96), we have

(97) $\displaystyle\phi_{1}(x_{k},\bar{\theta}_{k})-$
$\displaystyle\phi_{1}(x_{k+1},\bar{\theta}_{k})=r(x_{k})-r(x_{k+1})+\bar{\theta}_{k}\left\lVert{c(x_{k})}\right\rVert_{1}-\bar{\theta}_{k}\left\lVert{c(x_{k+1})}\right\rVert_{1}$
$\displaystyle>$
$\displaystyle-\bar{\beta}_{k}g_{k}^{T}\bar{d}_{k}-\frac{1}{2}\alpha_{k}\bar{\beta}_{k}^{2}\left\lVert{\bar{d}_{k}}\right\rVert^{2}+\bar{\theta}_{k}\left\lVert{c(x_{k})}\right\rVert_{1}-\bar{\theta}_{k}\left\lVert{c(x_{k+1})}\right\rVert_{1}$
$\displaystyle\geq$
$\displaystyle\bar{\beta}_{k}(\bar{g}_{k}-g_{k})^{T}d_{k}-\bar{\beta}_{k}\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert+(1-\eta_{\beta}\nu)\frac{1}{2}\alpha_{k}\bar{\beta}_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}.$

From Lemma 4.17, we have

(98)
$\displaystyle\mathbb{E}_{k}[\bar{\beta}_{k}(\bar{g}_{k}-g_{k})^{T}d_{k}]\geq-
c_{\beta}\sqrt{\eta\alpha_{k}}\left\lVert{d_{k}}\right\rVert^{2}$

To proceed, we apply Lemma 4.15 so that
$\bar{\beta}_{l}\leq\bar{\beta}_{k}\leq\bar{\beta}_{u}$ with probability 1.
Similar to (41), we have

(99)
$\displaystyle(1-\eta_{\beta}\nu)\frac{1}{2}\alpha_{k}\bar{\beta}_{l}\left\lVert{\bar{d}_{k}}\right\rVert^{2}\geq(1-\eta_{\beta}\nu)\frac{1}{2}\alpha_{k}\bar{\beta}_{l}\left[\left\lVert{d_{k}}\right\rVert^{2}+\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert^{2}-2\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert\left\lVert{d_{k}}\right\rVert\right].$

Taking the expectation $\mathbb{E}_{k}$ of (99) and applying Lemma 4.10,

(100)
$\displaystyle\mathbb{E}_{k}\left[(1-\eta_{\beta}\nu)\frac{\alpha_{k}}{2}\bar{\beta}_{l}\left\lVert{\bar{d}_{k}}\right\rVert^{2}\right]\geq(1-\eta_{\beta}\nu)\frac{\alpha_{k}}{2}\bar{\beta}_{l}\left[\left\lVert{d_{k}}\right\rVert^{2}+\mathbb{E}_{k}\left[\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert^{2}\right]-2\sqrt{\frac{\eta}{\alpha_{k}}}\left\lVert{d_{k}}\right\rVert^{2}\right].$

Taking the expectation $\mathbb{E}_{k}$ of the remaining terms on the right-
hand side on the last line of (97) and applying Lemma 4.10 and 4.9 leads to

(101)
$\displaystyle\mathbb{E}_{k}\left[-\bar{\beta}_{k}\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert\left\lVert{\bar{d}_{k}-d_{k}}\right\rVert\right]\geq-\bar{\beta}_{u}\eta\left\lVert{d_{k}}\right\rVert^{2}.$

From (98), (100) and (101), the expectation $\mathbb{E}_{k}$ on both sides of
(97) is

(102)
$\displaystyle\mathbb{E}_{k}\left[\phi_{1}(x_{k},\bar{\theta}_{k})-\phi_{1}(x_{k+1},\bar{\theta}_{k})\right]\geq\left[(1-\eta_{\beta}\nu)\frac{\alpha_{k}}{2}\bar{\beta}_{l}\left(1-2\sqrt{\frac{\eta}{\alpha_{k}}}\right)-\left(c_{\beta}\sqrt{\eta\alpha_{k}}+\bar{\beta}_{u}\eta\right)\right]\left\lVert{d_{k}}\right\rVert^{2}.$

Define $c^{\phi}_{k}$ as

(103) $\displaystyle
c^{\phi}_{k}=(1-\eta_{\beta}\nu)\frac{\alpha_{k}}{2}\bar{\beta}_{l}\left(1-2\sqrt{\frac{\eta}{\alpha_{k}}}\right)-\left(c_{\beta}\sqrt{\eta\alpha_{k}}+\bar{\beta}_{u}\eta\right),$

and the proof is completed.

Let $M_{c}>0$ be the upper bound of the constraints so that
$\left\lVert{c(x)}\right\rVert_{1}\leq M_{c}$ for all $x\in C$. We are ready
to prove the convergence of the expected value of the merit function in the
following theorem.

######  Theorem 4.21.

Let $\eta$, $\beta$, $\nu$, $\eta_{\beta}$ and $\alpha_{k}$ be chosen such
that $c^{\phi}_{k}>0$. Then, with probability 1,

(104)
$\displaystyle\lim_{k\to\infty}\mathbb{E}\left[\sum_{j=1}^{k-1}\frac{1}{2}\alpha_{k}\left\lVert{d_{k}}\right\rVert^{2}\right]<\infty.$

It follows that
$\lim_{k\to\infty}\mathbb{E}\left[\left\lVert{d_{k}}\right\rVert\right]=0$,
$\lim_{k\to\infty}\mathbb{E}\left[\left\lVert{g_{k}+v_{k}+\nabla
c(x_{k})\lambda^{k+1}}\right\rVert\right]=0$ and
$\lim_{k\to\infty}\mathbb{E}[\left\lVert{c(x_{k})}\right\rVert]=0$ with
probability 1.

######  Proof 4.22.

By Lemma 4.19, we have with probability 1,

(105)
$\displaystyle\mathbb{E}_{k}[\phi_{1}(x_{k+1},\bar{\theta}_{k})-\phi_{1}(x_{k},\bar{\theta}_{k})]<-c^{\phi}_{k}\left\lVert{d_{k}}\right\rVert^{2}.$

Since both $r(\cdot)$ and $\left\lVert{c(\cdot)}\right\rVert_{1}$ are bounded
below, so is $\phi_{1}(\cdot,\cdot)$. Let $\phi_{1\min}$ be the minimum of
$\phi_{1}(\cdot,\cdot)$ on $C$. Summing up $j=0,1,\dots,k-1$ of
$\phi_{1}(x_{j+1},\bar{\theta}_{j+1})-\phi_{1}(x_{j},\bar{\theta}_{j})$ and
taking the total expectation, we have

(106) $\displaystyle-\infty<\phi_{1\min}-\phi_{1}(x_{0},\bar{\theta}_{0})\leq$
$\displaystyle\mathbb{E}\left[\phi_{1}(x_{k},\bar{\theta}_{k})-\phi_{1}(x_{0},\bar{\theta}_{0})\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{i=1}^{k-1}\left(\phi_{1}(x_{i+1},\bar{\theta}_{i+1})-\phi_{1}(x_{i},\bar{\theta}_{i})\right)\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\sum_{i=1}^{k-1}(\bar{\theta}_{i+1}-\bar{\theta}_{i})\left\lVert{c(x_{i})}\right\rVert_{1}-\sum_{i=1}^{k-1}c^{\phi}_{i}\left\lVert{d_{i}}\right\rVert^{2}\right].$

Since $\alpha_{k}$ is monotonically non-decreasing, from the definition of
$c^{\phi}_{i}$ in (103), there exists $c^{\phi}_{l}>0$ such that
$c^{\phi}_{i}>c^{\phi}_{l}$ for all $i=1,2,\cdots$. Therefore,

(107) $\displaystyle-\infty<$
$\displaystyle(\bar{\theta}_{u}-\bar{\theta}_{0})M_{c}-c^{\phi}_{l}\mathbb{E}\left[\sum_{i=0}^{k-1}\left\lVert{d_{i}}\right\rVert^{2}\right].$

Let $k\to\infty$,
$\lim_{k\to\infty}\mathbb{E}[\left\lVert{d_{k}}\right\rVert^{2}]=0$. By the
first and third equations in (61), we obtain
$\lim_{k\to\infty}\mathbb{E}[\left\lVert{g_{k}+v_{k}+\nabla
c(x_{k})\lambda^{k+1}}\right\rVert]=0$, $g_{k}\in\bar{\partial}r(x_{k})$, and
$\lim_{k\to\infty}\mathbb{E}[\left\lVert{c(x_{k})}\right\rVert]=0$.

###  4.4 Bounded subgradient

In this section, the following assumption is made.

######  Assumption 4.23.

For all $k\in\mathbb{N}$ of Algorithm 2, the stochastic subgradient
approximation $\bar{g}_{k}$ is bounded, i.e., there exists $M_{g}>0$ such that

(108) $\displaystyle\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert\leq M_{g}.$

Assumption 4.23 preserves Lemma 4.13, 4.15, 4.17 and 4.19 without needing the
statement ‘with probability 1’. Assumption 4.23 is similar to Proposition 35
in [3] and leads to the following Lemma. For simplified proof of convergence,
we utilize the super-martingale convergence theorem (Lemma 3.17).

######  Theorem 4.24.

Under the conditions in Theorem 4.21, every accumulation point of the sequence
$\\{x_{k}\\}$ produced by Algorithm 2 is a KKT point of (9) with probability
1.

######  Proof 4.25.

Let $k$ be large enough so that $\bar{\theta}_{k}=\bar{\theta}$ becomes
constant. Then, apply Lemma 3.17 to 4.19 directly, where $a_{k}=0$ and
$b_{k}=0$ for, and we have $\\{\phi_{1}(x_{k},\bar{\theta})\\}$ converges with
probability 1, and $\lim_{k\to\infty}\left\lVert{d_{k}}\right\rVert^{2}=0$
with probability 1. Therefore, $\lim_{k\to\infty}d_{k}=0$ with probability 1.
Let $\bar{x}$ be an accumulation point of $\\{x_{k}\\}$. Then, passing on to a
subsequence if necessary, we can assume $\lim_{k\to\infty}x_{k}=\bar{x}$ where
$\bar{x}\in C$. By Lemma 4.13, $\\{\bar{\lambda}^{k}\\}$ is bounded. Further,
$g_{k}\in\bar{\partial}r(x_{k})$ is bounded. Thus, there exist accumulation
points for $\\{g_{k}\\}$ and $\\{\lambda^{k}\\}$ from quadratic subproblem
(57). Passing on to a subsequence if necessary, we have $g_{k}\to\bar{g}$ and
$\lambda^{k}\to\bar{\lambda}$. By the outer semicontinuity of Clark
subdifferential, we have $\bar{g}\in\bar{\partial}r(\bar{x})$.

From (61), $\lim_{k\to\infty}v_{k}=-\bar{g}-\nabla c(\bar{x})\bar{\lambda}$
with probability 1. Given that $v_{k}\in\partial i_{C}(x_{k})$, the outer
semicontinuity of $\partial i_{C}(\cdot)$ leads to
$\lim_{k\to\infty}v_{k}\in\partial i_{C}(\bar{x})$. Therefore,

(109) $\displaystyle 0\in\bar{\partial}r(\bar{x})+\nabla
c(\bar{x})\bar{\lambda}+\partial i_{C}(\bar{x})$ , $\displaystyle
c(\bar{x})=0,\ \bar{x}\in C$ .

Thus, $\bar{x}$ is a KKT point with probability 1.

The algorithm and convergence analysis can be readily extended to two-stage
stochastic programming problems in the form of (1), where the quadratic
approximation $\bar{\phi}_{k}(\cdot)$ is needed only for the stochastic
second-stage value function $r(\cdot)$.

##  5 Implementation and Numerical Applications

As noted in previous sections, the convergence analysis requires knowledge of
the functional and algorithmic parameters. In practice, such parameters need
to be estimated and adjusted as the optimization progresses. Further, the
Assumption 3.1 is not implementable and thus need to be approximated in step 5
of Algorithm 1 and step 7 of Algorithm 2.

Per convention, let $S_{k}$ denote the index set of samples of the random
variable $\xi$ with realizations $\xi_{i},i\in S_{k}$ at iteration $k$, and
define $N_{k}=|S_{k}|$ as the cardinality of the set. The stochastic estimate
of $g_{k}$ can be

(110) $\displaystyle\bar{g}_{k}=\frac{1}{N_{k}}\sum_{i\in
S_{k}}G(x_{k},\xi_{i}),$

where $G(x_{k},\xi_{i})\in\bar{\partial}R(x_{k},\xi_{i})$ is a subgradient of
$R(\cdot,\cdot)$. For nonsmooth objective $r(\cdot)$, a consistent form of
subgradient $G(x_{k},\xi_{i})$ at $x_{k}$ for samples $\xi_{i},i\in S_{k}$
would be efficient in producing a non-biased estimate $\bar{g}_{k}$ of a
$g_{k}\in\bar{\partial}r(x_{k})$. Assuming independent identically distributed
(i.i.d) random variable sampling, a practical approximation of (21) is

(111) $\displaystyle\frac{1}{|S_{k}|-1}\frac{\sum_{\xi_{i}\in
S_{k}}\left\lVert{G(x_{k},\xi_{i})-\bar{g}_{k}}\right\rVert^{2}}{|S_{k}|}\leq\eta\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}.$

The left-hand side of (111) is an unbiased estimate of
$\mathbb{E}_{k}[\left\lVert{\bar{g}_{k}-g_{k}}\right\rVert^{2}]$. If (111) is
satisfied, the sample size is maintained $|S_{k+1}|=|S_{k}|$. Otherwise,
$|S_{k}|$ is increased through

(112) $\displaystyle|S_{k+1}|=\frac{\sum_{\xi_{i}\in
S_{k}}\left\lVert{G(x_{k},\xi_{i})-\bar{g}_{k}}\right\rVert^{2}}{\eta\alpha_{k}\left\lVert{\bar{d}_{k}}\right\rVert^{2}(|S_{k}|-1)}.$

Next, we present two numerical examples to demonstrate the capabilities of the
proposed algorithm. They are chosen within the general formulation of two-
stage stochastic optimization problems. The first example is a joint
production, pricing, and shipment problem that include both an online store
and some offline physical stores. A similar problem is presented in [23]. The
first-stage variable is the product price $p\in\mathbb{R}$ and production
quantity $x\in\mathbb{R}$ for an online store. The demand curve for the online
store is assumed to be deterministic and the demand for physical stores
stochastic. The second-stage variables are the production for each
factory/warehouse $i$ and the units shipped from factory/warehouse $i$ to
physical store location $j$, denoted as $y_{i},i=1,\dots,M$ and
$z_{ij},i=1,\dots,M,j=1,\dots,N$, respectively. Given supply chain
constraints, the last-minute production is deemed infeasible and a minimum
production and storage for each physical and online store is required. The
mathematical representation of this two-stage stochastic programming problem
is

######  Example 5.1.

(113) $\displaystyle\underset{x,p}{\text{minimize}}$
$\displaystyle(c_{1}-p)x+\mathbb{E}[R(p,\xi)]$ subject to $\displaystyle
10\geq p\geq 1,\ x\geq 1$ $\displaystyle x\leq\alpha_{1}p+\beta_{1}.$

The function $R(p,\xi)$ is the value function to the second-stage problem

(114) $\displaystyle R(p,\xi)\ =$
$\displaystyle\underset{y,z}{\text{minimize}}$ $\displaystyle
c_{2}^{T}y+\sum_{i=1}^{M}\sum_{j=1}^{N}(s_{ij}-p)z_{ij}$ subject to
$\displaystyle\sum_{i=1}^{M}z_{ij}\leq\alpha_{j}(\xi)p+\beta_{j}(\xi),\
j=1,\dots,N,$ $\displaystyle\sum_{j=1}^{N}z_{ij}\leq y_{i},\ i=1,\dots,M,$
$\displaystyle z\geq 0,\ y\geq 1.$

The number of factories is $M=5$ and the number of physical stores is $N=5$.
The first-stage cost per unit is $c_{1}=4.2$, which reflects the cost of both
production and shipping. For the second-stage, the unit production cost is
$c_{2}=[2.2,3.2,3.3,4.2,2.4]^{T}$ and the unit shipment cost from factory $i$
to store $j$, denoted as $s_{ij}$, is $s_{ij}=2$ for all $i=1,\dots,5$ and
$j=1,\dots,5$. The random demand slope $\alpha_{j}$ at store $j$ is generated
from truncated normal distribution on $[-1.5,-0.5]$, $[-2,-1]$, $[-2.5,-1.5]$,
$[-3,-2]$ and $[-2.5,-1.5]$ for $j=1,\dots,5$. The random intercepts follow
truncated normal distribution on $[16,17]$, $[21,22]$, $[26,27]$, $[31,32]$
and $[26,27]$. The price variable is bounded, reflected as $p\in[1,10]$.
Additionally, we set a lower bound on $x$ to keep the factory/warehouse
active.

For this example, the sample set $S_{k}$ at iteration $k$ can be written as
$\\{\xi_{1},\dots,\xi_{N_{k}}\\}$. The second-stage problem is coupled both in
constraint and objective with $p$. Therefore, function $R(\cdot,\xi)$ is a DC
(difference-of-convex) function and more importantly upper-$\mathcal{C}^{2}$
in $p$. To illustrate this point, we set $N_{k}=1000$ and compute the estimate
of $\mathbb{E}[R(p,\xi)]$ with
$\frac{1}{N_{k}}\sum_{i=1}^{N_{k}}R(p,\xi_{i})$. Moreover, given the affine
nature of the second-stage problem, it is possible to compute the analytic
(true) expression of $\mathbb{E}[R(p,\xi)]$ and
$g_{k}\in\bar{\partial}r(x_{k})$ for $r(p)$. Both the true value function and
subgradient are plotted in Figure 1. The true subgradient $g_{k}$ is later
used in establishing the error measure.

As shown in Figure 1, the function $r(p)$ is nonsmooth nonconvex and
upper-$\mathcal{C}^{2}$. Further, an accurate estimate of it can be
established with sufficient number of sample points. A similar plot is shown
in [23]. The constraints of the first-stage problem are affine, and therefore
Algorithm 1 can be applied. The parameters of the algorithms are
$\alpha_{0}=15$, $\eta=1$, $\eta_{\alpha}=1.5$, and $x_{0}=[1.5,1.5]$.

Figure 1: Value function and its subgradient computed with analytic expression
and average over $N_{k}=1000$ samples

We consider four different sampling strategies for Algorithm 1. Three of them
have fixed $N_{k}$ at values $10,100,500$ and the remaining one uses (111) to
adaptively update $N_{k}$, which is capped at $500$. The error at each step is
computed based on the stationary measure $\left\lVert{g_{k}-\nabla
c(x_{k})\lambda^{k}}\right\rVert$ with the true subgradient $g_{k}$. The
constraints $c(x_{k})$ come from the inequality constraints in (113) and the
optimal Lagrange multipliers $\lambda^{k+1}\in\mathbb{R}^{m}$ are obtained by
solving a least-square optimization problem

(115) $\displaystyle\underset{\lambda}{\text{minimize}}$
$\displaystyle\left\lVert{g_{k}-\nabla c(x_{k})\lambda}\right\rVert^{2}$
subject to $\displaystyle c_{j}(x_{k})\lambda_{j}=0,j=1,2,\cdots,m$
$\displaystyle\lambda\geq 0.$

Each sampling strategy is given a budget of $25000$ second-stage problem
solutions and we call every $500$ second-stage solves an epoch. The
convergence and cost results are plotted in Figure 2. The result indicates
that overall fixed sample sizes with SQP is able to solve nonsmooth nonconvex
optimization problem with upper-$\mathcal{C}^{2}$ objective. The larger the
sample size, the smaller the optimality error. Further, with adaptive
sampling, the same level of optimality measure as $N_{k}=500$ can be reached
with much fewer overall second-stage problem solutions and subgradient
evaluations. This is reflected by the fact that $N_{k}$ for adaptive sampling
increased from $2$ to the maximum value $500$ at around $20$ iterations (see
Figure 5) and the error peak occurs much sooner in the epoch plot of Figure 2
compared to the case with $N_{k}=500$.

Figure 2: Convergence and cost of Example 1 (Algorithm 1) with different
sampling strategies.

In the second example, we aim to apply the algorithm to SCACOPF problems.

######  Example 5.2.

(smoothed SCACOPF) Example 2 is a SCACOPF problem with coupling affine active
power constraint for contingency (second-stage) problems. The network data
used in this example is from the ARPA-E Grid Optimization competition [31].
The complete mathematical formulation is complex but the master (first-stage)
problem fits in the form of (9), where $r$ is the expectation of the recourse
function of the contingency problems. Details of the problem setup can be seen
in [31]. Using a quadratic penalty of the coupling constraints in the
contingency problems, $R(\cdot,\xi)$ becomes upper-$\mathcal{C}^{2}$ in $x$.
The problem is hence referred to as the smoothed SCACOPF.

For the purpose of demonstration, we consider a set of $350$ contingencies
that follow discrete uniform distribution. The random variable $\xi$ models an
integer that represents one of the contingencies. The objective $r(\cdot)$ is
thus the average of $R(x,\xi_{i}),i=1,\cdots,350$ and is
upper-$\mathcal{C}^{2}$. Hence, the true objective and subgradient can be
obtained by going through exhaustively the complete set of contingencies. We
point out that for contingency problems that employs more complex probability
distribution, the true objective would be unavailable. Based on the problems,
the parameters of Algorithm 2 are set to $\alpha_{0}=5\times 10^{6}$,
$\eta_{\alpha}=1.5$, $\gamma=10$, $\eta_{\beta}=0.2$, $\nu=1$, and
$\eta=10^{5}$.

Four sampling strategies are compared with three fixed sample sizes
$15,50,150$ and the adaptive one proposed in the paper. An upper limit of
$150$ is imposed on the sample size $N_{k}$ in the adaptive sampling
algorithm. All four tests run for at least 200 iterations. The constraints are
satisfied by all four runs to acceptable levels. At each iteration of the
algorithms, the true objectives are evaluated and plotted in Figure 3. It is
clear that increasing the sample size provides a more stable reduction in the
objective value as expected. With a sample size of $150$, which is smaller
than the number of discrete random values, the oscillation from the stochastic
algorithm gradually reaches a tolerable level. Smaller sample sizes still
manage to reduce objective but cannot produce stabilized results. Figure 4
plots the first $4500$ contingency problem solutions and it is clear that the
adaptive sampling strategy successfully generates decrease rather quickly
while follow a stable path later on as designed.

Figure 3: Objective v.s. iteration for Example 2 (Algorithm 2) with different
sampling strategies. Figure 4: Objective v.s. epoch for Example 2 (Algorithm
2) with different sampling strategies. Figure 5: Sample size plots for both
examples.

The evolution of sample size of $S_{k}$ for both examples are shown in Figure
5. The result of example 2 encourages the application of adaptive sampling to
SCACOPF problems that might be too large to be solved conventionally or that
have a more complicated probability distribution for $\xi$.

##  6 Conclusions

In this paper, we have proposed and analyzed an adaptive sampling stochastic
optimization algorithm for constrained nonsmooth, nonconvex optimization
problems with upper-$\mathcal{C}^{2}$ objectives. A range of important
problems fit the mathematical setup, particularly two-stage stochastic
optimization problems. The proposed algorithms help to fill the gap of
nonsmooth stochastic optimization algorithms with adaptive sampling.
Furthermore, both equality and inequality constraints are considered in the
work, where problems with and without smooth equality constraints are
discussed separately with two distinct algorithms. Both algorithms formulate a
convex quadratic programming subproblem at each iteration based on stochastic
approximation of the objective. The equality constrained problem requires
additional, carefully designed line search step in order to ensure overall
progress in theory. Global convergence analysis of the proposed pair of
algorithms with respect to expectation is provided using widely adopted
assumptions. The adaptive nature of some of the assumptions can be used in
practice to design adaptive sampling steps while maintaining the convergence
properties. The algorithms can be viewed as an extension of stochastic SQP.

## Acknowledgments

Prepared by LLNL under Contract DE-AC52-07NA27344. This document was prepared
as an account of work sponsored by an agency of the United States government.
Neither the United States government nor Lawrence Livermore National Security,
LLC, nor any of their employees makes any warranty, expressed or implied, or
assumes any legal liability or responsibility for the accuracy, completeness,
or usefulness of any information, apparatus, product, or process disclosed, or
represents that its use would not infringe privately owned rights. Reference
herein to any specific commercial product, process, or service by trade name,
trademark, manufacturer, or otherwise does not necessarily constitute or imply
its endorsement, recommendation, or favoring by the United States government
or Lawrence Livermore National Security, LLC. The views and opinions of
authors expressed herein do not necessarily state or reflect those of the
United States government or Lawrence Livermore National Security, LLC, and
shall not be used for advertising or product endorsement purposes.

## References

  * [1] L. T. H. An and P. D. Tao, DC programming and DCA: thirty years of developments, Mathematical Programming, 169 (2018), pp. 5–68.
  * [2] A. S. Berahas, R. Bollapragada, and B. Zhou, An adaptive sampling sequential quadratic programming method for equality constrained stochastic optimization, 2022, https://arxiv.org/abs/2206.00712.
  * [3] A. S. Berahas, F. E. Curtis, D. Robinson, and B. Zhou, Sequential quadratic optimization for nonlinear equality constrained stochastic optimization, SIAM J. Optim., 31 (2021), pp. 1352–79.
  * [4] J. R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer-Verlag, New York, 1997.
  * [5] D. Boob, Q. deng, and G. Lan, Level constrained first order methods for function constrained optimization, 05 2022, https://doi.org/10.48550/arXiv.2205.08011.
  * [6] L. Bottou, Stochastic gradient descent tricks, in Neural networks: Tricks of the trade, Springer, 2012, pp. 421–436.
  * [7] R. H. Byrd, G. M. Chin, and J. N. et al, Sample size selection in optimization methods for machine learning, Math. Program., (2012), pp. 127–155.
  * [8] R. G. Carter, On the global convergence of trust region algorithms using inexact gradient information, SIAM Journal on Numerical Analysis, 28 (1991), p. 251–265.
  * [9] N. Chiang, C. G. Petra, and V. M. Zavala, Structured nonconvex optimization of large-scale energy systems using pips-nlp, in 2014 Power Systems Computation Conference, 2014, pp. 1–7.
  * [10] F. Clarke, Optimization and Nonsmooth Analysis, John Wiley & Sons New York, 1983.
  * [11] Y. Cui and J. S. Pang, Modern Nonconvex Nondifferentiable Optimization, Society for Industrial and Applied Mathematics, 2021.
  * [12] A. Daniilidis and P. Georgiev, Approximate convexity and submonotonicity, Journal of Mathematical Analysis and Applications, 291 (2004), p. 292–301.
  * [13] M. Dao, J. Gwinner, D. Noll, and N. Ovcharova, Nonconvex bundle method with application to a delamination problem, Computational Optimization and Applications, 65 (2016).
  * [14] D. Davis and B. Grimmer, Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems, SIAM Journal on Optimization, 29 (2019), p. 1908–1930.
  * [15] W. Hare, C. Sagastizabal, and M. Solodov, A proximal bundle method for nonsmooth nonconvex functions with inexact information, Computational Optimization and Applications, 63 (2015).
  * [16] W. Hare and C. Sagastizábal, A redistributed proximal bundle method for nonconvex optimization, SIAM J. Optim., 20 (2010), pp. 2442–73.
  * [17] P. Kall and S. W. Wallace, Stochastic Programming, John Wiley & Sons, Chichester, 2nd ed., 1994.
  * [18] K. Kiwiel, Restricted step and levenberg-marquardt techniques in proximal bundle methods for nonconvex nondifferentiable optimization, SIAM J. Optim., 6 (1996), pp. 227–249.
  * [19] D. P. Kouri and T. M. Surowiec, A primal–dual algorithm for risk minimization, Math. Program., (2022), pp. 337–363.
  * [20] C. Lemaréchal, Bundle methods in nonsmooth optimization, in Nonsmooth optimization (Proc. IIASA Workshop, Laxenburg, 1977), vol. 3, Pergamon, Oxford, 1978, pp. 79–102.
  * [21] C. Lemaréchal and C. Sagastizabal, Variable metric bundle methods: From conceptual to implementable forms, Math. Program., 76 (1996), pp. 393–410.
  * [22] J. Liu, Y. Cui, and J.-S. Pang, Solving nonsmooth and nonconvex compound stochastic programs with applications to risk measure minimization, Mathematics of Operations Research, 47 (2022).
  * [23] J. Liu, Y. Cui, J. S. Pang, and S. Sen, Two-stage stochastic programming with linearly bi-parameterized quadratic recourse, SIAM J. Optim., 30 (2020), p. 2530–2558.
  * [24] B. Mordukhovich, Necessary conditions in nonsmooth minimization via lower and upper subgradients, Set-Valued Analysis, 12 (2004), pp. 163–193.
  * [25] M. M. Mäkelä and P. Neittaanmäki, Nonsmooth Optimization, WORLD SCIENTIFIC, 1992.
  * [26] A. Nedic and S. Lee, On stochastic subgradient mirror-descent algorithm with weighted averaging, SIAM Journal on Optimization, 24 (2014), pp. 84–107.
  * [27] Y. Nesterov, Introductory lectures on convex optimization: A basic course, Springer New York, NY, 2003.
  * [28] D. Noll, Cutting plane oracles to minimize non-smooth non-convex functions, Set-Valued and Variational Analysis, 18 (2009), pp. 531–568.
  * [29] D. Noll, Bundle method for non-convex minimization with inexact subgradients and function values, Springer Proceedings in Mathematics and Statistics, 50 (2013).
  * [30] W. Oliveira, C. Sagastizábal, and S. Scheimberg, Inexact bundle methods for two-stage stochastic programming, SIAM Journal on Optimization, 21 (2011), p. 517–544.
  * [31] C. G. Petra and I. Aravena, Solving realistic security-constrained optimal power flow problems, Operations Research, submitted (2021).
  * [32] C. G. Petra, O. Schenk, and M. Anitescu, Real-time stochastic optimization of complex energy systems on high performance computers, Computing in Science and Engineering, 99 (2014), pp. 1–9.
  * [33] C. G. Petra, O. Schenk, M. Lubin, and K. Gärtner, An augmented incomplete factorization approach for computing the Schur complement in stochastic optimization, SIAM Journal on Scientific Computing, 36 (2014), pp. C139–C162.
  * [34] W. Qiu, A. J. Flueck, and F. Tu, A parallel algorithm for security constrained optimal power flow with an interior point method, in IEEE Power Engineering Society General Meeting, 2005, 2005, pp. 447–453 Vol. 1.
  * [35] S. S. Ram, A. Nedić, and V. V. Veeravalli, Incremental stochastic subgradient algorithms for convex optimization, SIAM Journal on Optimization, 20 (2009), pp. 691–717.
  * [36] H. Robbins and D. Siegmund, A convergence theorem for non negative almost supermartingales and some applications, in Optimizing Methods in Statistics, Academic Press, 1971, p. 233–257.
  * [37] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer-Verlag, Berlin Heidelberg, 1998.
  * [38] H. Schramm and J. Zowe, A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM J. Optim., 2 (1992), pp. 121–152.
  * [39] A. Shapiro, D. Dentcheva, and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, Second Edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014.
  * [40] N. Z. Shor, Minimization methods for non-differentiable functions, Springer-Verlag, Berlin Heidelberg, 3 ed., 1985.
  * [41] J. Spingarn, Submonotone subdifferentials of lipschitz functions, Transactions of the American Mathematical Society, 264 (1981), pp. 77–89.
  * [42] J. Wang, N. Y. Chiang, and C. G. Petra, An asynchronous distributed-memory optimization solver for two-stage stochastic programming problems, in 20th International Symposium on Parallel and Distributed Computing (ISPDC), IEEE, Jul 2021, pp. 33–40.
  * [43] J. Wang and C. G. Petra, A simplified nonsmooth nonconvex bundle method with applications to security-constrained acopf problems, 2022, https://arxiv.org/abs/arXiv:2203.17215.