This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Barty, K. Articles by Strugarek, C. Search for Related Content

Hilbert-Valued Perturbed Subgradient Algorithms

EDF R&D, 1, avenue du Géné ral de Gaulle, F-92141 Clamart Cedex, France
EDF R&D, 1, avenue du Géné ral de Gaulle, F-92141 Clamart Cedex, France
École Nationale des Ponts et Chaussées, 5-7, avenue Blaise Pascal, Cité Descartes, Champs-sur-Marne, F-77455 Marne-la-Vallée Cedex 2, France
kengy.barty{at}edf.fr
jean-sebastien.roy{at}edf.fr
strugare{at}cermics.enpc.fr

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
History: Received: January 16, 2006; revision received: June 7, 2006;