Finding the Maximum Eigenvalue of Essentially Nonnegative Symmetric Tensors via Sum of Squares Programming

Shenglong Hu, Guoyin Li, Liqun Qi, Yisheng Song

Research output: Journal article publicationJournal articleAcademic researchpeer-review

25 Citations (Scopus)

Abstract

Finding the maximum eigenvalue of a tensor is an important topic in tensor computation and multilinear algebra. Recently, for a tensor with nonnegative entries (which we refer it as a nonnegative tensor), efficient numerical schemes have been proposed to calculate its maximum eigenvalue based on a Perron-Frobenius-type theorem. In this paper, we consider a new class of tensors called essentially nonnegative tensors, which extends the concept of nonnegative tensors, and examine the maximum eigenvalue of an essentially nonnegative tensor using the polynomial optimization techniques. We first establish that finding the maximum eigenvalue of an essentially nonnegative symmetric tensor is equivalent to solving a sum of squares of polynomials (SOS) optimization problem, which, in its turn, can be equivalently rewritten as a semi-definite programming problem. Then, using this sum of squares programming problem, we also provide upper and lower estimates for the maximum eigenvalue of general symmetric tensors. These upper and lower estimates can be calculated in terms of the entries of the tensor. Numerical examples are also presented to illustrate the significance of the results.
Original languageEnglish
Pages (from-to)717-738
Number of pages22
JournalJournal of Optimization Theory and Applications
Volume158
Issue number3
DOIs
Publication statusPublished - 1 Sep 2013

Keywords

  • Maximum eigenvalue
  • Semi-definite programming problem
  • Sum of squares of polynomials
  • Symmetric tensors

ASJC Scopus subject areas

  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Cite this