9.5. Cones II#

9.5.1. Dual Cones#

Dual cones are defined for finite dimensional inner product spaces. Dual cones technically belong to the dual space V.

Recall that the dual space V of a vector space V is the set of all linear functionals on V. For finite dimensional spaces, V and its dual V are isomorphic. For an inner product space V every linear functional in V can be identified with a vector vV by the functional ,v (Theorem 4.106).

Definition 9.32 (Dual cone)

Let V be a finite dimensional inner product space and V be its dual space.

Let CV. The set

C{yV|x,y0xC}

is called the dual cone of C in V.

In the Euclidean space Rn, the dual cone can be written as:

C{yRn|x,y0xC}.

Geometric interpretation

  • For a vector y, the set Hy,+{x|x,y0} is a halfspace passing through origin.

  • y is the normal vector of the halfspace along (in the direction of) the halfspace.

  • If y belongs to the dual cone of C, then for every xC, we have x,y0.

  • Thus, the set C is contained in the halfspace Hy,+.

  • In particular, if C is a cone, then it will also touch the boundary of the half space Hy,+ as C contains the origin.

9.5.1.1. Properties#

Property 9.16

Dual cone is a cone.

Proof. Let yC. Then, by definition,

x,y0xC.

Thus, for some α0,

x,αy=αx,y0xC.

Thus, for every yC, αyC for all α0. Thus, C is a cone.

Property 9.17

Dual cone is convex.

Proof. Let y1,y2C. Let t[0,1] and

y=ty1+(1t)y2.

Then for an arbitrary xC,

x,y=x,ty1+(1t)y2=tx,y1+(1t)x,y20.

Thus, yC. Thus, C is convex.

We note that dual cone is a convex cone even if the original set C is neither convex nor a cone.

Property 9.18 (Containment reversal in dual cone)

Let C1 and C2 be two subsets of V and let C1 and C2 be their corresponding dual cones. Then,

C1C2C2C1.

The dual cone of the subset contains the dual cone of the superset.

Proof. Let yC2. Then

x,y0xC2x,y0xC1yC1.

Thus, C2C1.

Property 9.19 (Closedness)

A dual cone is a closed set.

Proof. The dual cone of a set C is given by

C={yV|x,y0xC}

Fix a xC and consider the set

Hx={yV|x,y0}.

The set Hx is a closed half space.

We can now see that

C=xCHx.

Thus, C is an intersection of closed half spaces. An arbitrary intersection of closed sets is closed. Hence C is closed.

Property 9.20 (Interior of dual cone)

The interior of the dual cone C is given by

intC={yV|x,y>0xC{0}}.

Proof. Let

A={y|x,y>0xC{0}}.

Let yA. By definition yC; i.e., AC.

Since x,y>0 for every nonzero xC, hence x,y+u>0 for every nonzero xC and every sufficiently small u. Hence, yintC. We have shown that AintC.

Now, let yA but yC. Then, x,y=0 for some nonzero xC. But then

x,ytx=x,ytx,x<0

for all t>0. Thus, yintC.

Hence, A=intC.

Property 9.21 (Non-empty interior implies pointed dual cone)

If C has a non-empty interior, then its dual cone C is pointed.

Proof. Let C have a non-empty interior and assume that its dual cone C is not pointed. Then, there exists a non-zero yC such that yC holds too.

Thus, x,y0 as well as x,y0 for every xC, i.e, x,y=0 for every xC. But this means that C lies in a hyperplane Hy,0 and hence has an empty interior. A contradiction.

Theorem 9.60 (Dual cone of a subspace)

The dual cone of a subspace VV is its orthogonal complement V defined as:

V={y|v,y=0vV}.

More precisely, V is isomorphic to V as the dual cone is a subset of V.

Proof. Let V be the dual cone of V. If vV, then by definition, vV. Thus, VV.

Let us now assume that there is a vector yV s.t. yV.

Then, there exists vV such that v,y>0. Since V is a subspace, it follows that vV. But then

v,y=v,y<0.

Thus, y cannot belong to V. A contradiction.

Thus, V=V.

9.5.1.2. Self Dual Cones#

Definition 9.33 (Self dual cone)

A cone C is called self dual if C=C, i.e., it is its own dual cone.

By equality, we mean that the dual cone C is isomorphic to C since technically CV.

Example 9.15 (Nonnegative orthant)

The non-negative orthant R+n is self dual.

Let C=R+n. For some u,vC, u,v0. Thus, R+nC.

Now, for some vR+n, there is at least one component which is negative. Without loss of generality, assume that the first component v1<0.

Now consider the vector u=[1,0,,0]R+n. v,u<0. Thus, vC.

Thus, C=R+n. It is self dual.

Example 9.16 (Positive semidefinite cone)

The positive semi-definite cone S+n is self dual.

Let C=S+n and YC. We first show that YC.

Choose an arbitrary XC.
Express X in terms of its eigenvalue decomposition as

X=λiqiqiT.

Since X is PSD, hence, λi0.

Then,

Y,X=tr(XY)=tr(YX)=tr(YλiqiqiT)=λitr(YqiqiT)=λitr(qiTYqi)=λi(qiTYqi).

But since Y is PSD, hence qiTYqi0. Hence Y,X0. Thus, YC.

Now, suppose YS+n. Then there exists a vector vRn such that vTYv<0. Consider the PSD matrix V=vvT.

Y,V=tr(VY)=tr(vvTY)=tr(vTYv)<0.

Thus, YC.

This completes the proof that C=C=S+n, i.e., the positive semi-definite cone is self dual.

9.5.2. Polar Cones#

Definition 9.34 (Polar cone)

Let V be a finite dimensional inner product space and V be its dual space.

Let CV. Then, its polar cone C is defined as

C{yV|x,y0xC}.

We note that polar cones are just the negative of dual cones. Thus, they exhibit similar properties as dual cones.

Example 9.17 (Polar cone of a ray)

Let x be a given nonzero vector. Let

C=cone{x}={tx|t0}.
  1. Let yC.

  2. Then for every t0, we have tx,y0.

  3. Equivalently, x,y0 since t0.

  4. Hence

    C={yV|x,y0}.
  5. Also note that C is closed and convex.

  6. We shall show later in polar cone theorem that

    (C)=C.
  7. Hence the polar cone of the set

    {yV|x,y0}

    is cone{x}.

9.5.2.1. Properties#

Property 9.22

Polar cone is a cone.

Proof. Let yC. Then, by definition,

x,y0xC.

Thus, for some α0,

x,αy=αx,y0xC.

Thus, for every yC, αyC for all α0. Thus, C is a cone.

Property 9.23

Polar cone is convex.

Proof. Let y1,y2C. Let t[0,1] and

y=ty1+(1t)y2.

Then for an arbitrary xC,

x,y=x,ty1+(1t)y2=tx,y1+(1t)x,y20.

Thus, yC. Thus, C is convex.

We note that polar cone is a convex cone even if the original set C is neither convex nor a cone.

Property 9.24 (Containment reversal in polar cone)

Let C1 and C2 be two subsets of V and let C1 and C2 be their corresponding polar cones. Then,

C1C2C2C1.

The polar cone of the subset contains the polar cone of the superset.

Proof. Let yC2. Then

x,y0xC2x,y0xC1yC1.

Thus, C2C1.

Property 9.25 (Closedness)

A polar cone is a closed set.

Proof. The polar cone of a set C is given by

C={yV|x,y0xC}

Fix a xC and consider the set

Hx={yV|x,y0}.

The set Hx is a closed half space.

We can now see that

C=xCHx.

Thus, C is an intersection of closed half spaces. An arbitrary intersection of closed sets is closed. Hence C is closed.

Property 9.26 (Interior of polar cone)

The interior of the polar cone C is given by

intC={yV|x,y<0xC{0}}.

Proof. Let

A={y|x,y<0xC{0}}.

Let yA. By definition yC; i.e., AC.

Since x,y<0 for every nonzero xC, hence x,y+u<0 for every xC and every sufficiently small u. Hence, yintC. We have shown that AintC.

Now, let yA but yC. Then, x,y=0 for some nonzero xC. But then

x,ytx=x,ytx,x>0

for all t<0. Thus, yintC.

Hence, A=intC.

Property 9.27 (Non-empty interior implies pointed polar cone)

If C has a non-empty interior, then its polar cone C is pointed.

