• Previous Article
    Optimal pricing and ordering strategies for dual-channel retailing with different shipping policies
  • JIMO Home
  • This Issue
  • Next Article
    Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
doi: 10.3934/jimo.2022073
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.

Quadratic tensor eigenvalue complementarity problems

1. 

School of Mathematics, Shanghai University of Finance and Economics, Shanghai 200433, China

2. 

School of Mathematical Sciences, Key Lab of Scientific and Engineering Computing (Ministry of Education), Shanghai Jiao Tong University, Shanghai 200240, China

*Corresponding author: Ruixue Zhao

Received  October 2021 Revised  March 2022 Early access April 2022

Fund Project: The first author is supported by the Science and Technology Commission of Shanghai Municipality grant 22YF1412400, the second author is supported by NSFC grant 11971309

In this paper, we study the quadratic tensor eigenvalue complementarity problem (QTEiCP). By a randomization process, the quadratic complementarity(QC) eigenvalues are classified into two cases. For each case, the QTEiCP is formulated as an equivalent generalized moment problem. The QC eigenvectors can be computed in order. Each of them can be solved by a sequence of semidefinite relaxations. We prove that such a sequence converges in finitely many steps for generic tensors.

Citation: Ruixue Zhao, Jinyan Fan. Quadratic tensor eigenvalue complementarity problems. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2022073
References:
[1]

F. BugarinD. Henrion and J. B. Lasserre, Minimizing the sum of many rational functions, Math. Prog. Comp., 8 (2016), 83-111.  doi: 10.1007/s12532-015-0089-z.

[2]

Z. Chen and L. Qi, A semismooth Newton method for tensor eigenvalue complementarity problem, Comput. Optim. Appl., 65 (2016), 109-126.  doi: 10.1007/s10589-016-9838-9.

[3]

Z. ChenQ. Yang and L. Ye, Generalized eigenvalue complementarity problem for tensors, Pac. J. Optim., 13 (2017), 527-545. 

[4]

R. Curto and L. Fialkow, Truncated K-moment problems in several variables, J. Operator Theory, 54 (2005), 189-226. 

[5]

J. FanJ. Nie and R. Zhao, The maximum tensor complementarity eigenvalues, Optim. Methods Softw., 35 (2020), 1179-1190.  doi: 10.1080/10556788.2018.1528251.

[6]

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

[7]

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

[8]

D. Henrion and J. Lasserre, Detecting global optimality and extracting solutions in GloptiPoly, Positive Polynomials in Control, 312 (2005), 293-310.  doi: 10.1007/10997703_15.

[9]

D. HenrionJ. Lasserre and J. Löefberg, GloptiPoly 3: Moments, optimization and semidefinite programming, Optim. Methods Softw., 24 (2009), 761-779.  doi: 10.1080/10556780802699201.

[10]

J. B. Lasserre, A semidefinite programming approach to the generalized problem of moments, Math. Program, 112 (2008), 65-92.  doi: 10.1007/s10107-006-0085-1.

[11] J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imperial College Press, London, 2010. 
[12] J. B. Lasserre, Introduction to Polynomial and Semi-Algebraic Optimization, Cambridge University Press, Cambridge, 2015.  doi: 10.1017/CBO9781107447226.
[13]

J. LasserreM. Laurent and P. Rostalski, Semidefinite characterization and computation of zero-dimensional real radical ideals, Found. Comput. Math., 8 (2008), 607-647.  doi: 10.1007/s10208-007-9004-y.

[14]

M. Laurent, Optimization over polynomials: Selected topics, Congress of Mathematicians—Seoul 2014, (2014), 843-869. 

[15]

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

[16]

Y. LiS. Du and L. Zhang, Tensor quadratic eigenvalue complementarity problem, Pac. J. Optm., 17 (2021), 251-268. 

[17]

C. LingH. He and L. Qi, On the cone eigenvalue complementarity problem for higher-order tensors, Comput. Optim. Appl., 63 (2016), 143-168.  doi: 10.1007/s10589-015-9767-z.

[18]

C. LingH. He and L. Qi, Higher-order eigenvalue complementarity problems for tensors, Comput. Optim. Appl., 64 (2016), 149-176.  doi: 10.1007/s10589-015-9805-x.

[19]

M. NgL. Qi and G. Zhou, Finding the largest eigenvalue of a nonnegative tensor, SIAM J. Matrix Anal. Appl., 31 (2009), 1090-1099.  doi: 10.1137/09074838X.

[20]

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

[21]

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

[22]

