Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ 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?

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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