# 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.

##### MSC:
 90C25 Convex programming 90C15 Stochastic programming 68W20 Randomized algorithms 68Q25 Analysis of algorithms and problem complexity
Full Text:
##### References:
  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)  Beale, EM, On minimizing a convex function subject to linear inequalities, J. R. Stat. Soc., 17, 173-184, (1955) · Zbl 0068.13701  Bertsimas, D; Vempala, S, Solving convex programs by random walks, JACM, 51, 540-556, (2004) · Zbl 1204.90074  Birge, J., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York (1997) · Zbl 0892.90142  Dantzig, G, Linear programming under uncertainty, Manag. Sci., 1, 197-206, (1955) · Zbl 0995.90589  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  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  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  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  Dyer, M; Stougie, L, A note on the complexity of some stochastic optimization problems, Math. Program., 106, 423-432, (2006) · Zbl 1134.90027  Ermoliev, Y; Shor, NZ, Method of random walk for the two-stage problem of stochastic programming and its generalization, Kibernetica, 4, 59-60, (1968)  Ermoliev, Y., Wets, R.J.-B. (eds.): Numerical Techniques for Stochastic Optimization. Springer, Berlin (1988) · Zbl 0658.00020  Grötschel, M., Lovasz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, New York (1988) · Zbl 0634.05001  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  Jerrum, M; Sinclair, A; Hochbaum, DS (ed.), The Markov chain Monte Carlo method: an approach to approximate counting and integration, 482-520, (1996), Boston  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  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  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  King, AJ; Rockafellar, RT, Asymptotic theory for solutions in statistical estimation and stochastic optimization, Math. Oper. Res., 18, 148-162, (1993) · Zbl 0798.90115  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  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  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  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  Nemirovski, A., Nesterov, Y.: Interior Point Polynomial Methods in Convex Programming. SIAM Press, Philadelphia, PA (1994) · Zbl 0824.90112  Nesterov, Y; Vial, J-P, Confidence level solutions for stochastic programming, Automatica, 6, 1559-1568, (2008) · Zbl 1283.93314  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  Prekopa, A.: Stochastic Programming, Mathematics and its Applications, vol. 324. Kluwer, Dordrecht (1995) · Zbl 0834.90098  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  Shapiro, A; Nemerovski, A; Jeyakumar, V (ed.); Rubinov, AM (ed.), On complexity of stochastic programming problems, 111-144, (2005), Berlin  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)  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  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)  Wets, R; Bachem, A (ed.); Groetschel, M (ed.); Korte, B (ed.), Stochastic programming: solution techniques and approximation, 566-603, (1983), Berlin  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.