More Web Proxy on the site http://driver.im/

article

Upper Bounds on the Expected Value of a Convex Function Using Gradient and Conjugate Function Information

Authors:

Marc TeboulleAuthors Info & Claims

Mathematics of Operations Research, Volume 14, Issue 4

Pages 745 - 759

https://doi.org/10.1287/moor.14.4.745

Published: 01 November 1989 Publication History

Abstract

New upper bounds are given for the expected value of a convex function. The bounds employ subgradient information and the conjugate function. In contrast to most other bounds, explicit moment information is not needed. We derive the bounds and compare them with previous bounds with different information requirements.

References

[1]

Arrow, K. J. (1971). Essay on the Theory of Risk-Bearing. Markham Publishing, Chicago.

[2]

Ben-Tal. A. and Hochman, E. (1972). More Bounds on the Expectation of a Convex Function. J. Appl. Prohab. 9 803-812.

[3]

Birge, J. R. and Wets, R. J. B (1986). Designing Approximations Schemes for Stochastic Optimization Problems, in Particular for Stochastic Programs with Recourse. Math. Programming Studies 27 54-102.

[4]

Birge, J. R. and Wets, R. J. B. (1986). A Sublinear Approximation Method for Stochastic Programming. Tech. Rep. 86-26. Department of Industrial and Operations Engineering. University of Michigan.

[5]

Birge, J. R. and Wets, R. J. B. (1987). Computing Bounds for Stochastic Programming Problems by Means of a Generalized Moment Problem. Math. Oper. Res. 12 149-162.

Digital Library

[6]

Cipra, T. Moment Problem with Given Covariance Structure in Stochastic Programming. Casopis Pest. Mat. (to appear).

[7]

Dempster, M. A. H. (1980). Stochastic Programming. Academic Press, London.

[8]

Dula, J. H. (1986). Bounds on the Expectation of Convex Function. Ph.D thesis, The University of Michigan, Ann Arbor.

[9]

Edmundson, H. P. (1956). Bounds on the Expectation of a Convex Function. Tech. Rep. 9B2. The Rand Corporation, Santa Monica.

[10]

Ermoliev, Y., Gaivoronsky, A. and Nedeva, C. (1985). Stochastic Optimization Problems with Partially Known Distribution Functions. SIAM J. Control Optim. 23 696-716.

[11]

Fishburn, P. C. (1970). Utility Theory for Decision Making. R. E. Krieger, Huntington, NY.

[12]

Frauendorfer, K. (1986). Solving S.L.P. Recourse Problems with Arbitrary Multivariate Distributions: The Dependent Case. Tech. Rep., Institut fuer Operations Research Zurich.

[13]

Gassmann, H. and Ziemba, W. (1986). A Tight Upper Bound for the Expectation of a Convex Function of a Multivariate Random Variable. Math. Programming Studies 27 39-53.

[14]

Gradshteyn, I. S. and Ryzhik, I. M. (1980). Table of Integrals. Series and Products. Academic Press, New York.

[15]

Hammond, J. S. (1974). Simplifying the Choice between Uncertainty Prospects Where Preference Is Nonlinear Management Sci. 20 1047-1072.

[16]

Karlin, S. and Rinott, Y. (1981). Univariate and Multivariate Total Positively, Generalized Convexity and Related Inequalities in Generalized Concavity in Optimization and Economics S. Shaible and W. T. Ziemba (Eds.), Academic Press, New York.

[17]

Madansky, A. (1959). Bounds on the Expectation of a Convex Function of a Multivariate Random Variable. Am. Math. Statist. 30 743-746.

[18]

Pratt, J. W. (1964). Risk Aversion in the Small and in the Large. Econometrica 32 122-136.

[19]

Prekopa, A. (1986). Sharp Bounds on Probabilities Using Linear Programming. RUTCOR Research Rep. 19-86. Rutgers University, New Brunswick. NJ.

[20]

Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press, Princeton, NJ.

[21]

Wets, R. J. B. (1974). Stochastic Programs with Fixed Recourse: The Equivalent Deterministic Program. SIAM Rev. 16 309-339.

[22]

Wilson, R. (1968). The Theory of Syndicates. Econometrica 36 119-132.

Cited By

Pierre-Louis PBayraksan GMorton D(2011)A combined deterministic and sampling-based sequential bounding method for stochastic programmingProceedings of the Winter Simulation Conference10.5555/2431518.2432016(4172-4183)Online publication date: 11-Dec-2011
https://dl.acm.org/doi/10.5555/2431518.2432016
Varakantham PSmith S(2008)Linear relaxation techniques for task management in uncertain settingsProceedings of the Eighteenth International Conference on International Conference on Automated Planning and Scheduling10.5555/3037281.3037327(363-371)Online publication date: 14-Sep-2008
https://dl.acm.org/doi/10.5555/3037281.3037327
Edirisinghe N(1996)New Second-Order Bounds on the Expectation of Saddle Functions with Applications to Stochastic Linear ProgrammingOperations Research10.1287/opre.44.6.90944:6(909-922)Online publication date: 1-Dec-1996
https://dl.acm.org/doi/10.1287/opre.44.6.909

Index Terms

Upper Bounds on the Expected Value of a Convex Function Using Gradient and Conjugate Function Information
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
  2. Probability and statistics
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

An upper bound on the expected value of a non-increasing convex function with convex marginal return functions

In this note, we show that if a convex function is non-increasing and has a special property we call convex marginal return functions, an effective upper bound can be established using only two function evaluations. Further, we show that this bound can ...
Some bounds for the renewal function and the variance of the renewal process
Highlights
- A new improved general lower bound for the renewal function.
- Improved upper and ...
Abstract
Renewal equations are frequently encountered in several applications when regenerative arguments are used in modelling. Since, these equations usually do not have analytical solutions, bounds have a great practical importance. The aim ...
Bounds on the Number of Pseudothreshold Functions

Upper and lower bounds are derived for the number of pseudothreshold functions of n variables. (Pseudothershold logic is a generalization of threshold logic.) It is shown that a lower bound on the number of pseudothreshold functions P(n) of exactly n ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematics of Operations Research

Mathematics of Operations Research Volume 14, Issue 4

November 1989

190 pages

ISSN:0364-765X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 November 1989

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pierre-Louis PBayraksan GMorton D(2011)A combined deterministic and sampling-based sequential bounding method for stochastic programmingProceedings of the Winter Simulation Conference10.5555/2431518.2432016(4172-4183)Online publication date: 11-Dec-2011
https://dl.acm.org/doi/10.5555/2431518.2432016
Varakantham PSmith S(2008)Linear relaxation techniques for task management in uncertain settingsProceedings of the Eighteenth International Conference on International Conference on Automated Planning and Scheduling10.5555/3037281.3037327(363-371)Online publication date: 14-Sep-2008
https://dl.acm.org/doi/10.5555/3037281.3037327
Edirisinghe N(1996)New Second-Order Bounds on the Expectation of Saddle Functions with Applications to Stochastic Linear ProgrammingOperations Research10.1287/opre.44.6.90944:6(909-922)Online publication date: 1-Dec-1996
https://dl.acm.org/doi/10.1287/opre.44.6.909

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents