1
$\begingroup$

I am listening to convex optimization lectures and I hear that dual cone of a $L^1$ norm cone is a $L^{\infty}$ norm cone. Can anybody please explain how? I understand that every point in the dual cone must have an non-negative inner product with any point in its corresponding cone.

How does that bring a diamond shaped $L^1$ norm to a square shaped $L^{\infty}$ norm?

$\endgroup$
1
$\begingroup$

Let $C$ be a cone and $C^*=\{y:\langle x,y\rangle\ge 0 \ \forall x\in C\} $ its dual cone. If a point $y$ satisfies $\langle x,y\rangle\ge 0$ for all extreme rays of $C$, then it satisfies this inequality for all rays of $C$. Therefore, we can restrict attention to the extreme rays of $C$. Each of these rays determines a half-plane $\{y:\langle x,y\rangle\ge 0\}$.

The above may be easier to visualize for bounded convex sets than for cones. (The geometry of a cone is determined by its base.) For example, the $\ell_1$ unit ball in $n$ dimensions is diamond-shaped with $2n$ extreme points $\pm e_j$. The half-planes corresponding to these extreme points form $2n$ faces of the $\ell_\infty$ ball, which is a cube.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.