A polynomial Hutton theorem with applications

Extending a classical linear result due to Hutton to a nonlinear setting, we prove that a continuous homogeneous polynomial between Banach spaces can be approximated by finite rank polynomials if and only if its adjoint can be approximated by finite rank linear operators. Among other consequences, we apply this result to generalize a classical result due to Aron and Schottenloher about the approximation property on spaces of polynomials and a recent result due to Çaliskan and Rueda about the quasi-approximation property on projective symmetric tensor products.     

Cones with a mapping cone symmetry in the finite-dimensional case

In the finite-dimensional case, we present a new approach to the theory of cones with a mapping cone symmetry, first introduced by Størmer. Our method is based on a definition of an inner product in the space of linear maps between two algebras of operators and the fact that the Jamio?kowski-Choi isomorphism is an isometry. We consider a slightly modified class of cones, although not substantially different from the original mapping cones by Størmer. Using the new approach, several known results are proved faster and often in more generality than before. For example, the dual of a mapping cone turns out to be a mapping cone as well, without any additional assumptions. The main result of the paper is a characterization of cones with a mapping cone symmetry, saying that a given map is an element of such cone if and only if the composition of the map with the conjugate of an arbitrary element in the dual cone is completely positive. A similar result was known in the case where the map goes from an algebra of operators into itself and the cone is a symmetric mapping cone. Our result is proved without the additional assumptions of symmetry and equality between the domain and the target space. We show how it gives a number of older results as a corollary, including an exemplary application.     

Integral mappings between Banach spaces

We consider the classes of “Grothendieck-integral” (G-integral) and “Pietsch-integral” (P-integral) linear and multilinear operators (see definitions below), and we prove that a multilinear operator between Banach spaces is G-integral (resp. P-integral) if and only if its linearization is G-integral (resp. P-integral) on the injective tensor product of the spaces, together with some related results concerning certain canonically associated linear operators. As an application we give a new proof of a result on the Radon-Nikodym property of the dual of the injective tensor product of Banach spaces. Moreover, we give a simple proof of a characterization of the G-integral operators on C(K,X) spaces and we also give a partial characterization of P-integral operators on C(K,X) spaces.     

Weighted Moore-Penrose inverses and fundamental theorem of even-order tensors with Einstein product

We treat even-order tensors with Einstein product as linear operators from tensor space to tensor space, define the null spaces and the ranges of tensors, and study their relationship. We extend the fundamental theorem of linear algebra for matrix spaces to tensor spaces. Using the new relationship, we characterize the least-squares (?) solutions to a multilinear system and establish the relationship between the minimum-norm (N) least-squares (?) solution of a multilinear system and the weighted Moore-Penrose inverse of its coefficient tensor. We also investigate a class of even-order tensors induced by matrices and obtain some interesting properties.     

Geometry of the copositive and completely positive cones

The copositive cone, and its dual the completely positive cone, have useful applications in optimisation, however telling if a general matrix is in the copositive cone is a co-NP-complete problem. In this paper we analyse some of the geometry of these cones. We discuss a way of representing all the maximal faces of the copositive cone along with a simple equation for the dimension of each one. In doing this we show that the copositive cone has faces which are isomorphic to positive semidefinite cones. We also look at some maximal faces of the completely positive cone and find their dimensions. Additionally we consider extreme rays of the copositive and completely positive cones and show that every extreme ray of the completely positive cone is also an exposed ray, but the copositive cone has extreme rays which are not exposed rays.     

Construction of proximal distances over symmetric cones

Abstract

This paper is devoted to the study of proximal distances defined over symmetric cones, which include the non-negative orthant, the second-order cone and the cone of positive semi-definite symmetric matrices. Specifically, our first aim is to provide two ways to build them. For this, we consider two classes of real-valued functions satisfying some assumptions. Then, we show that its corresponding spectrally defined function defines a proximal distance. In addition, we present several examples and some properties of this distance. Taking into account these properties, we analyse the convergence of proximal-type algorithms for solving convex symmetric cone programming (SCP) problems, and we study the asymptotic behaviour of primal central paths associated with a proximal distance. Finally, for linear SCP problems, we provide a relationship between the proximal sequence and the primal central path.     

Extreme positive operators on minimal and almost minimal cones

