May  2022, 18(3): 1505-1517. doi: 10.3934/jimo.2021030

Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints

School of Mathematics, Tianjin University, 135 Yaguan Road, Tianjin 300354, China

* Corresponding author: Xinzhen Zhang

Received  May 2020 Revised  November 2020 Published  May 2022 Early access  February 2021

Fund Project: The work is supported by National Natural Science Foundation of China grant 11871369

Polynomial optimization problem with second-order cone complementarity constraints (SOCPOPCC) is a special case of mathematical program with second-order cone complementarity constraints (SOCMPCC). In this paper, we consider how to apply Lasserre's type of semidefinite relaxation method to solve SOCPOPCC. To this end, we first reformulate SOCPOPCC equivalently as a polynomial optimization and then solve the reformulated polynomial optimization with semidefinite relaxation method. For a special case of SOCPOPCC, we present another reformulation of polynomial optimization, which is of lower degree. SDP relaxation method is applied to solve the new polynomial optimization. Numerical examples are reported to show the efficiency of our proposed method.

Citation: Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030
References:
[1]

F. Alizadeh and D. Goldfarb, Second-order cone programming, Mathematical Programming, 95 (2003), 3-51.  doi: 10.1007/s10107-002-0339-5.

[2]

J. Bochnak, M. Coste and M.-F. Roy, Real Algebraic Geometry, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-662-03718-8.

[3]

R. E. Curto and L. A. Fialkow, Truncated K-moment problems in several variable, Journal of Operator Theory, 54 (2005), 189-226. 

[4]

L. Cheng and X. Zhang, A semidefinite relaxation method for second-order cone polynomial complementarity problems, Computational Optimization and Applications, 75 (2020), 629-647.  doi: 10.1007/s10589-019-00162-1.

[5]

L. Cheng, X. Zhang and G. Ni, A semidefinite relaxation method for second-order cone tensor eigenvalue complementarity problems, Journal of Global Optimization, (2020). doi: 10.1007/s10898-020-00954-4.

[6]

J. FanJ. Nie and A. Zhou, Tensor eigenvalue complementarity problems, Mathematical Pogramming, 170 (2018), 507-539.  doi: 10.1007/s10107-017-1167-y.

[7]

M. FukushimaZ.-Q. Luo and P. Tseng, Smoothing functions for second-order cone complementarity problems, SIAM Journal on Optimization, 12 (2001), 436-460.  doi: 10.1137/S1052623400380365.

[8]

J. W. Helton and J. Nie, A semidefinite approach for truncated K-moment problems, Foundations of Computational Mathematics, 12 (2012), 851-881.  doi: 10.1007/s10208-012-9132-x.

[9]

M. Ko$\breve{c}$vara, J. Outrata and J. Zowe, Nonsmooth approach to optimization problem with equilibrium constraints: Theory, application and numerical results, Computers and Mathematics with applications, 1999.

[10]

J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization, 11 (2001), 796-817.  doi: 10.1137/S1052623400366802.

[11] J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imperial College Press, 2010. 
[12]

M. Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging Applications of Algebraic Geometry, IMA Volumes in Mathematics and its Applications (Eds. M. Putinar and S. Sullivant), Springer, 149 2009,157–270. doi: 10.1007/978-0-387-09686-5_7.

[13]

L. LiX. ZhangZ.-H. Huang and L. Qi, Test of copositive tensors, Journal of Industrial and Management Optimizaiton, 15 (2019), 881-891.  doi: 10.3934/jimo.2018075.

[14]

Y.-C. LiangX.-D. Zhu and G.-H. Lin, Necessary optimality conditions for mathematical programs with second-order cone complementarity constraints, Set Valued and Variational Analysis, 22 (2014), 59-78.  doi: 10.1007/s11228-013-0250-7.

[15] Z.-Q. LuoJ.-S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, UK, 1996.  doi: 10.1017/CBO9780511983658.
[16]

J. Nie, Polynomial optimization with real varieties, SIAM Journal on Optimization, 23 (2013), 1634-1646.  doi: 10.1137/120898772.

[17]

J. Nie, Certifying convergence of Lasserre's hierarchy via flat truncation, Mathematical Programming, 142 (2013), 485-510.  doi: 10.1007/s10107-012-0589-9.

[18]

J. Nie, Optimality conditions and finite convergence of Lasserre's hierarchy, Mathematical Programming, 146 (2014), 97-121.  doi: 10.1007/s10107-013-0680-x.

[19]

