## Invited Session Mon.2.H 0112

#### Monday, 13:15 - 14:45 h, Room: H 0112

**Cluster 16: Nonlinear programming** [...]

### Structures, complexities, and eigenvalues of tensor forms and polynomial functions

**Chair: Shuzhong Zhang**

**Monday, 13:15 - 13:40 h, Room: H 0112, Talk 1**

**Shuzhong Zhang**

Cones of nonnegative quartic polynomial functions and their applications

**Coauthors: Bo Jiang, Zhening Li**

**Abstract:**

Polynomial and tensor optimization models have proved to be useful in a wide range of applications in engineering and scientific computation. Applications aside, the structure of higher order polynomial/tensor functions however remains largely unknown. For example, the computational status to test if a quartic function is convex or not had remained an open problem until 2010 when Ahmadi et al. proved that it is in fact strongly NP hard. In this talk we discuss six particular convex cones generated from the nonnegative quartic polynomial functions. Our goal is to illustrate the rich structure of nonnegative quartic polynomial functions. In particular, these convex cones are in decreasing order, much like the Russian Matryoshka dolls, with varying computational complexities. We discuss the modeling power and applications of these convex cones. In the context of these cones we also introduce an interesting result known as Hilbert's identity, and discuss its role in our study.

**Monday, 13:45 - 14:10 h, Room: H 0112, Talk 2**

**Lek-Heng Lim**

3-tensors as the boundary of tractability

**Coauthor: Christopher Hillar**

**Abstract:**

Why do problems in numerical computing become intractable as they transition from linear to nonlinear or convex to nonconvex? We shall argue that 3-tensor problems form the boundary separating the tractability of linear algebra and convex optimization from the intractability of polynomial algebra and nonconvex optimization - 3-tensor analogues of many efficiently computable matrix problems are NP-hard. Our list includes: determining the feasibility of a system of bilinear equations, deciding whether a 3-tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or spectral norm; determining the rank or a best rank-1 approximation to a 3-tensor. Additionally, some of these problems have no polynomial time approximation schemes, some are undecidable over **Q**, and at least one enumerative version is #P-complete. Restricting these problems to symmetric 3-tensors does not alleviate their NP-hardness.

**Monday, 14:15 - 14:40 h, Room: H 0112, Talk 3**

**Qingzhi Yang**

Some properties of tensors’ eigenvalues and related optimization problem

**Abstract:**

In this talk, I will focus on the properties of tensors’ eigenvalues and related optimization problem. The tensor is an array of high dimensional data, which can be viewed as the extension of the vector and matrix. In the past some years, especially recent years, due to the needs of real problems, the study on the tensors attracts a great attention. Several different definitions of eigenvalues of tensors were presented, and various properties with respect to tensors’ eigenvalues were put forward, some interesting conclusions were generalized from the matrix to tensor, such as the Perron-Frobenius theorem for nonnegative matrix. In addition, for some problems one has to find the largest or smallest eigenvalues of tensors, which can be written as some special constrained optimization problem(s). I will introduce the recent development in properties of tensors’ eigenvalues as well as the algorithms for solving the related optimization problem(s).