Skip to main content
3 of 3
added 497 characters in body
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229

The dual norm of $(a,b)$ is $|a|\vee|b|\vee|a+b|$, where $A\vee B\vee\cdots:=\max(A,B,\dots)$.


Details:

The dual norm of $(a,b)\in\mathbb R^2$ is $$m=m_1\vee m_2, \tag{1} $$ where $$m_1:=\max\{ax+by\colon-1\le x\le 1,0\le y\le 1,-1\le x-y\le 1\} \\ =\max\{ax+by\colon0\le y\le 1,y-1\le x\le 1\}, $$ $$m_2:=\max\{ax+by\colon-1\le x\le 1,-1\le y\le 0,-1\le x-y\le 1\} \\ =\max\{ax+by\colon-1\le y\le 0,-1\le x\le 1+y\}. $$ Further, by the linearity of $ax+by$ in $(x,y)$, $$m_1=\max\{a(y-1)+by\colon0\le y\le 1\}\vee \max\{a+by\colon0\le y\le 1\} \\ =(-a)\vee b\vee a\vee(a+b). \tag{2} $$ Similarly, $$m_2=(-a-b)\vee(-a)\vee a\vee(-b). \tag{3} $$ So, by (1)--(3), indeed $m=|a|\vee|b|\vee|a+b|$.


Another way to compute the dual norm $m$ of $(a,b)$ is to note that $m$, equal the maximum of the linear form $ax+by$ over all points $(x,y)$ in the unit ball $K$, is the maximum of $ax+by$ over all the extreme points of $K$, which are $(-1,-1),(0,-1),(1,0),(1,1),(0,1),(-1,0)$. Here is the picture of the ball $K$:

enter image description here

So, $$m=(-a-b)\vee(-b)\vee a\vee(a+b)\vee b\vee(-a)=|a|\vee|b|\vee|a+b|. $$

Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229