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

Special Issue: Continuous Optimization

Previous Articles Next Articles

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

CLC Number:

90C33
90C15

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.

TrendMD

References 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

Knowledge

Abstract

Cite this article

share this article

References 36

Related Articles 5

Recommended Articles

Metrics

Comments

[1]	Chun-Rong Chen, Xia Chen, Hong-Zhi Wei, Sheng-Jie Li. Error Bounds for Generalized Mixed Vector Equilibrium Problems via a Minimax Strategy [J]. Journal of the Operations Research Society of China, 2018, 6(2): 317-331.
[2]	Le Han · Xiao-Lan Liu. Convex Relaxation Algorithm for a Structured Simultaneous Low-Rank and Sparse Recovery Problem [J]. Journal of the Operations Research Society of China, 2015, 3(3): 363-.
[3]	Xiang-Feng Wang. On the Convergence Rate of a Class of Proximal-Based Decomposition Methods for Monotone Variational Inequalities [J]. Journal of the Operations Research Society of China, 2015, 3(3): 347-.
[4]	Mojtaba Kadkhodaie · Maziar Sanjabi ·Zhi-Quan Luo. On the Linear Convergence of the Approximate Proximal Splitting Method for Non-smooth Convex Optimization [J]. Journal of the Operations Research Society of China, 2014, 2(2): 123-142.
[5]	Hai-Bin Zhang · Jiao-Jiao Jiang · Zhi-Quan Luo. On the Linear Convergence of a Proximal Gradient Method for a Class of Nonsmooth Convex Minimization Problems [J]. Journal of the Operations Research Society of China, 2013, 1(2): 163-.