Two pairs of families of polyhedral norms versus (Formula presented.) -norms: proximity and applications in optimization

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- (Formula presented.) norm) and its dual norm, while the second two families consist of the convex combination of the (Formula presented.) - and (Formula presented.) -norms, referred to as the deltoidal norm, and its dual norm. These families contain the (Formula presented.) - and (Formula presented.) -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 (Formula presented.) -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 (Formula presented.) - and (Formula presented.) -norms, respectively, for (Formula presented.) satisfying (Formula presented.). In addition, the deltoidal norm and its dual norm are shown to have better proximity to the (Formula presented.) -norm than the CVaR norm and its dual. Numerical examples demonstrate that LP solutions with optimized parameters attain better approximation of the (Formula presented.) -norm than the (Formula presented.) - and (Formula presented.) -norms do.