Proof. Let C have a non-empty interior and assume that its polar cone C is not pointed. Then, there exists a non-zero yC such that yC holds too.

Thus, x,y0 as well as x,y0 for every xC, i.e, x,y=0 for every xC. But this means that C lies in a hyperplane Hy,0 and hence has an empty interior. A contradiction.

Theorem 9.61 (Polar cone of a subspace)

The polar cone of a subspace VV is its orthogonal complement V defined as:

V={y|v,y=0vV}.

More precisely, V is isomorphic to V as the polar cone is a subset of V.

Proof. Let V be the polar cone of V. If vV, then by definition, vV. Thus, VV.

Let us now assume that there is a vector yV s.t. yV.

Then, there exists vV such that v,y<0. Since V is a subspace, it follows that vV. But then

v,y=v,y>0.

Thus, y cannot belong to V. A contradiction.

Thus, V=V.

Example 9.18 (Polar cone of a null space)

Let ARm×n and C=nullA.

  1. Recall from linear algebra that

    (nullA)=rangeAT.
  2. Hence by Theorem 9.61,

    C=C=rangeAT.

We can verify this result easily.

  1. Let vrangeAT.

  2. Then there exists uRm such that v=ATu.

  3. For every xnullA, we have Ax=0.

  4. Hence

    x,v=x,ATu=Ax,u=0.
  5. Hence v(nullA).

Property 9.28 (Polar cone and closure)

For any nonempty set C, we have

C=(clC).

Proof. We first show that (clC)C.

  1. We have CclC.

  2. Hence by Property 9.24,

    (clC)C.

We now show that C(clC).

  1. Let yC.

  2. Then for every xC, we have x,y0.

  3. Let xclC.

  4. There exists a sequence {xk} of C such that limxk=x.

  5. But xk,y0 for every k.

  6. Hence, taking the limit, we have x,y0.

  7. Hence for every xclC, we have x,y0.

  8. Hence y(clC).

  9. Hence C(clC).

Property 9.29 (Polar cone and convex hull)

For any nonempty set C, we have

C=(convC).

Proof. We first show that (convC)C.

  1. We have CconvC.

  2. Hence by Property 9.24,

    (convC)C.

We now show that C(convC).

  1. Let yC.

  2. Then for every xC, we have x,y0.

  3. Let xconvC.

  4. Then there exist x1,,xkC and t1,tk0 with t1++tk=1 such that

    x=i=1ktixi.
  5. Then

    x,y=i=1ktixi,y.
  6. But xi,y0 since xiC for every i.

  7. Hence x,y0.

  8. Hence for every xconvC, we have x,y0.

  9. Hence y(convC).

  10. Hence C(convC).

Property 9.30 (Polar cone and conic hull)

For any nonempty set C, we have

C=(coneC).

Proof. We first show that (coneC)C.

  1. We have CconeC.

  2. Hence by Property 9.24,

    (coneC)C.

We now show that C(coneC).

  1. Let yC.

  2. Then for every xC, we have x,y0.

  3. Let xconeC.

  4. Then there exist x1,,xkC and t1,tk0 such that

    x=i=1ktixi.
  5. Then

    x,y=i=1ktixi,y.
  6. But xi,y0 since xiC for every i.

  7. Hence x,y0.

  8. Hence for every xconeC, we have x,y0.

  9. Hence y(coneC).

  10. Hence C(coneC).

Theorem 9.62 (Polar cone theorem)

For any nonempty cone C, we have

(C)=clconvC.

In particular, if C is closed and convex, we have

(C)=C.

Proof. First we assume that C is nonempty, closed and convex and show that (C)=C.

  1. Pick any xC.

  2. By definition, we have x,y0 for every yC.

  3. Hence x(C).

  4. Hence C(C).

  5. Now choose any z(C).

  6. Since C is nonempty, closed and convex, hence by projection theorem (Theorem 10.7), there exists a unique projection of z on C, denoted by z^ that satisfies

    xz^,zz^0xC.
  7. Since C is a cone, hence 0C.

  8. Since C is a cone and z^C, hence 2z^C.

  9. By putting x=0, we get

    z^,zz^0.
  10. By putting x=2z^, we get

    z^,zz^0.
  11. Together, we have

    z^,zz^=0.
  12. Putting this back into the projection inequality, we get

    x,zz^0xC.
  13. Hence zz^C.

  14. Since z(C), hence z,zz^0.

  15. We also have z^,zz^=0.

  16. Adding these two, we get

    zz^,zz^0.
  17. This means that

    zz^220.
  18. It follows that z=z^.

  19. Hence zC.

  20. Hence (C)C.

