Skip to main content
2 of 3
added 694 characters in body
Iosif Pinelis
  • 127.7k
  • 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|$.

Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229