J. NieZ. Yang and X. Zhang, A complete semidefinite algorithm for detecting copositive matrices and tensors, SIAM Journal on Optimization, 28 (2018), 2902-2921.  doi: 10.1137/17M115308X.

[20]

X. WangX. Zhang and G. Zhou, SDP relaxation algorithms for $\mathbb{P}(\mathbb{P}_0)$-tensor detection, Computational Optimization and Applications, 75 (2020), 739-752.  doi: 10.1007/s10589-019-00145-2.

[21]

J. WuL. Zhang and Y. Zhang, A smoothing Newton method for mathematical programs governed by second-order cone constrained generalized equations, Journal of Global Optimization, 55 (2013), 359-385.  doi: 10.1007/s10898-012-9880-9.

[22]

X. ZhuJ. ZhangJ. Zhou and X. Yang, Mathematical programs with second-order cone complementarity constraints: Strong stationarity and approximation method, Journal of Optimization Theory and Applications, 181 (2019), 521-540.  doi: 10.1007/s10957-018-01464-w.

[23]

J. J. Ye and J. Zhou, First-order optimality conditions for mathematical programs with second-order cone complementarity constraints, SIAM Journal on Optimization, 26 (2016), 2820-2846.  doi: 10.1137/16M1055554.

[24]

J. J. Ye and J. Zhou, Exact formulas for the proximal/regular/limiting normal cone of the second-order cone complementarity set, Mathematical Programming, 162 (2017), 33-50.  doi: 10.1007/s10107-016-1027-1.

show all references

References:
[1]

F. Alizadeh and D. Goldfarb, Second-order cone programming, Mathematical Programming, 95 (2003), 3-51.  doi: 10.1007/s10107-002-0339-5.

[2]

J. Bochnak, M. Coste and M.-F. Roy, Real Algebraic Geometry, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-662-03718-8.

[3]

R. E. Curto and L. A. Fialkow, Truncated K-moment problems in several variable, Journal of Operator Theory, 54 (2005), 189-226. 

[4]

L. Cheng and X. Zhang, A semidefinite relaxation method for second-order cone polynomial complementarity problems, Computational Optimization and Applications, 75 (2020), 629-647.  doi: 10.1007/s10589-019-00162-1.

[5]

L. Cheng, X. Zhang and G. Ni, A semidefinite relaxation method for second-order cone tensor eigenvalue complementarity problems, Journal of Global Optimization, (2020). doi: 10.1007/s10898-020-00954-4.

[6]

J. FanJ. Nie and A. Zhou, Tensor eigenvalue complementarity problems, Mathematical Pogramming, 170 (2018), 507-539.  doi: 10.1007/s10107-017-1167-y.

[7]

M. FukushimaZ.-Q. Luo and P. Tseng, Smoothing functions for second-order cone complementarity problems, SIAM Journal on Optimization, 12 (2001), 436-460.  doi: 10.1137/S1052623400380365.

[8]

J. W. Helton and J. Nie, A semidefinite approach for truncated K-moment problems, Foundations of Computational Mathematics, 12 (2012), 851-881.  doi: 10.1007/s10208-012-9132-x.

[9]

M. Ko$\breve{c}$vara, J. Outrata and J. Zowe, Nonsmooth approach to optimization problem with equilibrium constraints: Theory, application and numerical results, Computers and Mathematics with applications, 1999.

[10]

J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization, 11 (2001), 796-817.  doi: 10.1137/S1052623400366802.

[11] J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imperial College Press, 2010. 
[12]

M. Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging Applications of Algebraic Geometry, IMA Volumes in Mathematics and its Applications (Eds. M. Putinar and S. Sullivant), Springer, 149 2009,157–270. doi: 10.1007/978-0-387-09686-5_7.

[13]

L. LiX. ZhangZ.-H. Huang and L. Qi, Test of copositive tensors, Journal of Industrial and Management Optimizaiton, 15 (2019), 881-891.  doi: 10.3934/jimo.2018075.

[14]

Y.-C. LiangX.-D. Zhu and G.-H. Lin, Necessary optimality conditions for mathematical programs with second-order cone complementarity constraints, Set Valued and Variational Analysis, 22 (2014), 59-78.  doi: 10.1007/s11228-013-0250-7.

[15] Z.-Q. LuoJ.-S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, UK, 1996.  doi: 10.1017/CBO9780511983658.
[16]

J. Nie, Polynomial optimization with real varieties, SIAM Journal on Optimization, 23 (2013), 1634-1646.  doi: 10.1137/120898772.

[17]

