American Institute of Mathematical Sciences

• Previous Article
Second-Order characterizations for set-valued equilibrium problems with variable ordering structures
• JIMO Home
• This Issue
• Next Article
Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
doi: 10.3934/jimo.2021030
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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 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 & Management Optimization, 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.  Google Scholar [2] J. Bochnak, M. Coste and M.-F. Roy, Real Algebraic Geometry, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-662-03718-8.  Google Scholar [3] R. E. Curto and L. A. Fialkow, Truncated K-moment problems in several variable, Journal of Operator Theory, 54 (2005), 189-226.   Google Scholar [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.  Google Scholar [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.  Google Scholar [6] J. Fan, J. Nie and A. Zhou, Tensor eigenvalue complementarity problems, Mathematical Pogramming, 170 (2018), 507-539.  doi: 10.1007/s10107-017-1167-y.  Google Scholar [7] M. Fukushima, Z.-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.  Google Scholar [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.  Google Scholar [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. Google Scholar [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.  Google Scholar [11] J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imperial College Press, 2010.   Google Scholar [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.  Google Scholar [13] L. Li, X. Zhang, Z.-H. Huang and L. Qi, Test of copositive tensors, Journal of Industrial and Management Optimizaiton, 15 (2019), 881-891.  doi: 10.3934/jimo.2018075.  Google Scholar [14] Y.-C. Liang, X.-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.  Google Scholar [15] Z.-Q. Luo, J.-S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, UK, 1996.  doi: 10.1017/CBO9780511983658.  Google Scholar [16] J. Nie, Polynomial optimization with real varieties, SIAM Journal on Optimization, 23 (2013), 1634-1646.  doi: 10.1137/120898772.  Google Scholar [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.  Google Scholar [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.  Google Scholar [19] J. Nie, Z. 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.  Google Scholar [20] X. Wang, X. 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.  Google Scholar [21] J. Wu, L. 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.  Google Scholar [22] X. Zhu, J. Zhang, J. 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.  Google Scholar [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.  Google Scholar [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.  Google Scholar

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.  Google Scholar [2] J. Bochnak, M. Coste and M.-F. Roy, Real Algebraic Geometry, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-662-03718-8.  Google Scholar [3] R. E. Curto and L. A. Fialkow, Truncated K-moment problems in several variable, Journal of Operator Theory, 54 (2005), 189-226.   Google Scholar [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.  Google Scholar [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.  Google Scholar [6] J. Fan, J. Nie and A. Zhou, Tensor eigenvalue complementarity problems, Mathematical Pogramming, 170 (2018), 507-539.  doi: 10.1007/s10107-017-1167-y.  Google Scholar [7] M. Fukushima, Z.-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.  Google Scholar [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.  Google Scholar [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. Google Scholar [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.  Google Scholar [11] J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imperial College Press, 2010.   Google Scholar [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.  Google Scholar [13] L. Li, X. Zhang, Z.-H. Huang and L. Qi, Test of copositive tensors, Journal of Industrial and Management Optimizaiton, 15 (2019), 881-891.  doi: 10.3934/jimo.2018075.  Google Scholar [14] Y.-C. Liang, X.-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.  Google Scholar [15] Z.-Q. Luo, J.-S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, UK, 1996.  doi: 10.1017/CBO9780511983658.  Google Scholar [16] J. Nie, Polynomial optimization with real varieties, SIAM Journal on Optimization, 23 (2013), 1634-1646.  doi: 10.1137/120898772.  Google Scholar [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.  Google Scholar [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.  Google Scholar [19] J. Nie, Z. 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.  Google Scholar [20] X. Wang, X. 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.  Google Scholar [21] J. Wu, L. 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.  Google Scholar [22] X. Zhu, J. Zhang, J. 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.  Google Scholar [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.  Google Scholar [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.  Google Scholar
 [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 & 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 & 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 & 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 & 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 & 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 & 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 & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1 [8] Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010 [9] Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185 [10] Meng Xue, Yun Shi, Hailin Sun. Portfolio optimization with relaxation of stochastic second order dominance constraints via conditional value at risk. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2581-2602. doi: 10.3934/jimo.2019071 [11] Qilin Wang, Shengji Li, Kok Lay Teo. Continuity of second-order adjacent derivatives for weak perturbation maps in vector optimization. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 417-433. doi: 10.3934/naco.2011.1.417 [12] 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 [13] Eugenii Shustin, Emilia Fridman, Leonid Fridman. Oscillations in a second-order discontinuous system with delay. Discrete & Continuous Dynamical Systems, 2003, 9 (2) : 339-358. doi: 10.3934/dcds.2003.9.339 [14] Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965 [15] Jinling Zhao, Wei Chen, Su Zhang. Immediate schedule adjustment and semidefinite relaxation. Journal of Industrial & Management Optimization, 2019, 15 (2) : 633-645. doi: 10.3934/jimo.2018062 [16] Xiaoling Guo, Zhibin Deng, Shu-Cherng Fang, Wenxun Xing. Quadratic optimization over one first-order cone. Journal of Industrial & Management Optimization, 2014, 10 (3) : 945-963. doi: 10.3934/jimo.2014.10.945 [17] Leonardo Colombo, David Martín de Diego. Second-order variational problems on Lie groupoids and optimal control applications. Discrete & Continuous Dynamical Systems, 2016, 36 (11) : 6023-6064. doi: 10.3934/dcds.2016064 [18] Qiong Meng, X. H. Tang. Solutions of a second-order Hamiltonian system with periodic boundary conditions. Communications on Pure & Applied Analysis, 2010, 9 (4) : 1053-1067. doi: 10.3934/cpaa.2010.9.1053 [19] Qilin Wang, Xiao-Bing Li, Guolin Yu. Second-order weak composed epiderivatives and applications to optimality conditions. Journal of Industrial & Management Optimization, 2013, 9 (2) : 455-470. doi: 10.3934/jimo.2013.9.455 [20] W. Sarlet, G. E. Prince, M. Crampin. Generalized submersiveness of second-order ordinary differential equations. Journal of Geometric Mechanics, 2009, 1 (2) : 209-221. doi: 10.3934/jgm.2009.1.209

2020 Impact Factor: 1.801