zbMATH — the first resource for mathematics

A simple randomised algorithm for convex optimisation. Application to two-stage stochastic programming. (English) Zbl 1297.90116
Summary: We consider maximising a concave function over a convex set by a simple randomised algorithm. The strength of the algorithm is that it requires only approximate function evaluations for the concave function and a weak membership oracle for the convex set. Under smoothness conditions on the function and the feasible set, we show that our algorithm computes a near-optimal point in a number of operations which is bounded by a polynomial function of all relevant input parameters and the reciprocal of the desired precision, with high probability. As an application to which the features of our algorithm are particularly useful we study two-stage stochastic programming problems. These problems have the property that evaluation of the objective function is \(\#\mathrm P\)-hard under appropriate assumptions on the models. Therefore, as a tool within our randomised algorithm, we devise a fully polynomial randomised approximation scheme for these function evaluations, under appropriate assumptions on the models. Moreover, we deal with smoothing the feasible set, which in two-stage stochastic programming is a polyhedron.

90C25 Convex programming
90C15 Stochastic programming
68W20 Randomized algorithms
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Applegate, D., Kannan, R.: Sampling and integration of near log-concave functions. In: Proceedings of the 23th ACM Symposium on the Theory of Computing, pp. 156-163 (1990)
[2] Beale, EM, On minimizing a convex function subject to linear inequalities, J. R. Stat. Soc., 17, 173-184, (1955) · Zbl 0068.13701
[3] Bertsimas, D; Vempala, S, Solving convex programs by random walks, JACM, 51, 540-556, (2004) · Zbl 1204.90074
[4] Birge, J., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York (1997) · Zbl 0892.90142
[5] Dantzig, G, Linear programming under uncertainty, Manag. Sci., 1, 197-206, (1955) · Zbl 0995.90589
[6] Dupačovà, J; Wets, RJ-B, Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems, Ann. Stat., 16, 1517-1549, (1988) · Zbl 0667.62018
[7] Dyer, M., Frieze, A.: Computing the volume of convex bodies: a case where randomness provably helps. In: Probabilistic Combinatorics and its Applications. Proceedings of AMS Symposia in Applied Mathematics, vol. 44, pp. 123-169 (1991) · Zbl 0754.68052
[8] Dyer, M; Frieze, A; Kannan, R, A random polynomial time algorithm for approximating the volume of convex bodies, JACM, 38, 1-17, (1991) · Zbl 0799.68107
[9] Dyer, M., Kannan, R., Stougie, L.A.: Simple algorithm randomised algorithm for convex optimis; Application to two-stage stochastic programming. Technical Report SPOR-Report 2002-2005, Department of Mathematics and Computer Science, Eindhoven Tecnical Universtiy, Eindhoven (2002) · Zbl 1326.90059
[10] Dyer, M; Stougie, L, A note on the complexity of some stochastic optimization problems, Math. Program., 106, 423-432, (2006) · Zbl 1134.90027
[11] Ermoliev, Y; Shor, NZ, Method of random walk for the two-stage problem of stochastic programming and its generalization, Kibernetica, 4, 59-60, (1968)
[12] Ermoliev, Y., Wets, R.J.-B. (eds.): Numerical Techniques for Stochastic Optimization. Springer, Berlin (1988) · Zbl 0658.00020
[13] Grötschel, M., Lovasz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, New York (1988) · Zbl 0634.05001
[14] Higle, JL; Sen, S, Stochastic decomposition: an algorithm for two stage linear programs with recourse, Math. Oper. Res., 16, 650-699, (1991) · Zbl 0746.90045
[15] Jerrum, M; Sinclair, A; Hochbaum, DS (ed.), The Markov chain Monte Carlo method: an approach to approximate counting and integration, 482-520, (1996), Boston
[16] Kannan, R; Lovasz, L; Simonovits, M, Random walks and an \(O^*(n^5)\) volume algorithm for convex bodies, Random Struct. Algorithms, 11, 1-50, (1997) · Zbl 0895.60075
[17] Kannan, R; Narayanan, H, Random walks on polytopes and an affine interior point method for linear programming, Math. Oper. Res., 37, 1-20, (2012) · Zbl 1243.65033
[18] Kannan, R., Nolte, A.: Local search in smooth convex sets. In: Proceedings of the 39th Symposium on Foundations of Computer Science, pp. 218-226 (1998) · Zbl 1283.93314
[19] King, AJ; Rockafellar, RT, Asymptotic theory for solutions in statistical estimation and stochastic optimization, Math. Oper. Res., 18, 148-162, (1993) · Zbl 0798.90115
[20] Kleywegt, AJ; Shapiro, A; Homem-De-Mello, T, The sample average approximation method for stochastic discrete optimization, SIAM J. Optim., 12, 479-502, (2001) · Zbl 0991.90090
[21] Mak, W-K; Morton, DP; Wood, RK, Monte-Carlo bounding techniques for determining solution quality in stochastic programs, Oper. Res. Lett., 24, 47-56, (1999) · Zbl 0956.90022
[22] Lovasz, L; Simonovits, M, Random walks in a convex body and an improved volume algorithm, Random Struct. Algorithms, 4, 359-412, (1993) · Zbl 0788.60087
[23] Lovasz, L., Vempala, S.: Fast algorithms for logconcave functions: sampling, rounding, integration and optimization. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 57-68 (2006) · Zbl 0799.68107
[24] Nemirovski, A., Nesterov, Y.: Interior Point Polynomial Methods in Convex Programming. SIAM Press, Philadelphia, PA (1994) · Zbl 0824.90112
[25] Nesterov, Y; Vial, J-P, Confidence level solutions for stochastic programming, Automatica, 6, 1559-1568, (2008) · Zbl 1283.93314
[26] Nesterov, Y., Vial, J.-P.: Confidence level solutions for stochastic programming. Technical Report Core Discussion Papers. http://www.core.ucl.ac.be/services/psfiles/dp00/dp2000-13.pdf (2000) · Zbl 1283.93314
[27] Prekopa, A.: Stochastic Programming, Mathematics and its Applications, vol. 324. Kluwer, Dordrecht (1995) · Zbl 0834.90098
[28] Shapiro, A; Homem-de-Mello, TA, Simulation-based approach to two-stage stochastic programming with recourse, Math. Program., 81, 301-325, (1998) · Zbl 0919.90120
[29] Shapiro, A; Nemerovski, A; Jeyakumar, V (ed.); Rubinov, AM (ed.), On complexity of stochastic programming problems, 111-144, (2005), Berlin
[30] Shmoys, D.B., Swamy, C.: Stochastic optimization is (almost) as easy as deterministic optimization. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 228-237 (2004)
[31] Shmoys, DB; Swamy, C, An approximation scheme for stochastic linear programming and its applications to stochastic integer programs, JACM, 53, 978-1012, (2006) · Zbl 1326.90059
[32] Tintner, G.: Stochastic linear programming with applications to agricultural economics. In: Antosiewicz, H.A. (ed.) Proceedings of the Second Symposium on Linear Programming, Washington, pp. 197-207 (1955)
[33] Wets, R; Bachem, A (ed.); Groetschel, M (ed.); Korte, B (ed.), Stochastic programming: solution techniques and approximation, 566-603, (1983), Berlin
[34] Wets, R.: Stochastic programming. In: Optimization, Handbooks of Operations Research and Management Science, vol. 1, pp. 573-629. Amsterdam, North-Holland (1989)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.