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

research-article

Entropic Approximation for Mathematical Programs with Robust Equilibrium Constraints

Authors:

Huifu XuAuthors Info & Claims

SIAM Journal on Optimization, Volume 24, Issue 3

Pages 933 - 958

https://doi.org/10.1137/130931011

Published: 01 January 2014 Publication History

Abstract

In this paper, we consider a class of mathematical programs with robust equilibrium constraints represented by a system of semi-infinite complementarity constraints (SICC). We propose a numerical scheme for tackling SICC. Specifically, by relaxing the complementarity constraints and then randomizing the index set of SICC, we employ the well-known entropic risk measure to approximate the semi-infinite constraints with a finite number of stochastic inequality constraints. Under some moderate conditions, we quantify the approximation in terms of the feasible set and the optimal value. The approximation scheme is then applied to a class of two stage stochastic mathematical programs with complementarity constraints in combination with the polynomial decision rules. Finally, we extend the discussion to a mathematical program with distributionally robust equilibrium constraints, which is essentially a one stage stochastic program with semi-infinite stochastic constraints indexed by some probability measures from an ambiguity set defined through the KL-divergence.

References

[1]

F. Alvarez and M. Carrasco, Minimization of the expected compliance as an alternative approach to multiload truss optimization, Struct. Multidiscip. Optim., 29 (2005), pp. 470--476.

[2]

E. Anderson, H. Xu, and D. Zhang, Approximating Parametric Maximization Problems Through CVaR with Applications in Minimax and Robust Convex Optimization, manuscript, 2014.

[3]

D. Azé, A survey on error bounds for lower semicontinuous functions, ESAIM Proc., 13 (2003), pp. 1--17.

[4]

D. Bampou and D. Kuhn, Polynomial approximations for continuous linear programs, SIAM J. Optim., 22 (2012), pp. 628--648.

[5]

A. Ben-Tal and A. Nemirovski, Robust truss topology design via semidefinite programming, SIAM J. Optim., 7 (1997), pp. 991--1016.

[6]

A. Ben-Tal and A. Nemirovski, Robust convex optimization, Math. Oper. Res., 23 (1998), pp. 769--805.

[7]

A. Ben-Tal and A. Nemirovski, Robust solutions of uncertain linear programs, Oper. Res. Lett., 25 (1999), pp. 1--13.

[8]

A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, Robust Optimization, Princeton University Press, Princeton, NJ, 2009.

[9]

A. Ben-Tal, A. Goryashko, E. Guslitzer, and A. Nemirovski, Adjustable robust solutions of uncertain linear programs, Math. Program., 99 (2004), pp. 351--376.

[10]

A. Ben-Tal, D. Hertog, A. D. Waegenaere, B. Melenberg, and G. Rennen, Robust solutions of optimization problems affected by uncertain probabilities, Manage. Sci., 59 (2013), pp. 341--357.

[11]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer Ser. Oper. Res., Springer-Verlag, New York, 2000.

[12]

G. Calafiore and M. C. Campi, Uncertain convex programs: Randomized solutions and confidence levels, Math. Program., 102 (2005), pp. 25--46.

[13]

G. Calafiore and M. C. Campi, The scenario approach to robust control design, IEEE Trans. Automat. Control, 51 (2006), pp. 742--753.

[14]

G. C. Calafiore, Uncertain convex programs, SIAM J. Optim., 20 (2010), pp. 3427--3464.

[15]

X. Chen, M. Sim, P. Sun, and J. Zhang, A linear decision-based approximation approach to stochastic programming, Oper. Res., 56 (2008), pp. 344--357.

[16]

E. Delage and Y. Ye, Distributionally robust optimization under moment uncertainty with application to data-driven problems, Oper. Res., 58 (2010), pp. 595--612.

[17]

H. Föllmer and A. Schied, Stochastic Finance: An Introduction in Discrete Time, 2nd ed., Walter de Gruyter, Berlin, 2004.

[18]

H. Föllmer and T. Knispel, Entropic risk measures: Coherence vs. convexity, model ambiguity, and robust large deviations, Stoch. Dyn., 11 (2011), pp. 333--351.

[19]

M. Grant and S. Boyd, CVX, for convex optimization, http://www.stanford.edu/ boyd/http://www.stanford.edu/ boyd/www.stanford.edu/$\sim$boyd/.

[20]

J. Goh and M. Sim, Distributionally robust optimization and its tractable approximations, Oper. Res., 58 (2010), pp. 902--917.

[21]

Z. Hu and J. Hong, Kullback-Leibler Divergence Constrained Distributionally Robust Optimization, manuscript, 2012.

[22]

D. Klatte, A note on quantitative stability results in nonlinear optimization, Seminarbericht 90, Sektion Mathematik, Humboldt-Universität zu Berlin, Berlin, 1987, pp. 77--86,.

[23]

D. Kuhn, W. Wiesemann, and A. Georghiou, Primal and dual linear decision rules in stochastic and robust optimization, Math. Program., 130 (2011), pp. 177--209.

[24]

G.-H. Lin, X. Chen, and M. Fukushima, Solving stochastic mathematical programs with equilibrium constraints via approximation and smoothing implicit programming with penalization, Math. Program., 116 (2009), pp. 343--368.

