• Previous Article
    A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem
  • JIMO Home
  • This Issue
  • Next Article
    Impact of cap-and-trade regulation on coordinating perishable products supply chain with cost learning
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  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. FanJ. 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. 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.  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. 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.  Google Scholar

[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.  Google Scholar

[15] Z.-Q. LuoJ.-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. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  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. FanJ. 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. 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.  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. 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.  Google Scholar

[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.  Google Scholar

[15] Z.-Q. LuoJ.-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. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  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]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027

[2]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151

[3]

Francisco Braun, Jaume Llibre, Ana Cristina Mereu. Isochronicity for trivial quintic and septic planar polynomial Hamiltonian systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (10) : 5245-5255. doi: 10.3934/dcds.2016029

[4]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79

[5]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133

[6]

Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597

[7]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[8]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[9]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[10]

Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623

[11]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617

[12]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[13]

A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044

[14]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[15]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (13)
  • HTML views (42)
  • Cited by (0)

Other articles
by authors

[Back to Top]