On reduced semidefinite programs for second order moment bounds with applications

详细信息    查看全文

• 作者：Karthik Natarajan ; Chung-Piaw Teo
• 关键词：Moment bounds ; Newsvendor ; Random walk ; Choice model
• 刊名：Mathematical Programming
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：161
• 期：1-2
• 页码：487-518
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Calculus of Variations and Optimal Control; Optimization; Mathematics of Computing; Numerical Analysis; Combinatorics; Theoretical, Mathematical and Computational Physics; Mathematical Methods in Phys
• 出版者：Springer Berlin Heidelberg
• ISSN：1436-4646
• 卷排序：161

文摘

We show that the complexity of computing the second order moment bound on the expected optimal value of a mixed integer linear program with a random objective coefficient vector is closely related to the complexity of characterizing the convex hull of the points \(\{{1 \atopwithdelims (){\varvec{x}}}{1 \atopwithdelims (){\varvec{x}}}' \ | \ {\varvec{x}} \in {\mathcal {X}}\}\) where \({\mathcal {X}}\) is the feasible region. In fact, we can replace the completely positive programming formulation for the moment bound on \({\mathcal {X}}\), with an associated semidefinite program, provided we have a linear or a semidefinite representation of this convex hull. As an application of the result, we identify a new polynomial time solvable semidefinite relaxation of the distributionally robust multi-item newsvendor problem by exploiting results from the Boolean quadric polytope. For \({\mathcal {X}}\) described explicitly by a finite set of points, our formulation leads to a reduction in the size of the semidefinite program. We illustrate the usefulness of the reduced semidefinite programming bounds in estimating the expected range of random variables with two applications arising in random walks and best–worst choice models.