Fiedler and Pták called a cone minimal if it is n-dimensional and has n+1 extremal rays. We call a cone almost minimal if it is n-dimensional and has n+2 extremal rays. Duality properties stemming from the use of Gale pairs lead to a general technique for identifying the extreme cone-preserving (positive) operators between polyhedral cones. This technique is most effective for cones with dimension not much smaller than the number of their extreme rays. In particular, the Fiedler-Pták characterization of extreme positive operators between minimal cones is extended to the following cases: (i) operators from a minimal cone to an arbitrary polyhedral cone, (ii) operators from an almost minimal cone to a minimal cone.     

An entropy-like proximal algorithm and the exponential multiplier method for convex symmetric cone programming

We introduce an entropy-like proximal algorithm for the problem of minimizing a closed proper convex function subject to symmetric cone constraints. The algorithm is based on a distance-like function that is an extension of the Kullback-Leiber relative entropy to the setting of symmetric cones. Like the proximal algorithms for convex programming with nonnegative orthant cone constraints, we show that, under some mild assumptions, the sequence generated by the proposed algorithm is bounded and every accumulation point is a solution of the considered problem. In addition, we also present a dual application of the proposed algorithm to the symmetric cone linear program, leading to a multiplier method which is shown to possess similar properties as the exponential multiplier method (Tseng and Bertsekas in Math. Program. 60:1–19, 1993) holds.     

Compact adjoint operators and approximation properties

This paper is concerned with the space of all compact adjoint operators from dual spaces of Banach spaces into dual spaces of Banach spaces and approximation properties. For some topology on the space of all bounded linear operators from separable dual spaces of Banach spaces into dual spaces of Banach spaces, it is shown that if a bounded linear operator is approximated by a net of compact adjoint operators, then the operator can be approximated by a sequence of compact adjoint operators whose operator norms are less than or equal to the operator norm of the operator. Also we obtain applications of the theory and, in particular, apply the theory to approximation properties.     

Elliptic cone optimization and primal–dual path-following algorithms

In elliptic cone optimization problems, we minimize a linear objective function over the intersection of an affine linear manifold with the Cartesian product of the so-called elliptic cones. We present some general classes of optimization problems that can be cast as elliptic cone programmes such as second-order cone programmes and circular cone programmes. We also describe some real-world applications of this class of optimization problems. We study and analyse the Jordan algebraic structure of the elliptic cones. Then, we present a glimpse of the duality theory associated with elliptic cone optimization. A primal–dual path-following interior-point algorithm is derived for elliptic cone optimization problems. We prove the polynomial convergence of the proposed algorithms by showing that the logarithmic barrier is a strongly self-concordant barrier. The numerical examples show the path-following algorithms are efficient.     

The minimal cone for conic linear programming

It is known that the minimal cone for the constraint system of a conic linear programming problem is a key component in obtaining strong duality without any constraint qualification. For problems in either primal or dual form, the minimal cone can be written down explicitly in terms of the problem data. However, due to possible lack of closure, explicit expressions for the dual cone of the minimal cone cannot be obtained in general. In the particular case of semidefinite programming, an explicit expression for the dual cone of the minimal cone allows for a dual program of polynomial size that satisfies strong duality. In this paper we develop a recursive procedure to obtain the minimal cone and its dual cone. In particular, for conic problems with so-called nice cones, we obtain explicit expressions for the cones involved in the dual recursive procedure. As an example of this approach, the well-known duals that satisfy strong duality for semidefinite programming problems are obtained. The relation between this approach and a facial reduction algorithm is also discussed.     

On cone metric spaces: A survey

Using an old M. Krein’s result and a result concerning symmetric spaces from [S. Radenovi?, Z. Kadelburg, Quasi-contractions on symmetric and cone symmetric spaces, Banach J. Math. Anal. 5 (1) (2011), 38-50], we show in a very short way that all fixed point results in cone metric spaces obtained recently, in which the assumption that the underlying cone is normal and solid is present, can be reduced to the corresponding results in metric spaces. On the other hand, when we deal with non-normal solid cones, this is not possible. In the recent paper [M.A. Khamsi, Remarks on cone metric spaces and fixed point theorems of contractive mappings, Fixed Point Theory Appl. 2010, 7 pages, Article ID 315398, doi:10.1115/2010/315398] the author claims that most of the cone fixed point results are merely copies of the classical ones and that any extension of known fixed point results to cone metric spaces is redundant; also that underlying Banach space and the associated cone subset are not necessary. In fact, Khamsi’s approach includes a small class of results and is very limited since it requires only normal cones, so that all results with non-normal cones (which are proper extensions of the corresponding results for metric spaces) cannot be dealt with by his approach.     

Tractability through increasing smoothness

