Tensor Optimization And Eigenvalue Problem

In recent years, tensor optimization and tensor eigenvalue problems arise in manyresearches and applications. This thesis researches some theories and algorithm prob-lems of this rising field.In Chapter1, we give a background of tensor optimization problems and the re-lationship between tensor and vector and matrix. After introducing the problems westudied in this thesis, we add a comment on the notations that will be used in the se-quel.In Chapter2, we research a certain quadratically constrained quadratic program(QCQP) whose variable is a third-order tensor. This problem can be viewed as a gen-eralization of the ordinary QCQP with vector or matrix as it’s variant. Under somemild conditions, we first show that SDP relaxation provides exact optimal solutions forthe original problem. Then we focus on two classes of homogeneous quadratic tensorprograms which have no requirements on the constraints number. For one, we providean easily implemental polynomial-time algorithm to approximately solve the problemand discuss the approximation ratio. For the other, we show there is no gap betweenthe semidefinite relaxation and itself.In Chapter3, first, we propose two polynomial-time algorithms with1m-approximation ratio for the bi-quadratic optimization problem. Then, for the secondalgorithm, we use an easily implemented routine to gain an approximation solution withratio1m. As a special form, we consider the homogenous polynomial optimization toget a1n approximation ratio. In the last subsection, we give some numerical resultsto validate our approximation algorithm presented in subsection3.3.In Chapter4, first we introduce the definition of H-eigenvalue and Z-eigenvalueof a supersymmetric tensor, then we define a new eigenvalue for the unsupersymmetrictensor. Kolda and Mayo [42] propose the shifted symmetric higher-order power methodto solve the Z-eigenvalue problem, after making some changes to this method, by usinga similar approach, we show the convergence of our modified shifted high-order power method.In Chapter5, after introducing the centrosymmetric structure for tensors in subsec-tion5.2, we show some properties about the eigenvalue and eigenvector of centrosym-metric tensor. By exploiting this particular structure, we modify the NQZ-algorithm[68] through replacing the original tensor by a lower dimensional tensor to reduce thecomputation and store cost.