home | index | units | counting | geometry | algebra | trigonometry & functions | calculus
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Final Answers
© 2000-2014   Gérard P. Michon, Ph.D.

Convex Geometry
Calculus of Inequalities

If you optimize everything,
 you will always be unhappy
.
  Donald Knuth  (b. 1938)
 
People are so afraid of convex analysis.
  The Omnipresence of Lagrange  (2003, 2007)  by  Claude Lemaréchal  (b. 1944)
 border
 border

On this site, see also:

Related Links (Outside this Site)

An Elementary Introduction to Modern Convex Geometry  by  Keith M. Ball  (1997)
In 1992, Ball refined the ellipsoid theorem [1948]  of  Fritz John (1910-1994).
 
Convex Optimization (Cambridge University Press, 2004)
by  Stephen P. Boyd   (Stanford, EE364a & EE364b)
and  Lieven Vandenberghe  (UCLA, EE236B)
 
Convex Optimization & Euclidean Distance Geometry  (2001-2012)   by  Jon Dattorro.
 
Wikipedia:   Convexity  |  Convex geometry  |  Convex set  |  Convex hull  |  Convex combination
Convex analysis  |  Convex function  |  Convex optimization  |  Linear programming  |  Duality  |  Lagrangian relaxation  |  Combinatorial optimization  |  Operations Research  |  Convexity in economics
 
border
border

Convex Geometry


(2012-10-27)   Convex Sets
A set is convex if it contains every segment between two of its points.

In a  linear space  over the field of  real numbers, the segment between the points  A  and  B  is the following set:

{  (1-u) A  +  u B   |   u Î [0,1]  }

In this, [0,1]  denotes the  interval  consisting of all real numbers between  0  and  1  (both extremities included).

A subset of a  real  linear space is said to be  convex  if it contains all the segments between every pair of its points.

Convexity is not defined for linear spaces whose scalar fields are not endowed with a total ordering relation  (e.g., p-adic numbers).


(2014-01-12)   Uniformly convex space   (James A. Clarkson, 1936)
The middle of a not-too-short segment of the unit ball is deep inside it.

Let  E  be a  normed vector space  whose  unit ball  is:

B   =   { z Î E   |   || z ||  ≤  1  }

E  is a  uniformly convex space  if and only if the following is true:

" e > 0,  $ d > 0,  "xÎB"yÎB,   { || x - y ||  ≤  e }   Þ   { || ½ (x+y) ||  ≤  1-d }

Wikipedia :   Uniformly convex space   |   Milman-Pettis theorem (1938 & 1939)


(2013-04-18)   Aspect ratio  (absolute or relative to a given "vertical")
The aspect ratio of a convex body is its  length  divided by its  height.

Technically, the  width  of a convex shape depends on the direction with respect to with it is measured:  It's the least possible distance of two parallel planes perpendicular to that direction which surround the body.  It's what a  sliding calipers  measure.

The  height  of the shape can be given either of the following definitions:

  • The least width  (the measurement direction is called  vertical ).
  • The width along a prescribed direction, identified as vertical.

The former definition is called  absolute,  the latter is dubbed  relative.

In either case, the  length  of the body is then defined as the largest width along an horizontal direction  (a direction is said to be horizontal when it's perpendicular to the aforementioned vertical direction).

The  aspect ratio  of a body is the ratio of its height to its length so defined.

The  diameter  of a body is simply its largest width.  For example, the diameter of a rectangle is equal to its diagonal.

Either flavor of  aspect ratio  can be a convenient parameter to use when discussing the geometry of a family of objects.  It makes little sense for nonconvex things, except by considering their  convex hulls.  An  absolute  aspect ratio is never less than unity.  A  relative  aspect ratio can be.

Playing Cards


(2012-10-27)   The  closed unit ball  of a norm.
A nontrivial closed convex set, symmetric about 0, characterizes a  norm.

The  unit ball  associated with a  norm  is defined as the set of all vectors whose norm is less than or equal to 1.  The basic properties of a  norm  always make this a  closed  convex set  symmetric about the origin  (i.e., it contains  -V  if it contains  V )  and containing more than 0 itself  (except in the trivial case of the space  {0}  of dimension zero).

Conversely  (Minkowski)  any such set  B  uniquely specifies a norm of which it is the  unit ball,  the norm of a vector  V  being  defined  as:

|| V ||   =     inf  {  |x|   |   V  Π x B  }

The above definition of a norm from a convex, origin-symmetric, closed body  B  is called  Minkowski's functional.

The notation  x B  was introduced by Minkowski himself.  It denotes the set of all vectors that are equal to the scalar  x  multiplied into  some  element of  B.  Likewise, Minkowski defined the sum  A+B  of two sets of vectors as the set of all vectors that can be obtained by adding together an element of  A  and an element of  B.  Similarly, any well-defined operation on the elements of sets induces a natural extension of that operation to sets themselves, which is sometimes called a  Minkowski operation  on sets  (the most common is  Minkowski addition,  which has nice convexity properties).

Minkowski functional


(2012-10-27)   Convex hull  (or  convex envelope ) :   Conv (S)
The smallest convex set  containing a given set of points  S.

The intersection of any family of convex sets is itself convex.  (HINT:  If two points are in that intersection, so is the segment between them.)

Therefore, the intersection of all convex sets that contain a set  S  of vectors is a convex set containing  S.  It's clearly the smallest such set.  It's called the  convex hull of  S  and it's usually denoted  Conv (S).

The convex hull of a  sum of sets  is the sum of their convex hulls:

Conv ( S1 + S2 )   =   Conv ( S1 )  +  Conv ( S2 )

convex hull  is not necessarily  closed.  (Consider, for example, an open halfspace together with a single point on its boundary.)

The closure of  Conv (S)  is the convex hull of the closure of  S :

Conv ( S )   =   Conv ( S )

As discussed next, a closed convex set is the intersection of all [closed] halfspaces that contain it.  The closure of the convex hull of S  (or, equivalently, the convex hull of the closure of S)  is the intersection of all halfspaces that contain S.

Shapley-Folkman lemma :  The [Minkowski] sum of many sets is nearly convex.


(2012-11-03)   Intersections of closed halfpaces.
Any closed convex set is an intersections of [infinitely many] halfspaces.

An hyperplane separates space into three disjoint regions; itself and two  open halfspaces.  A closed halfspace is obtained as the union of the hyperplane with either of the two open halfspaces it borders.

When we say that any closed convex set is the intersection of halfspaces, we're normally thinking about  closed  ones.  It's "more economical" to do so, but it's not strictly necessary  (since a closed halfspace containing  S  is clearly the intersection of infinitely many open halfspaces).

The converse proposition only holds for closed halfspaces, though.  An intersection of any family of closed sets is guaranteed to be closed  (an infinite intersection of open sets could be open, closed or neither).

{ closed convex sets }   =   { intersections of closed halfspaces }

This proposition is the  geometric Hahn-Banach theorem.

Convex Optimization  by  Stephen P. Boyd  &  Lieven Vandenberghe.


(2012-10-27)   Polar  (or  dual )  of a  closed  convex set.
Duality with respect to Euclidean scalar product  (dot product).

In  Euclidean space  (i.e., real linear space endowed with a positive-definite scalar product)  a  linear hyperplane  can be defined as the set of all vectors orthogonal to a prescribed nonzero vector.  An  affine hyperplane  (or, simply, an  hyperplane)  is obtained by adding to some point every vector from such a  linear hyperplane.

An hyperplane which does  not  go through the origin can be characterized by an othogonal vector  H  pointing to it from the origin with a length equal to the inverse of the Euclidean distance from the origin.  That hyperplane is the set of all vectors whose dot-product into  H  is equal to 1 :

V   |   V.H  =  1  }