J. Nie, The A-truncated K-moment problem, Found. Comput. Math., 14 (2014), 1243-1276.  doi: 10.1007/s10208-014-9225-9.

[23]

J. Nie, Linear optimization with cones of moments and nonnegative polynomials, Math. Program., 153 (2015), 247-274.  doi: 10.1007/s10107-014-0797-6.

[24]

L. QiG. Yu and E. X. Wu, Higher order positive semidefinite diffusion tensor imaging, SIAM J. Imaging Sci., 3 (2010), 416-433.  doi: 10.1137/090755138.

[25]

J. F. Sturm, SeDuMi 1.02: A MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11/12 (1999), 625-653.  doi: 10.1080/10556789908805766.

[26]

X. Zhao and J. Fan, A semidefinte method for tensor complementarity problems, Optim. Methods Softw., 34 (2019), 758-769.  doi: 10.1080/10556788.2018.1439489.

[27]

R. Zhao and J. Fan, Higher-degree tensor eigenvalue complementarity problems, Comput. Optim. Appl., 75 (2020), 799-816.  doi: 10.1007/s10589-019-00159-w.

[28]

R. X. ZhaoA. W. Zhou and J. Y. Fan, The quadratic tensor eigenvalue complementarity problem (in Chinese), Sci. Sin. Math., (2021). 

show all references

References:
[1]

F. BugarinD. Henrion and J. B. Lasserre, Minimizing the sum of many rational functions, Math. Prog. Comp., 8 (2016), 83-111.  doi: 10.1007/s12532-015-0089-z.

[2]

Z. Chen and L. Qi, A semismooth Newton method for tensor eigenvalue complementarity problem, Comput. Optim. Appl., 65 (2016), 109-126.  doi: 10.1007/s10589-016-9838-9.

[3]

Z. ChenQ. Yang and L. Ye, Generalized eigenvalue complementarity problem for tensors, Pac. J. Optim., 13 (2017), 527-545. 

[4]

R. Curto and L. Fialkow, Truncated K-moment problems in several variables, J. Operator Theory, 54 (2005), 189-226. 

[5]

J. FanJ. Nie and R. Zhao, The maximum tensor complementarity eigenvalues, Optim. Methods Softw., 35 (2020), 1179-1190.  doi: 10.1080/10556788.2018.1528251.

[6]

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

[7]

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

[8]

D. Henrion and J. Lasserre, Detecting global optimality and extracting solutions in GloptiPoly, Positive Polynomials in Control, 312 (2005), 293-310.  doi: 10.1007/10997703_15.

[9]

D. HenrionJ. Lasserre and J. Löefberg, GloptiPoly 3: Moments, optimization and semidefinite programming, Optim. Methods Softw., 24 (2009), 761-779.  doi: 10.1080/10556780802699201.

[10]

J. B. Lasserre, A semidefinite programming approach to the generalized problem of moments, Math. Program, 112 (2008), 65-92.  doi: 10.1007/s10107-006-0085-1.

[11] J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imperial College Press, London, 2010. 
[12] J. B. Lasserre, Introduction to Polynomial and Semi-Algebraic Optimization, Cambridge University Press, Cambridge, 2015.  doi: 10.1017/CBO9781107447226.
[13]

J. LasserreM. Laurent and P. Rostalski, Semidefinite characterization and computation of zero-dimensional real radical ideals, Found. Comput. Math., 8 (2008), 607-647.  doi: 10.1007/s10208-007-9004-y.

[14]

M. Laurent, Optimization over polynomials: Selected topics, Congress of Mathematicians—Seoul 2014, (2014), 843-869. 

[15]

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

[16]

Y. LiS. Du and L. Zhang, Tensor quadratic eigenvalue complementarity problem, Pac. J. Optm., 17 (2021), 251-268. 

[17]

C. LingH. He and L. Qi, On the cone eigenvalue complementarity problem for higher-order tensors, Comput. Optim. Appl., 63 (2016), 143-168.  doi: 10.1007/s10589-015-9767-z.

[18]

C. LingH. He and L. Qi, Higher-order eigenvalue complementarity problems for tensors, Comput. Optim. Appl., 64 (2016), 149-176.  doi: 10.1007/s10589-015-9805-x.

[19]

M. NgL. Qi and G. Zhou, Finding the largest eigenvalue of a nonnegative tensor, SIAM J. Matrix Anal. Appl., 31 (2009), 1090-1099.  doi: 10.1137/09074838X.

[20]

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

[21]

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

[22]

