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

doi:10.1007/s40305-018-0225-3

Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (2): 251-283.doi: 10.1007/s40305-018-0225-3

所属专题： Continuous Optimization； Stochastic optimization

收稿日期:2018-02-03 修回日期:2018-08-08 出版日期:2019-06-30 发布日期:2019-06-30
通讯作者: Guo Sun, Jin Zhang, Li-Ying Yu, Gui-Hua Lin E-mail:qrsunguo@163.com;zhangjin@hkbu.edu.hk;yuliying@shu.edu.cn;guihualin@shu.edu.cn

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

Guo Sun^1,2, Jin Zhang³, Li-Ying Yu¹, Gui-Hua Lin¹

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:2018-02-03 Revised:2018-08-08 Online:2019-06-30 Published:2019-06-30
Contact: Guo Sun, Jin Zhang, Li-Ying Yu, Gui-Hua Lin E-mail:qrsunguo@163.com;zhangjin@hkbu.edu.hk;yuliying@shu.edu.cn;guihualin@shu.edu.cn
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).

摘要/Abstract

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 R₀-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

中图分类号:

90C33
90C15

. [J]. Journal of the Operations Research Society of China, 2019, 7(2): 251-283.

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.

参考文献 36

[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)

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 36

相关文章 10

编辑推荐

Metrics

本文评价