Abstract

This paper makes two contributions to optimization theory derived from new methods of discrete convex analysis. Our first contribution is to stochastic optimization: The scenario approach developed by Calafiore and Campi to attack chance-constrained convex programs (i.e., optimization problems with convex constraints that are parametrized by an uncertainty parameter) utilizes random sampling on the uncertainty parameter to substitute the original problem with a deterministic continuous convex optimization with NN convex constraints which is a relaxation of the original. Calafiore and Campi provided an explicit estimate on the size NN of the sampling relaxation to yield high-likelihood feasible solutions of the chance-constrained problem. They measured the probability of the original constraints to be violated by the random optimal solution from the relaxation of size NN. We present a generalization of the Calafiore-Campi results to both integer and mixed-integer variables. We demonstrate that their sampling estimates work naturally even for variables that take on more sophisticated values restricted to some subset SS of Rd\mathbb{R}^d. In this way, a sampling or scenario algorithm for chance-constrained convex mixed integer optimization algorithm is just a very special case of a stronger sampling result in convex analysis. Second, motivated by the first half of the paper, for a subset S⊂RdS \subset \mathbb{R}^d, we formally introduce the notion of an SS-optimization problem, where the variables take on values over SS. SS-optimization generalizes continuous (S=RdS=\mathbb{R}^d), integer (S=ZdS=\mathbb{Z}^d), and mixed-integer optimization (S=Rk×Zd−kS=\mathbb{R}^k \times \mathbb{Z}^{d-k}). We illustrate with examples the expressive power of SS-optimization to capture combinatorial and integer optimization problems with difficult modular constraints. We reinforce the evidence that SS-optimization is ``the right concept'' by showing that a second well-known randomized sampling algorithm of K. Clarkson for low-dimensional convex optimization problems can be extended to work with variables taking values over SS. The key element in all the proofs, are generalizations of Helly's theorem where the convex sets are required to intersect S⊂RdS \subset \mathbb{R}^d. The size of samples in both algorithms will be directly determined by the SS-Helly numbers.

Author information

Contact details are reproduced from the original publication and may be historical.

Jesus A. De Loera

Department of Mathematics, University of California, One Shields Avenue, Davis, CA 95616, U.S.A.

deloera@math.ucdavis.edu

Reuben N. La Haye

Department of Mathematics, University of California, One Shields Avenue, Davis, CA 95616, U.S.A.

rlahaye@math.ucdavis.edu

Déborah Oliveros

Instituto de Matemáticas, Universidad Nacional Autónoma de México (UNAM), Campus Juriquilla, 04510 México

dolivero@matem.unam.mx

Edgardo Roldán-Pensado

Centro de Ciencias Matemáticas, Universidad Nacional Autónoma de México (UNAM), Campus Morelia, 04510 México

e.roldan@im.unam.mx

Keywords

  • Chance-constrained optimization
  • convex mixed-integer optimization
  • optimization with restricted variable values
  • randomized sampling algorithms
  • Helly-type theorems
  • S-optimization
  • convexity spaces
  • combinatorial convexity

Mathematics Subject Classification

90C15, 90C11, 90C48

