Hilbert-valued perturbed subgradient algorithms

被引:28
作者
Barty, Kengy
Roy, Jean-Sebastien
Strugarek, Cyrille
机构
[1] EDF R&D, F-92141 Clamart, France
[2] Ecole Natl Ponts & Chaussees, F-77455 Champ Sur Marne 2, Marne La Vallee, France
关键词
stochastic quasigradient; perturbed subgradient; infinite dimensional problems; nonsmooth optimization;
D O I
10.1287/moor.1070.0253
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
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.
引用
收藏
页码:551 / 562
页数:12
相关论文
共 30 条
[1]   On the projected subgradient method for nonsmooth convex optimization in a Hilbert space [J].
Alber, YI ;
Iusem, AN ;
Solodov, MV .
MATHEMATICAL PROGRAMMING, 1998, 81 (01) :23-35
[2]  
[Anonymous], 1982, SEMIMARTINGALES
[3]  
BARTY K, 2005, STOCHASTIC PROGRAMMI, V16
[4]  
Benveniste A, 1990, Adaptive algorithms and stochastic approximations
[5]  
BERLIOCCHI H, 1972, CR ACAD SCI PARIS A, V274, P1623
[6]   Gradient convergence in gradient methods with errors [J].
Bertsekas, DP ;
Tsitsiklis, JN .
SIAM JOURNAL ON OPTIMIZATION, 2000, 10 (03) :627-642
[7]  
CHEN X, 1998, ECONOMETRIC THEORY, V12, P284
[8]  
Chen XH, 2002, STUD NONLINEAR DYN E, V6
[9]  
Clark D., 1978, STOCHASTIC APPROXIMA
[10]   DECOMPOSITION COORDINATION ALGORITHMS IN STOCHASTIC OPTIMIZATION [J].
CULIOLI, JC ;
COHEN, G .
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1990, 28 (06) :1372-1403