We prove that some multivariate linear tensor product problems are tractable in the worst case setting if they are defined as tensor products of univariate problems with logarithmically increasing smoothness. This is demonstrated for the approximation problem defined over Korobov spaces and for the approximation problem of certain diagonal operators. For these two problems we show necessary and sufficient conditions on the smoothness parameters of the univariate problems to obtain strong polynomial tractability. We prove that polynomial tractability is equivalent to strong polynomial tractability, and that weak tractability always holds for these problems. Under a mild assumption, the Korobov space consists of periodic functions. Periodicity is crucial since the approximation problem defined over Sobolev spaces of non-periodic functions with a special choice of the norm is not polynomially tractable for all smoothness parameters no matter how fast they go to infinity. Furthermore, depending on the choice of the norm we can even lose weak tractability.     

Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones

We describe an implementation of nonsymmetric interior-point methods for linear cone programs defined by two types of matrix cones: the cone of positive semidefinite matrices with a given chordal sparsity pattern and its dual cone, the cone of chordal sparse matrices that have a positive semidefinite completion. The implementation takes advantage of fast recursive algorithms for evaluating the function values and derivatives of the logarithmic barrier functions for these cones. We present experimental results of two implementations, one of which is based on an augmented system approach, and a comparison with publicly available interior-point solvers for semidefinite programming.     

Characterizations for solidness of dual cones with applications

In this paper, some characterizations for the solidness of dual cones are established. As applications, we prove that a Banach space is reflexive if it contains a solid pointed closed convex cone having a weakly compact base, and prove an analogue of a Karamardian’s result for the linear complementarity problem in reflexive Banach spaces. The uniqueness of the solution of the linear complementarity problem is also discussed.     

Self-Scaled Barrier Functions on Symmetric Cones and Their Classification

Self-scaled barrier functions on self-scaled cones were axiomatically introduced by Nesterov and Todd in 1994 as a tool for the construction of primal—dual long-step interior point algorithms. This paper provides firm foundations for these objects by exhibiting their symmetry properties, their close ties with the symmetry groups of their domains of definition, and subsequently their decomposition into irreducible parts and their algebraic classification theory. In the first part we recall the characterization of the family of self-scaled cones as the set of symmetric cones and develop a primal—dual symmetric viewpoint on self-scaled barriers, results that were first discovered by the second author. We then show in a short, simple proof that any pointed, convex cone decomposes into a direct sum of irreducible components in a unique way, a result which can also be of independent interest. We then proceed to showing that any self-scaled barrier function decomposes, in an essentially unique way, into a direct sum of self-scaled barriers defined on the irreducible components of the underlying symmetric cone. Finally, we present a complete algebraic classification of self-scaled barrier functions using the correspondence between symmetric cones and Euclidean—Jordan algebras. December 5, 1999. Final version received: September 6, 2001.     

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.     

Generating Polynomials and Symmetric Tensor Decompositions

This paper studies symmetric tensor decompositions. For symmetric tensors, there exist linear relations of recursive patterns among their entries. Such a relation can be represented by a polynomial, which is called a generating polynomial. The homogenization of a generating polynomial belongs to the apolar ideal of the tensor. A symmetric tensor decomposition can be determined by a set of generating polynomials, which can be represented by a matrix. We call it a generating matrix. Generally, a symmetric tensor decomposition can be determined by a generating matrix satisfying certain conditions. We characterize the sets of such generating matrices and investigate their properties (e.g., the existence, dimensions, nondefectiveness). Using these properties, we propose methods for computing symmetric tensor decompositions. Extensive examples are shown to demonstrate the efficiency of proposed methods.     

High-order sum-of-squares structured tensors:theory and applications

Tensor decomposition is an important research area with numerous applications in data mining and computational neuroscience.An important class of tensor decomposition is sum-of-squares(SOS)tensor decomposition.SOS tensor decomposition has a close connection with SOS polynomials,and SOS polynomials are very important in polynomial theory and polynomial optimization.In this paper,we give a detailed survey on recent advances of high-order SOS tensors and their applications.It first shows that several classes of symmetric structured tensors available in the literature have SOS decomposition in the even order symmetric case.Then,the SOS-rank for tensors with SOS decomposition and the SOS-width for SOS tensor cones are established.Further,a sharper explicit upper bound of the SOS-rank for tensors with bounded exponent is provided,and the exact SOS-width for the cone consists of all such tensors with SOS decomposition is identified.Some potential research directions in the future are also listed in this paper.