References

  1. A. A. Aly, J. A. White: Probabilistic formulation of the emergency service location problem, J. Oper. Res. Soc. 29 (1978) 1167–1179.https://doi.org/10.1057/jors.1978.261Google Scholar
  2. N. Amenta: Helly theorems and generalized linear programming, Discrete Comp. Geometry 12 (1994) 241–261.https://doi.org/10.1007/BF02574379Google Scholar
  3. J. L. Arocha, J. Bracho, L. Montejano: Flat transversals to flats and convex sets of a fixed dimension, Adv. Math. 213(2) (2007) 902–918.https://doi.org/10.1016/j.aim.2007.01.017Google Scholar
  4. G. Averkov, R. Weismantel: Transversal numbers over subsets of linear spaces, Adv. Geometry 12(1) (2012) 19–28.https://doi.org/10.1515/advgeom.2011.028Google Scholar
  5. B. R. Barmish, P. S. Shcherbakov: On avoiding vertexization of robustness problems: the approximate feasibility concept, in: Decision and Control 2000, Proc. of the 39th IEEE Conference, vol. 2 (2000) 1031–1036.https://doi.org/10.1109/CDC.2000.911986Google Scholar
  6. A. Barvinok, J. E. Pommersheim: An algorithmic theory of lattice points in polyhedra, New perspectives in algebraic combinatorics 38 (1999) 91–147.https://doi.org/10.1017/9781009701587.004Google Scholar
  7. A. Basu, M. Conforti, G. Cornuéjols, R. Weismantel, S. Weltge: Optimality certificates for convex minimization and Helly numbers, arXiv 1610.08648 (2016).Google Scholar
  8. A. Basu, T. Oertel: Centerpoints: A link between optimization and convex geometry, SIAM J. Optimization 27(2) (2017) 866–889.https://doi.org/10.1137/16M1092908Google Scholar
  9. D. E. Bell: A theorem concerning the integer lattice, Studies in Appl. Math. 56(2) (1976) 187–188.https://doi.org/10.1002/sapm1977562187Google Scholar
  10. P. Beraldi, M. E. Bruni, D. Conforti: Designing robust emergency medical service via stochastic programming, Eur. J. Oper. Res. 158(1) (2004) 183–193.https://doi.org/10.1016/S0377-2217(03)00351-5Google Scholar
  11. G. Calafiore, M. C. Campi: Uncertain convex programs: randomized solutions and confidence levels, Math. Program. Ser. A 102(1) (2005) 25–46.https://doi.org/10.1007/s10107-003-0499-yGoogle Scholar
  12. G. C. Calafiore, M. C. Campi: The scenario approach to robust control design, IEEE Trans. Automat. Control 51(5) (2006) 742–753.https://doi.org/10.1109/TAC.2006.875041Google Scholar
  13. M. C. Campi, S. Garatti: The exact feasibility of randomized solutions of uncertain convex programs, SIAM J. Optimization 19(3) (2008) 1211–1230.https://doi.org/10.1137/07069821XGoogle Scholar
  14. K. L. Clarkson: Las Vegas algorithms for linear and integer programming, Journal of the ACM 42(2) (1995) 488–499.https://doi.org/10.1145/201019.201036Google Scholar
  15. J. A. De Loera, R. N. La Haye, D. Oliveros, E. Roldán-Pensado: Helly numbers of algebraic subsets of Rd, Advances in Geometry, to appear, arXiv: 1508.02380 (2015).Google Scholar
  16. D. Dentcheva, A. Prékopa, A. Ruszczyński: Bounds for probabilistic integer programming problems, Discrete Appl. Math. 124(1-3) (2002) 55–65.https://doi.org/10.1016/S0166-218X(01)00329-8Google Scholar
  17. J.-P. Doignon: Convexity in cristallographical lattices, J. Geometry 3 (1973) 71–85.https://doi.org/10.1007/BF01949705Google Scholar
  18. J.-P. Doignon, R. J. Reay, G. Sierksma: A Tverberg-type generalization of the Helly number of a convexity space, J. Geometry 16 (1981) 117–125.https://doi.org/10.1007/BF01917580Google Scholar
  19. F. Eisenbrand: Fast integer programming in fixed dimension, in: Proc. of the European Symposium on Algorithms 2003, G. Di Battista and U. Zweik (eds.), Lect. Notes Computer Science 2832, Springer, Berlin (2003) 196–207.https://doi.org/10.1007/978-3-540-39658-1_20Google Scholar
  20. A. A. Gaivoronski, G. Pflug: Value-at-risk in portfolio optimization: properties and computational approach, Journal of Risk 7(2) (2005) 1–31.https://doi.org/10.21314/JOR.2005.106Google Scholar
  21. B. Gärtner, J. Matoušek, L. Rüst, P. Škovroň: Violator spaces: structure and algorithms, Discrete Appl. Math. 156(11) (2008) 2124–2141.https://doi.org/10.1016/j.dam.2007.08.048Google Scholar
  22. F. Glover: Integer programming over a finite additive group, SIAM J. Control 7 (1969) 213–231.https://doi.org/10.1137/0307015Google Scholar
  23. A. J. Hoffman: Binding constraints and Helly numbers, in: Second International Conference on Combinatorial Mathematics, New York 1978, Ann. New York Acad. Sci. 319, New York Acad. Sci., New York (1979) 284–288.https://doi.org/10.1111/j.1749-6632.1979.tb32803.xGoogle Scholar
  24. R. Jamison: Partition numbers for trees and ordered sets, Pacific J. Math. 96(1) (1981) 115–140.https://doi.org/10.2140/pjm.1981.96.115Google Scholar
  25. D. Kay, E. W. Womble: Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers, Pacific J. Math. 38(2) (1971) 471–485.https://doi.org/10.2140/pjm.1971.38.471Google Scholar
  26. J. Luedtke, S. Ahmed: A sample approximation approach for optimization with probabilistic constraints, SIAM J. Optimization 19(2) (2008) 674–699.https://doi.org/10.1137/070702928Google Scholar
  27. V. Marianov, M. Ríos: A probabilistic quality of service constraint for a location model of switches in ATM communications networks, Annals of Oper. Research 96(1-4) (2000) 237–243.https://doi.org/10.1023/A:1018955603355Google Scholar
  28. B. K. Pagnoncelli, S. Ahmed, A. Shapiro: Computational study of a chance constrained portfolio selection problem, Optimization Online (2008).Google Scholar
  29. B. K. Pagnoncelli, S. Ahmed, A. Shapiro: Sample average approximation method for chance constrained programming: theory and applications, J. Optim. Theory Appl. 142(2) (2009) 399–416.https://doi.org/10.1007/s10957-009-9523-6Google Scholar
  30. H. E. Scarf: An observation on the structure of production sets with indivisibilities, Proc. Nat. Acad. Sci. U.S.A. 74(9) (1977) 3637–3641.https://doi.org/10.1073/pnas.74.9.3637Google Scholar
  31. A. Shapiro, D. Dentcheva, A. Ruszczyński: Lectures on Stochastic Programming, MOS-SIAM Series on Optimization, 2nd edition, SIAM, Philadelphia (2014).https://doi.org/10.1137/1.9781611973433Google Scholar
  32. M. Sharir, E. Welzl: A combinatorial bound for linear programming and related problems, in: Proc. 9th Symposium on Theoretical Aspects of Computer Science, Lect. Notes Computer Science 577, Springer, Berlin (1992) 569–579.https://doi.org/10.1007/3-540-55210-3_213Google Scholar
  33. M. L. J. van de Vel: Theory of Convex Structures, North-Holland, Amsterdam (1993).Google Scholar
  34. A. N. Venetsanopoulos, I. Singh: Topological optimization of communication networks subject to reliability constraints, Prob. Control Info. Theory. 15(1) (1986) 63–78.Google Scholar
  35. J. P. Vielma, S. Ahmed, G. L. Nemhauser: Mixed integer linear programming formulations for probabilistic constraints, Oper. Res. Lett. 40(3) (2012) 153–158.https://doi.org/10.1016/j.orl.2012.01.007Google Scholar

Suggested citation

J. A. De Loera, R. N. La Haye, D. Oliveros, E. Roldán-Pensado. “Chance-Constrained Convex Mixed-Integer Optimization and Beyond: Two Sampling Algorithms within S-optimization.” Journal of Convex Analysis 25 (2018), No. 1, 201–218. https://doi.org/10.68381/jca25012

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2018. Rights now held by Banach Press LLC.