Copositivity Detection of Tensors: Theory and Algorithm

A symmetric tensor is called copositive if it generates a multivariate form taking nonnegative values over the nonnegative orthant. Copositive tensors have found important applications in polynomial optimization, tensor complementarity problems and vacuum stability of a general scalar potential. In this paper, we consider copositivity detection of tensors from both theoretical and computational points of view. After giving several necessary conditions for copositive tensors, we propose several new criteria for copositive tensors based on the representation of the multivariate form in barycentric coordinates with respect to the standard simplex and simplicial partitions. It is verified that, as the partition gets finer and finer, the concerned conditions eventually capture all strictly copositive tensors. Based on the obtained theoretical results with the help of simplicial partitions, we propose a numerical method to judge whether a tensor is copositive or not. The preliminary numerical results confirm our theoretical findings.     

高度有序氧化钨纳米棒的制备和表征

采用直流磁控溅射法结合阳极氧化法在铝基纳米点阵上制备氧化钨(WO3)纳米棒. 运用原子力学显微镜(AFM), 电子扫描显微镜(SEM), X射线衍射仪(XRD), 电化学工作站(EW)和紫外-可见分光光度计(UV)观察表征了WO3纳米棒的表面形貌、结构、光学性能和电致变色性能. 结果表明: 在溅射过程中, 溅射粒子优先沉积于铝基纳米点阵的凸点上, 然后成核并形成棒状; WO3纳米棒的直径约为200 nm, 与铝基纳米点阵的直径一致, 拥有一定的电致变色性能.     

一个求解对称锥互补问题的具有非单调线搜索的光滑算法的全局收敛性

提出一个求解单调对称锥互补问题（简记为SCCP）的具有非单调线搜索的光滑算法,并且证明提出的算法在所求解问题的解集非空的条件下是全局收敛的.这样的假设比现有的大多数求解对称锥优化问题的算法中所使用的假设都要弱.最后在适当的条件下,证明所提算法得到的解是一个极大互补解.     

A smoothing Newton algorithm based on a one-parametric class of smoothing functions for linear programming over symmetric cones

In this paper, we introduce a one-parametric class of smoothing functions which contains the Fischer–Burmeister smoothing function and the CHKS smoothing function as special cases. Based on this class of smoothing functions, a smoothing Newton algorithm is extended to solve linear programming over symmetric cones. The global and local quadratic convergence results of the algorithm are established under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool in our analysis.     

Smoothing algorithms for complementarity problems over symmetric cones

There recently has been much interest in studying optimization problems over symmetric cones. In this paper, we first investigate a smoothing function in the context of symmetric cones and show that it is coercive under suitable assumptions. We then extend two generic frameworks of smoothing algorithms to solve the complementarity problems over symmetric cones, and prove the proposed algorithms are globally convergent under suitable assumptions. We also give a specific smoothing Newton algorithm which is globally and locally quadratically convergent under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool which is extensively used in our analysis. Preliminary numerical results for second-order cone complementarity problems are reported.     

A Smoothing-Type Algorithm for Solving Linear Complementarity Problems with Strong Convergence Properties

In this paper, we construct an augmented system of the standard monotone linear complementarity problem (LCP), and establish the relations between the augmented system and the LCP. We present a smoothing-type algorithm for solving the augmented system. The algorithm is shown to be globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, if the LCP has a solution, then the algorithm either generates a maximal complementary solution of the LCP or detects correctly solvability of the LCP, and in the latter case, an existing smoothing-type algorithm can be directly applied to solve the LCP without any additional assumption and it generates a maximal complementary solution of the LCP; and that if the LCP is infeasible, then the algorithm detect correctly infeasibility of the LCP. To the best of our knowledge, such properties have not appeared in the existing literature for smoothing-type algorithms. This work was partially supported by the National Natural Science Foundation of China (Grant No. 10571134), the Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200), and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems

In this paper, we propose a new family of NCP-functions and the corresponding merit functions, which are the generalization of some popular NCP-functions and the related merit functions. We show that the new NCP-functions and the corresponding merit functions possess a system of favorite properties. Specially, we show that the new NCP-functions are strongly semismooth, Lipschitz continuous, and continuously differentiable; and that the corresponding merit functions have SC¹$S{C}^1$ property (i.e., they are continuously differentiable and their gradients are semismooth) and LC¹$L{C}^1$ property (i.e., they are continuously differentiable and their gradients are Lipschitz continuous) under suitable assumptions. Based on the new NCP-functions and the corresponding merit functions, we investigate a derivative free algorithm for the nonlinear complementarity problem and discuss its global convergence. Some preliminary numerical results are reported.     

The Hölder continuity of Löwner’s operator in Euclidean Jordan algebras

Löwner’s operator in Euclidean Jordan algebras, defined via the spectral decomposition of the elements of a scalar function, has been widely used in various optimization problems over Euclidean Jordan algebras. In this note, we shall show that Löwner’s operator in Euclidean Jordan algebras is Hölder continuous if and only if the underlying scalar function is Hölder continuous. Such a property will be useful in designing solution methods for symmetric cone programming and symmetric cone complementarity problem.     

Formulating an <Emphasis Type="Italic">n</Emphasis>-person noncooperative game as a tensor complementarity problem

In this paper, we consider a class of n-person noncooperative games, where the utility function of every player is given by a homogeneous polynomial defined by the payoff tensor of that player, which is a natural extension of the bimatrix game where the utility function of every player is given by a quadratic form defined by the payoff matrix of that player. We will call such a problem the multilinear game. We reformulate the multilinear game as a tensor complementarity problem, a generalization of the linear complementarity problem; and show that finding a Nash equilibrium point of the multilinear game is equivalent to finding a solution of the resulted tensor complementarity problem. Especially, we present an explicit relationship between the solutions of the multilinear game and the tensor complementarity problem, which builds a bridge between these two classes of problems. We also apply a smoothing-type algorithm to solve the resulted tensor complementarity problem and give some preliminary numerical results for solving the multilinear games.