Two pairs of families of polyhedral norms versus -norms: proximity and applications in optimization

• 成果类型: Article
• 署名作者: Gotoh, Jun-ya; Uryasev, Stan
• 署名单位: Chuo University; State University System of Florida; University of Florida
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0899-9
• 发表日期: 2016
• 页码: 391-431
• 关键词: approximations; selection

摘要

This paper studies four families of polyhedral norms parametrized by a single parameter. The first two families consist of the CVaR norm (which is equivalent to the D-norm, or the largest- norm) and its dual norm, while the second two families consist of the convex combination of the - and -norms, referred to as the deltoidal norm, and its dual norm. These families contain the - and -norms as special limiting cases. These norms can be represented using linear programming (LP) and the size of LP formulations is independent of the norm parameters. The purpose of this paper is to establish a relation of the considered LP-representable norms to the -norm and to demonstrate their potential in optimization. On the basis of the ratio of the tight lower and upper bounds of the ratio of two norms, we show that in each dual pair, the primal and dual norms can equivalently well approximate the - and -norms, respectively, for satisfying . In addition, the deltoidal norm and its dual norm are shown to have better proximity to the -norm than the CVaR norm and its dual. Numerical examples demonstrate that LP solutions with optimized parameters attain better approximation of the -norm than the - and -norms do.