A semidefinite algorithm for completely positive tensor decomposition

A symmetric tensor, which has a symmetric nonnegative decomposition, is called a completely positive tensor. In this paper, 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 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.     

Completely positive reformulations for polynomial optimization

Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution schemes for quadratic polynomial optimization problems have been designed by drawing on conic programming tools, and the extensively studied cones of completely positive and of copositive matrices. In particular, this approach has been applied to solve key combinatorial optimization problems. Along this line of research, we consider polynomial optimization problems that are not necessarily quadratic. For this purpose, we use a natural extension of the cone of completely positive matrices; namely, the cone of completely positive tensors. We provide a general characterization of the class of polynomial optimization problems that can be formulated as a conic program over the cone of completely positive tensors. As a consequence of this characterization, it follows that recent related results for quadratic problems can be further strengthened and generalized to higher order polynomial optimization problems. Also, we show that the conditions underlying the characterization are conceptually the same, regardless of the degree of the polynomials defining the problem. To illustrate our results, we discuss in further detail special and relevant instances of polynomial optimization problems.     

Completely positive semidefinite rank

Mathematical Programming - An $$ntimes n$$ matrix X is called completely positive semidefinite (cpsd) if there exist $$dtimes d$$ Hermitian positive semidefinite matrices $${P_i}_{i=1}^n$$ (for...     

A note on semidefinite programming relaxations for polynomial optimization over a single sphere

We study two instances of polynomial optimization problem over a single sphere. The first problem is to compute the best rank-1 tensor approximation. We show the equivalence between two recent semidefinite relaxations methods. The other one arises from Bose-Einstein condensates (BEC), whose objective function is a summation of a probably nonconvex quadratic function and a quartic term. These two polynomial optimization problems are closely connected since the BEC problem can be viewed as a structured fourth-order best rank-1 tensor approximation. We show that the BEC problem is NP-hard and propose a semidefinite relaxation with both deterministic and randomized rounding procedures. Explicit approximation ratios for these rounding procedures are presented. The performance of these semidefinite relaxations are illustrated on a few preliminary numerical experiments.     

Completely positive reformulations of polynomial optimization problems with linear constraints

A polynomial optimization problem (POP) is an optimization problem in which both the objective and constraints can be written in terms of polynomials on the decision variables. Recently, it has been shown that under appropriate assumptions POPs can be reformulated as conic problems over the cone of completely positive tensors; which generalize the set of completely positive matrices. Here, we show that by explicitly handling the linear constraints in the formulation of the POP, one obtains a generalization of the completely positive reformulation of quadratically constrained quadratic programs recently introduced by Bai et al. (Math Program 1–28, 2016).     

Solving polynomial least squares problems via semidefinite programming relaxations

A polynomial optimization problem whose objective function is represented as a sum of positive and even powers of polynomials, called a polynomial least squares problem, is considered. Methods to transform a polynomial least square problem to polynomial semidefinite programs to reduce degrees of the polynomials are discussed. Computational efficiency of solving the original polynomial least squares problem and the transformed polynomial semidefinite programs is compared. Numerical results on selected polynomial least square problems show better computational performance of a transformed polynomial semidefinite program, especially when degrees of the polynomials are larger.     

Completely positive module maps and completely positive extreme maps

Let be unital -algebras and be the set of all completely positive linear maps of into . In this article we characterize the extreme elements in , for all , and pure elements in in terms of a self-dual Hilbert module structure induced by each in . Let be the subset of consisting of -module maps for a von Neumann algebra . We characterize normal elements in to be extreme. Results here generalize various earlier results by Choi, Paschke and Lin.

     

On approximating complex quadratic optimization problems via semidefinite programming relaxations

In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive semidefinite (in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an -approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain the well-known π /4 result due to Ben-Tal et al. [Math Oper Res 28(3):497–523, 2003], and independently, Zhang and Huang [SIAM J Optim 16(3):871–890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and that of the SDP relaxation can be arbitrarily close to π /4. We also show that the unified analysis can be used to obtain an Ω(1/ log n)-approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite. This research was supported in part by NSF grant DMS-0306611.     

Infinite tensor products of completely positive semigroups

We construct a new class of semigroups of completely positive maps on which can be decomposed into an infinite tensor product of such semigroups. Under suitable hypotheses, the minimal dilations of these semigroups to E ₀-semigroups are pure, and have no normal invariant states. Concrete examples are discussed in some detail.     

Completely positive tensor recovery with minimal nuclear value

In this paper, we introduce the CP-nuclear value of a completely positive (CP) tensor and study its properties. A semidefinite relaxation algorithm is proposed for solving the minimal CP-nuclear-value tensor recovery. If a partial tensor is CP-recoverable, the algorithm can give a CP tensor recovery with the minimal CP-nuclear value, as well as a CP-nuclear decomposition of the recovered CP tensor. If it is not CP-recoverable, the algorithm can always give a certificate for that, when it is regular. Some numerical experiments are also presented.     

On the strength of recursive McCormick relaxations for binary polynomial optimization

Recursive McCormick relaxations are among the most popular convexification techniques for binary polynomial optimization. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal sequence amounts to solving a difficult combinatorial optimization problem. We prove that any recursive McCormick relaxation is implied by the extended flower relaxation, a linear programming relaxation, which for binary polynomial optimization problems with fixed degree can be solved in strongly polynomial time.     

张量分析和多项式优化的若干进展

张量分析 (也称多重数值线性代数) 主要包括张量分解和张量特征值的理论和算法,多项式优化主要包括目标和约束均为多项式的一类优化问题的理论和算法. 主要介绍这两个研究领域中若干新的研究结果. 对张量分析部分,主要介绍非负张量H-特征值谱半径的一些性质及求解方法,还介绍非负张量最大 (小) Z-特征值的优化表示及其解法;对多项式优化部分,主要介绍带单位球约束或离散二分单位取值、目标函数为齐次多项式的优化问题及其推广形式的多项式优化问题和半定松弛解法. 最后对所介绍领域的发展趋势做了预测和展望.     

Semidefinite resolution and exactness of semidefinite relaxations for satisfiability

This paper explores new connections between the satisfiability problem and semidefinite programming. We show how the process of resolution in satisfiability is equivalent to a linear transformation between the feasible sets of the relevant semidefinite programming problems. We call this transformation semidefinite programming resolution, and we demonstrate the potential of this novel concept by using it to obtain a direct proof of the exactness of the semidefinite formulation of satisfiability without applying Lasserre’s general theory for semidefinite relaxations of 0/1 problems. In particular, our proof explicitly shows how the exactness of the semidefinite formulation for any satisfiability formula can be interpreted as the implicit application of a finite sequence of resolution steps to verify whether the empty clause can be derived from the given formula.     

On linear and semidefinite programming relaxations for hypergraph matching

The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for this problem are all local search algorithms. In this paper we analyze different linear and semidefinite programming relaxations for the hypergraph matching problem, and study their connections to the local search method. Our main results are the following:

We consider the standard linear programming relaxation of the problem. We provide an algorithmic proof of a result of Füredi, Kahn and Seymour, showing that the integrality gap is exactly ${k-1+\frac{1}{k}}$ for k-uniform hypergraphs, and is exactly k ? 1 for k-partite hypergraphs. This yields an improved approximation algorithm for the weighted 3-dimensional matching problem. Our algorithm combines the use of the iterative rounding method and the fractional local ratio method, showing a new way to round linear programming solutions for packing problems.

We study the strengthening of the standard LP relaxation by local constraints. We show that, even after linear number of rounds of the Sherali-Adams lift-and-project procedure on the standard LP relaxation, there are k-uniform hypergraphs with integrality gap at least k ? 2. On the other hand, we prove that for every constant k, there is a strengthening of the standard LP relaxation by only a polynomial number of constraints, with integrality gap at most ${\frac{k+1}{2}}$ for k-uniform hypergraphs. The construction uses a result in extremal combinatorics.

We consider the standard semidefinite programming relaxation of the problem. We prove that the Lovász ${\vartheta}$ -function provides an SDP relaxation with integrality gap at most ${\frac{k+1}{2}}$ . The proof gives an indirect way (not by a rounding algorithm) to bound the ratio between any local optimal solution and any optimal SDP solution. This shows a new connection between local search and linear and semidefinite programming relaxations.

     

Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization

We observe that in a simple one-dimensional polynomial optimization problem (POP), the ??optimal?? values of semidefinite programming (SDP) relaxation problems reported by the standard SDP solvers converge to the optimal value of the POP, while the true optimal values of SDP relaxation problems are strictly and significantly less than that value. Some pieces of circumstantial evidences for the strange behaviors of the SDP solvers are given. This result gives a warning to users of the SDP relaxation method for POPs to be careful in believing the results of the SDP solvers. We also demonstrate how SDPA-GMP, a multiple precision SDP solver developed by one of the authors, can deal with this situation correctly.     

The equivalence of semidefinite relaxations of polynomial 0-1 and ± 1 programs via scaling

Many combinatorial optimization problems can be modelled as polynomial-programming problems in binary variables that are all 0-1 or ±1. A sufficient condition under which a common method for obtaining semidefinite-programming relaxations of the two models of the same problem gives equivalent relaxations is established.     

Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems

Semidefinite relaxations of certain combinatorial optimization problems lead to approximation algorithms with performance guarantees. For large-scale problems, it may not be computationally feasible to solve the semidefinite relaxations to optimality. In this paper, we investigate the effect on the performance guarantees of an approximate solution to the semidefinite relaxation for MaxCut, Max2Sat, and Max3Sat. We show that it is possible to make simple modifications to the approximate solutions and obtain performance guarantees that depend linearly on the most negative eigenvalue of the approximate solution, the size of the problem, and the duality gap. In every case, we recover the original performance guarantees in the limit as the solution approaches the optimal solution to the semidefinite relaxation.     

Semidefinite relaxations for semi-infinite polynomial programming

This paper studies how to solve semi-infinite polynomial programming (SIPP) problems by semidefinite relaxation methods. We first recall two SDP relaxation methods for solving polynomial optimization problems with finitely many constraints. Then we propose an exchange algorithm with SDP relaxations to solve SIPP problems with compact index set. At last, we extend the proposed method to SIPP problems with noncompact index set via homogenization. Numerical results show that the algorithm is efficient in practice.     

Completely positive completion of partial matrices whose entries are completely bounded maps

We study completion problems of partial matrices associated with a graph where entries are completely bounded maps on aC ^*-algebra. We characterize a graph for which every -partial completely positive matrix has a completely positive completion. As a special case we study -partial functional matrices. We give a necessary and sufficient condition for a -partial functional matrix to have a positive completion and a representation for such matrices. These generalize some results on inflated Schur product maps due to Paulsen, Power and Smith. As an application, we study completely positive completions of partial matrices whose entries are completely bounded multipliers of the Fourier algebra of a locally compact group.