TY - GEN

T1 - Convex nondifferentiable stochastic optimization

T2 - A local randomized smoothing technique

AU - Yousefian, Farzad

AU - Nedić, Angelia

AU - Shanbhag, Uday V.

PY - 2010

Y1 - 2010

N2 - We consider a class of stochastic nondifferentiable optimization problems where the objective function is an expectation of a random convex function, that is not necessarily differentiable. We propose a local smoothing technique, based on random local perturbations of the objective function, that lead to differentiable approximations of the function. Under the assumption that the local randomness originates from a uniform distribution, we establish a Lipschitzian property for the gradient of the approximation. This facilitates the development of a stochastic approximation framework, which now requires sampling in the product space of the original measure and the artificially introduced distribution. We show that under suitable assumptions, the resulting diminishing steplength stochastic subgradient algorithm, with two samples per iteration, converges to an optimal solution of the problem when the subgradients are bounded.

AB - We consider a class of stochastic nondifferentiable optimization problems where the objective function is an expectation of a random convex function, that is not necessarily differentiable. We propose a local smoothing technique, based on random local perturbations of the objective function, that lead to differentiable approximations of the function. Under the assumption that the local randomness originates from a uniform distribution, we establish a Lipschitzian property for the gradient of the approximation. This facilitates the development of a stochastic approximation framework, which now requires sampling in the product space of the original measure and the artificially introduced distribution. We show that under suitable assumptions, the resulting diminishing steplength stochastic subgradient algorithm, with two samples per iteration, converges to an optimal solution of the problem when the subgradients are bounded.

KW - Local smoothing technique

KW - Nondifferentiable convex minimization

KW - Stochastic approximation method

UR - http://www.scopus.com/inward/record.url?scp=77957824010&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77957824010&partnerID=8YFLogxK

U2 - 10.1109/acc.2010.5530908

DO - 10.1109/acc.2010.5530908

M3 - Conference contribution

AN - SCOPUS:77957824010

SN - 9781424474264

T3 - Proceedings of the 2010 American Control Conference, ACC 2010

SP - 4875

EP - 4880

BT - Proceedings of the 2010 American Control Conference, ACC 2010

PB - IEEE Computer Society

ER -