Journal of the Operations Research Society of China >

2019 , Vol. 7 >Issue 2: 251 - 283

DOI: https://doi.org/10.1007/s40305-018-0225-3

A New Complementarity Function and Applications in Stochastic Second-Order Cone Complementarity Problems

Expand
  • 1 School of Management, Shanghai University, Shanghai 200444, China;
    2 School of Management Science, Qufu Normal University, Qufu 276800, Shandong, China;
    3 Department of Mathematics, Hong Kong Baptist University, Hong Kong, HKBU Institute of Research and Continuing Education, Shenzhen, China

Received date: 2018-02-03

  Revised date: 2018-08-08

  Online published: 2019-06-30

Supported by

This work was supported in part by the National Natural Science Foundation of China (Nos. 71831008, 11671250, 11431004 and 11601458), Humanity and Social Science Foundation of Ministry of Education of China (No. 15YJA630034), Shandong Province Natural Science Fund (No. ZR2014AM012), Higher Educational Science and Technology Program of Shandong Province (No. J13LI09), and Scientific Research of Young Scholar of Qufu Normal University (No. XKJ201315).

Fold

Abstract

This paper considers the so-called expected residual minimization (ERM) formulation for stochastic second-order cone complementarity problems, which is based on a new complementarity function called termwise residual complementarity function associated with second-order cone. We show that the ERM model has bounded level sets under the stochastic weak R0-property. We further derive some error bound results under either the strong monotonicity or some kind of constraint qualifications. Then, we apply the Monte Carlo approximation techniques to solve the ERM model and establish a comprehensive convergence analysis. Furthermore, we report some numerical results on a stochastic second-order cone model for optimal power flow in radial networks.

Key words： Stochastic second-order cone complementarity problem; Complementarity function; Expected Residual Minimization (ERM) model; Monte Carlo method; Error bound; Optimal power flow

Cite this article

Guo Sun, Jin Zhang, Li-Ying Yu, Gui-Hua Lin . A New Complementarity Function and Applications in Stochastic Second-Order Cone Complementarity Problems[J]. Journal of the Operations Research Society of China, 2019 , 7(2) : 251 -283 . DOI: 10.1007/s40305-018-0225-3

References

