CONVEX ENVELOPES OF SOME QUADRATIC FUNCTIONS OVER THE n-DIMENSIONAL UNIT SIMPLEX

摘要

In this paper we discuss convex envelopes over the unit simplex for some quadratic functions. The discussion exploits the combinatorics related to quadratic functions over the unit simplex. After recalling the definition of the underlying convex graph of a quadratic function, i.e., the graph whose nodes are the vertices of the unit simplex, and whose edges correspond to the edges of the unit simplex along which the function is strictly convex, it is shown that the analytical formula of the convex envelope for quadratic functions whose underlying graph is triangle-free, is the maximum of a finite number of functions, each of which is related to a spanning forest of the graph. The special case of an underlying star graph is discussed, and computational experiments, based on a decomposition of a general quadratic function into a sum of quadratic functions with an underlying star graph, are presented.