On reduced semidefinite programs for second order moment bounds with applications

• 成果类型: Article
• 署名作者: Natarajan, Karthik; Teo, Chung-Piaw
• 署名单位: Singapore University of Technology & Design; National University of Singapore
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1019-1
• 发表日期: 2017
• 页码: 487-518
• 关键词: linear-programs; optimization; models

摘要

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 where is the feasible region. In fact, we can replace the completely positive programming formulation for the moment bound on , 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 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.