J. Nie, The A-truncated K-moment problem, Found. Comput. Math., 14 (2014), 1243-1276.  doi: 10.1007/s10208-014-9225-9.

[23]

J. Nie, Linear optimization with cones of moments and nonnegative polynomials, Math. Program., 153 (2015), 247-274.  doi: 10.1007/s10107-014-0797-6.

[24]

L. QiG. Yu and E. X. Wu, Higher order positive semidefinite diffusion tensor imaging, SIAM J. Imaging Sci., 3 (2010), 416-433.  doi: 10.1137/090755138.

[25]

J. F. Sturm, SeDuMi 1.02: A MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11/12 (1999), 625-653.  doi: 10.1080/10556789908805766.

[26]

X. Zhao and J. Fan, A semidefinte method for tensor complementarity problems, Optim. Methods Softw., 34 (2019), 758-769.  doi: 10.1080/10556788.2018.1439489.

[27]

R. Zhao and J. Fan, Higher-degree tensor eigenvalue complementarity problems, Comput. Optim. Appl., 75 (2020), 799-816.  doi: 10.1007/s10589-019-00159-w.

[28]

R. X. ZhaoA. W. Zhou and J. Y. Fan, The quadratic tensor eigenvalue complementarity problem (in Chinese), Sci. Sin. Math., (2021). 

[1]

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

[2]

Mengmeng Zheng, Ying Zhang, Zheng-Hai Huang. Global error bounds for the tensor complementarity problem with a P-tensor. Journal of Industrial and Management Optimization, 2019, 15 (2) : 933-946. doi: 10.3934/jimo.2018078

[3]

David Bourne, Howard Elman, John E. Osborn. A Non-Self-Adjoint Quadratic Eigenvalue Problem Describing a Fluid-Solid Interaction Part II: Analysis of Convergence. Communications on Pure and Applied Analysis, 2009, 8 (1) : 143-160. doi: 10.3934/cpaa.2009.8.143

[4]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117

[5]

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

[6]

Wanbin Tong, Hongjin He, Chen Ling, Liqun Qi. A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 425-437. doi: 10.3934/naco.2020042

[7]

H. M. Hastings, S. Silberger, M. T. Weiss, Y. Wu. A twisted tensor product on symbolic dynamical systems and the Ashley's problem. Discrete and Continuous Dynamical Systems, 2003, 9 (3) : 549-558. doi: 10.3934/dcds.2003.9.549

[8]

Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2553-2566. doi: 10.3934/jimo.2021080

[9]

Ya Li, ShouQiang Du, YuanYuan Chen. Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems. Journal of Industrial and Management Optimization, 2022, 18 (1) : 157-172. doi: 10.3934/jimo.2020147

[10]

X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287

[11]

Tijana Levajković, Hermann Mena, Amjad Tuffaha. The stochastic linear quadratic optimal control problem in Hilbert spaces: A polynomial chaos approach. Evolution Equations and Control Theory, 2016, 5 (1) : 105-134. doi: 10.3934/eect.2016.5.105

[12]

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

[13]

John Fogarty. On Noether's bound for polynomial invariants of a finite group. Electronic Research Announcements, 2001, 7: 5-7.

[14]

Alexander Moreto. Complex group algebras of finite groups: Brauer's Problem 1. Electronic Research Announcements, 2005, 11: 34-39.

[15]

Florian Méhats, Olivier Pinaud. A problem of moment realizability in quantum statistical physics. Kinetic and Related Models, 2011, 4 (4) : 1143-1158. doi: 10.3934/krm.2011.4.1143

[16]

Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911

[17]

Stuart S. Antman, David Bourne. A Non-Self-Adjoint Quadratic Eigenvalue Problem Describing a Fluid-Solid Interaction Part I: Formulation, Analysis, and Computations. Communications on Pure and Applied Analysis, 2009, 8 (1) : 123-142. doi: 10.3934/cpaa.2009.8.123

[18]

Mary Wilkerson. Thurston's algorithm and rational maps from quadratic polynomial matings. Discrete and Continuous Dynamical Systems - S, 2019, 12 (8) : 2403-2433. doi: 10.3934/dcdss.2019151

[19]

Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial and Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99

[20]

Arezu Zare, Mohammad Keyanpour, Maziar Salahi. On fractional quadratic optimization problem with two quadratic constraints. Numerical Algebra, Control and Optimization, 2020, 10 (3) : 301-315. doi: 10.3934/naco.2020003

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (116)
  • HTML views (35)
  • Cited by (0)

Other articles
by authors

[Back to Top]