Stochastic matrices play an important role in the study of probability theory and statistics, and are often used in a variety of modeling problems in economics, biology and operation research. Recently, the study of tensors and their applications became a hot topic in numerical analysis and optimization. In this paper, we focus on studying stochastic tensors and, in particular, we study the extreme points of a set of multi-stochastic tensors. Two necessary and sufficient conditions for a multi-stochastic tensor to be an extreme point are established. These conditions characterize the "generators" of multi-stochastic tensors. An algorithm to search the convex combination of extreme points for an arbitrary given multi-stochastic tensor is developed. Based on our obtained results, some expression properties for third-order and n-dimensional multi-stochastic tensors (n = 3 and 4) are derived, and all extreme points of 3-dimensional and 4-dimensional triply-stochastic tensors can be produced in a simple way. As an application, a new approach for the partially filled square problem under the framework of multi-stochastic tensors is given.
Bibliographical noteFunding Information:
Supported by the Sino-German Science Center (grant id 1228) on the occasion of the Chinese-German Workshop on Computational and Applied Mathematics in Augsburg 2015, and in part by National Natural Science Foundation of China (grant no. 11271144), by Project of Department of Education of Guangdong Province (grant no. 2013KJCX0053), and by NSF 1021203 of the United States.
© 2016 by De Gruyter.
- Convex Combination
- Extreme Points
- Multi-Stochastic Tensors