Abstract
In many instances, the exact evaluation of an objective function and its subgradients can be computationally demanding. By way of example, we cite problems that arise within the context of stochastic optimization, where the objective function is typically defined via multi-dimensional integration. In this paper, we address the solution of such optimization problems by exploring the use of successive approximation schemes within subgradient optimization methods. We refer to this new class of methods as inexact subgradient algorithms. With relatively mild conditions imposed on the approximations, we show that the inexact subgradient algorithms inherit properties associated with their traditional (i.e., exact) counterparts. Within the context of stochastic optimization, the conditions that we impose allow a relaxation of requirements traditionally imposed on steplengths in stochastic quasi-gradient methods. Additionally, we study methods in which steplengths may be defined adaptively, in a manner that reflects the improvement in the objective function approximations as the iterations proceed. We illustrate the applicability of our approach by proposing an inexact subgradient optimization method for the solution of stochastic linear programs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S. Agmon, “The relaxation method for linear inequalities”,Canadian Journal of Mathematics 6 (1954) 382–392.
E. Allen, R. Helgason, J. Kennington and B. Shetty, “A generalization of Polyak's result for subgradient optimization,”Mathematical Programming 37 (1987) 309–317.
H. Attouch,Variational Convergence for Functions and Operators (Pitman, Boston, MA, 1984).
J.R. Birge and L. Qi, “Computing block angular Karmarkar projections with applications to stochastic programming,”Management Science 34 (1988) 1472–1479.
J.R. Birge and R.J.-B. Wets, “Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse,”Mathematical Programming Study 27 (1986) 54–102.
G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princteon, NJ, 1963).
Y. Ermoliev, “Stochastic quasigradient methods,” in: Y. Ermoliev and R.J.-B. Wets, eds.,Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988) pp. 141–185.
M.L. Fisher, “Lagrangian relaxation method for solving integer programming,”Management Science 27 (1981) 1–18.
K. Frauendorfer, “Solving SLP recourse problems with arbitrary multivariate distributions—the dependent case,”Mathematics of Operations Research 13 (1988) 377–394.
A.A. Gaivoronski, “Approximation methods of solution of stochastic programming problems,”Cybernetics 18 (1982) 241–249.
A.A. Gaivoronski, A. Golodnikov and L.D. Fung, “Solution of limiting extremal problems for minimizing functional,”Cybernetics 16 (1980) 97–103.
A.A. Gaivoronski and L. Nazareth, “Combining generalized programming and sampling techniques for stochastic programs with recourse,” in: G.B. Dantzig and P. Glynn, eds.,Proceedings of the Workshop on Resource Planning Under Uncertainty in Electric Power Systems (Stanford University, Stanford, CA, 1989) pp. 141–158.
M. Held, P. Wolfe and H.P. Crowder, “Validation of subgradient optimization,”Mathematical Programming 6 (1974) 62–88.
J.L. Higle and S. Sen, “Stochastic Decomposition: An algorithm for stage linear programs with recourse,”Mathematics of Operations Research 16 (1991a) 650–669.
J.L. Higle and S. Sen, “Statistical verification of optimality conditions,”Annals of Operations Research 30 (1991b) 215–240.
J.L. Higle and S. Sen, “On the convergence of algorithms, with implications for stochastic and nondifferentiable optimization,”Mathematics of Operations Research 17 (1992) 112–131.
J.-B. Hiriart-Urruty, “Contributions à la programmation mathématique: cas déterministe et stochastique,” Ph.D. Thesis, Université de Clermont II (Aubière, France, 1977).
G. Infanger, “Monte Carlo (importance) sampling within a Benders' decomposition for stochastic linear programs,” Technical Report, SOL 89-13, Department of Operations Research, Stanford University (Stanford, CA, 1989).
A.J. King and R.J.-B. Wets, “Epi-consistency of convex stochastic programs,”Stochastics and Stochastics Reports 34 (1991) 83–92.
H.J. Kushner and D.S. Clark,Stochastic Approximations Methods for Constrained and Unconstrained Systems (Springer, Berlin, 1978).
C. Lemaréchal, “Nonsmooth optimization and descent methods,” Technical Report RR-78-4, International Institute for Applied Systems Analysis (Laxenberg, Austria, 1978).
K. Marti and E. Plochinger, “Optimal step sizes in semi-stochastic approximation procedures. I II,”Optimization 21 (1990) 123–153 and 21 (1990) 281–312.
T. Motzkin and I.J. Schoenberg, “The relaxation method for linear inequalities,”Canadian Journal of Mathematics 6 (1954) 393–404.
B.T. Poljak, “A general method for solving extremum problems,”Soviet Mathematics Doklady 8 (1976) 593–597.
R.T. Rockafellar and R.J.-B. Wets, “Scenarios and policy aggregation in optimization under uncertainty,”Mathematics of Operations Research 16 (1991) 119–147.
A. Ruszczynski, “A linearization method for nonsmooth stochastic programming problems,”Mathematics of Operations Research 12 (1987) 32–49.
S. Sen and H.D. Sherali, “A class of convergent primal-dual subgradient algorithms for decomposable convex programs,”Mathematical Programming 35 (1986) 279–297.
N.Z. Shor,Minimization Methods for Nondifferentiable Functions (Springer, Berlin, 1985).
S. Urasiev, “Adaptive stochastic quasigradient methods,” in: Y. Ermoliev and R.J.-B. Wets, eds.,Numerical Techniques for Stochatic Optimization (Springer, Berlin, 1988) pp. 373–392.
R. Van Slyke and R.J.-B. Wets, “L-Shaped linear programs with application to optimal control and stochastic programming,”SIAM Journal on Applied Mathematics 17 (1969) 638–663.
R.J.-B. Wets, “Stochastic programming: solution techniques and approximation schemes”, in: A. Bachem, M. Grötschel and B. Korte, eds.,Mathematical Programing: The State of the Art, 1982 (Springer, Berlin, 1982) pp. 566–603.
Author information
Authors and Affiliations
Additional information
This work was supported by Grant Nos. NSF-DDM-89-10046 and NSF-DDM-9114352 from the National Science Foundation.
Rights and permissions
About this article
Cite this article
Au, K.T., Higle, J.L. & Sen, S. Inexact subgradient methods with applications in stochastic programming. Mathematical Programming 63, 65–82 (1994). https://doi.org/10.1007/BF01582059
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582059