J. Nie, Certifying convergence of Lasserre's hierarchy via flat truncation, Mathematical Programming, 142 (2013), 485-510.  doi: 10.1007/s10107-012-0589-9.

[18]

J. Nie, Optimality conditions and finite convergence of Lasserre's hierarchy, Mathematical Programming, 146 (2014), 97-121.  doi: 10.1007/s10107-013-0680-x.

[19]

J. NieZ. Yang and X. Zhang, A complete semidefinite algorithm for detecting copositive matrices and tensors, SIAM Journal on Optimization, 28 (2018), 2902-2921.  doi: 10.1137/17M115308X.

[20]

X. WangX. Zhang and G. Zhou, SDP relaxation algorithms for $\mathbb{P}(\mathbb{P}_0)$-tensor detection, Computational Optimization and Applications, 75 (2020), 739-752.  doi: 10.1007/s10589-019-00145-2.

[21]

J. WuL. Zhang and Y. Zhang, A smoothing Newton method for mathematical programs governed by second-order cone constrained generalized equations, Journal of Global Optimization, 55 (2013), 359-385.  doi: 10.1007/s10898-012-9880-9.

[22]

X. ZhuJ. ZhangJ. Zhou and X. Yang, Mathematical programs with second-order cone complementarity constraints: Strong stationarity and approximation method, Journal of Optimization Theory and Applications, 181 (2019), 521-540.  doi: 10.1007/s10957-018-01464-w.

[23]

J. J. Ye and J. Zhou, First-order optimality conditions for mathematical programs with second-order cone complementarity constraints, SIAM Journal on Optimization, 26 (2016), 2820-2846.  doi: 10.1137/16M1055554.

[24]

J. J. Ye and J. Zhou, Exact formulas for the proximal/regular/limiting normal cone of the second-order cone complementarity set, Mathematical Programming, 162 (2017), 33-50.  doi: 10.1007/s10107-016-1027-1.

[1]

Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951

[2]

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050

[3]

Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089

[4]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171

[5]

Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111

[6]

Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial and Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703

[7]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1

[8]

Xin-He Miao, Kai Yao, Ching-Yu Yang, Jein-Shan Chen. Levenberg-Marquardt method for absolute value equation associated with second-order cone. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 47-61. doi: 10.3934/naco.2021050

[9]

Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010

[10]

Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185

[11]

Meng Xue, Yun Shi, Hailin Sun. Portfolio optimization with relaxation of stochastic second order dominance constraints via conditional value at risk. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2581-2602. doi: 10.3934/jimo.2019071

[12]

Qilin Wang, Shengji Li, Kok Lay Teo. Continuity of second-order adjacent derivatives for weak perturbation maps in vector optimization. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 417-433. doi: 10.3934/naco.2011.1.417

[13]

José F. Cariñena, Javier de Lucas Araujo. Superposition rules and second-order Riccati equations. Journal of Geometric Mechanics, 2011, 3 (1) : 1-22. doi: 10.3934/jgm.2011.3.1

[14]

Eugenii Shustin, Emilia Fridman, Leonid Fridman. Oscillations in a second-order discontinuous system with delay. Discrete and Continuous Dynamical Systems, 2003, 9 (2) : 339-358. doi: 10.3934/dcds.2003.9.339

[15]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965

[16]

Jinling Zhao, Wei Chen, Su Zhang. Immediate schedule adjustment and semidefinite relaxation. Journal of Industrial and Management Optimization, 2019, 15 (2) : 633-645. doi: 10.3934/jimo.2018062

[17]

Xiaoling Guo, Zhibin Deng, Shu-Cherng Fang, Wenxun Xing. Quadratic optimization over one first-order cone. Journal of Industrial and Management Optimization, 2014, 10 (3) : 945-963. doi: 10.3934/jimo.2014.10.945

[18]

Leonardo Colombo, David Martín de Diego. Second-order variational problems on Lie groupoids and optimal control applications. Discrete and Continuous Dynamical Systems, 2016, 36 (11) : 6023-6064. doi: 10.3934/dcds.2016064

[19]

Qiong Meng, X. H. Tang. Solutions of a second-order Hamiltonian system with periodic boundary conditions. Communications on Pure and Applied Analysis, 2010, 9 (4) : 1053-1067. doi: 10.3934/cpaa.2010.9.1053

[20]

Qilin Wang, Xiao-Bing Li, Guolin Yu. Second-order weak composed epiderivatives and applications to optimality conditions. Journal of Industrial and Management Optimization, 2013, 9 (2) : 455-470. doi: 10.3934/jimo.2013.9.455

2020 Impact Factor: 1.801

Article outline

[Back to Top]