The hyperplane is the border of a closed half-plane containing the origin:

V   |   V.H  ≤  1  }

As stated in the previous section, we may always define any  closed  convex set  C as the intersection of  (possibly infinitely many)  such closed half-spaces, namely:

C   =   {  V   |   "HÎC'V.H  ≤  1  }

All sets  C'  that yield  C  in this way have the same convex hull  C*  which is called the  polar  of  C.  The bodies  C  and  C*  are polars of  each other :

C*   =   {  V   |   "HÎC  ,  V.H  ≤  1  }
C     =   {  V   |   "HÎC* ,  V.H  ≤  1  }

If  C  and  C*  are  polytopes  (resulting from a  finite  C' )  then their networks of vertices, edges and faces are  topological duals of each other.

 Icosidodecahedron   Rhombic triacontahedron

The above describes duality with respect to a sphere  (or hypersphere)  of unit radius centered at the origin.  Any center and any radius could be used in practice.


(2012-10-27)   Minkowski's separation theorem(s)  (Minkowski).
Two disjoint convexes belong to two  closed  adjoining halfspaces.

If the two disjoint convex sets are neither open nor closed,  the hyperplane at the border of the two halfspaces may intersect  both  convexes...

Consider, for example, the following bounded planar regions:

{  (x,y)   |   x2+y2 ≤ 1   and   either  y > 0   or  [ y = 0  &  x > 0 ]  }
{  (x,y)   |   x2+y2 ≤ 1   and   either  y < 0   or  [ y = 0  &  x < 0 ]  }

Each region is convex and the two are disjoint.  Only one straight line  (of equation  y = 0)  can be drawn "between" them, but it intersects both.

If both sets are closed, one of them can be contained in a  closed  halfspace which doesn't intersect the other.   [ Conjecture. ]

If at least one of them is compact, then two disjoint  closed  convex sets can always be separated by an hyperplane which doesn't intersect either set  (in fact, infinitely many such hyperplanes exist, in that case).

Two  open disjoint convex sets  can always be separated by  at least one  hyperplane that doesn't intersect either of them.

Hyperplane separation theorem   |   Hermann Minkowski (1864-1909)
MIT 18.409, by Jonathan Kelner :   Convex geometry | Separating hyperplanes


(2013-01-01)   Strict separation of two closed convex sets :
If one is compact, two closed convexes are separated by an hyperplane.

The theorem doesn't apply for closed sets if neither is compact.  Example:

 pink area (left) {  (x,y)   |   0 <  1/x  ≤ y  }
 pink area (bottom)
 
{  (x,y)   |   y ≤ 0  }
 

Both regions are convex and closed, yet no straight line separates them.  (HINT:  To separate  anything  from the lower convex set  (blue)  a straight line must have zero slope and  positive  intercept.)

 Separating hyperplane is perpendicular to separating axis.

Proof  (two closed convexes, one compact) :

Let  A  and  B  be two disjoint convexes in the vector space  E,  such that  A  is compact and  B  is closed.  Consider the following function  f,  defined for any point  M  of  E :

f (M)   =   inf { d(M,x)   |   x Î B }

f  is well-defined because any set of nonnegative reals has a lower bound.  It is  continuous.

 Come back later, we're
 still working on this one...



(2013-01-02)   Strict separation of two open convexes :
Two disjoint open convexes are always separated by an hyperplane.

 Come back later, we're
 still working on this one...

border
border
visits since October 27, 2012
 (c) Copyright 2000-2014, Gerard P. Michon, Ph.D.