We have so far shown that if C is a nonempty, closed and convex cone then

C=(C).

Now consider the case where C is just an arbitrary nonempty cone.

  1. Then clconvC is a closed convex cone.

  2. By previous argument

    clconvC=(clconvC)).
  3. But

    (clconvC)=(convC)=C.
  4. Hence

    clconvC=(C).

9.5.3. Normal Cones#

Definition 9.35 (Normal vector)

Let S be an arbitrary subset of V. A vector vV is said to be normal to S at a point aS if v does not make an acute angle with any line segment starting from a and ending at some xS; i.e., if

xa,v0xS.

Example 9.19 (Normal vector)

Let C be a half space given by:

C={x|x,bs}.

Let a be any point on the boundary hyperplane of C given by a,b=s.

Then, b is normal to C at a since for any xC

xa,b=x,ba,bss=0.

Note that b points opposite to the direction of the halfspace.

Definition 9.36 (Normal cone)

The set of all vectors normal to a set S at a point aS, denoted by NS(a), is called the normal cone to S at a.

NS(a){vV|xa,v0xS}.

We customarily define NS(a)= for any aS.

Property 9.31

A normal cone is always a convex cone.

Proof. Let S be a subset of V and let aS. Let N denote the set of normal vectors to S at a. We have to show that N is a convex cone; i.e., we have to show that N contains all its conic combinations.

For any xS:

xa,0=0.

Thus, 0N.

Assume uN. Then,

xa,u0xS.

But then for any t0,

xa,tu=txa,u0xS.

Thus, tuN. Thus, N is closed under nonnegative scalar multiplication.

Now, let u,vN. Then,

xa,u+v=xa,u+xa,v0xS.

since sum of two nonpositive quantities is nonpositive.

Thus, u+vN. Thus, N is closed under vector addition.

Combining these two observations, N is closed under conic combinations. Hence, N is a convex cone.

Property 9.32

A normal cone is closed.

Specifically, if NS(a) is the normal cone to a set S at a point aS, then:

NS(a)=xS{vV|xa,v0}.

Proof. For some fixed aS and any fixed xV, define:

H(xa)={vV|xa,v0}.

Note that H(xa) is a closed half-space passing through origin of V extending opposite to the direction xa.

Let vNS(a) be a normal vector to S at a.

  1. Then, for every xS, xa,v0.

  2. Thus, for every xS, vH(xa).

  3. Thus, vxSH(xa).

  4. Thus, NS(a)xSH(xa).

Going in the opposite direction:

  1. Let vxSH(xa).

  2. Then, for every xS, vH(xa).

  3. Thus, for every xS, xa,v0.

  4. Thus, v is a normal vector to S at a.

  5. Thus, vNS(a).

  6. Thus, xSH(xa)NS(a).

Combining, we get:

NS(a)=xSH(xa).

Now, since NS(a) is an arbitrary intersection of closed half spaces which are individually closed sets, hence NS(a) is closed.

Since each half space is convex and intersection of convex sets is convex, hence, as a bonus, this proof also shows that NS(a) is convex.

Theorem 9.63 (Normal cone of entire space)

Let C=V. We wish to compute the normal cone NC(x) at every xC.

  1. Let vNC(x).

  2. Then we must have

    yx,v0yV.
  3. This is equivalent to

    z,v0zV.
  4. The only vector that satisfies this inequality is v=0.

  5. Hence NC(x)={0}.

Theorem 9.64 (Normal cone of unit ball)

NB[0,1](x)={yV|yx,y}.

Proof. The unit ball at origin is given by:

S=B[0,1]={xV|x1}.

Consider xS. Then, yNS(x) if and only if

zx,y0zSz,yx,yzSsupz1z,yx,yyx,y.

Therefore, for any xS:

NS(x)={yV|yx,y}.