|
Article Excerpt
We propose a Hilbert-valued perturbed subgradient algorithm with stochastic noises, and we provide a convergence proof for this algorithm under classical assumptions on the descent direction and new assumptions on the stochastic noises. Instead of requiring the stochastic noises to correspond to martingale increments, we only require these noises to be asymptotically so. Furthermore, the variance of these noises is allowed to grow infinitely under the control of a decreasing sequence linked with the subgradient stepsizes. This algorithm can be used to solve stochastic closed-loop control problems without any a priori discretization of the uncertainty, such as linear decision rules or tree representations. It can also be used as a way to perform stochastic dynamic programming without state-space discretization or a priori functional bases (i.e., approximate dynamic programming). Both problems arise frequently--for example, in power systems scheduling or option pricing. This article focuses on the theorical foundations of the algorithm, and gives references to detailed practical experimentations.
Key words: stochastic quasigradient; perturbed subgradient; infinite dimensional problems; nonsmooth optimization
**********
1. Introduction. Infinite dimensional optimization problems typically appear in the field of stochastic programming or stochastic dynamic programming. In these research fields, the variable of interest is functional, because it is either an optimal control variable (feedback) or Bellman functions. Power systems scheduling as well as option pricing involve this type of difficulties. There is, hence, a big challenge in proposing efficient methods for solving infinite dimensional problems. Essentially, solutions of such problems can only be estimated, and a natural way to solve these problems is to use stochastic approximation.
The field of stochastic approximation theory actually began with the seminal paper of Robbins and Monro [27]. Thanks to the various and numerous applications, stochastic approximation has been studied very thoroughly, and the results, either general or more applied, are today well known, especially in the case of finite dimensional stochastic approximation (see, e.g., Lai [21] for an historical survey of stochastic approximation, or Duflo [13] for the many branches of this field, or Nevel'son and Has'minskii [23] for their important monograph).
A lot of various assumptions on stochastic approximation algorithms already exist: Our goal is not to make this field more complicated but to propose some new general assumptions particularly adapted to stochastic optimal control and infinite dimensional problems. The study of Hilbert-valued stochastic approximations has also been developed, for example by Revesz [25, 26], Salov [29], and, further, by Goldstein [17]. An important progress in this area is the paper by Yin and Zhu [30], showing the convergence and giving asymptotic properties of a Hilbert-valued Robbins-Monro algorithm under assumptions that mimick usual finite-dimensional assumptions. However, in all these cases, it is not possible to take into account a projection onto a convex subset during the iterations of the algorithms. The important work presented in Hiriart-Urruty [18] studies the role of stochastic approximation to solve general Hilbert-valued variational equations, using both probabilistic and variational arguments. In those infinite-dimensional papers, the noise assumptions are practically impossible to verify.
Our work aims to bring some other assumptions to ensure the convergence of stochastic approximation procedure in the general framework of infinite dimensional Hilbert spaces. It has been motivated by the practical need to propose efficient ways to solve infinite dimensional stochastic optimization problems.
Indeed, most of the existing results cannot be practically applied in infinite dimensional optimization problems such as stochastic programming or stochastic dynamic programming. The existing results are either available only in a finite dimensional setting, or their assumptions are not practically implementable for infinite dimensional problems.
Convergence proofs of stochastic approximation algorithms exist from various point of views. Historically, convergence proofs were given through the so-called Robbins-Siegmund lemma (see Robbins and Siegmund [28]); those proofs have been developed by, e.g., Benveniste et al. [3] or Polyak and Tsypkin [24]. Other approaches have been developed successfully: In the well-known monograph by Clark and Kushner [8], a stability analysis is developed; the method based on the analysis of the underlying ordinary differential equation, introduced by Derevitskii and Fradkov [12], is thoroughly studied. This method has been used in, e.g., Yin and Zhu [30] to derive their infinite dimensional convergence results. Following the same direction, thanks to general results on Hilbert-valued mixingales (see Chen and White [6]), the recent paper by Chen and White [7] provides a comprehensive framework for infinite dimensional Robbins-Monro type procedures. They use modified stochastic approximation with boundedness properties to derive almost sure convergence results and asymptotic normality. Starting from the same ideas, we can also mention Horn and Kulkarni [19] or Deylon [11], founded on deterministic arguments, but limited to the finite dimensional case. Another original approach valid for the finite dimensional setting is proposed in Bertsekas and Tsitsiklis [5]. Among those approaches, we will follow in this paper an approach more based on probabilistic martingale or quasimartingale arguments (see Metivier [22]).
In this paper, we focus on the theoretical and general setting of the stochastic approximation procedure we suggest, centered on the solution of stochastic optimization problems. The paper by Hiriart-Urruty [18] is the nearest to ours with regard to the techniques used in the proofs and the problems it adresses, but the results are significantly different from ours. The biggest difference is the explicit introduction in our paper of stochastic noises that are not martingale increments from the beginning, but are only asymptotically so. The assumptions made in Hiriart-Urruty [18, Theorems 5.1 and 5.2] involve the whole sequence of the noises, and can hence be difficult to verify. Starting from the same ideas, we propose other assumptions that lead to the same result but involve only instantaneous perturbations and are more verifiable practically.
The results of Chen and White [7] differ from ours in that they are not robust to any projection, except the projection on a particular finite dimensional subspace of the original Hilbert space; they focus on modified stochastic approximation procedures with boundedness properties; they provide more restrictive assumptions on the perturbation sequences, and they need the differentiability of the cost function, whereas we need only subgradients.
Our paper is organized as follows. Section 3 adresses nonsmooth minimization problems. We provide in [section]3.2 a convergence proof with general assumptions. In [section]3.3, we place our result in the context of stochastic approximation and projected subgradient algorithms, and we especially compare it with the result of Alber et al. [1]. In [section]3.4, we show how our results can be...
|
