Completely Positive Programming And Some Related Problems

A symmetric matrix C is completely positive(CP)if there exists an entry-wise nonnegative matrix U such that C=UUT.Nowadays,completely positive programming has become an important and frontier research topic in optimization with significant theoretical value and practical application background.It has wide applications in combinatorics and statistis,etc.This Ph.D.dissertation mainly focuses on the problems arising in the completely positive programming and some related problems.See below for details:First of all,we give a brief introduction about the relevant background and development to our work.It was shown that checking whether a matrix is CP or not is NP-hard.The CP-matrix completion problem is more difficult,and is an open question in matrix theory.We propose a semidefinite algorithm for solving general CP-completion problems,and study its properties.When all the diagonal entries are given,the algorithm can give a certificate if a partial matrix is not CP-completable,and it almost always gives a CP-completion if it is CP-completable.When diagonal entries are partially given,similar properties hold.Another hard problem is how to check whether a matrix is in the interior of the CP cone,and little work is known for checking interiors or boundaries of the CP cone.We characterize this problem from the view of optimization and formu-late it as a linear optimization problem with moments.A semidefinite algorithm is proposed,and its properties are studied.A CP-decomposition of a matrix in Dickinson's form can also be obtained if it is an interior of the CP cone.As an extension of CP matrix,checking whether a matrix is partially positive(PP)or not is also NP-hard.And there is little work on this.We give a character-ization of partially positive matrices.Two algorithms are presented for checking whether a matrix is partially positive or not.Their properties are studied.A PP-decomposition of a matrix can also be obtained,if it is partially positive.Based on the above-mentioned work,we consider the more complicated CP-matrix approximation problem,which is to approximate a given matrix by a CP matrix under some linear constraints,in the general p-norm(p=1,2,?,or F).We formulate the problem as a linear optimization problem with the p-norm cone and the cone of moments,then construct a hierarchy of semidefinite relaxations for solving it.The finite convergence of our algorithm is also studied.If it is infeasible,we can get a certificate for that.Otherwise,we can always get a best CP approximation,and a CP decomposition can also be obtained.We are also concerned with the problem of computing the distance between the linear matrix pencil and the completely positive cone.We formulate it as a linear optimization problem with the cone of moments and the second order cone.A semidefinite relaxation algorithm is presented and the convergence is studied.We also propose a new model for checking the membership in the completely positive cone.Finally,we consider some problems in tensor optimization.Completely posi-tive tensor is an extension of the CP matrix.Checking whether a tensor is complete-ly positive or not is also NP-hard.We characterize the completely positive tensor as a truncated moment sequence,and transform the problem of checking whether a tensor is completely positive to checking whether its corresponding truncated moment sequence admits a representing measure.Then we present a semidefinite algorithm to solve it.If a tensor is not completely positive,a certificate for it can be obtained;if it is completely positive,a nonnegative decomposition can be obtained.Tensor eigenvalue complementarity problem is also an NP-hard problem.Ba-sic properties of standard and complementarity tensor eigenvalues are discussed.We formulate the tensor eigenvalue complementarity problem equivalently as poly-nomial optimization by a randomization process.If the number of complementar-ity eigenvalues is finite,then they can be computed sequentially.The formulated polynomial optimization can be solved by Lasserre's hierarchy of semidefinite re-laxations.We show that it has finite convergence for general tensors.Numerical experiments are presented to show the efficiency of proposed methods.