[25]

G. H. Lin and M. Fukushima, Stochastic equilibrium problems and stochastic mathematical programs with equilibrium constraints: A survey, Pac. J. Optim., 6 (2010), pp. 455--482.

[26]

Y. Liu, H. Xu, and G. H. Lin, Stability analysis of two-stage stochastic mathematical programs with complementarity constraints via NLP-regularization, SIAM J. Optim., 21 (2011), pp. 609--705.

[27]

Y. Liu, H. Xu, and J. J. Ye, Penalized sample average approximation methods for stochastic mathematical programs with complementarity constraints, Math. Oper. Res., 36 (2011), pp. 670--694.

[28]

Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press}, Cambridge, UK, 1996.

[29]

F. Meng and H. Xu, A regularized sample average approximation method for stochastic mathematical programs with nonsmooth equality constraints, SIAM J. Optim., 17 (2006), pp. 891--919.

[30]

J. Outrata, M. Kočvara, and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications, and Numerical Results, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998.

[31]

J-S. Pang, Error bounds in mathematical programming, Math. Programming, 79 (1997), pp. 299--332.

[32]

M. Patriksson and L. Wynter, Stochastic mathematical programs with equilibrium constraints, Oper. Res. Lett., 25 (1999), pp. 159--167.

[33]

S. J. Qu and M. Goh, Distributionally Robust Games with an Application to Supply Chain, manuscript, 2012.

[34]

R. T. Rockafellar and S. Uryasev, Conditional value-at-risk for general loss distributions, J. Bank. Finan., 26 (2002), pp. 1443--1471.

[35]

A. Ruszczynski and A. Shapiro, Stochastic Programming, Handbook in Operations Research and Management Science, Elsevier, Amsterdam, 2003.

[36]

S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim., 11 (2001), pp. 918--936.

[37]

A. Shapiro, Asymptotic analysis of stochastic programs, Ann. Oper. Res., 30 (1991), pp. 169--186.

[38]

A. Shapiro, Stochastic mathematical programs with equilibrium constraints, J. Optim. Theory Appl., 128 (2006), pp. 223--243.

[39]

A. Shapiro, D. Dentcheva, and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, MPS/SIAM Ser. Optim. 9, SIAM, Philadelphia, 2009.

[40]

A. Shapiro and A. Nemirovski, On complexity of stochastic programming problems, Continuous Optimization, V. Jeyakumar and A. Rubinov, eds., Springer, New York, 2005, pp. 111--146.

[41]

A. Shapiro and H. Xu, Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation, Optimization, 57 (2008), pp. 395--418.

[42]

H. Xu, An implicit programming approach for a class of stochastic mathematical programs with complementarity constraints, SIAM J. Optim., 16 (2006), pp. 670--696.

[43]

H. Xu, Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming. J. Math. Anal. Appl., 368 (2010), pp. 692--710.

[44]

H. Xu and J. J. Ye, Necessary optimality conditions for two-stage stochastic programs with equilibrium constraints, SIAM J. Optim., 20 (2010), pp. 1685--1715.

[45]

H. Xu, C. Caramanis, and S. Mannor, A distributional interpretation of robust optimization, Math. Oper. Res., 37 (2012), pp. 95--110.

Cited By

Chuong TYu XEberhard ALi CLiu C(2024)Hierarchy relaxations for robust equilibrium constrained polynomial problems and applications to electric vehicle charging schedulingJournal of Global Optimization10.1007/s10898-024-01421-090:3(781-811)Online publication date: 20-Jul-2024
https://dl.acm.org/doi/10.1007/s10898-024-01421-0

Index Terms

Entropic Approximation for Mathematical Programs with Robust Equilibrium Constraints
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
      1. Approximation
    2. Mathematical optimization
      1. Continuous optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization

Index terms have been assigned to the content through auto-classification.

Recommendations

Mathematical Programs with Second-Order Cone Complementarity Constraints: Strong Stationarity and Approximation Method

The existence of complementarity constraints causes the difficulties for studying mathematical programs with second-order cone complementarity constraints, since the standard constraint qualification, such as Robinson's constraint qualification, is ...
Solving stochastic mathematical programs with equilibrium constraints via approximation and smoothing implicit programming with penalization

In this paper, we consider the stochastic mathematical programs with linear complementarity constraints, which include two kinds of models called here-and-now and lower-level wait-and-see problems. We present a combined smoothing implicit programming ...
Solving Mathematical Programs with Equilibrium Constraints

This paper aims at developing effective numerical methods for solving mathematical programs with equilibrium constraints. Due to the existence of complementarity constraints, the usual constraint qualifications do not hold at any feasible point, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Optimization

SIAM Journal on Optimization Volume 24, Issue 3

2014

648 pages

ISSN:1052-6234

DOI:10.1137/sjope8.24.3

Issue’s Table of Contents

© 2014, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2014

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chuong TYu XEberhard ALi CLiu C(2024)Hierarchy relaxations for robust equilibrium constrained polynomial problems and applications to electric vehicle charging schedulingJournal of Global Optimization10.1007/s10898-024-01421-090:3(781-811)Online publication date: 20-Jul-2024
https://dl.acm.org/doi/10.1007/s10898-024-01421-0

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents