On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints

Previous Article
Single-machine rescheduling problems with learning effect under disruptions
JIMO Home
This Issue
Next Article
Uniqueness of solutions to fuzzy relational equations regarding Max-av composition and strong regularity of the matrices in Max-av algebra

July 2018, 14(3): 981-1005. doi: 10.3934/jimo.2017086

On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints

Yi Zhang ^1, , Liwei Zhang ^2, and Jia Wu ^2,

1.	School of Science, East China University of Science and Technology, Shanghai 200237, China
2.	Institute of ORCT, School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China

Received April 2016 Revised December 2016 Published September 2017

Fund Project: This study is supported by the National Natural Science Foundation of China under projects No.11401210, No.11671183, No.11571059, No.91330206 and No.11301049

This paper focuses on a class of mathematical programs with symmetric cone complementarity constraints (SCMPCC). The explicit expression of C-stationary condition and SCMPCC-linear independence constraint qualification (denoted by SCMPCC-LICQ) for SCMPCC are first presented. We analyze a parametric smoothing approach for solving this program in which SCMPCC is replaced by a smoothing problem $P_{\varepsilon}$ depending on a (small) parameter $\varepsilon$. We are interested in the convergence behavior of the feasible set, stationary points, solution mapping and optimal value function of problem $P_{\varepsilon}$ when $\varepsilon \to 0$ under SCMPCC-LICQ. In particular, it is shown that the convergence rate of Hausdorff distance between feasible sets $\mathcal{F}_{\varepsilon}$ and $\mathcal{F}$ is of order $\mbox{O}(|\varepsilon|)$ and the solution mapping and optimal value of $P_{\varepsilon}$ are outer semicontinuous and locally Lipschitz continuous at $\varepsilon=0$ respectively. Moreover, any accumulation point of stationary points of $P_{\varepsilon}$ is a C-stationary point of SCMPCC under SCMPCC-LICQ.

Keywords: Mathematical program with symmetric cone complementarity constraints, C-stationary point, parametric smoothing approach, rate of convergence.

Mathematics Subject Classification: Primary: 90C33, 90C26; Secondary: 65K05.

Citation: Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial & Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086

References:

[1]	A. Ben-Tal and A. Nemirovski, Robust convex optimization methodology and applications, Mathematical Programming, 92 (2002), 453-480. doi: 10.1007/s101070100286. Google Scholar
[2]	G. Bouza and G. Still, Mathematical programs with complementarity constraints: Convergence properties of a smoothing method, Mathematics of Operations Research, 32 (2007), 467-483. doi: 10.1287/moor.1060.0245. Google Scholar
[3]	X. Chen and M. Fukushima, A smoothing method for a mathematical program with P-matrix linear complementarity constraints, Computational Optimization and Applications, 27 (2004), 223-246. doi: 10.1023/B:COAP.0000013057.54647.6d. Google Scholar
[4]	F. Clarke, Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, 1983.
[5]	C. Ding, D. Sun and J. Ye, First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints, Mathematical Programming, Ser.A, 147 (2014), 539-579. doi: 10.1007/s10107-013-0735-z. Google Scholar
[6]	F. Facchinei, H. Jiang and L. Qi, A smoothing method for mathematical programs with equilibrium constraints, Mathematical Programming, 85 (1999), 107-134. doi: 10.1007/s10107990015a. Google Scholar
[7]	J. Faraut and A. Korányi, Analysis on Symmetric Cones, Oxford University Press, New York, 1994.
[8]	L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithm, Journal of Computational and Applied Mathematics, 86 (1997), 149-175. doi: 10.1016/S0377-0427(97)00153-2. Google Scholar
[9]	M. Fukushima and J. Pang, Convergence of a smoothing continuation method for mathematical problems with complementarity constraints, Lecture Notes in Economics and Mathematical Systems, 477 (1999), 99-110. doi: 10.1007/978-3-642-45780-7_7. Google Scholar
[10]	M. Gowda, R. Sznajder and J. Tao, Some P-properties for linear transformations on Euclidean Jordan algebras, Linear algebra and its applications, 393 (2004), 203-232. doi: 10.1016/j.laa.2004.03.028. Google Scholar
[11]	K. Koecher, The Minnesota Notes on Jordan Algebras and Their Applications, edited and annotated by A. Brieg and S. Walcher, Springer, Berlin, 1999. doi: 10.1007/BFb0096285. Google Scholar
[12]	G. Lin and M. Fukushima, A modified relaxation scheme for mathematical prgrams with complementarity constraints, Annals of Operations Research, 133 (2005), 63-84. doi: 10.1007/s10479-004-5024-z. Google Scholar
[13]	Z. Luo, J. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, United Kingdom, 1996. doi: 10.1017/CBO9780511983658.
[14]	J. Outrata, M. Ko$\breve{c}$vara and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, Kluwer Academic Publishers, Boston, MA, 1998. doi: 10.1007/978-1-4757-2825-5. Google Scholar
[15]	R. Rockafellar and R. Wets, Variational Analysis, Springer-Verlag, New York, 1998. doi: 10.1007/978-3-642-02431-3.
[16]	S. Scheel and S. Scholtes, Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity, Mathematics of Operation Research, 25 (2000), 1-22. doi: 10.1287/moor.25.1.1.15213. Google Scholar
[17]	S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM Journal on Optimization, 11 (2001), 918-936. doi: 10.1137/S1052623499361233. Google Scholar
[18]	D. Sun and J. Sun, Löwner's operator and spectral functions on Euclidean Jordan algebras, Mathematics of Operation Research, 33 (2008), 421-445. doi: 10.1287/moor.1070.0300. Google Scholar
[19]	D. Sun, J. Sun and L. Zhang, The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming, Mathematical Programming, 114 (2008), 349-391. doi: 10.1007/s10107-007-0105-9. Google Scholar
[20]	E. Takeshi, A Smoothing Method for Mathematical Programs with Second-Order Cone Complementarity Constraints, Master thesis, Kyoto University in Kyoto, 2007.Google Scholar
[21]	Y. Wang, Perturbation Analysis of Optimimization Problems over Symmetric Cones, Ph. D. Thesis, Dalian University of Technology, China, 2008.Google Scholar
[22]	T. Yan and M. Fukushima, Smoothing method for mathematical programs with symmetric cone complementarity constraints, Optimization, 60 (2011), 113-128. doi: 10.1080/02331934.2010.541458. Google Scholar
[23]	Y. Zhang, J. Wu and L. Zhang, First order necessary optimality conditions for mathematical programs with second-order cone complementarity constraint, Journal of Global Optimization, 63 (2015), 253-279. doi: 10.1007/s10898-015-0295-2. Google Scholar
[24]	Y. Zhang, L. Zhang and J. Wu, Convergence properties of a smoothing approach for mathematical programs with second-order cone complementarity constraints, Set-Valued and Variational Analysis, 19 (2011), 609-646. doi: 10.1007/s11228-011-0190-z. Google Scholar

show all references

References:

[1]	A. Ben-Tal and A. Nemirovski, Robust convex optimization methodology and applications, Mathematical Programming, 92 (2002), 453-480. doi: 10.1007/s101070100286. Google Scholar
[2]	G. Bouza and G. Still, Mathematical programs with complementarity constraints: Convergence properties of a smoothing method, Mathematics of Operations Research, 32 (2007), 467-483. doi: 10.1287/moor.1060.0245. Google Scholar
[3]	X. Chen and M. Fukushima, A smoothing method for a mathematical program with P-matrix linear complementarity constraints, Computational Optimization and Applications, 27 (2004), 223-246. doi: 10.1023/B:COAP.0000013057.54647.6d. Google Scholar
[4]	F. Clarke, Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, 1983.
[5]	C. Ding, D. Sun and J. Ye, First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints, Mathematical Programming, Ser.A, 147 (2014), 539-579. doi: 10.1007/s10107-013-0735-z. Google Scholar
[6]	F. Facchinei, H. Jiang and L. Qi, A smoothing method for mathematical programs with equilibrium constraints, Mathematical Programming, 85 (1999), 107-134. doi: 10.1007/s10107990015a. Google Scholar
[7]	J. Faraut and A. Korányi, Analysis on Symmetric Cones, Oxford University Press, New York, 1994.
[8]	L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithm, Journal of Computational and Applied Mathematics, 86 (1997), 149-175. doi: 10.1016/S0377-0427(97)00153-2. Google Scholar
[9]	M. Fukushima and J. Pang, Convergence of a smoothing continuation method for mathematical problems with complementarity constraints, Lecture Notes in Economics and Mathematical Systems, 477 (1999), 99-110. doi: 10.1007/978-3-642-45780-7_7. Google Scholar
[10]	M. Gowda, R. Sznajder and J. Tao, Some P-properties for linear transformations on Euclidean Jordan algebras, Linear algebra and its applications, 393 (2004), 203-232. doi: 10.1016/j.laa.2004.03.028. Google Scholar
[11]	K. Koecher, The Minnesota Notes on Jordan Algebras and Their Applications, edited and annotated by A. Brieg and S. Walcher, Springer, Berlin, 1999. doi: 10.1007/BFb0096285. Google Scholar
[12]	G. Lin and M. Fukushima, A modified relaxation scheme for mathematical prgrams with complementarity constraints, Annals of Operations Research, 133 (2005), 63-84. doi: 10.1007/s10479-004-5024-z. Google Scholar
[13]	Z. Luo, J. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, United Kingdom, 1996. doi: 10.1017/CBO9780511983658.
[14]	J. Outrata, M. Ko$\breve{c}$vara and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, Kluwer Academic Publishers, Boston, MA, 1998. doi: 10.1007/978-1-4757-2825-5. Google Scholar
[15]	R. Rockafellar and R. Wets, Variational Analysis, Springer-Verlag, New York, 1998. doi: 10.1007/978-3-642-02431-3.
[16]	S. Scheel and S. Scholtes, Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity, Mathematics of Operation Research, 25 (2000), 1-22. doi: 10.1287/moor.25.1.1.15213. Google Scholar
[17]	S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM Journal on Optimization, 11 (2001), 918-936. doi: 10.1137/S1052623499361233. Google Scholar
[18]	D. Sun and J. Sun, Löwner's operator and spectral functions on Euclidean Jordan algebras, Mathematics of Operation Research, 33 (2008), 421-445. doi: 10.1287/moor.1070.0300. Google Scholar
[19]	D. Sun, J. Sun and L. Zhang, The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming, Mathematical Programming, 114 (2008), 349-391. doi: 10.1007/s10107-007-0105-9. Google Scholar
[20]	E. Takeshi, A Smoothing Method for Mathematical Programs with Second-Order Cone Complementarity Constraints, Master thesis, Kyoto University in Kyoto, 2007.Google Scholar
[21]	Y. Wang, Perturbation Analysis of Optimimization Problems over Symmetric Cones, Ph. D. Thesis, Dalian University of Technology, China, 2008.Google Scholar
[22]	T. Yan and M. Fukushima, Smoothing method for mathematical programs with symmetric cone complementarity constraints, Optimization, 60 (2011), 113-128. doi: 10.1080/02331934.2010.541458. Google Scholar
[23]	Y. Zhang, J. Wu and L. Zhang, First order necessary optimality conditions for mathematical programs with second-order cone complementarity constraint, Journal of Global Optimization, 63 (2015), 253-279. doi: 10.1007/s10898-015-0295-2. Google Scholar
[24]	Y. Zhang, L. Zhang and J. Wu, Convergence properties of a smoothing approach for mathematical programs with second-order cone complementarity constraints, Set-Valued and Variational Analysis, 19 (2011), 609-646. doi: 10.1007/s11228-011-0190-z. Google Scholar

[1]	Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153
[2]	Jie Zhang, Shuang Lin, Li-Wei Zhang. A log-exponential regularization method for a mathematical program with general vertical complementarity constraints. Journal of Industrial & Management Optimization, 2013, 9 (3) : 561-577. doi: 10.3934/jimo.2013.9.561
[3]	Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial & Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53
[4]	Xiao-Hong Liu, Wei-Zhe Gu. Smoothing Newton algorithm based on a regularized one-parametric class of smoothing functions for generalized complementarity problems over symmetric cones. Journal of Industrial & Management Optimization, 2010, 6 (2) : 363-380. doi: 10.3934/jimo.2010.6.363
[5]	X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287
[6]	Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951
[7]	Xin-He Miao, Jein-Shan Chen. Error bounds for symmetric cone complementarity problems. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 627-641. doi: 10.3934/naco.2013.3.627
[8]	Lei Guo, Gui-Hua Lin. Globally convergent algorithm for solving stationary points for mathematical programs with complementarity constraints via nonsmooth reformulations. Journal of Industrial & Management Optimization, 2013, 9 (2) : 305-322. doi: 10.3934/jimo.2013.9.305
[9]	Tim Hoheisel, Christian Kanzow, Alexandra Schwartz. Improved convergence properties of the Lin-Fukushima-Regularization method for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 49-60. doi: 10.3934/naco.2011.1.49
[10]	Liping Pang, Fanyun Meng, Jinhe Wang. Asymptotic convergence of stationary points of stochastic multiobjective programs with parametric variational inequality constraint via SAA approach. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1653-1675. doi: 10.3934/jimo.2018116
[11]	Tohru Nakamura, Shinya Nishibata, Naoto Usami. Convergence rate of solutions towards the stationary solutions to symmetric hyperbolic-parabolic systems in half space. Kinetic & Related Models, 2018, 11 (4) : 757-793. doi: 10.3934/krm.2018031
[12]	Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141
[13]	Michal Kočvara, Jiří V. Outrata. Inverse truss design as a conic mathematical program with equilibrium constraints. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1329-1350. doi: 10.3934/dcdss.2017071
[14]	Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733
[15]	Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019033
[16]	Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial & Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99
[17]	Yongchao Liu. Quantitative stability analysis of stochastic mathematical programs with vertical complementarity constraints. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 451-460. doi: 10.3934/naco.2018028
[18]	Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the PNCP. Journal of Industrial & Management Optimization*, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569
[19]	Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1
[20]	Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

American Institute of Mathematical Sciences