[1] Alizadeh, F., Goldfarb, D.:Second-order cone programming. Math. Program. 95, 3-51(2003)
[2] Ferris, M.C., Mangasarian, O.L., Pang, J.S.:Complementarity:Applications, Algorithms and Extensions. Kluwer Academic Publishers, Dordrecht (2001)
[3] Monteiro, R.D.C., Tsuchiya, T.:Polynomial convergence of primal-dual algorithms for the secondorder cone programs based on the MZ-family of directions. Math. Program. 88, 61-83(2000)
[4] Tsuchiya, T.:A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming. Optim. Methods Softw. 11, 141-182(1999)
[5] Chen, X.D., Sun, D., Sun, J.:Complementarity functions and numerical experiments for second-order cone complementarity problems. Comput. Optim. Appl. 25, 39-56(2003)
[6] Fukushima, M., Luo, Z.Q., Tseng, P.:Smoothing functions for second-order cone complementarity problems. SIAM J. Optim. 12, 436-460(2002)
[7] Hayashi, S., Yamashita, N., Fukushima, M.:A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15, 593-615(2005)
[8] Kanzow, C., Ferenczi, I., Fukushima, M.:On the local convergence of semismooth Newton methods for linear and nonlinear second-order cone programs without strict complementarity. SIAM J. Optim. 20, 297-320(2009)
[9] Pan, S.H., Chen, J.S.:A damped Gauss-Newton method for the second-order cone complementarity problem. Appl. Math. Optim. 59, 293-318(2009)
[10] Chen, J.S., Tseng, P.:An unconstrained smooth minimization reformulation of the second-order cone complementarity problem. Math. Program. 104, 293-327(2005)
[11] Chen, J.S.:Two classes of merit functions for the second-order cone complementarity problem. Math. Methods Oper. Res. 64, 495-519(2006)
[12] Chen, J.S.:A new merit function and its related problems for the second-order cone complementarity problem. Pac. J. Optim. 2, 167-179(2006)
[13] Tseng, P.:Growth behavior of a class of merit functions for the nonlinear complementarity problem. J. Optim. Theory Appl. 89, 17-37(1996)
[14] Chen, X., Fukushima, M.:Expected residual minimization method for stochastic linear complementarity problems. Math. Oper. Res. 30, 1022-1038(2005)
[15] Chen, X., Zhang, C., Fukushima, M.:Robust solution of monotone stochastic linear complementarity problems. Math. Program. 117, 51-80(2009)
[16] Fang, H., Chen, X., Fukushima, M.:Stochastic R0 matrix linear complementarity problems. SIAM J. Optim. 18, 482-506(2007)
[17] Lin, G.H., Chen, X., Fukushima, M.:New restricted NCP function and their applications to stochastic NCP and stochastic MPEC. Optimization 56, 641-753(2007)
[18] Lin, G.H., Fukushima, M.:New reformulations for stochastic nonlinear complementarity problems. Optim. Methods Softw. 21, 551-564(2006)
[19] Zhang, C., Chen, X.:Stochastic nonlinear complementarity problem and applications to traffic equilibrium under uncertainty. J. Optim. Theory Appl. 137, 277-295(2008)
[20] Faraut, J., Korányi, A.:Analysis on Symmetric Cones. Oxford Mathematical Monographs. Oxford University Press, New York (1994)
[21] Mordukhovich, B.S.:Generalized differential calculus for nonsmooth and set-valued mappings. J. Math. Anal. Appl. 183, 250-288(1994)
[22] Aubin, J.P.:Lipschitz behavior of solutions to convex minimization problems. Math. Oper. Res. 9, 87-111(1994)
[23] Robinson, S.M.:Stability theory for systems of inequalities. Part I:linear systems. SIAM J. Numer. Anal. 12, 754-769(1975)
[24] Rockafellar, R.T., Wets, R.J.:Variational Analysis. Springer, New York (1998)
[25] Ye, J.J., Ye, X.Y.:Necessary optimality conditions for optimization problems with variational inequality constraints. Math. Oper. Res. 22, 977-997(1997)
[26] Ruszczý nski, A., Shapiro, A.:Stochastic Programming. Handbooks in Operations Research and Management Science. Elsevier, Amsterdam (2003)
[27] Kong, L., Tuncel, L., Xiu, N.:Vector-valued implicit Lagrangian for symmetric cone complementarity problems. Asia-Pacific J. Oper. Res. 26, 199-233(2009)
[28] Chung, K.L.:A Course in Probability Theory. Academic Press, New York (1974)
[29] Ye, J.J.:Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints. SIAM J. Optim. 10, 943-962(2000)
[30] Mordukhovich, B.S.:Variational Analysis and Generalized Differentiation:I and Ⅱ. Springer, Berlin (2006)
[31] Robinson, S.M.:Some continuity properties of polyhedral multifunctions. Math. Program. Stud. 14, 206-214(1981)
[32] Henrion, R., Outrata, J.V.:Calmness of constraint systems with applications. Math. Program. 104, 437-464(2005)
[33] Shapiro, A., Xu, H.:Stochastic mathematical programs with equilibrium constraints, modelling and sample average approximation. Optimization 57, 395-418(2008)
[34] Farivar, M., Low, S.H.:Branch flow model:relaxations and convexification. In:IEEE 51st Annual Conference on Decision and Control, pp. 3672-3679(2012)
[35] Gan, L., Li, N., Topcu, U., Low, S.H.:Exact convex relaxation of optimal power flow in radial networks. IEEE Trans. Autom. Control 60, 72-87(2015)
[36] Lopez, M., Still, G.:Semi-infinite programming. Eur. J. Oper. Res. 180, 491-518(2007)
Options
Outlines

/

〈 〉

Copyright © Operations Research Society of China, The Periodicals Agency of Shanghai University , and Springer-Verlag Berlin Heidelberg 2016