Enumerating Extreme Points of the Polytopes of Stochastic Tensors: An Optimization Approach

Fuzhen Zhang; Xiao-Dong Zhang

doi:10.1080/02331934.2019.1647198

Enumerating Extreme Points of the Polytopes of Stochastic Tensors: An Optimization Approach

Fuzhen Zhang
, Xiao-Dong Zhang

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

This paper is concerned with the extreme points of the polytopes of stochastic tensors. By a tensor we mean a multi-dimensional array over the real number field. A line-stochastic tensor is a nonnegative tensor in which the sum of all entries on each line (i.e. one free index) is equal to 1; a plane-stochastic tensor is a nonnegative tensor in which the sum of all entries on each plane (i.e. two free indices) is equal to 1. In enumerating extreme points of the polytopes of line- and plane-stochastic tensors of order 3 and dimension n , we consider the approach by linear optimization and present new lower and upper bounds. We also study the coefficient matrices that define the polytopes.

Original language	American English
Pages (from-to)	729-741
Number of pages	13
Journal	Optimization
Volume	69
Issue number	4
DOIs	https://doi.org/10.1080/02331934.2019.1647198
State	Published - Apr 1 2020

Bibliographical note

Publisher Copyright:
© 2019, © 2019 Informa UK Limited, trading as Taylor & Francis Group.

Funding

Fuzhen Zhang's work was partially supported by an NSU PFRDG Research Scholar grant and by National Natural Science Foundation of China (NNSF) No. 11571220 via Shanghai University. Xiao-Dong Zhang's work was partially supported by NNSF No. 11531001, No. 11271256, NSFC-ISF Research Program (No. 11561141001) and the Montenegrin-Chinese Science and Technology Cooperation Project (No. 3-12). The authors thank the anonymous referee for suggestion and Chi-Kwong Li for his comments in the early stage of the project. Fuzhen Zhang thanks the SKKU Applied Algebra & Optimization Research Center of South Korea for the hospitality during the May 2017 Workshop on Matrix/Operator Theory.

Funders	Funder number
Montenegrin-Chinese Science and Technology Cooperation Project	3-12
NSFC-ISF	11561141001
National Natural Science Foundation of China	11571220
National Natural Science Foundation of China
Namseoul University
Sungkyunkwan University
Shanghai University	11271256, 11531001
Shanghai University

ASJC Scopus Subject Areas

Control and Optimization
Management Science and Operations Research
Applied Mathematics

Keywords

Birkhoff polytope
Birkhoff-von Neumann theorem
Extreme point
Line-stochastic tensor
Plane-stochastic tensor
Polytope
Tensor
Vertex
Primary 52B11
vertex
plane-stochastic tensor
extreme point
tensor
15B51
line-stochastic tensor
polytope

Disciplines

Mathematics

Access to Document

10.1080/02331934.2019.1647198License: Unspecified

Cite this

@article{85f7c37bfa18401d87ca4c3a961d01c1,

title = "Enumerating Extreme Points of the Polytopes of Stochastic Tensors: An Optimization Approach",

abstract = " This paper is concerned with the extreme points of the polytopes of stochastic tensors. By a tensor we mean a multi-dimensional array over the real number field. A line-stochastic tensor is a nonnegative tensor in which the sum of all entries on each line (i.e. one free index) is equal to 1; a plane-stochastic tensor is a nonnegative tensor in which the sum of all entries on each plane (i.e. two free indices) is equal to 1. In enumerating extreme points of the polytopes of line- and plane-stochastic tensors of order 3 and dimension n , we consider the approach by linear optimization and present new lower and upper bounds. We also study the coefficient matrices that define the polytopes.",

keywords = "Birkhoff polytope, Birkhoff-von Neumann theorem, Extreme point, Line-stochastic tensor, Plane-stochastic tensor, Polytope, Tensor, Vertex, Primary 52B11, vertex, plane-stochastic tensor, extreme point, tensor, 15B51, line-stochastic tensor, polytope",

author = "Fuzhen Zhang and Xiao-Dong Zhang",

note = "Publisher Copyright: {\textcopyright} 2019, {\textcopyright} 2019 Informa UK Limited, trading as Taylor \& Francis Group.",

year = "2020",

month = apr,

day = "1",

doi = "10.1080/02331934.2019.1647198",

language = "American English",

volume = "69",

pages = "729--741",

journal = "Optimization",

issn = "0233-1934",

publisher = "Taylor and Francis Ltd.",

number = "4",

}

TY - JOUR

T1 - Enumerating Extreme Points of the Polytopes of Stochastic Tensors: An Optimization Approach

AU - Zhang, Fuzhen

AU - Zhang, Xiao-Dong

PY - 2020/4/1

Y1 - 2020/4/1

N2 - This paper is concerned with the extreme points of the polytopes of stochastic tensors. By a tensor we mean a multi-dimensional array over the real number field. A line-stochastic tensor is a nonnegative tensor in which the sum of all entries on each line (i.e. one free index) is equal to 1; a plane-stochastic tensor is a nonnegative tensor in which the sum of all entries on each plane (i.e. two free indices) is equal to 1. In enumerating extreme points of the polytopes of line- and plane-stochastic tensors of order 3 and dimension n , we consider the approach by linear optimization and present new lower and upper bounds. We also study the coefficient matrices that define the polytopes.

AB - This paper is concerned with the extreme points of the polytopes of stochastic tensors. By a tensor we mean a multi-dimensional array over the real number field. A line-stochastic tensor is a nonnegative tensor in which the sum of all entries on each line (i.e. one free index) is equal to 1; a plane-stochastic tensor is a nonnegative tensor in which the sum of all entries on each plane (i.e. two free indices) is equal to 1. In enumerating extreme points of the polytopes of line- and plane-stochastic tensors of order 3 and dimension n , we consider the approach by linear optimization and present new lower and upper bounds. We also study the coefficient matrices that define the polytopes.

KW - Birkhoff polytope

KW - Birkhoff-von Neumann theorem

KW - Extreme point

KW - Line-stochastic tensor

KW - Plane-stochastic tensor

KW - Polytope

KW - Tensor

KW - Vertex

KW - Primary 52B11

KW - vertex

KW - plane-stochastic tensor

KW - extreme point

KW - tensor

KW - 15B51

KW - line-stochastic tensor

KW - polytope

UR - https://nsuworks.nova.edu/math_facarticles/293

UR - https://www.scopus.com/pages/publications/85081943838

UR - https://www.scopus.com/pages/publications/85081943838#tab=citedBy

U2 - 10.1080/02331934.2019.1647198

DO - 10.1080/02331934.2019.1647198

M3 - Article

SN - 0233-1934

VL - 69

SP - 729

EP - 741

JO - Optimization

JF - Optimization

IS - 4

ER -

Enumerating Extreme Points of the Polytopes of Stochastic Tensors: An Optimization Approach

Abstract

Bibliographical note

Funding

ASJC Scopus Subject Areas

Keywords

Disciplines

Access to Document

Other files and links

Fingerprint

Cite this